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());//输出数据