2011級(jí)本數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教案

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)性實(shí)驗(yàn)項(xiàng)目1. 線性表的合并：已知線性表La和Lb的元素按值非遞減排列。歸并La和Lb得到新的線性表Lc，Lc的元素也按值非遞減排列。分別采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)來(lái)實(shí)現(xiàn)。2. 線性表的逆置：設(shè)有一個(gè)線性表（e0, e1, , en-2, en-1），請(qǐng)編寫一個(gè)函數(shù)將這個(gè)線性表原地逆置，即將線性表內(nèi)容置換為（en-1, en-2, , e1, e0）。線性表中的數(shù)據(jù)可以為整數(shù)、字符或字符串，試分別采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)來(lái)實(shí)現(xiàn)。3. 約瑟夫環(huán)的實(shí)現(xiàn)：設(shè)有n個(gè)人圍坐一圈，用整數(shù)序列1, 2, 3, , n表示順序圍坐在圓桌周圍的人， 現(xiàn)從某個(gè)位置 s上的人開始報(bào)數(shù)，數(shù)到

2、m的人出列，接著從出列的下一個(gè)人又從1開始重新報(bào)數(shù)，數(shù)到m的人出列，如此下去，直到所有人都出列為此。試設(shè)計(jì)確定他們的出列次序序列的程序。如 n=8, m=4 ,s=1時(shí)， 設(shè)每個(gè)人的編號(hào)依次為 1，2，3，開始報(bào)數(shù)，則得到的出列次序?yàn)?，8，5，2，1，3，7，6。檢查程序的正確性和健壯性。(1)采用數(shù)組表示作為求解過(guò)程中使用的數(shù)據(jù)結(jié)構(gòu)。(2) 采用單向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬整個(gè)過(guò)程，循環(huán)鏈表可不設(shè)頭節(jié)點(diǎn),必須注意空表和非空表的界限。4. 數(shù)制轉(zhuǎn)換： 利用順序棧和鏈棧實(shí)現(xiàn)數(shù)制轉(zhuǎn)換5. 二叉樹的遍歷：分別以順序存儲(chǔ)結(jié)構(gòu)和二叉鏈表作存儲(chǔ)結(jié)構(gòu)，試編寫前序、中序、后序及層次順序遍歷二叉樹的算法。6.

3、 赫夫曼樹與赫夫曼編碼：已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符a,b,c,d,e,f,g,h，其概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)Huffman編碼，并計(jì)算其平均碼長(zhǎng)。(1) 初始化：從鍵盤讀入8個(gè)字符，以及它們的權(quán)值，建立Huffman樹。(2)編碼：根據(jù)建立的Huffman樹，求每個(gè)字符的Huffman編碼。對(duì)給定的待編碼字符序列進(jìn)行編碼。(3) 譯碼：利用已經(jīng)建立好的Huffman樹，對(duì)上面的編碼結(jié)果譯碼。譯碼的過(guò)程是分解電文中的字符串，從根結(jié)點(diǎn)出發(fā)，按字符0和1確定找左孩子或右孩子，直至葉結(jié)點(diǎn)，便求得該子串相應(yīng)的字符。(4

4、) 打印Huffman樹。7. 學(xué)生成績(jī)管理查詢系統(tǒng)：每個(gè)學(xué)生的數(shù)據(jù)信息有準(zhǔn)考證號(hào)（主關(guān)鍵字）、姓名、語(yǔ)文、英語(yǔ)、數(shù)學(xué)、和總分等數(shù)據(jù)項(xiàng)，所有學(xué)生的信息構(gòu)成一個(gè)學(xué)生成績(jī)表。假設(shè)準(zhǔn)考證號(hào)的頭兩位表示地區(qū)編號(hào)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)管理系統(tǒng)達(dá)到如下基本要求：（1） 初始化：建立一個(gè)學(xué)生成績(jī)表，輸入準(zhǔn)考證號(hào)、姓名、語(yǔ)文、英語(yǔ)、數(shù)學(xué)，然后計(jì)算每個(gè)學(xué)生的總分，存入相應(yīng)的數(shù)據(jù)項(xiàng)；注意：分析數(shù)據(jù)對(duì)象和它們之間的關(guān)系，并以合適的方式進(jìn)行組織（可選擇無(wú)序的順序表、有序的順序表或索引順序表來(lái)進(jìn)行存儲(chǔ)表示）；（2） 查找：綜合應(yīng)用基本查找算法完成數(shù)據(jù)的基本查詢工作，并輸出查詢的結(jié)果；（3） 輸出：有選擇性地輸出滿足一定條件的數(shù)據(jù)

