《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表實(shí)驗(yàn)報(bào)告《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第1頁(yè)。院（系）：課程名稱：數(shù)據(jù)結(jié)構(gòu)日期：《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第1頁(yè)。班級(jí)學(xué)號(hào)實(shí)驗(yàn)室專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)姓名計(jì)算機(jī)號(hào)實(shí)驗(yàn)名稱實(shí)驗(yàn)2順序表的操作成績(jī)?cè)u(píng)定所用軟件VC教師簽名實(shí)驗(yàn)?zāi)康?.掌握線性表的基本概念2.掌握順序表的建立、插入和刪除等方法。3.掌握順序表的基本算法。實(shí)驗(yàn)準(zhǔn)備1.復(fù)習(xí)書(shū)上有關(guān)內(nèi)容。2.閱讀實(shí)驗(yàn)步驟中的函數(shù)，寫(xiě)出函數(shù)功能。3.寫(xiě)出實(shí)驗(yàn)中要編程的源程序。（本次實(shí)驗(yàn)需4學(xué)時(shí)）實(shí)驗(yàn)內(nèi)容1.分析下列程序并上機(jī)運(yùn)行，寫(xiě)出各子函數(shù)功能并寫(xiě)出運(yùn)行結(jié)果。#defineMAXSIZE100typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;sqlist*init_sqlist(){sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;returnL;}voidcreatsqlist(sqlist*L){inti;printf("%d",L->last);scanf("%d",&(*L).last);for(i=0;i<=(*L).last;i++)scanf("%d",&(*L).elem[i]);}intLocation_sqlist(sqlist*L,intx){inti=0;while(i<=L->last&&L->elem[i]!=x)i++;if(i>L->last)return-1;elsereturni;}intInsList(sqlist*L,inti,intx){intk;if((i<1)||(i>L->last+2)){printf("LocateError!");return(0);}/*位置i值不合法*/if(L->last>=MAXSIZE-1){printf("Filled!");return(0);}for(k=L->last;k>=i-1;k--)L->elem[k+1]=L->elem[k];/*插入位置后的元素依次右移*/L->elem[i-1]=x;/*插入x*/L->last++;/*表長(zhǎng)加1*/return(1);}voidmain() {inti;sqlist*a;a=init_sqlist();creatsqlist(a);printf("%d\n",Location_sqlist(a,3));for(i=0;i<=a->last;i++)printf("%d",a->elem[i]);if(InsList(a,2,78))printf("\nOK!");/*執(zhí)行函數(shù)調(diào)用*/elseprintf("\nERROR!");for(i=0;i<=a->last;i++)printf("%d",a->elem[i]);}2.下列函數(shù)的功能是在順序表中刪除第i個(gè)元素，請(qǐng)編制主函數(shù)進(jìn)行函數(shù)調(diào)用，上機(jī)調(diào)試運(yùn)行。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(ERROR); } *e=L->elem[i-1];/*將刪除的元素存放到e所指向的變量中*/ for(k=i;i<=L->last;k++) L->elem[k-1]=L->elem[k];/*將后面的元素依次前移*/ L->last--; return(OK);《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第2頁(yè)。}《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第2頁(yè)。3.閱讀下列函數(shù)，寫(xiě)出函數(shù)的功能，再編制主函數(shù)進(jìn)行函數(shù)調(diào)用，寫(xiě)出主函數(shù)運(yùn)行結(jié)果。#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("請(qǐng)輸入線性表的長(zhǎng)度"); scanf("%d",&i); L->last=i-1; printf("請(qǐng)輸入線性表中的各元素值，注意：必須有序"); 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順序表全文共15頁(yè)，當(dāng)前為第3頁(yè)。 LC->elem[k]=LA->elem[i];《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第3頁(yè)。 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;}4.若順序表a中的數(shù)據(jù)元素按升序排列，要求將x插入到順序表中的合適位置，以保證表的有序性，試給出其程序，并上機(jī)調(diào)試運(yùn)行。提示：（1）設(shè)順序表中原有數(shù)據(jù)個(gè)數(shù)為10個(gè)，依次是{1,3,5,7,12,45,67,89,92,99}。（2）設(shè)需要插入的數(shù)據(jù)x值為25。（3）注意表長(zhǎng)的變化。（4）有序表的插入，需要分兩步完成：第一步確定插入位置，第二步在插入位置上插入指定的數(shù)據(jù)。5.將順序表(a1，a2，...，an)重新排列為以a1為界的兩部分：a1前面的值均比a1小，a1后面的值都比a1大(這里假設(shè)數(shù)據(jù)元素的類型具有可比性,不妨設(shè)為整型)參考思路：從第二個(gè)元素開(kāi)始到最后一個(gè)元素，逐一向后掃描：（1）當(dāng)前數(shù)據(jù)元素aI比a1大時(shí)，表明它已經(jīng)在a1的后面，不必改變它與a1之間的位置，繼續(xù)比較下一個(gè)。（2）當(dāng)前結(jié)點(diǎn)若比a1小，說(shuō)明它應(yīng)該在a1的前面，此時(shí)將它上面的元素都依次向下移動(dòng)一個(gè)位置，然后將它置入最上方。6.編寫(xiě)程序從一給定的順序表A中刪除值在x，y(x<=y)之間的所有元素。提示：1）方法：逐一比較每個(gè)元素的值，若元素值在X，Y之間，則刪除。2）主函數(shù)的編寫(xiě)可模仿第一題7.編寫(xiě)程序，將給定的順序表逆置。例如：順序表中的元素為：247191238逆置后為：831291742《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第4頁(yè)。8.請(qǐng)說(shuō)明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲(chǔ)結(jié)構(gòu)更好些。

