线性表的查找算法

软件基础基础实验报告系别：地质工程系班级：09测绘 学号：0910205006 姓名：严康文实验时间：实验地点：网教中心实验环境：vc6.0实验名称：线性表的查找算法实验目的：(1)掌握线性表的顺序查找算法(2)掌握有序表的折半查找算法实验内容：在顺序存储的长度为n的线性表中顺序查找元素x在表中的下标。备注：需要用到的算法是：serch()在头指针为head的线性链表中顺序查找元素x的存储序号。备注：需要用到的算法是：lserch()在顺序存储的长度为n的线性表中对分查找元素x在表中的下标。备注：需要用到的算法是：bserch()程序代码：#include"stdio.h"#include"stdlib.h"voidinput(int*v,int*n){inti;printf("请输入％d元素到线性表山",*。)；for(i=0;i<*n;i++){scanf("%d",v+i);printf("\n请输入下一个元素到线性表5");}printf("输入完成，停止输入\n");}voidoutput(int*v,int*n){inti;for(i=0;i<*n;i++)printf(”线性表的第％d(元素为%d\n",i+1,*(v+i));}int*initsl(intm,int*n){int*v;v=(int*)malloc(m*sizeof(int));returnv;}voidinsl(int*v,intm,int*n,inti,intb){intj;if(*n==m){printf("overflow\n");return;}if(i>*n-1)i=*n+1;if(i<1)i=1;for(j=*n;j>=i;j--)v[j]=v[j-1];v[i-1]=b;*n=*n+1;return;}voiddesl(int*v,intm,int*n,inti){intj;if(*n==0){printf("underflow\n");return;if((i<1)||(i>*n))printf("notthiselementisin\n");return;}for(j=i;j<=*n-1;j++)v[j-1]=v[j];*n=*n-1;return;}voidmenu(){printf("************请选择需要操作************\n")；printf("************进行插入请选择i************\n")；printf("************进行删除请选择2************\n");printf("************査找请选择3************\n");printf("************对分査找请选择4************\n");printf("************退出请选择5************\n");return;}voidbserch(int*v,int*n,intx){inti,j,k;i=1;j=*n;while(i<=j){k=(i+j)/2;if(v[k-1]==x)break;if(v[k-1]>x)j=k-1;elsei=k+1;}if(k!=-1)printf("被査找的元素序数是％d\n",k);elseprintf("notfounded\n");}voidserch(int*v,int*n,intx){intk=0;while((k<*n)&&(v[k]!=x))k=k+1;if(k==*n)k=-1;if(k!=-1)printf("被査找的元素序数是%d\n",k+1);elseprintf("notfoundedVn");}voidmain(){int*v=NULL,*n=NULL,m,i,b,j,x;n=(int*)malloc(sizeof(int));printf("请输入所建表的容量m\n");scanf("%d",&m);printf("请输入所建表的元素个数n\n");scanf("%d",n);v=initsl(m,n);〃建立线型表printf("请输入所建表的元素\n");input(v,n);output(v,n);menu();scanf("%d",&j);do{if(j==1){printf(”请输入在第个i元素前插入元素b\n");scanf("%d%d",&i,&b);insl(v,m,n,i,b);output(v,n);}elseif(j==2){printf(”请输入删除的元素顺序i\n");scanf("%d",&i);desl(v,m,n,i);output(v,n);}elseif(j==3){printf(”请输入要査找的元素x\n");scanf("%d",&x);serch(v,nx);}elseif(j==4){printf("请输入要査找的元素x\n");scanf("%d",&x);bserch(v,n,x);}elsebreak;

menu();scanf("%d",&j);}while(j!=5);}运行结果：顺序查找：顺序查找：请输入下一个元素到线性表输入完成，停止输入性表的第1个元素为1性表的第请输入下一个元素到线性表输入完成，停止输入性表的第1个元素为1性表的第2个元素为6性表的第3个元素为9性表的第4个元素为3性表的第5个元素为5性表的第6个元素为6XXXXXXXXXXXX请选择需要操作XXXXXXXXXXXX

