用C语言编写顺序查找和二分查找(折半查找)

一、用C语言编写顺序查找和二分查找(折半查找)

顺序查找：在一个已知无序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同的数为止。复杂度为o(n).

二分查找又称折半查找，它是一种效率较高的查找方法。

【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。

【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

【算法复杂度】假设其数组长度为n，其算法复杂度为o（log（n））

int search(int a[],int x,int n)//x为要查找的元素，n为数组长度

int search1(int a[],int x,int n)//x为要查找的元素，n为数组长度

printf("请输入要查找的元素");

if(search(a,x,10)!=-1)printf("查找的元素在数组中的位置为%d.\n",search(a,x,10));

else printf("该元素不在数组中\n");

if(search1(a,x,10)!=-1)printf("查找的元素在数组中的位置为%d.\n",search1(a,x,10));

else printf("该元素不在数组中\n");

二、用C语言实现线性表的顺序存储(创建,插入,删除和查找)

//C++课程设计---学生成绩管理系统

typedef struct studentinfo//结构体定义

int sex;//性别，1为男性，0为女性

#define FILENAME"D:\\1.txt"

STUDENT* create_linkbyfile(char*);

int save_info(char*,STUDENT*,int);

int find_infile_printf(char*);

STUDENT* printf_sort(STUDENT*);

STUDENT* reverse(STUDENT*head)

p1=head;//p1使之永远指向排好序的第一个结点，初值为head，head使之永远是已经排好序的最后一个结点

while(head->next!=NULL)//本次循环使ptemp排好序

ptemp=head->next;//ptemp指向未排好序的第一个结点

head->next=ptemp->next;//

ptemp->next=p1;//ptemp也排好序了，ptemp变成排好序的第一个结点了

p1=ptemp;//再次让p1成为第一个排好序的结点

return p1;//头结点为第一个结点

//功能：输出功能菜单，提供人-机接口

cout<<"\t\t学生成绩管理系统\n";

cout<<"##########################################\n";

cout<<"#\t\t 1.新增学生信息\t\t#\n";

cout<<"#\t\t 2.加载数据库\t\t#\n";

cout<<"#\t\t 3.删除学生信息\t\t#\n";

cout<<"#\t\t 4.保存学生信息\t\t#\n";

cout<<"#\t\t 5.数据库查询\t\t#\n";

cout<<"#\t\t 6.原序输出\t\t#\n";

cout<<"#\t\t 7.排序输出\t\t#\n";

cout<<"#\t\t 8.退出\t\t\t#\n";

cout<<"##########################################\n";

cout<<"请输入操作编号：";

free_link(head);//释放链表空间

head=new_student();//新增学生信息

free_link(head);//释放链表空间

cout<<"请输入要加载的数据库文件的路径"<<endl;

head=create_linkbyfile(file_name);//读取数据文件

cout<<"数据库"<<file_name<<"已加载"<<endl;

del_info(head);//删除学生信息

case'4'://保存学生信息

cout<<"请先生成学生信息"<<endl;

cout<<"想将学生信息保存到哪个数据库文件？";

cout<<"请选择保存方式：0追加到文件末尾 1覆盖文件\n";

if(save_info(file_name,head,menu_Num-'0')==0)//0表示追加，1表示覆盖

cout<<"信息保存失败\n";

cout<<"数据已保存到"<<file_name<<endl;

find_infile_printf(FILENAME);//数据库查询

case'6'://原序输出信息

cout<<"返回主菜单？ Y/N\t";

}while(ch!='Y'&&ch!='y');

case'7'://排序输出信息

if((head=printf_sort(head))==NULL)

cout<<"数据库未加载"<<endl;

cout<<"选择其他方式排序？ Y/N\t";

}while(ch=='Y'||ch=='y');

free_link(head);//释放链表空间

cout<<"输入有误！请重新输入！"<<endl;

//功能：创建学生信息（通过链表）

pnew=(STUDENT*)malloc(sizeof(STUDENT)*1);

cout<<"请输入学生的学号(0表示取消)：";

cout<<"请输入学生的姓名：";

cout<<"请输入学生的性别：0/1\t";

if(pnew->sex&&pnew->sex-1)

cout<<"性别输入错误，0表示女性，1表示男性，请重新输入"<<endl;

cout<<"请依次输入学生的数学、英语、政治、语文成绩："<<endl;

for(pnew->total=0,pfloat=&pnew->math;pfloat<&pnew->math+4;)

if(*pfloat<0||*pfloat>150)

cout<<"成绩输入错误，只能为0~150"<<endl;

cout<<"##########################该学生信息已生成#########################\n";

cout<<"建立另一个学生的信息？ Y/N\t";

}while(ch=='Y'||ch=='y');

STUDENT* create_linkbyfile(char*filename)

//参数：如果filename不为空，则打开该文件，如果filename为空，要求输入文件位置

//创建的链表的所有结点的next全部修改，指向物理地址上的下一个结点

if(filename==NULL)//若filename为空，要求输入文件绝对地址

cout<<"请输入数据库文件的路径："<<endl;

if(NULL==(fp=fopen(file_name,"rb")))

cout<<"数据库连接失败\n";

if(NULL==(fp=fopen(filename,"rb")))

cout<<"数据库连接失败\n";

pnew=(STUDENT*)malloc(sizeof(STUDENT)*1);

