1、5種方式實作二分查找,案例結構:
halffind.h
#ifndef
_halffind_
#define
/************************************************************************/
/*
初始化長度為l的數組 */
extern
void
initarray(int
*arr,
int
n);
列印數組 */
printarr(int
列印次數 */
printtimes(int
pos);
通過while循環的方式實作二分查找 */
halffindbywhile(int
n,
num);
二分查找查詢某個數值,通過do-while
*/
halffindbydowhile(int
二分查找,通過goto語句實作
halffindbygoto(int
通過for循環的方式實作二分查找
halffindbyfor(int
通過遞歸的方式進行查找 */
halffindbyrecursion(int
*arr,int
n,int
#endif
halffuncs.c
#include
<stdio.h>
<stdlib.h>
<time.h>
"halffind.h"
初始化數組的值 */
//voidinitarray(int *arr,int n)
//{
//
//時間資料類型
time_t ts;
unsigned int num = time(&ts);
//初始化随機數種子
srand(num);
for (int i = 0; i < n; i++) {
//
arr[i] = rand() % n;
}
//}
n)
{
for (int
i = 0;
i <
n;
i++) {
arr[i]
= i;
列印數組
*/
i++)
printf("%d
",arr[i]);
列印搜尋次數 */
pos) {
printf("\nposition
= %d\n",pos);
二分查找查詢某個數值,通過while表達式
num)
//參數分别表示開始查詢位置,結束查詢位置,中間位置
start_pos = 0,
end_pos =
n - 1,
middle_pos = 0;
while (start_pos
<= end_pos)
middle_pos = (start_pos
+ end_pos) / 2;
//如果中間值恰好是要找的值
if (num
== arr[middle_pos])
{
return
middle_pos;
}
else
if (num
> arr[middle_pos])
start_pos =
middle_pos + 1;
middle_pos - 1;
if (start_pos
> end_pos)
printf("\n沒有找到\n");
return -1;
do
start_pos =
} while (start_pos
<= end_pos);
通過goto語句查找 */
flag:middle_pos
= (start_pos +
end_pos) / 2;
goto
flag;
printf("\n對不起,沒有找到!\n");
通過for循環的方式進行查找
for (;
start_pos <=
end_pos;)
通過遞歸的方式二分查找 */
recursion(int
num,
start_pos,int
end_pos,int
middle_pos)
if(start_pos
recursion(arr,
start_pos,
end_pos,
middle_pos);
通過遞歸的方式進行二分查找
//接收遞歸傳回來的值
halffind.c
n 45
main(int
argc,char
*argv[]){
arr[n];
//times表示查找了多少次
//start_pos表示開始查找位置
//end_pos最後位置
//num辨別要查找的值
pos;
initarray(arr,n);
//列印數組
printarr(arr,
//查找
//1、通過while的方式進行查找
//pos = halffindbywhile(arr, n, 60);
//2、通過do-while的方式進行查找
//pos = halffindbydowhile(arr, n, 60);
//3、通過for循環的方式進行二分查找
//pos = halffindbygoto(arr,n,30);
//4、通過for循環的方式進行二分查找
//pos = halffindbyfor(arr,n,30);
//5、通過遞歸的方式實作二分查找
pos =
halffindbyrecursion(arr,n,60);
printtimes(pos);
system("pause");
return 0;
2、結合結構體實作棧存儲結構,代碼如下:
n
50
struct
mystack
top;//棧頂
data[n];//存放資料
};
selfstack = { -1, { 0 } };//棧的初始化
//函數聲明
isempty();
//1為空
0非空
setempty();
//棧設定為空
push(int
num);
//壓入資料,成功1,失敗傳回0
pop();
//彈出資料
判斷棧是否為空 */
isempty()
if (selfstack.top
== -1)
//表示是空的
return 1;
//表示不是空的
将棧設定成為空 */
setempty()
selfstack.top
= -1;
壓入資料,成功傳回1,失敗傳回0
//一定要記住:要判斷棧是否溢出
== n - 1)
//壓棧失敗
+= 1; //小标移動一下
selfstack.data[selfstack.top]
= num;//壓入資料
彈出資料 */
pop()
//判斷棧是否為空
return -1;//棧為空
-= 1;
selfstack.data[selfstack.top
+ 1];//彈出的資料
argc,
char *argv[])
a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (i
= 0; i < 10;
//填充資料
push(a[i]);
while (!isempty())
printf("%d\n",
pop());//輸出資料