进行插入请选择2进行删除请选择3共兴共共共共共共共兴共XXXXXXXXXXXX查找请选择外XXXXXXXXXXXXXXXXXXXXXXX对分杳找请选择辱XXXXXXXXXXXxxxxxxxxxxxxjg出i青选择5共餐餐餐餐共餐共共餐餐餐售输入要杳找的元素X被查找的元素序禁是3 口请选择需要操作XXXXXXXXXXXX进行插入请选择心XXXXXXXXXXXXXXXXXXXXXXX进行删除请选择岔XXXXXXXXXXX餐餐餐餐共共餐共餐餐餐餐查找i青选择3共餐餐餐餐共餐共共餐餐餐对分查找请选择％共兴共共共共共共共兴共XXXXXXXXXXXX退出请选择界XXXXXXXXXXX5Pressanykeytocontinue对分查找：线,线,线,线'线'性表的第1个元素为1性表的第2个元素为2性表的第3个元素为3性表的第耳个元素为4性表的第5个元素为6XXXXXXXXXXXX对分查找：线,线,线,线'线'性表的第1个元素为1性表的第2个元素为2性表的第3个元素为3性表的第耳个元素为4性表的第5个元素为6XXXXXXXXXXXX对分杳找请选择辱XXXXXXXXXXXxxxxxxxxxxxxjK出i青选择5共其共共共共共共共其共共售输入要查找的元素X被查找的元素序敦是3 °XXXXXXXXXXXX请选择需要操作XXXXXXXXXXXXXXXXXXXXXXXX进行插入请选择心XXXXXXXXXXXXXXXXXXXXXXX进行删除请选择岔XXXXXXXXXXX查找请选择3共xxxxxxxxxxxx•■分查找i青选择坤共共共共共共共共共共共共xxxxxxxxxxxxjK出i青选择5餐餐餐餐餐餐共共共共餐餐5Pressangkeytocontinue程序代码二：#include"stdlib.h"#include"stdio.h"structnode{intd;structnode*next;};structnode*input(structnode*head,int*n){structnode*p,*q;intx;p=NULL;q=NULL;scanf("%d",&x);while(x>0){*n=*n+1;p=(structnode*)malloc(sizeof(structnode));p->d=x;p->next=NULL;if(head==NULL){head=(structnode*)malloc(sizeof(structnode));head=p;}elseq->next=p;q=p;scanf("%d",&x);}returnhead;}voidoutput(structnode*head,int*n){structnode*p;p=head;while(p!=NULL){printf("%5d",p->d);p=p->next;}}structnode*lookst(structnode*head,intx){structnode*p;p=head;while((p->next!=NULL)&&(((p->next)->d)!=x))p=p->next;return(p);}structnode*inslst(structnode*head,intx,intb,int*n){structnode*p,*q;p=(structnode*)malloc(sizeof(structnode));p->d=b;if(head==NULL){head=p;p->next=NULL;returnhead;}

if(head->d==x){p->next=head;head=p;returnhead;}q=lookst(head,x);p->next=q->next;q->next=p;*n=*n+1;returnhead;}structnode*delst(structnode*head,intx,int*n){structnode*p,*q;if(head==NULL){printf("thisisanemptylist!\n");returnhead;}if((head->d)==x){p=head->next;free(head);head=p;returnhead;}q=lookst(head,x);if(q->next==NULL){printf("nothisnodeinthelist!\n");returnhead;}p=q->next;q->next=p->next;free(p);*n=*n-1;returnhead;}voidmenu1()************5!新建建立线性表************5!新建建立线性表}voidmenu2(){printf(printf(printf(printf(printf(}printf("**********请选择您所要进行的操作***********1\n!出}voidmenu2(){printf(printf(printf(printf(printf(}"************请选择需要操作************\n")・"************进行插入请选择3************\n");"************进行删除请选择4************\n")・"************查找请选择5************\n")・"************退出请选择6************\n")・voidlserch(structnode*head,intx){structnode*p・intk=0・p=head・while((p!=NULL)&&(p->d!=x)){k++・p=p->next・}if(p==NULL)k=-1・if(k!=-1)printf("被查找的元素序数是％d\n",k+l);elseprintf("notfounded'n");voidmain(){int*n,b,x,j,k;structnode*head;head=NULL;n=NULL;n=(int*)malloc(sizeof(int));*n=0;printf("********您好！欢迎您使用这款软件。********\n本软件是由严康文开发出来的，版权所用，翻版必究！\n 本软件是用于实现线性表的删除与插入运算，操作界面简单，人性化适用于数据库的建立，插入与删除\n");menu1();scanf("%d",&j);if(j==1){printf("现在开始建立一个线性表\n");printf("请输入元素到线性链表中:")；head=input(head,n);printf("线性表中的元素是:")；output(head,n)；menu2()；scanf("%