5、記錄，如輸出地區(qū)編號(hào)為01，并且總分在550分以上的學(xué)生的信息；（4） 計(jì)算：計(jì)算在等概率情況下該查找表的平均查找長(zhǎng)度。8. 排序：編制程序讓機(jī)器隨機(jī)產(chǎn)生2000個(gè)整數(shù)，放入一個(gè)數(shù)組中；對(duì)此2000個(gè)隨機(jī)數(shù)序列分別用冒泡排序、快速排序、希爾排序和堆排序方法進(jìn)行排序，并比較它們的運(yùn)行時(shí)間。注意：每三、四個(gè)同學(xué)組成一個(gè)小組。每個(gè)實(shí)驗(yàn)中的題目，可分別由不同的同學(xué)完成。其它題目可以相互交流，以利于互相提高。數(shù)據(jù)結(jié)構(gòu)驗(yàn)證性實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)一 線性表的順序存儲(chǔ)實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康募耙?、掌握在TC環(huán)境下調(diào)試順序表的基本方法2、掌握順序表的基本操作，插入、刪除、查找、以及有序順序表的合并等算法的實(shí)現(xiàn)。二、實(shí)驗(yàn)學(xué)時(shí)

6、2學(xué)時(shí)三、實(shí)驗(yàn)任務(wù)1、 生成一個(gè)順序表并動(dòng)態(tài)地刪除任意元素和在任意位置插入元素。2、 將兩個(gè)有序表合并成一個(gè)有序表。四、實(shí)驗(yàn)重點(diǎn)、難點(diǎn)1、 在順序表中移動(dòng)元素。2、 在順序表中找到正確的插入位置。五、操作要點(diǎn) (一)順序表基本操作的實(shí)現(xiàn)問題描述 當(dāng)我們要在順序表的第i個(gè)位置上插入一個(gè)元素時(shí)，必須先將順序表中第i個(gè)元素之后的所有元素依次后移一個(gè)位置，以便騰空一個(gè)位置，再把新元素插入到該位置。若是欲刪除第i個(gè)元素時(shí)，也必須把第i個(gè)元素之后的所有元素前移一個(gè)位置。基本要求 要求生成順序表時(shí)，可以鍵盤上讀取元素，用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)。實(shí)現(xiàn)提示 要實(shí)現(xiàn)基本操作，可用實(shí)現(xiàn)的基本操作，也可設(shè)計(jì)簡(jiǎn)單的算法實(shí)

7、現(xiàn)。程序?qū)崿F(xiàn)#include #include typedef int DataType ;# define maxnum 20typedef structint datamaxnum;int length;SeqList;/*插入函數(shù)*/int insert(SeqList *L , int i , DataType x)/* 將新結(jié)點(diǎn)x插入到順序表L第i個(gè)位置 */ int j ;if( i(*L).length +1) printf( n i 值不合法 ! ); return 0;if(* L).length =maxnum-1) printf( n 表滿不能插入!); return 0

8、; for(j=(*L).length;j=i;j-) (*L).dataj+1=(*L).dataj;(*L).datai = x;(*L).length+;return 1;/*刪除函數(shù)*/int delete( SeqList *L ,int i) /*從順序L中刪除第i個(gè)結(jié)點(diǎn)*/ int j ;if( i(*L).length ) printf( n 刪除位置錯(cuò)誤 ! ) ;return 0;for(j=i+1;j=(*L).length;j+)(*L).dataj-1 =(*L).dataj;(*L).length-;return 1;/*生成順序表*/void creatlist(

9、SeqList * L) int n , i , j ;printf(請(qǐng)輸入順序表 L 的數(shù)據(jù)個(gè)數(shù)：n) ;scanf(%d , &n) ;for(i=0 ; in ; i+) printf(data%d = , i) ; scanf(%d,&(*L).datai);(*L).length=n-1;printf(n) ;/*creatlist */*輸出順序表 L*/printout(SeqList * L) int i ;for (i=0 ; i=(* L).length ; i+) printf( data%d=, i) ; printf(%d, (*L).datai);/*printou

10、t */printf(n);main() SeqList *L ;char cmd ;int i , t , x;clrscr() ;creatlist(L);doprintf(ni , I - 插入n) ;printf(d , D - 刪除n) ;printf(q , Q - 退出n) ;docmd=getchar() ;while(cmd!=i)&(cmd!=I)&(cmd!=d)&(cmd!=D)&(cmd!=q)&(cmd!=Q);switch(cmd) case i: case I:printf(nPlease input the DATA: );scanf(%d,&x) ;prin