⑴若線性表的總長(zhǎng)度基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素。

⑵如果n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化。

⑶描述一個(gè)城市的設(shè)計(jì)和規(guī)劃?！稊?shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第4頁(yè)。9.程序閱讀題，下列程序是有關(guān)順序表的有關(guān)操作，請(qǐng)閱讀，然后再上機(jī)運(yùn)行。#defineLIST_INIT_SIZE8//線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10//線性表存儲(chǔ)空間的分配增量#defineOVERFLOW-2#defineERROR0#defineOK1#defineTRUE1#defineFALSE0typedefintStatus;typedefintElemType;typedefstruct{ ElemType*elem;//存儲(chǔ)空間基址 intlength;//當(dāng)前長(zhǎng)度 intlistsize;//當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為單位)}SqList;//俗稱順序表typedefSqListOdSqList;//有序順序表StatusInitList(OdSqList&);//結(jié)構(gòu)初始化voidDestroy(OdSqList&);//銷毀有序順序表voidClearList(OdSqList&);//清空有序表StatusListEmpty(OdSqList);//判有序表為空intListLength(OdSqList);//求表長(zhǎng)intLocateElem(OdSqList,ElemType);//查找voidListInsert(OdSqList&,ElemType);//插入元素StatusListDelete(OdSqList&,int,ElemType&);//刪除元素intListDeletem(OdSqList&L,ElemTypee);//刪除所有值為e的元素,返回刪除的元素個(gè)數(shù)intListDeletemn(OdSqList&,ElemType,ElemType);//刪除所有值界于mink~maxk的元素，并返回刪除的元素個(gè)數(shù)voidListTraverse(OdSqList);//遍歷非遞減有序線性表#include<stdio.h>#include<stdlib.h>StatusInitList(OdSqList&L){//構(gòu)造一個(gè)空的線性表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE;《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第5頁(yè)。 returnOK;《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第5頁(yè)。}//InitListvoidListTraverse(OdSqListL){ //遍歷線性表 inti; printf("listsizeis%d.\n",L.listsize); printf("listlengthis%d.\n",L.length); printf("thelistis:("); for(i=1;i<=L.length;i++) printf("%d",L.elem[i-1]); printf(")\n");}intLocateElem(OdSqListL,ElemTypee){ //在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素，若存在，則返回它的位序，否則返回0 inti; i=1;//i的初值為第1元素的位序 ElemType*p; p=L.elem;//p的初值為第1元素的存儲(chǔ)位置 while(i<=L.length&&*p++!=e)++i; if(i<=L.length)returni; elsereturn0;}voidListInsert(OdSqList&L,ElemTypee){//在順序表L中保序插入新的元素e ElemType*newbase,*p,*q; if(L.length>=L.listsize){//當(dāng)前存儲(chǔ)空間已滿，增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW);//存儲(chǔ)分配失敗 L.elem=newbase;//新基址 L.listsize+=LISTINCREMENT;//增加存儲(chǔ)容量 } q=&(L.elem[0]);//q指示第1個(gè)元素位置 for(p=&(L.elem[L.length-1]);p>=q&&*p>e;--p) *(p+1)=*p;//插入位置及之后的元素右移 *(p+1)=e;//插入e ++L.length;//表長(zhǎng)增1}StatusListDelete(OdSqList&L,inti,ElemType&e){ ElemType*p,*q; if((i<1)||(i>L.length))returnERROR;//刪除位置不合法 p=&(L.elem[i-1]);//p為被刪除元素的位置 e=*p;//被刪除元素的值賦給e《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第6頁(yè)。 q=L.elem+L.length-1;//表尾元素的位置《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第6頁(yè)。 for(++p;p<=q;++p)*(p-1)=*p;//被刪除元素之后的元素左移 --L.length;//表長(zhǎng)減1 returnOK;}voidDestroy(OdSqList&L){ //銷毀有序順序表 free(L.elem);}voidClearList(OdSqList&L){ //清空有序表 L.length=0;}StatusListEmpty(OdSqListL){ //判有序表為空 if(L.length==0) returnTRUE; elsereturnFALSE;}intListLength(OdSqListL){ //求表長(zhǎng) returnL.length;}intListDeletem(OdSqList&L,ElemTypee){ //刪除所有值為e的元素,返回刪除的元素個(gè)數(shù) ElemType*p,*q,*r; inti=0;//刪除的元素個(gè)數(shù) p=&L.elem[0];//掃描指針 for(q=&L.elem[L.length-1];*p<e&&p<=q;p++); if(p<=q&&*p==e){ i++; for(r=p+1;*r==e&&r<=q;r++,i++); if(r<=q) for(;r<=q;r++,p++) *p=*r; } L.length-=i; returni;}intListDeletemn(OdSqList&L,ElemTypemink,ElemTypemaxk){ //刪除所有值界于mink~maxk的元素，并返回刪除的元素個(gè)數(shù) ElemType*p,*q,*r,temp; inti=0;《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第7頁(yè)。 if(maxk<mink){《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第7頁(yè)。 temp=maxk; maxk=mink; mink=temp; } p=&L.elem[0]; for(q=&L.elem[L.length-1];*p<mink&&p<=q;p++);//p指針指向第1個(gè)大于等于mink的元素if(p<=q&&*p<=maxk){//若*p小于等于maxk i++; for(r=p+1;*r<=maxk&&r<=q;r++,i++);//r指針指向第1個(gè)大于maxk的元素 if(r<=q) for(;r<=q;r++,p++) *p=*r; } L.length-=i; returni;}voidmain(){ OdSqListL; intk; chari; ElemTypee,mink,maxk; printf("OdSqListisinit……\n"); i=InitList(L); ListTraverse(L); while(1){ printf("\n\npleaseselect:\n"); printf("1------insert\n"); printf("2------traverse\n"); printf("3------deletei\n"); printf("4------deletek\n"); printf("5------deletemink-maxk\n"); printf("6------locate\n"); printf("7------isempty\n"); printf("8------length\n"); printf("9------clearlist\n"); printf("0------quit\n"); scanf("%d",&k); switch(k){ case1: printf("pleaseinpute:"); scanf("%d",&e); ListInsert(L,e); ListTraverse(L);《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第8頁(yè)。 scanf("%c",&i);《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第8頁(yè)。 printf("pleasepressanykeytocontinue……"); scanf("%c",&i); break; case2: ListTraverse(L); scanf("%c",&i); printf("pleasepressanykeytocontinue……"); scanf("%c",&i); break; case3: while(1){ printf("pleaseinputdeletei:"); scanf("%d",&i); if(ListDelete(L,i,e)==ERROR) printf("deletepositoniserror!\n"); else{ printf("Deletedelemis%d\n",e); break; } } ListTraverse(L); scanf("%c",&i); printf("pleasepressanykeytocontinue……"); scanf("%c",&i); break; case4: printf("pleaseinputdeletee:"); scanf("%d",&e); ListTraverse(L); printf("%delemisdeleted.\n",ListDeletem(L,e)); ListTraverse(L); scanf("%c",&i); printf("pleasepressanykeytocontinue……"); scanf("%c",&i); break; case5: printf("pleaseinputdeleteminkandmaxk:"); scanf("%d%d",&mink,&maxk); ListTraverse(L); printf("%delemisdeleted.\n",ListDeletemn(L,mink,maxk)); ListTraverse(L); scanf("%c",&i); printf("pleasepressanykeytocontinue……");《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第9頁(yè)。 scanf("%c",&i);《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)2順序表全文共15頁(yè)，當(dāng)前為第9頁(yè)。 break; case6: printf("pleaseinputlocatee:"); scanf("%d",&e); i=LocateElem(L,e); if(i==0) printf("locateDefaulted!\n"); else printf("locatedno.is%d\n",i); ListTraverse(L); scanf("%c",&i); printf("pleasepressanykeytocontinue……"); scanf("%c",&i); break; case7: if(ListEmpty(L)) printf("theorderlistisempty!\n"); else printf("theorderlistisnotempty!\n"); scanf("%c",&i); printf("pleasepressanykeytocontinue……"); scanf("%c",&i); break; case8: printf("lengthis%d.\n",ListLength(L)); scanf("%c",&i); printf("pleasepressanykeytocontinue……");