線性表的查找算法

軟件基礎(chǔ)基礎(chǔ)實(shí)驗(yàn)報(bào)告系別：地質(zhì)工程系班級(jí)：09測(cè)繪 學(xué)號(hào)：0910205006 姓名：嚴(yán)康文實(shí)驗(yàn)時(shí)間：實(shí)驗(yàn)地點(diǎn)：網(wǎng)教中心實(shí)驗(yàn)環(huán)境：vc6.0實(shí)驗(yàn)名稱：線性表的查找算法實(shí)驗(yàn)?zāi)康模?1)掌握線性表的順序查找算法(2)掌握有序表的折半查找算法實(shí)驗(yàn)內(nèi)容：在順序存儲(chǔ)的長(zhǎng)度為n的線性表中順序查找元素x在表中的下標(biāo)。備注：需要用到的算法是：serch()在頭指針為head的線性鏈表中順序查找元素x的存儲(chǔ)序號(hào)。備注：需要用到的算法是：lserch()在順序存儲(chǔ)的長(zhǎng)度為n的線性表中對(duì)分查找元素x在表中的下標(biāo)。備注：需要用到的算法是：bserch()程序代碼：#include"stdio.h"#include"stdlib.h"voidinput(int*v,int*n){inti;printf("請(qǐng)輸入％d元素到線性表山",*。)；for(i=0;i<*n;i++){scanf("%d",v+i);printf("\n請(qǐng)輸入下一個(gè)元素到線性表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("************請(qǐng)選擇需要操作************\n")；printf("************進(jìn)行插入請(qǐng)選擇i************\n")；printf("************進(jìn)行刪除請(qǐng)選擇2************\n");printf("************査找請(qǐng)選擇3************\n");printf("************對(duì)分査找請(qǐng)選擇4************\n");printf("************退出請(qǐng)選擇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("請(qǐng)輸入所建表的容量m\n");scanf("%d",&m);printf("請(qǐng)輸入所建表的元素個(gè)數(shù)n\n");scanf("%d",n);v=initsl(m,n);〃建立線型表printf("請(qǐng)輸入所建表的元素\n");input(v,n);output(v,n);menu();scanf("%d",&j);do{if(j==1){printf(”請(qǐng)輸入在第個(gè)i元素前插入元素b\n");scanf("%d%d",&i,&b);insl(v,m,n,i,b);output(v,n);}elseif(j==2){printf(”請(qǐng)輸入刪除的元素順序i\n");scanf("%d",&i);desl(v,m,n,i);output(v,n);}elseif(j==3){printf(”請(qǐng)輸入要査找的元素x\n");scanf("%d",&x);serch(v,nx);}elseif(j==4){printf("請(qǐng)輸入要査找的元素x\n");scanf("%d",&x);bserch(v,n,x);}elsebreak;

menu();scanf("%d",&j);}while(j!=5);}運(yùn)行結(jié)果：順序查找：順序查找：請(qǐng)輸入下一個(gè)元素到線性表輸入完成，停止輸入性表的第1個(gè)元素為1性表的第請(qǐng)輸入下一個(gè)元素到線性表輸入完成，停止輸入性表的第1個(gè)元素為1性表的第2個(gè)元素為6性表的第3個(gè)元素為9性表的第4個(gè)元素為3性表的第5個(gè)元素為5性表的第6個(gè)元素為6XXXXXXXXXXXX請(qǐng)選擇需要操作XXXXXXXXXXXX

進(jìn)行插入請(qǐng)選擇2進(jìn)行刪除請(qǐng)選擇3共興共共共共共共共興共XXXXXXXXXXXX查找請(qǐng)選擇外XXXXXXXXXXXXXXXXXXXXXXX對(duì)分杳找請(qǐng)選擇辱XXXXXXXXXXXxxxxxxxxxxxxjg出i青選擇5共餐餐餐餐共餐共共餐餐餐售輸入要杳找的元素X被查找的元素序禁是3 口請(qǐng)選擇需要操作XXXXXXXXXXXX進(jìn)行插入請(qǐng)選擇心XXXXXXXXXXXXXXXXXXXXXXX進(jìn)行刪除請(qǐng)選擇岔XXXXXXXXXXX餐餐餐餐共共餐共餐餐餐餐查找i青選擇3共餐餐餐餐共餐共共餐餐餐對(duì)分查找請(qǐng)選擇％共興共共共共共共共興共XXXXXXXXXXXX退出請(qǐng)選擇界XXXXXXXXXXX5Pressanykeytocontinue對(duì)分查找：線,線,線,線'線'性表的第1個(gè)元素為1性表的第2個(gè)元素為2性表的第3個(gè)元素為3性表的第耳個(gè)元素為4性表的第5個(gè)元素為6XXXXXXXXXXXX對(duì)分查找：線,線,線,線'線'性表的第1個(gè)元素為1性表的第2個(gè)元素為2性表的第3個(gè)元素為3性表的第耳個(gè)元素為4性表的第5個(gè)元素為6XXXXXXXXXXXX對(duì)分杳找請(qǐng)選擇辱XXXXXXXXXXXxxxxxxxxxxxxjK出i青選擇5共其共共共共共共共其共共售輸入要查找的元素X被查找的元素序敦是3 °XXXXXXXXXXXX請(qǐng)選擇需要操作XXXXXXXXXXXXXXXXXXXXXXXX進(jìn)行插入請(qǐng)選擇心XXXXXXXXXXXXXXXXXXXXXXX進(jìn)行刪除請(qǐng)選擇岔XXXXXXXXXXX查找請(qǐng)選擇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("**********請(qǐng)選擇您所要進(jìn)行的操作***********1\n!出}voidmenu2(){printf(printf(printf(printf(printf(}"************請(qǐng)選擇需要操作************\n")?"************進(jìn)行插入請(qǐng)選擇3************\n");"************進(jìn)行刪除請(qǐng)選擇4************\n")?"************查找請(qǐng)選擇5************\n")?"************退出請(qǐng)選擇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本軟件是由嚴(yán)康文開發(fā)出來的，版權(quán)所用，翻版必究！\n 本軟件是用于實(shí)現(xiàn)線性表的刪除與插入運(yùn)算，操作界面簡(jiǎn)單，人性化適用于數(shù)據(jù)庫(kù)的建立，插入與刪除\n");menu1();scanf("%d",&j);if(j==1){printf("現(xiàn)在開始建立一個(gè)線性表\n");printf("請(qǐng)輸入元素到線性鏈表中:")；head=input(head,n);printf("線性表中的元素是:")；output(head,n)；menu2()；scanf("%