11、tf(nWhere? );scanf(%d,&i) ;insert(L,i,x) ;printout(L);break ;case d:case D :printf(nWhere to Delete? );scanf(%d,&i);delete(L,i);printout(L);break ;while(cmd!=q)&(cmd!=Q);（二）有序順序表的合并問題描述 已知順序表la和lb中的數(shù)據(jù)元素按非遞減有序排列，將la和lb表中的數(shù)據(jù)元素，合并成為一個(gè)新的順序表lc基本要求 lc中的數(shù)據(jù)元素仍按非遞減有序排列，并且不破壞la和lb表程序?qū)崿F(xiàn)# include # define maxnu

12、m 20typedef int DataType ;typedef struct DataType datamaxnum ; int length ;SeqList ;int MergeQL(SeqList la , SeqList lb , SeqList *lc) int i , j , k ;if (la.length+1 + lb.length+1maxnum) printf(narray overflow!) ;return 0;i=j=k=0;while(i=la.length & j=lb.length) if (la.dataidatak+=la.datai+ ;else lc

13、-datak+=lb.dataj+;/* 處理剩余部分 */while (idatak+=la.datai+;while (jdatak+=lb.dataj+;lc-length=k-1;return 1;main() SeqList la=3,4,7,12,15,4 ;SeqList lb=2,5,7,15,18,19,5 ;SeqList lc ;int i ;if (MergeQL(la,lb,&lc) printf(n) ;for(i=0;i=lc.length ; i+)printf(%4d,lc.datai); 六、注意事項(xiàng)1、 刪除元素或插入元素表的長(zhǎng)度要變化。2、 在合并表中當(dāng)

14、某一個(gè)表到表尾了就不用比較了，直接將另一個(gè)表的元素復(fù)制到總表去即可。實(shí)驗(yàn)二 單鏈表實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康募耙?、掌握用在TC環(huán)境下上機(jī)調(diào)試單鏈表的基本方法2、掌握單鏈表的插入、刪除、查找、求表長(zhǎng)以及有序單鏈表的合并算法的實(shí)現(xiàn)3、進(jìn)一步掌握循環(huán)單鏈表的插入、刪除、查找算法的實(shí)現(xiàn)二、實(shí)驗(yàn)學(xué)時(shí)4學(xué)時(shí)三、實(shí)驗(yàn)任務(wù)1、在帶頭結(jié)點(diǎn)的單鏈表h中第i個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素。2、將兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表。3、生成一個(gè)循環(huán)單鏈表。4、在循環(huán)單鏈表中刪除一個(gè)節(jié)點(diǎn)。四、實(shí)驗(yàn)重點(diǎn)、難點(diǎn)1、 在單鏈表中尋找到第i-1個(gè)結(jié)點(diǎn)并用指針p指示。2、 比較兩個(gè)單鏈表的節(jié)點(diǎn)數(shù)據(jù)大小。3、循環(huán)單鏈表中只有一個(gè)節(jié)點(diǎn)的判

15、斷條件。4、在循環(huán)單鏈表中刪除一個(gè)節(jié)點(diǎn)。五、操作要點(diǎn)（一）單鏈表基本操作的實(shí)現(xiàn)問題描述要在帶頭結(jié)點(diǎn)的單鏈表h中第i個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素x ，首先需要在單鏈表中尋找到第i-1個(gè)結(jié)點(diǎn)并用指針p指示，然后申請(qǐng)一個(gè)由指針s 指示的結(jié)點(diǎn)空間，并置x為其數(shù)據(jù)域值，最后修改第i-1個(gè)結(jié)點(diǎn)，并使x結(jié)點(diǎn)的指針指向第i個(gè)結(jié)點(diǎn)，要在帶頭結(jié)點(diǎn)的單鏈表h中刪除第i個(gè)結(jié)點(diǎn)，首先要計(jì)數(shù)尋找到第i個(gè)結(jié)點(diǎn)并使指針p指向其前驅(qū)第i-1個(gè)結(jié)點(diǎn)，然后刪除第i個(gè)結(jié)點(diǎn)并釋放被刪除結(jié)點(diǎn)空間?；疽笥面?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)實(shí)現(xiàn)提示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不是隨機(jī)存儲(chǔ)結(jié)構(gòu)，即不能直接取到單鏈表中某個(gè)結(jié)點(diǎn)，而要從單鏈表的頭結(jié)點(diǎn)開始一個(gè)一個(gè)地計(jì)數(shù)尋

16、找。程序?qū)崿F(xiàn)# include # include typedef char DataType ;typedef struct node DataType data; /*結(jié)點(diǎn)的數(shù)據(jù)域*/ struct node *next; /*結(jié)點(diǎn)的指針域*/ListNode;void Init_List(ListNode *L)(*L)=(ListNode *)malloc(sizeof(ListNode);/*產(chǎn)生頭結(jié)點(diǎn)*/(*L)-next=NULL;int List_Length(ListNode *L )int n=0;ListNode *p=L-next;while(p!=NULL)n+;p=

17、p-next;return n;ListNode* GetNode(ListNode *L,int i) int j; ListNode *p; p=L;j=0; /*從頭結(jié)點(diǎn)開始掃描*/ while(p-next&j!=i) /*順指針向后掃描,直到p-next為NULL或i=j為止*/ p=p-next; j+; if(i=j) return p; /*找到了第i個(gè)結(jié)點(diǎn)*/ else return NULL; /*當(dāng)i0時(shí),找不到第i個(gè)結(jié)點(diǎn)*/ void InsertList(ListNode *L,DataType x,int i) ListNode *p,*s; p=GetNode(L

18、,i-1); /*尋找第i-1個(gè)結(jié)點(diǎn)*/ if (p=NULL) /*in+1時(shí)插入位置i有錯(cuò)*/ printf(position error); return ; s=(ListNode *)malloc(sizeof(ListNode); s-data=x;s-next=p-next;p-next=s; void DeleteList(ListNode *L ,int i)ListNode *p,*r;p=GetNode(L,i-1); /*找到第i-1個(gè)結(jié)點(diǎn)*/if (p=NULL|p-next=NULL) /*in時(shí),刪除位置錯(cuò)*/ printf(position error); re

19、turn ; r=p-next; /*使r指向被刪除的結(jié)點(diǎn)a*/p-next=r-next; /*將ai從鏈上刪除*/free(r); /*使用頭插法建立帶頭結(jié)點(diǎn)鏈表算法*/ListNode * CreatListF(void)char ch;ListNode *head=(ListNode *)malloc(sizeof(ListNode); /*生成頭結(jié)點(diǎn)*/ListNode *s; /*工作指針*/head-next=NULL; ch=getchar(); /*讀入第1個(gè)字符*/while(ch!=n) s=(ListNode *)malloc(sizeof(ListNode); /*生

20、成新結(jié)點(diǎn)*/ s-data=ch; /*將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中*/ s-next=head-next; head-next=s; ch=getchar(); /*讀入下一字符*/return head; /*使用尾插法建立帶頭結(jié)點(diǎn)鏈表算法*/ListNode * CreatListR1(void) char ch; ListNode *head=(ListNode *)malloc(sizeof(ListNode); /*生成頭結(jié)點(diǎn)*/ ListNode *s,*r; /*工作指針*/ r=head; /*尾指針初值也指向頭結(jié)點(diǎn)*/ while(ch=getchar()!=n) s=

21、(ListNode *)malloc(sizeof(ListNode); s-data=ch; r-next=s; r=s; r-next=NULL; /*終端結(jié)點(diǎn)的指針域置空,或空表的頭結(jié)點(diǎn)指針域置空*/ return head; /*復(fù)制鏈表A中的內(nèi)容到表B中*/ void copy(ListNode *a, ListNode *b) ListNode *pa=a-next; ListNode *u; ListNode *rb=b; while(pa!=NULL) u=( ListNode *)malloc(sizeof(ListNode); u-data=pa-data; rb-next

22、=u; rb=u; pa=pa-next;rb-next=NULL;/*輸出帶頭結(jié)點(diǎn)的單鏈表*/void DisplaySL(ListNode *la, char *comment) ListNode *p ; p=la-next ; if(p) printf(n%sn , comment) ; while(p)printf(%4c,p-data);p=p-next; printf(n) ;/*主函數(shù)*/main( ) ListNode *la ,*lb,*lc, *p ;int n,x,i;printf(n用頭插法建立鏈表la，請(qǐng)輸入節(jié)點(diǎn)內(nèi)容:);la=CreatListF();Displa

23、ySL(la,新生成鏈la節(jié)點(diǎn)內(nèi)容:); printf(n鏈表la的長(zhǎng)度: %2d,List_Length(la);printf(n請(qǐng)輸入要插入的元素: );scanf(%c,&x) ;printf(n請(qǐng)輸入要插入的位置：);scanf(%d,&i) ;InsertList(la,x,i);DisplaySL(la,插入后鏈la節(jié)點(diǎn)內(nèi)容);printf(n請(qǐng)輸入要?jiǎng)h除元素的位置：);scanf(%d,&i);DeleteList(la,i);DisplaySL(la, 刪除后鏈la節(jié)點(diǎn)內(nèi)容);printf(n用尾插法建立鏈表lb，請(qǐng)輸入節(jié)點(diǎn)內(nèi)容:);fflush(stdin);lb=Creat

24、ListR1();DisplaySL(lb,新生成鏈lb節(jié)點(diǎn)內(nèi)容:); Init_List(&lc);copy(la,lc);DisplaySL(lc,復(fù)制生成的鏈lc節(jié)點(diǎn)內(nèi)容:); （二）有序單鏈表的合并問題描述 已知單鏈表la和lb中的數(shù)據(jù)元素按非遞減有序排列，將la和lb中的數(shù)據(jù)元素,合并為一個(gè)新的單鏈表lc,lc中的數(shù)據(jù)元素仍按非遞減有序排列?；疽?不破壞la表和lb表的結(jié)構(gòu)。程序?qū)崿F(xiàn)#include #include#define NULL 0typedef int DataType;typedef struct SLNode DataType data; struct SLNo

25、de * next; slno;int MergeSL(slno *la,slno *lb,slno *lc);int CreateSL(slno *la,int n);void DisplaySL(slno *la , char * comment);void main( ) slno *la, *lb, *lc ;int n,m;la=(slno *)malloc(sizeof(slno);la-next=NULL;lb=(slno *)malloc(sizeof(slno);lb-next=NULL;lc=(slno *)malloc(sizeof(slno);lc-next=NULL;

26、printf(n 輸入鏈la節(jié)點(diǎn)數(shù):);scanf(%d,&n);printf(n 輸入鏈la 節(jié)點(diǎn)內(nèi)容:);CreateSL(la,n);DisplaySL(la,鏈la 節(jié)點(diǎn)內(nèi)容:);printf(n 輸入鏈lb節(jié)點(diǎn)數(shù):);scanf(%d,&m);printf(n 輸入鏈lb節(jié)點(diǎn)內(nèi)容:);CreateSL(lb,m);DisplaySL(lb,鏈lb 節(jié)點(diǎn)內(nèi)容:);if(MergeSL(la,lb,&lc) DisplaySL(lc,合成后的鏈lc:);getchar();int MergeSL(slno * la , slno *lb,slno *lc) slno * pa, * pb

27、, * pc; *lc=(slno *)malloc(sizeof(slno); pa=la-next; pb=lb-next; pc= *lc; while(pa&pb) pc-next=(slno*)malloc(sizeof(slno); pc=pc-next; if(pa-datadata) pc-data=pa-data; pa=pa-next; else pc-data=pb-data; pb=pb-next; while (pa) /*插入la鏈的剩余段 */ pc-next=(slno*)malloc(sizeof(slno); pc=pc-next; pc-data=pa-d

28、ata; pa=pa-next; /*插入lb鏈的剩余段*/ while(pb) pc-next=(slno*)malloc(sizeof(slno); pc=pc-next; pc-data=pb-data; pb=pb-next; pc-next=NULL; return 1;/*生成單鏈表*/int CreateSL(slno *la ,int n) int i ;slno *p , *q ;q=la ;for (i=1 ; idata) ;q-next=p;q=p;q-next=NULL ;return 1 ;/*輸出單鏈表*/void DisplaySL(slno *la, char

29、 *comment) slno *p ;p=la-next ;if(p) printf(n%sn , comment) ;while(p) printf(n%3d , p-data);p=p-next ;printf(n) ;printf(n) ;（三） 約瑟夫環(huán)問題問題描述設(shè)有N個(gè)人圍坐一圈，現(xiàn)從某個(gè)人開始報(bào)數(shù)，數(shù)到M的人出列，接著從出列的下一個(gè)人開始重新報(bào)數(shù)，數(shù)到M的人以出列，如此下去，直到所有人都出列為此。試設(shè)計(jì)確定他們的出列次序序列的程序。基本要求 選擇單向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬整個(gè)過(guò)程，并依次輸出列的各人的編號(hào)。實(shí)現(xiàn)提示 程序運(yùn)行之后，首先要求用戶指定初始報(bào)數(shù)的下限值，可以n=30

30、,此題循環(huán)鏈表可不設(shè)頭節(jié)點(diǎn)，而且必須注意空表和非空表的界限。如 n=8, m=4 時(shí)，若從第一個(gè)人， 設(shè)每個(gè)人的編號(hào)依次為 1，2，3，開始報(bào)數(shù)，則得到的出列次序?yàn)?，8，5，2，1，3，7，6，如下圖所示，內(nèi)層數(shù)字表示人的編號(hào) ，每個(gè)編號(hào)外層的數(shù)字代表人出列的序號(hào)。程序?qū)崿F(xiàn)#include #include typedef struct node int num; struct node *next; linklist;linklist *creat(head,n) /*使n個(gè)人圍成一圈，并給每個(gè)人標(biāo)識(shí)號(hào)數(shù)*/ linklist *head; int n ; linklist *s,*p;

31、int i; s=(linklist * )malloc(sizeof(linklist); head=s; s-num=1; p=s; for(i=2;inum=i; p-next=s; p=s; p-next=head; return(head); /* creat */linklist * select(linklist *head, int m) linklist *p, *q; int i, t; p=head; t=1; q=p; /* q為p的前趨指針*/ p=p-next; do t=t+1 ; /*報(bào)一次數(shù)*/ if(t%m=0) printf(%4d, p-num); q-

32、next=p-next; free(p); p=q-next; else q=p; p=p-next; while(q!=p); head=p; printf(%4d,p-num); return (head); /* select */main( ) int n,m; linklist *head; printf(ninput the total number:n=); scanf(%d, &n); printf(ninput the number to call:m=); scanf(%d, &m); head=creat(head,n); head=select(head,m); pri

33、ntf(nthe last one is :%d, head-num); /* main */六、注意事項(xiàng) 1、在第i個(gè)節(jié)點(diǎn)前刪除或插入節(jié)點(diǎn)需要用指針來(lái)表示第i-1個(gè)節(jié)點(diǎn)。2、在合并鏈表時(shí)需要設(shè)置多個(gè)指針變量。3、如果不是要?jiǎng)h除的節(jié)點(diǎn)則指針后移，否則刪除該節(jié)點(diǎn)。七、思考題1、編程實(shí)現(xiàn)兩個(gè)循環(huán)單鏈表的合并。實(shí)驗(yàn)三 棧、隊(duì)列的實(shí)現(xiàn)及應(yīng)用一、實(shí)驗(yàn)?zāi)康募耙?、掌握棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際背景下靈活運(yùn)用。2、掌握棧和隊(duì)列的特點(diǎn)，即先進(jìn)后出與先進(jìn)先出的原則。3、掌握棧和隊(duì)列的基本操作實(shí)現(xiàn)方法。二、實(shí)驗(yàn)學(xué)時(shí)2學(xué)時(shí)三、實(shí)驗(yàn)任務(wù)1. 實(shí)現(xiàn)棧的順序存儲(chǔ)2. 利用棧實(shí)現(xiàn)數(shù)制轉(zhuǎn)換四、實(shí)驗(yàn)重點(diǎn)

34、、難點(diǎn)1. 進(jìn)棧、出棧棧頂指針都要改變。2. 數(shù)制轉(zhuǎn)換結(jié)束的判斷條件。五、操作要點(diǎn)（一）實(shí)現(xiàn)棧的順序存儲(chǔ)# define MAXSIZE 100 typedef int ElemType;typedef struct ElemType dataMAXSIZE; int top;SeqStack; void InitStack(SeqStack *s) s-top=0; return 1;int StackEmpty(SeqStack *s) if(s-top=0) return 1; else return 0;int StackFull(SeqStack *s) if(s-top=MAXSI

35、ZE-1) return 1; else return 0; void Push(SeqStack *s,int x) if (StackFull(s) printf(the stack is overflow!n); return 0; else s-datas-top=x; s-top+; void Display(SeqStack *s) if(s-top=0) printf(the stack is empty!n); else while(s-top!=0) printf(%d-,s-datas-top); s-top=s-top-1; ElemType Pop(SeqStack *

36、s) if(StackEmpty(s) return 0; else return s-data-s-top; ElemType StackTop(SeqStack *s) int i;if(StackEmpty(s) return 0; else i=s-top-1;return s-datai; /*返回棧頂元素的值，但不改變棧頂指針*/ main(SeqStack *p) int n,i,k,h,x1,x2,select; printf(create a empty stack!n); InitStack(p); printf(input a stack length:n); scanf

37、(%d,&n); for(i=0;i%dn,x1); display(p); break; case 4:x2=StackTop(p);printf(x2-%d,x2);break; （二）利用棧實(shí)現(xiàn)數(shù)制轉(zhuǎn)換 # define MAXSIZE 100typedef int ElemType； /*將順序棧的元素定義為整型*/typedef struct ElemType dataMAXSIZE; int top;SeqStack; void InitStack(SeqStack *s) s-top=0; return 1;int StackEmpty(SeqStack *s) if(s-top

38、=0) return 1; else return 0;int StackFull(SeqStack *s) if(s-top=m-1) return 1; else return 0; void Push(SeqStack *s,int x) if (StackFull(s) printf(the stack is overflow!n); return 0; else s-datas-top=x; s-top+; ElemType Pop(SeqStack *s) ElemType y; if(StackEmpty(s) printf(the stack is empty!n); retu

39、rn 0; else y=s-datas-top; s-top=s-top-1; return y; ElemType StackTop(SeqStack *s) if(StackEmpty(s) return 0; else return s-datas-top;void Dec_to_Ocx (int N) /* n是非負(fù)的十進(jìn)制整數(shù)，輸出等值的八進(jìn)制數(shù)*/SeqStack *S； /*定義一個(gè)順序棧*/ElemType x； Init_SeqStack(S)； /*初始化棧*/if(Ndata=x; t-lchild=creat(); t-rchild=creat(); return(t

40、);/*creat*/* 前序遍歷二叉樹t */void preorder(BiTree t) if(t!=NULL) printf(%4d,t-data); preorder(t-lchild);preorder(t-rchild); /* 中序遍歷二叉樹t */void inorder(BiTree t) if(t!=NULL) inorder(t-lchild); printf(%4d,t-data); inorder(t-rchild); /* 后序遍歷二叉樹t */void postorder(BiTree t) if(t!=NULL) postorder(t-lchild); po

41、storder(t-rchild); printf(%4d,t-data); void enqueue(BitTNode *t)if (front!=(rear+1)%M) rear=(rear+1)%M; querear=t; /*enqueue*/BitTNode * delqueue() if(front=rear)return NULL; front=(front+1)%M; return (quefront); /*delqueue*/* 按層次遍歷二叉樹t */void levorder(BiTree t) BitTNode *p; if(t!=NULL) enqueue(t);

42、while (front!=rear) p=delqueue(); printf(%4d,p-data); if(p-lchild!=NULL) enqueue(p-lchild); if(p-rchild!=NULL) enqueue(p-rchild); /* levorder */main()BitTNode *root; root=creat();printf(n按先序遍歷次序生成的二叉樹); printf(n前序遍歷二叉樹); preorder(root);printf(n中序遍歷二叉樹); inorder(root);printf(n后序遍歷二叉樹); postorder(root); printf(