線性表的實現(xiàn)及操作(二)

實驗一、線性表的實現(xiàn)及操作(一)一、 實驗?zāi)康牧私夂驼莆站€性表的順序存儲結(jié)構(gòu)；掌握用C語言上機調(diào)試線性表的基本方法；掌握線性表的基本操作：插入、刪除、查找以及線性表合并等運算在順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)上的運算，以及對相應(yīng)算法的性能分析。二、 實驗要求給冷一段程序代碼，程序代碼所完成的功能為：(1)建立一個線性表；(2)依次輸入數(shù)據(jù)元素1,2,3,4,5,6,7,8,9,10；(3)刪除數(shù)據(jù)元素5；(4)依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。假設(shè)該線性表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過100個，要求使用順序表。程序中有3處錯誤的地方，有標(biāo)識，屬于邏輯錯誤，對照書中的代碼仔細(xì)分析后，要求同學(xué)們修改錯誤的代碼，修改后上機調(diào)試得到正確的運行結(jié)果。需求分析：這份實驗報告為所有必做題的實驗報告。包括實驗一順序表建立、插入、刪除等基本操作，實驗二單鏈表的建立、插入、刪除等基本操作，實驗四二叉樹的基本操作：樹的建立、前序、中序、后序遍歷及實驗六圖的遍歷：深度優(yōu)先和廣度優(yōu)先。這四份基礎(chǔ)性的實驗為改錯性質(zhì)，將每個實驗題目中的錯誤改正過來并通過調(diào)試，有助于對基礎(chǔ)知識的理解與強化記憶。概要設(shè)計：實驗一為對順序線性表實現(xiàn)插入，刪除，查找等基本操作。需要用到的語句包括voidListIiiitiate(SeqList*L)iiitListIiisert(SeqList*L.iiiti,DataTvpex)mtListDelete(SeqList*L,mti,DataT^e*x)mtListGet(SeqListL,mti.DataTvpe*x)等。實驗二是對單鏈表進行建立，插入，刪除等基本操作。需要的語句為voidListInitiate(SeqList*L)mtListIiisert(SeqList*L.iiiti,DataTypex)mtListDelete(SeqList*L,mti.DataType*x)mtListGet(SeqListL,mti,DataType*x)等。實驗四為二叉樹，要求建立一個二叉樹，并實現(xiàn)前序，中序及后序的遍歷。所需語句包括voidListInitiate(SeqList*L)mtListIiisert(SeqList*L.iiiti,DataTypex)mtListDelete(SeqList*L,mti.DataType*x)mtListGet(SeqListL,mti,DataType*x)等。實驗六的內(nèi)容是圖的遍歷包括鄰接矩陣和鄰接鏈表兩種方法。三、程序代碼(更正后的代碼)

#include<stdio.h>#defineMaxSize100tvpedefintDataType;tvpedefstnict{DataTypelist[MaxSize];intsize;}SeqList;voidListhutiate(SeqList*L){L->size=0;mtListLengtli(SeqListL){letumL.size;/*voidListhutiate(SeqList*L){L->size=0;mtListLengtli(SeqListL){letumL.size;/*定義初始數(shù)據(jù)元素個數(shù)*//*返回順序表L的當(dāng)前數(shù)據(jù)元素個數(shù)*/mtListhiseit(SeqList*L,int1,DataTypex)/*在順序表L的位置i(0W1Wsize)前插入數(shù)據(jù)元素值x*/嚴(yán)插入成功返回1,插入失敗返1?10*/mtj;if(L->size>=MaxSize){pnntf(”順序表己滿無法插入!E);letum0;}elseif(i<0||i>L->size){piintfC，參數(shù)1不合法!\n”)；letum0;}elsefbi(j=L->size;j>i;j-)L->list[j]=L->list[j]; /*為插入做準(zhǔn)備*/L->list[i]=x; /*插入*/L->size卄； /*元素個數(shù)加1*/leturn1;mtListDelete(SeqList*L,mti,DataTvpe*x)嚴(yán)刪除順序表L中位置i(0WiWsize-1)的數(shù)據(jù)元素值并存放到參數(shù)x中*/嚴(yán)刪除成功返回1,刪除失敗返1?10*/mtj;if(L->size<=0){piintf("順序表己空無數(shù)據(jù)元素可刪!\n“);letuin0;}elseif(i<0||1>L->size-l){piintfC*參數(shù)1不合法”)；letuin0;}else{//此段程序有一處錯誤*x=L->list[i]; /*保存刪除的元素到參數(shù)x中*/foi(j=i+l;j<=L->size-l;j++)L->list[j]=L->list[j-l]; /*依次前移L->size-; /*數(shù)據(jù)元素個數(shù)減1*/letuin1;}}mtListGet(SeqListL,inti,DataTvpe*x)嚴(yán)取順序表L中第「個數(shù)據(jù)元素於]值存于x中，成功則返回1,失敗返{if(i<O||i>L.size-l){pnntf(n參數(shù)1不合法!\ii")；letuin0;}else{*x=L.list[i];letuin1;}}voidmain(void)SeqListmvList;lilt1、x;Listlmtiate(&myList);fbi(i=0;i<10;i++)ListLisert(&mvList,i,1十1);ListDelete(&myLis「4,&x);foi(i=0;i<ListLength(myList);i++){?ListGet(myList,1,&x);//此段程序有一處錯誤piintf(n%d”,x);}}測試結(jié)果:1 23455555Pressanykeytocontinue線性表的實現(xiàn)及操作（二）一、 實驗?zāi)康牧私夂驼莆站€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)；掌握用C語言上機調(diào)試線性表的基本方法；掌握線性表的基本操作：插入、刪除、查找以及線性表合并等運算在順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)上的運算，以及對相應(yīng)算法的性能分析。二、 實驗要求給定一段程序代碼，程序代碼所完成的功能為：（1）建立一個線性表；（2）依次輸入數(shù)據(jù)元素1,2,3,4僅6,7,&9,10：（3）刪除數(shù)據(jù)元素5；（4）依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。假設(shè)該線性表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過100個，要求使用單鏈表。程序中有3處錯誤的地方，有標(biāo)識，屬于邏輯錯誤，對照書中的代碼仔細(xì)分析后，要求同學(xué)們修改錯誤的代碼，上機調(diào)試并得到正確的運行結(jié)果。三、程序代碼：（更正后的結(jié)果）存include<stdio.h>存include<stdlib.h>存inchide<malloc.h>/*該文件包含pnngtft）等函數(shù)*//*該文件包含exit。等函數(shù)*//*該文件包含malloc（）等函數(shù)*/typedefmtDataTvpe;/*定義DataType為iiit*/typedefstmctNodeiDataTypedata;stmctNode*next;}SLNode;嚴(yán)初始化*7嚴(yán)初始化*7嚴(yán)如果有內(nèi)存空間，申請頭結(jié)點空間并使頭指針head指向頭結(jié)點引if((*head=(SLNode*)malloc(sizeof(SLNode)))=NULL)exit(l);(*head)->next=NULL; 嚴(yán)置鏈尾標(biāo)記NULL*/}/*p指向首元結(jié)點嚴(yán)/*p指向首元結(jié)點嚴(yán)size初始為0*/SLNode*p=head;mtsize=0;

