《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案實(shí)驗(yàn)報(bào)告《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第1頁。院（系）：課程名稱：數(shù)據(jù)結(jié)構(gòu)日期：《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第1頁。班級(jí)學(xué)號(hào)實(shí)驗(yàn)室專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)姓名計(jì)算機(jī)號(hào)實(shí)驗(yàn)名稱順序表的運(yùn)算成績評定所用軟件VC或TC教師簽名實(shí)驗(yàn)?zāi)康恼莆枕樞虮淼幕靖拍钫莆枕樞虮淼慕ⅰ⒉迦牒蛣h除等方法。掌握順序表的基本算法。實(shí)驗(yàn)準(zhǔn)備復(fù)習(xí)書上有關(guān)內(nèi)容。閱讀實(shí)驗(yàn)步驟中的函數(shù)，寫出函數(shù)功能。寫出實(shí)驗(yàn)的源程序。實(shí)驗(yàn)1.各子函數(shù)功能：*init_sqlist()順序表的初始化creatsqlist(sqlist*L)順序表的建立Location_sqlist(sqlist*L,intx)在順序表中查找指定元素InsList(sqlist*L,inti,intx)將x插入到順序表的第i個(gè)位置2.源程序以及運(yùn)行結(jié)果如下：#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}SeqList;SeqList*init_sqlist(){SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));L->last=-1;returnL;}voidcreatsqlist(SeqList*L){inti;printf("請輸入最后一個(gè)元素的下標(biāo)");scanf("%d",&(L->last));printf("請輸入%d個(gè)元素",L->last+1);for(i=0;i<=L->last;i++)scanf("%d",&(*L).elem[i]);}intDelList(SeqList*L,inti,elemtype*e)/*在順序表L中刪除第i個(gè)數(shù)據(jù)元素，并用指針參數(shù)e返回其值。i的合法取值為1≤i≤L.last+1*/{ intk; if((i<1)||(i>L->last+1)) { printf("刪除位置不合法!"); return(0); } *e=L->elem[i-1];/*將刪除的元素存放到e所指向的變量中*/ for(k=i;k<=L->last;k++) L->elem[k-1]=L->elem[k];/*將后面的元素依次前移*/ L->last--; return(1);}voidmain() {inti,x,j;SeqList*a;a=init_sqlist();creatsqlist(a);printf("\n建立的順序表為：\n");for(i=0;i<=a->last;i++) printf("%d",a->elem[i]);printf("\n請問想要?jiǎng)h除第幾個(gè)元素？\n");scanf("%d",&j);if(DelList(a,j,&x))printf("\n被刪除的元素是%d\n",x);/*執(zhí)行函數(shù)調(diào)用*/printf("\n刪除后的順序表為：\n");for(i=0;i<=a->last;i++) printf("%d",a->elem[i]);printf("\n");}《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第2頁?！稊?shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第2頁。3.源代碼如下：#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;sqlist*init_sqlist(){sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;returnL;}voidcreatsqlist(sqlist*L){inti; printf("請輸入線性表的長度\n"); scanf("%d",&i); L->last=i-1; printf("請輸入線性表中的各元素值，注意：必須有序\n"); for(i=0;i<=L->last;i++) scanf("%d",&(*L).elem[i]);}void merge(sqlist*LA,sqlist*LB,sqlist*LC){ inti,j,k; i=0;j=0;k=0; while(i<=LA->last&&j<=LB->last) if(LA->elem[i]<=LB->elem[j]) { LC->elem[k]=LA->elem[i]; i++; k++; } else { LC->elem[k]=LB->elem[j]; j++; k++;} while(i<=LA->last) /*當(dāng)表LA有剩余元素時(shí)，則將表LA余下的元素賦給表LC*/ {《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第3頁。 LC->elem[k]=LA->elem[i];《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第3頁。 i++; k++; } while(j<=LB->last)/*當(dāng)表LB有剩余元素時(shí)，則將表LB余下的元素賦給表LC*/ { LC->elem[k]=LB->elem[j]; j++; k++; } LC->last=LA->last+LB->last+1;}voidmain() {inti,x,j;sqlist*a,*b,c;printf("\n*******建立順序表a********\n");a=init_sqlist();creatsqlist(a);printf("\n建立的順序表a為：\n");for(i=0;i<=a->last;i++) printf("%d",a->elem[i]);printf("\n*******建立順序表b********\n");b=init_sqlist();creatsqlist(b);printf("\n建立的順序表b為：\n");for(i=0;i<=b->last;i++) printf("%d",b->elem[i]);merge(a,b,&c);printf("\n合并后的順序表為：\n");for(i=0;i<=c.last;i++) printf("%d",c.elem[i]);printf("\n");《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第4頁。}《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第4頁。4.源程序?yàn)椋?defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;intInsList(sqlist*l,elemtypex){inti;if(l->last==MAXSIZE-1)return0;for(i=l->last;l->elem[i]>x&&i>=0;i--)l->elem[i+1]=l->elem[i];l->last++;l->elem[i+1]=x;return1;}voidmain() /*順序表插入的主函數(shù)*/{inti,x;sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;printf("請輸入元素的個(gè)數(shù)\n");scanf("%d",&x);for(i=0;i<x;i++){L->elem[i]=i*3;L->last=L->last+1;}printf("\n建立的順序表為\n");for(i=0;i<=L->last;i++)printf("%d",L->elem[i]);《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第5頁。printf("\n");《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第5頁。printf("\n請輸入要插入的數(shù)\n");scanf("%d",&x);InsList(L,x);/*執(zhí)行函數(shù)調(diào)用*/printf("\n插入元素%d后的順序表為\n",x);for(i=0;i<=L->last;i++)printf("%d",L->elem[i]);printf("\n");}5.將順序表(a1，a2，...，an)重新排列為以a1為界的兩部分：a1前面的值均比a1小，a1后面的值都比a1大(這里假設(shè)數(shù)據(jù)元素的類型具有可比性,不妨設(shè)為整型)基本思路：從第二個(gè)元素開始到最后一個(gè)元素，逐一向后掃描：（1）當(dāng)前數(shù)據(jù)元素aI比a1大時(shí)，表明它已經(jīng)在a1的后面，不必改變它與a1之間的位置，繼續(xù)比較下一個(gè)。（2）當(dāng)前結(jié)點(diǎn)若比a1小，說明它應(yīng)該在a1的前面，此時(shí)將它上面的元素都依次向下移動(dòng)一個(gè)位置，然后將它置入最上方。源程序如下：#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;//順序表結(jié)構(gòu)體類型的定義sqlist*init_sqlist()//順序表的初始化{sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;returnL;}voidcreatsqlist(sqlist*L)//順序表的建立《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第6頁。{inti;《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第6頁。printf("請輸入順序表中最后一個(gè)元素的下標(biāo)\n");scanf("%d",&(*L).last);printf("請輸入%d個(gè)元素\n",L->last+1);for(i=0;i<=(*L).last;i++)scanf("%d",&(*L).elem[i]);}voidpart(sqlist*L)//順序表的拆分{inti,j;elemtypex,y;x=L->elem[0];/*將基準(zhǔn)置入x中*/for(i=1;i<=L->last;i++)if(L->elem[i]<x)/*當(dāng)前元素小于基準(zhǔn)*/{y=L->elem[i];for(j=i-1;j>=0;j--)/*移動(dòng)*/L->elem[j+1]=L->elem[j];L->elem[0]=y; }}voiddayin(sqlist*a){inti;for(i=0;i<=a->last;i++)printf("%d",a->elem[i]);//順序表的輸出printf("\n");}voidmain() /*順序表的主函數(shù)*/{sqlist*a;a=init_sqlist();//調(diào)用函數(shù)對順序表的初始化creatsqlist(a);//建立順序表printf("建立的順序表為：\n");dayin(a);//輸出順序表part(a);//順序表的拆分printf("拆分后的順序表為：\n");dayin(a);//輸出拆分后的線性表《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第7頁。}《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第7頁。其中拆分函數(shù)還可以用如下方式實(shí)現(xiàn)，請比較兩種算法的效率，即算法法的時(shí)間復(fù)雜度分析voidpart(sqlist*L){inti,j,k;elemtypex,y;x=L->elem[0];i=1;j=L->last;k=0;while(L->elem[j]>x)j--;if(i<j){L->elem[k]=L->elem[j];k=j;}while(L->elem[i]<=x)i++;if(i<j){L->elem[k]=L->elem[i];k=i;}L->elem[k]=x;}6.編寫程序從一給定的順序表A中刪除值在x，y(x<=y)之間的所有元素。提示：1）方法：逐一比較每個(gè)元素的值，若元素值在X，Y之間，則刪除。2）主函數(shù)的編寫可模仿第一題#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;//順序表結(jié)構(gòu)體類型的定義sqlist*init_sqlist()//順序表的初始化{sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;returnL;《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第8頁。}《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第8頁。voidcreatsqlist(sqlist*L)//順序表的建立{inti;printf("請輸入順序表中最后一個(gè)元素的下標(biāo)\n");scanf("%d",&(*L).last);printf("請輸入%d個(gè)元素\n",L->last+1);for(i=0;i<=(*L).last;i++)scanf("%d",&(*L).elem[i]);}voiddele(sqlist*L)//順序表的刪除{inti,j;intx,y;printf("請輸入要?jiǎng)h除的值的下界");scanf("%d",&x);printf("請輸入要?jiǎng)h除的值的上界");scanf("%d",&y);for(i=0;i<=L->last;i++)if(L->elem[i]>=x&&L->elem[i]<=y){for(j=i;j<=L->last;j++)L->elem[j]=L->elem[j+1];L->last--; i--; }}voiddayin(sqlist*a){inti;for(i=0;i<=a->last;i++)printf("%d",a->elem[i]);//順序表的輸出printf("\n");}voidmain() /*順序表的主函數(shù)*/{sqlist*a;a=init_sqlist();//調(diào)用函數(shù)對順序進(jìn)行初始化creatsqlist(a);//建立順序表printf("建立的順序表為：\n");dayin(a);//輸出順序表dele(a);//刪除順序表指定范圍內(nèi)的數(shù)printf("刪除后的順序表為：\n");dayin(a);//輸出刪除后的線性表}《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第9頁?！稊?shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表答案全文共11頁，當(dāng)前為第9頁。7.編寫程序，將給定的順序表逆置。例如：順序表中的元素為：247191238逆置后為：831291742#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;//順序表結(jié)構(gòu)體類型的定義sqlist*init_sqlist()//順序表的初始化{sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;returnL;}voidcreatsqlist(sqlist*L)//順序表的建立{inti;printf("請輸入順序表中最后一個(gè)元素的下標(biāo)\n");scanf("%d",&(*L).last);printf("請輸入%d個(gè)元素\n",L->last+1);for(i=0;i<=(*L).last;i++)scanf("%d",&(*L).elem[i]);}voidinver(sqlist*L)//順序表的逆置{inti;elemtypet;for(i=0;i<=L->last/2;i++){t=L->elem[i];L->elem[i]=L->elem[L->last-i];L->elem[L->last-i]=t;}}voidshowsqlist(sqlist*a){inti;for(i=0;i<=a->last;i++)printf("%d",a->elem[i]);//順序表的輸出printf("\n");}voidmain() /*順序表的主