if(fread(pnew,sizeof(STUDENT),1,fp)!=NULL)

STUDENT*del_info(STUDENT*head)

cout<<"数据库未加载"<<endl;

cout<<"请输入要删除学生的学号：";

if(p1==head)//要删除的结点是头结点

int save_info(char*filename,STUDENT*head,int flag)

//功能：将链表按Binary写入文件末尾

strcpy(openmethod,"ab+");//追加

strcpy(openmethod,"w");//覆盖

if(NULL==(fp=fopen(filename,openmethod)))//

cout<<"数据库连接失败"<<endl;

if((fwrite(p,sizeof(STUDENT),1,fp))==NULL)

cout<<"数据库创建失败"<<endl;

int find_infile_printf(char*filename)

//功能：根据学号和姓名来查询某个学生

//也可先根据文件创建链表，再搜索链表，缺点是如果文件较大，占用内存多

memset(stu_name,0,sizeof(stu_name));

cout<<"查询学号或查询姓名？ 1查询学号 0查询姓名";

//flag=1根据学号来查询，flag=0根据姓名来查询

cout<<"输入要查询的学号：";

cout<<"正在为您查询学号为"<<num<<"的学生……"<<endl;

cout<<"输入要查询的姓名：";

cout<<"正在为您查询姓名为"<<stu_name<<"的学生……"<<endl;

cout<<"输入有误"<<endl;

if(NULL==(fp=fopen(filename,"rw")))

cout<<"数据库连接失败\n";

while(fread(&stu,sizeof(STUDENT),1,fp)!=NULL)

if(strcmp(stu.name,stu_name)==0||stu.num==num)

cout<<"学号\t姓名\t性别\t数学\t英语\t政治\t语文\t总成绩\n";

cout<<stu.num<<"\t"<<stu.name<<"\t"<<stu.sex<<"\t"<<stu.math<<"\t"<<stu.english<<"\t"<<stu.politic<<"\t"<<stu.chinese<<"\t"<<stu.total<<endl;

//不加break;可支持多个相同数据的索引

cout<<"##########################查询完毕#########################\n";

cout<<"查询另一个学生的信息？ Y/N\t";

}while(ch=='Y'||ch=='y');

int pri_whole_link(STUDENT*head)

//功能：显示整条链表的学生信息

//参数：head头结点指针，如果head为空，返回空

cout<<"数据库未加载"<<endl;

cout<<"学号\t姓名\t性别\t数学\t英语\t政治\t语文\t总成绩\n";

cout<<p->num<<"\t"<<p->name<<"\t"<<p->sex<<"\t"<<p->math<<"\t"<<p->english<<"\t"<<p->politic<<"\t"<<p->chinese<<"\t"<<p->total<<endl;

STUDENT* printf_sort(STUDENT*head)

//功能：根据学号|某科目成绩|总成绩对链表进行排序，然后输出

//参数：head链表头指针，如果head为空，返回空

//返回值：返回新的链表的头结点指针

STUDENT*p1,*p2,*ptemp,*pfinished=NULL;

cout<<"选择排序依据 0.数学成绩1.英语成绩2.政治成绩3.语文成绩4.总成绩\n";

if(num>'4'||num<'0')

cout<<"输入有误，请重新输入 0~4"<<endl;

cout<<"升序/降序输出？ 0.降序1.升序";

if(flag>'1'||flag<'0')

cout<<"输入有误，请重新输入 0~1"<<endl;

for(p1=head;p1->next!=pfinished;)//对链表进行从大到小排序（这里用冒泡法）

//p1使之总是指向头结点，pfinished使之总是指向已排序好的最前面的结点

//ptemp作为中介，保存p2的上一个结点

for(p2=p1;p2->next!=pfinished;)

if(*(&(p2->math)+num-'0')<*(&(p2->next->math)+num-'0'))//p2的值小于p2->next的值，交换 ptemp p2 p2->next

else//不需要交换，则p2、ptemp前进1位

cout<<"##########################信息显示完毕#########################\n";

//释放链表空间，如果head，什么都不做

free(p1);//free后 p1->next数据丢失

三、c语言如何实现-数组排序,二分查找

1、给定已经排好序的n个元素，现在要在这n个元素中找出一特定元素x。顺序搜索的方法是逐个比较，直至找出元素。二分搜索则利用了元素间的次序关系，可大大提高效率。二分法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x作比较。如果x==a[n/2]，则终止。如果x<a[n/2]，则只需在数组的左半部分继续搜索。如果x>a[n/2]，则只需在右半部分搜索。本题要求利用上一题得到的数组进行顺序查找和二分查找，分别为两种查找方法计时。

2、 for(i=0; i<n-1; i++)/*要选择的次数：0~n-2共n-1次*/

3、 min= i;/*假设当前下标为i的数最小，比较后再调整*/

4、 for(j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/

5、 min= j;/*如果后面的数比前面的小，则记下它的下标*/

6、 if(min!= i)/*如果min在循环中改变了，就需要交换数据*/

7、printf("找到X=%d,a[%d]\n",x,i);

8、printf("没有你要找的数\n");

9、printf("%fs\n",clock()/CLOCKS_PER_SEC);

10、printf("找到x=%d,a[%d]\n",x,mid);

11、printf("没有你要找的数\n");

12、printf("%fs\n",(clock()-y)/CLOCKS_PER_SEC);