嚴(yán)循壞計數(shù)可while(p->next!=NULL){嚴(yán)循壞計數(shù)可p=p->next;size++;}returnsize;}intListIiiseil(SLNode*head.iiiti.DataTypex)/*在帶頭結(jié)點的單鏈表head的數(shù)據(jù)元素ai(0WiWsize)結(jié)點前*//*插入一個存放數(shù)據(jù)元素x的結(jié)點*/{SLNode*p,*q;mtj;p=head; /*p指向首元結(jié)點*/j=-l; /*j初始為-1*/while(p->next!=NULL&&j<i-1)/*最終讓指針p指向數(shù)據(jù)元素ai-1結(jié)點*/{p=p->next;J卄；}W){pnntf(“插入位置參數(shù)錯！”);return0;嚴(yán)生成新結(jié)點由指針q指示if((q=(SLNode*)inalloc(sizeof(SLNode)))=NULL)exit(l);q->data=x;〃此段程序有一處錯誤p->next〃此段程序有一處錯誤p->next=q->next;p->next=q;return1;}/*給指針q>next賦值*/嚴(yán)給指針p->next重新賦值可intListDelete(SLNode*head,mti,DataTvpe*x)/*intListDelete(SLNode*head,mti,DataTvpe*x)/*刪除帶頭結(jié)點的單鏈表head的數(shù)據(jù)元素ai(0WiWsize-1)結(jié)點*//*刪除結(jié)點的數(shù)據(jù)元素域值由x帶回。刪除成功時返回1；失敗返回0*/SLNode*p,*s;mtj;p=head; /*p指向首元結(jié)點*7J=-l; /*J初始為-1*/while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)/*最終讓指針p指向數(shù)據(jù)元素ai-1結(jié)點*/{p=p->next;j++;}W){pnntf(“插入位置參數(shù)錯！”);return0;〃此段程序有一處錯誤s=p->next;*x=s->data;p->next=s->next;fiee(s);return1;}/*s=p->next;*x=s->data;p->next=s->next;fiee(s);return1;}/*把指針s所指結(jié)點的數(shù)據(jù)元素域值賦予X*//*把數(shù)據(jù)元素ai結(jié)點從單鏈表中刪除指*//*釋放指針s所指結(jié)點的內(nèi)存空間可intListGet(SLNode*head,mti,DataType*x)/*取數(shù)據(jù)元素ai和刪除函數(shù)類同，只是不刪除數(shù)據(jù)元素ai結(jié)點*/{SLNode*p;mtj;p=head;J=-l;while(p->next!=NULL&&j<i){P=p->next;j++；}pnntfC取元素位置參數(shù)錯！”);return0;〃此段程序有一處錯誤*x=p->data;return1;}voidDestroy(SLNode**head){SLNode*p,*pl;p=*head;xvhile(p!=NULL){pl=p;p=p->next;fiee(pl);}*head=NULL;voidniaiii(void){SLNode*head;iiiti,x;Listliiitiate(&head); /*初始化*/for(i=0;i<10;i++){if(ListIiisert(head,i,i+1)==0) /*