線性表的查找算法

軟件基礎(chǔ)基礎(chǔ)實驗報告系別：地質(zhì)工程系班級：09測繪 學(xué)號：0910205006 姓名：嚴康文實驗時間：實驗地點：網(wǎng)教中心實驗環(huán)境：vc6.0實驗名稱：線性表的查找算法實驗?zāi)康模?1)掌握線性表的順序查找算法(2)掌握有序表的折半查找算法實驗內(nèi)容：在順序存儲的長度為n的線性表中順序查找元素x在表中的下標(biāo)。備注：需要用到的算法是：serch()在頭指針為head的線性鏈表中順序查找元素x的存儲序號。備注：需要用到的算法是：lserch()在順序存儲的長度為n的線性表中對分查找元素x在表中的下標(biāo)。備注：需要用到的算法是：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("被査找的元素序數(shù)是％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("被査找的元素序數(shù)是%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("請輸入所建表的元素個數(shù)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);}運行結(jié)果：順序查找：順序查找：請輸入下一個元素到線性表輸入完成，停止輸入性表的第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("被查找的元素序數(shù)是％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本軟件是由嚴康文開發(fā)出來的，版權(quán)所用，翻版必究！\n 本軟件是用于實現(xiàn)線性表的刪除與插入運算，操作界面簡單，人性化適用于數(shù)據(jù)庫的建立，插入與刪除\n");menu1();scanf("%d",&j);if(j==1){printf("現(xiàn)在開始建立一個線性表\n");printf("請輸入元素到線性鏈表中:")；head=input(head,n);printf("線性表中的元素是:")；output(head,n)；menu2()；scanf("%