數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書(1)課案

1、數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書鄭州輕工業(yè)學(xué)院2016.02.20實驗01順序表的基本操作 3實驗02單鏈表的基本操作 11實驗03棧的基本操作 19實驗04隊列的基本操作 21實驗05二叉樹的基本操作 23實驗06哈夫曼編碼 24實驗07圖的兩種存儲和遍歷 26實驗08最小生成樹、拓撲排序和最短路徑 .29實驗09二叉排序樹的基本操作 31實驗10哈希表的生成 32實驗11常用的內(nèi)部排序算法 34附：實驗報告模板 36數(shù)據(jù)結(jié)構(gòu)試驗指導(dǎo)書數(shù)據(jù)結(jié)構(gòu)是計算機相關(guān)專業(yè)的一門核心基礎(chǔ)課程，是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系 統(tǒng)程序和大型應(yīng)用程序開發(fā)的重要基礎(chǔ)，也是很多高?？佳袑I(yè)課之一。它主要介紹線性結(jié)構(gòu)、樹

2、型結(jié) 構(gòu)、圖狀結(jié)構(gòu)三種邏輯結(jié)構(gòu)的特點和在計算機內(nèi)的存儲方法，并在此基礎(chǔ)上介紹一些典型算法及其時、空 效率分析。這門課程的主要任務(wù)是研究數(shù)據(jù)的邏輯關(guān)系以及這種邏輯關(guān)系在計算機中的表示、存儲和運算,培養(yǎng)學(xué)生能夠設(shè)計有效表達和簡化算法的數(shù)據(jù)結(jié)構(gòu)，從而提高其程序設(shè)計能力。通過學(xué)習(xí)，要求學(xué)生能夠 掌握各種數(shù)據(jù)結(jié)構(gòu)的特點、存儲表示和典型算法的設(shè)計思想及程序?qū)崿F(xiàn)，能夠根據(jù)實際問題選取合適的數(shù) 據(jù)表達和存儲方案，設(shè)計出簡潔、高效、實用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開發(fā)打下良好的基礎(chǔ)。另 外本課程的學(xué)習(xí)過程也是進行復(fù)雜程序設(shè)計的訓(xùn)練過程，通過算法設(shè)計和上機實踐的訓(xùn)練，能夠培養(yǎng)學(xué)生 的數(shù)據(jù)抽象能力和程序設(shè)計能力。

3、學(xué)習(xí)這門課程，習(xí)題和實驗是兩個關(guān)鍵環(huán)節(jié)。學(xué)生理解算法，上機實驗 是最佳的途徑之一。因此，實驗環(huán)節(jié)的好壞是學(xué)生能否學(xué)好數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。為了更好地配合學(xué)生實 驗，特編寫實驗指導(dǎo)書。一、實驗?zāi)康谋菊n程實驗主要是為了原理和應(yīng)用的結(jié)合，通過實驗一方面使學(xué)生更好的理解數(shù)據(jù)結(jié)構(gòu)的概念和常用 的幾種數(shù)據(jù)結(jié)構(gòu)在計算機中的存儲和實現(xiàn)的方法，加強學(xué)生動手能力；另一方面培養(yǎng)學(xué)生從實際問題中抽 象出對應(yīng)的抽象數(shù)據(jù)類型，進而找到合適的計算機存儲方法和算法，為以后課程的學(xué)習(xí)、大型軟件的開發(fā)、實際工程問題打下良好的軟件開發(fā)基礎(chǔ)。二、實驗要求1、每次實驗前學(xué)生必須根據(jù)實驗內(nèi)容認真準備實驗程序及調(diào)試時所需的輸入數(shù)據(jù)。2、在指導(dǎo)教

4、師的幫助下能夠完成實驗內(nèi)容，得出正確的實驗結(jié)果。3、實驗結(jié)束后總結(jié)實驗內(nèi)容、書寫實驗報告。4、遵守實驗室規(guī)章制度、不缺席、按時上、下機。5、實驗學(xué)時內(nèi)必須做數(shù)據(jù)結(jié)構(gòu)的有關(guān)內(nèi)容，不允許上網(wǎng)聊天或玩游戲，如發(fā)現(xiàn)上述現(xiàn)象，取消本次 上機資格，平時成績扣 10分。6、 實驗報告有一次不合格，扣5分，兩次以上不合格者，平時成績以零分記。三、實驗環(huán)境VC+6.0或其他C+相關(guān)的編譯環(huán)境。四、說明1、本實驗的所有算法中元素類型應(yīng)根據(jù)實際需要合理選擇。2、實驗題目中帶*者為較高要求，學(xué)生可自選；其余部分為基本內(nèi)容，應(yīng)盡量完成（至少完成 70%，否則實驗不合格）。3、數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學(xué)考試的專業(yè)

5、課之一，希望有志于考研的學(xué)生能夠在學(xué)習(xí)過 程中注意各種算法的理解，以便為考研做一定的準備。4、好的算法決定了好的程序，要有效地實現(xiàn)算法，就需要設(shè)計能夠有效表達和簡化算法的數(shù)據(jù)結(jié)構(gòu)， 因此數(shù)據(jù)結(jié)構(gòu)是有效進行程序設(shè)計的基礎(chǔ)，是每個程序員的必修課。五、實驗報告的書寫要求1、明確實驗的目的及要求。2、記錄實驗的輸入數(shù)據(jù)和輸出結(jié)果。3、說明實驗中出現(xiàn)的問題和解決過程。4、寫出實驗的體會和實驗過程中沒能解決的問題。5、 實驗程序請構(gòu)建為多文件程序，每一個算法對應(yīng)的函數(shù)原型聲明存放在頭文件*.h中，對應(yīng)的函數(shù)實現(xiàn)存放在源文件*.c中；main（）函數(shù)存放在另一個源文件中，該文件包含頭文件*.h即可。六、成績

6、考評辦法1、期末考試占70分，閉卷。2、 平時考評占30分。其中實驗環(huán)節(jié)占 20分（實驗準備、上機、報告、驗收等）；平時占10分（出 勤、作業(yè)、測驗等）。七、參考書目1、 數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴蔚敏等 清華大學(xué)出版社2、 數(shù)據(jù)結(jié)構(gòu)題集（C語言版） 嚴蔚敏等 清華大學(xué)出版社3、數(shù)據(jù)結(jié)構(gòu)與算法分析一一 C語言描述，Mark Allen Weiss 著，機械工業(yè)出版社， 201239實驗01順序表的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：順序表的插入、刪除及應(yīng)用。目的要求：1 掌握順序存儲結(jié)構(gòu)的特點。2 掌握順序存儲結(jié)構(gòu)的常見算法。實驗內(nèi)容：編寫一個完整的程序，實現(xiàn)順序表的生成、插入、刪除、

7、輸出等基本運算。(1) 建立一個順序表，含有 n個數(shù)據(jù)元素。(2) 輸出順序表。(3) 在順序表中刪除值為 x的結(jié)點或者刪除給定位置 i的結(jié)點。(4) 實現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前，即表的前面為奇數(shù)，后面為偶數(shù)。(5) 輸入整型元素序列，利用有序表插入算法建立一個有序表。(6) *利用算法5建立兩個非遞減有序表 A和B，并把它們合并成一個非遞減有序表C。(7) 在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。(8) *綜合訓(xùn)練：利用順序表實現(xiàn)一個班級學(xué)生信息管理(數(shù)據(jù)錄入、插入、刪除、排序、查找等)。實驗說明：1 請構(gòu)建多文件程序，算法1至算法6對應(yīng)的函數(shù)原型聲明存放在頭文件SqList.

8、h中，對應(yīng)的函數(shù)實現(xiàn)存放在源文件 SqList.c中；main()函數(shù)存放在另一個源文件中，該文件包含頭文件SqList.h即可。2 類型定義#define MAXSIZE 100表中元素的最大個數(shù)typedef int ElemType;/ 元素類型typedef structElemType *elem; / 線性表in t le ngth; 表的實際長度in t listsize;/當(dāng)前分配的存儲容量SqList;順序表的類型名3 建立順序表時可利用隨機函數(shù)自動產(chǎn)生數(shù)據(jù)。注意問題：1、插入、刪除時元素的移動原因、方向及先后順序。2、理解函數(shù)形參與實參的傳遞關(guān)系。部分源代碼：DS.h#i

9、nclude #i nclude #in elude #in elude #defi ne TRUE 1#defi ne FALSE 0#defi ne OK 1#defi ne ERROR 0typedef int Status;SqList.h#ifndef SQLIST_H_INCLUDED#defi ne SQLIST_H_INCLUDED#i nclude DS.htypedef int ElemType;#defi ne LIST_INIT_SIZE 50typedef structElemType *elem;int len gth;int listsize;SqList;voi

10、d menu();Status InitList_Sq(SqList &L);/*初始化順序表 */Status CreateList_Sq(SqList &L);/*建立順序表 */void PrintList_Sq(SqList L);/*輸出順序表 */Status DeleteList_Sq(SqList &L,int i,ElemType &e);/*刪除第 i 個元素 */Status DeleteListX_Sq(SqList &L,ElemType x);/*刪除值為 x 的元素 */Status AdjustList_Sq(SqList & L);/*奇數(shù)排在偶數(shù)之前 */S

11、tatus OrderList_sq(SqList & L, i nt n);/*插入法生成遞增有序表*/void MergeList_Sq(SqList La, SqList Lb, SqList &Lc );/*兩個非遞減有序表 A 和 B，并把它們合并成一個非遞減有序表C*/#en dif / SQLIST_H_INCLUDEDSqList.cpp#i nclude SqList.hvoid menu()prin tf(ttt順序表基本操作nn);prin tf(ttt1.建立順序表 n)prin tf(ttt2.遍歷順序表 n)printf(ttt3.刪除第 i 個元素n);print

12、f(ttt4.刪除值為 x 的元素 n);printf(ttt5.奇 數(shù)排在 偶數(shù)之 前n);prin tf(ttt6.插入法生成遞增有序表n);printf(ttt7.兩個非遞減有序表La和Lb合并成非遞減有序表Lcn);printf(ttt0.退出 nn);/*初始化順序表*/Status In itList_Sq(SqList &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW);L.le ngth=O;L.listsize=LIST_INIT_SIZE;return

13、 OK;/*建立順序表*/Status CreateList_Sq(SqList &L)int n, i;printf(請輸入順序表長度：);scanf(%d, &n);if(n LIST_INIT_SIZE & InitList_Sq(L)printf(請輸入%d個元素：”,n);for(i = 0; i n; i+)scanf(%d, &L.elemi);L.len gth = n;return OK;elsereturn ERROR;/*輸出順序表*/void Prin tList_Sq(SqList L)int i;printf(順序表中元素為:n);for(i = 0; i L.le

14、n gth; i+)prin tf(%d , L.elemi);prin tf(n);/*刪除第i個元素*/Status DeleteList_Sq(SqList &L,int i,ElemType &e) ElemType *p, *q;if( (iL.length) return ERROR;p = & (L.elemi_1);e = *p;q = L.elem+L.le ngth-1;for(+p; p = q; +p) *(p-1) = *p;-Len gth;return OK;/*刪除值為x的元素，刪除成功返回OK,刪除失敗返回ERROR*/Status DeleteListX_S

15、q(SqList &L,ElemType x)ElemType *p, *q;/*請補充完整代碼*/*奇數(shù)排在偶數(shù)之前*/Status AdjustList_Sq(SqList &L)ElemType *p, *q;int temp;OK，失敗返回ERROR*/*請補充完整代碼*/*插入法生成遞增有序表，有序表生成成功返回Status OrderList_sq(SqList & L, i nt n)int i, j, x; /*x表示每次待插入的元素*/*請補充完整代碼*/*兩個非遞減有序表 A和B，并把它們合并成一個非遞減有序表C*/void MergeList_Sq(SqList La,

16、SqList Lb, SqList &Lc )ElemType *pa, *pb, *pc, *pa_last, *pb_last;pa = La.elem; pb = Lb.elem;Lc.li stsize = Lcen gth = La.len gth+Lben gth;pc = Lc.elem = (ElemType *)malloc(Lc.listsize * sizeof(ElemType);if (!Lc.elem) exit (OVERFLOW);pa_last = La.elem + La.len gth - 1; pb_last = Lb.elem + Lb.len gth

17、 - 1;while (pa = pa_last & pb = pb_last) if (*pa = *pb) *pc+ = *pa+; else *pc+ = *pb+;while(pa = pa_last) *pc+ = *pa+; while(pb = pb_last) *pc+ = *pb+;main .cpp#i nclude SqList.hint mai n()int choice, n, i, x;SqList L, La, Lb, Lc;while(1)men u();printf(”選擇你的操作：);sca nf(%d,&choice);switch(choice)case

18、 1:if(CreateList_Sq(L)printf(順序表創(chuàng)建成功n); elseprintf(順序表創(chuàng)建失敗n); break;case 2:Prin tList_Sq(L);break;case 3:printf(請輸入刪除元素的位置：); scan f(%d, & i);if(DeleteList_Sq(L, i, x) printf(被刪除元素值為：dn,x);elseprintf(刪除失敗 n);break;case 4:printf(請輸入刪除元素值：”)； scan f(%d, &x);if(DeleteListX_Sq(L, x)printf(刪除成功 n);elsepr

19、intf(刪除失敗 n);Prin tList_Sq(L);break;case 5:AdjustList_Sq(L);printf(新鏈表為:n);Prin tList_Sq(L);break;case 6:printf(請輸入順序表長度：);scan f(%d, &n);if(OrderList_sq(L, n)printf(值有序順序表為:n);Prin tList_Sq(L);elseprintf(順序表創(chuàng)建失敗n);break;case 7:printf(請輸入順序表La的長度：);scan f(%d, &n);OrderList_sq(La, n);printf(請輸入順序表Lb的

20、長度：); scan f(%d, &n);OrderList_sq(Lb, n);MergeList_Sq(La, Lb, Lc);printf(合并后的順序表為：n);Prin tList_Sq(Lc);break;case 0:return 0;default:printf(輸入錯誤，請重新輸入n);實驗02單鏈表的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：單鏈表的插入、刪除及應(yīng)用。目的要求：1 掌握單鏈表的存儲特點及其實現(xiàn)。2 掌握單鏈表的插入、刪除算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。實驗內(nèi)容：編寫一個完整的程序，實現(xiàn)單鏈表的生成、插入、刪除、輸出等基本操作。(1 )隨機產(chǎn)生或鍵盤輸入一組

21、元素，建立一個帶頭結(jié)點的單向鏈表(無序)。(2) 計算單鏈表的長度，遍歷單鏈表。(3) 把單鏈表中的元素逆置(不允許申請新的結(jié)點空間)。(4) 在單鏈表中刪除所有值為偶數(shù)的元素結(jié)點。(5) 編寫在非遞減有序單鏈表中插入一個元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個非遞減有序單鏈表。(6) *利用算法5建立兩個非遞減有序單鏈表，然后合并成一個非遞增有序鏈表。(7) *利用算法5建立兩個非遞減有序單鏈表，然后合并成一個非遞減有序鏈表。(8) *利用算法1建立的鏈表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為 偶數(shù)(盡量利用已知的存儲空間)。(9) *采用單鏈表實現(xiàn)一元多項式的存

22、儲并實現(xiàn)兩個多項式相加并輸出結(jié)果。(10) 在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。(11) *綜合訓(xùn)練：1 )利用鏈表實現(xiàn)一個班級學(xué)生信息管理(數(shù)據(jù)錄入、插入、刪除、排序、查找等，并能夠?qū)崿F(xiàn)將數(shù)據(jù)存儲到文件中)2)約瑟夫環(huán)問題：設(shè)有 n個人圍坐在圓桌周圍，從某個位置開始編號為1, 2, 3,，n,坐在編號為1的位置上的人從1開始報數(shù)，數(shù)到 m的人便出列；下一個(第 m+1個)人又從1開始報數(shù)，數(shù)到 m 的人便是第二個出列的人；如此重復(fù)下去，直到最后一個人出列為止，得到一個出列的編號順序。例如，當(dāng)n=8, m=4時，若從第一個位置數(shù)起，則出列的次序為4, 8, 5, 2, 1, 3,

23、7, 6。試編寫程序確定出列的順序。要求用不帶頭結(jié)點的單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打 印出個人編號。實驗說明：1 類型定義typedef int ElemType;/ 元素類型typedef struct nodeElemType data;struct node *n ext;Li nkNode, *Li nkList;2為了算法實現(xiàn)簡單，建議采用帶頭結(jié)點的單鏈表。注意問題：1 .重點理解鏈式存儲的特點及指針的含義。2 .注意比較順序存儲與鏈式存儲的各自特點。3 注意比較帶頭結(jié)點、無頭結(jié)點鏈表實現(xiàn)插入、刪除算法時的區(qū)別。4 單鏈表的操作是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，一定要注意對這部分

24、常見算法的理解。部分源代碼：DS.h#i nclude #i nclude #in clude #in clude #defi ne TRUE 1#define FALSE 0#defi ne OK 1#defi ne ERROR 0 typedef int Status;Lin kList.h#i nclude DS.h typedef int Elemtype;typedef struct NodeElemtype data; struct Node *n ext; Lno de,*Li nkList;void menu();/*菜單*/Status Init_Linklist(LinkL

25、ist &L);/*初始化空表*/Status Creat_L in klist(L in kList & L);/*尾插法建立單鏈表*/void Disp_L in klist(L in kList L);/*單鏈表遍歷*/int length_Linklist(LinkList L);/*計算單鏈表長度*/void Reverse_L in klist(L in kList L);/*單鏈表逆置*/void DelEve n_Lin klist(L in kList L);/*刪除值為偶數(shù)的結(jié)點*/Status Insert_Linklist(LinkList L, int x);/*在有

26、序單鏈表L中插入兀素x,鏈表仍然有序*/Status CreatOrder_Linklist(LinkList &L);/*創(chuàng)建非遞減有序單鏈表*/void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc);/*兩個非遞減有序單鏈表La 和 Lb合并成一個非遞增有序鏈表Lc*/void MergeAscend_Linklist(LinkList La, LinkList Lb, LinkList &Lc); /*兩個非遞減有序單鏈表La 和 Lb 合并成一個非遞減有序鏈表Lc*/void Split_Linklist(L

27、inkList La, LinkList &Lb); 偶數(shù)*/*鏈表La按值分解成兩個鏈表，La全部為奇數(shù)，Lb全部為Lin kList.cpp#in clude Li nkList.h void menu()prin tf(ttt單鏈表基本操作nn);prin tf(ttt1.建立單鏈表 n);prin tf(ttt2.遍歷單鏈表 n);prin tf(ttt3.計算鏈表長度n);prin tf(ttt4.鏈表逆置 n);prin tf(ttt5.刪除偶數(shù)節(jié)點n);printf(ttt6.生成值有序單鏈表n”)；printf(ttt7.合并生成降序鏈表n);printf(ttt8.合并生成升

28、序鏈表n);printf(ttt9.分解鏈 表n);printf(ttt0.退出 nn);/*初始化空表*/Status In it_Li nklist(L in kList &L)L=(Li nkList)malloc(sizeof(L no de);if(!L) return ERROR;L- next=NULL;return OK;/*尾插法建立單鏈表*/Status Creat_Li nklist(L in kList &L)int兀Lin kList p,rear;In it_L in klist(L);rear = L;printf(輸入-1表示輸入結(jié)束n);while(sca n

29、f(%d, &x),x != -1)p = (Lin kList)malloc(sizeof(L no de); if(!p) return ERROR;p-data = x;rear-next = p;rear = p;rear-n ext = NULL;return OK;/*單鏈表遍歷*/void Disp_L in klist(L in kList L) Lin kList p;p = L_n ext;while(p)printf(%d , p-data); p = p_n ext;prin tf(n);/*計算單鏈表長度*/in t le ngth_Li nklist(Li nkLi

30、st L)int count = 0;/*count表示單鏈表長度 */Lin kList p;/*請補充完整代碼*/retur n count;/*單鏈表逆置*/void Reverse_L in klist(L in kList L) Lin kList p, q ;/*請補充完整代碼*/ /*刪除值為偶數(shù)的結(jié)點*/void DelEven_Linklist(LinkList L)Lin kList p, q;/*請補充完整代碼*/ERROR*/*在有序單鏈表中插入元素，鏈表仍然有序，插入成功返回OK，插入失敗返回Status Insert_Linklist(LinkList L, int

31、 x)/*請補充完整代碼*/*創(chuàng)建非遞減有序單鏈表，創(chuàng)建成功返回OK,創(chuàng)建失敗返回ERROR*/Status CreatOrder_Li nklist(L in kList &L)/*請補充完整代碼*/*兩個非遞減有序單鏈表La和Lb合并成一個非遞增有序鏈表Lc*/void MergeDesce nd_Lin klist(L in kList La, Lin kList Lb, Lin kList &Lc)/*請補充完整代碼*/*兩個非遞減有序單鏈表La和Lb合并成一個非遞減有序鏈表Lc*/void MergeAsce nd_Lin klist(L in kList La, Lin kList

32、 Lb, Lin kList &Lc)Lin kList pa, pb, pc;pa = La-n ext;pb = Lb-n ext;pc = Lc = La;while(pa & pb)if(pa-data data)pc-n ext = pa; pc = pa; pa = pa-n ext;elsepc-n ext = pb; pc = pb; pb = pb-n ext;pc- n ext = pa ? pa : pb;free(Lb); /*鏈表La按值分解成兩個鏈表，La全部為奇數(shù)，Lb全部為偶數(shù)*/ void Split_Linklist(LinkList La, LinkLis

33、t &Lb)/*請補充完整代碼*/main .cpp#in elude Li nkList.h int mai n()int choice, le ngth;Lin kList L, La, Lb, Lc;while(1)men u();printf(”選擇你的操作：);sca nf(%d,&choice);switch(choice)case 1:if(Creat_Li nklist(L)printf(單鏈表創(chuàng)建成功n);elseprintf(單鏈表創(chuàng)建失敗n); break;case 2:Disp_Li nklist(L);break;case 3:len gth = len gth_L

34、in klist(L);printf(單鏈表長度為:%dn,le ngth); break;case 4:Reverse_Li nklist(L);printf(逆置后的鏈表為：n);Disp_Li nklist(L); break;case 5:DelEven_Li nklist(L);printf(新鏈表為:n);Disp_Li nklist(L); break;case 6:if(CreatOrder_Li nklist(L)printf(值有序鏈表為:n);Disp_Li nklist(L);elseprintf(單鏈表創(chuàng)建失敗n);break;case 7:CreatOrder_L

35、in klist(La);CreatOrder_L in klist(Lb);MergeDesce nd_Lin klist(La, Lb, Lc);printf(合并后的新鏈表為:n);Disp_Li nklist(Lc); break;case 8:CreatOrder_L in klist(La);CreatOrder_L in klist(Lb);MergeAsce nd_Lin klist(La, Lb, Lc);printf(合并后的新鏈表為:n);Disp_Li nklist(Lc); break;case 9:Creat_L in klist(L);Split_Li nklis

36、t(L, Lb);printf(分裂后的新鏈表為：n);Disp_Li nklist(L);Disp_Li nklist(Lb);break;case 0:return 0;default:printf(輸入錯誤，請重新輸入n);實驗03棧的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：順序棧、鏈棧，入棧、出棧。目的要求：1 掌握棧的思想及其存儲實現(xiàn)。2 掌握棧的常見算法的程序?qū)崿F(xiàn)。實驗內(nèi)容：(1 )采用順序存儲實現(xiàn)棧的初始化、入棧、出棧操作。(2) 采用鏈式存儲實現(xiàn)棧的初始化、入棧、出棧操作。(3) 在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。(4) *綜合訓(xùn)練：1) 堆棧操作合法性：

37、假設(shè)以 S和X分別表示入棧和出棧操作。如果根據(jù)一個僅由S和X構(gòu)成的序 列，對一個空堆棧進行操作，相應(yīng)操作均可行(如沒有出現(xiàn)刪除時?？?且最后狀態(tài)也是?？?，則稱該序列是合法的堆棧操作序列。請編寫程序，輸入S和X序列，判斷該序列是否合法。2) 括號匹配檢驗：假設(shè)表達式中允許包括兩種括號：圓括號和方括號，其嵌套的順序隨意，即() 或()等為正確的格式，()或()等均為不正確格式。輸入一個表達式，判斷其中的括號是否能正確匹配。3) 表達式轉(zhuǎn)換：算術(shù)表達式有前綴表示法、中綴表示法和后綴表示法等形式。日常使用的算術(shù)表達式是采用中綴表示法，即二元運算符位于兩個運算數(shù)中間。請設(shè)計程序?qū)⒅芯Y表達式轉(zhuǎn)換為后綴表達

38、式。輸入在一行中給出不含空格的中綴表達式，可包含+、-、*、以及左右括號()，表達式不超過20個字符。在一行中輸出轉(zhuǎn)換后的后綴表達式，要求不同對象(運算數(shù)、運算符號) 之間以空格分隔，但結(jié)尾不得有多余空格。實驗說明：1 類型定義順序棧示例#define MAX 100 / 棧的最大值typedef struct SElemType *base ;SElemType *top ;int stacksize ;SqStack ;鏈棧示例typedef int ElemType; / 元素類型typedef struct snodeSElemType data;struct snode *n ext

39、;StackNode, *Li nkStack;2 算法4的每個子功能盡可能寫成函數(shù)形式。注意問題：1 重點理解棧的算法思想，能夠根據(jù)實際情況選擇合適的存儲結(jié)構(gòu)。2 注意算法4的各個函數(shù)之間值的傳遞情況。3 棧的算法是后續(xù)實驗的基礎(chǔ)（樹、圖、查找、排序等）。實驗04隊列的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：循環(huán)隊列、鏈隊列，入隊、出隊。目的要求：1 掌握隊列的思想及其存儲實現(xiàn)。2 掌握隊列的常見算法的程序?qū)崿F(xiàn)。實驗內(nèi)容：(1 )采用順序存儲實現(xiàn)循環(huán)隊列的初始化、入隊、出隊操作。(2) 采用鏈式存儲實現(xiàn)隊列的初始化、入隊、出隊操作。(3) 在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算

40、法。(4) *綜合訓(xùn)練：銀行排隊系統(tǒng)模擬：請用一個隊列來模擬銀行排隊系統(tǒng)，隊列中存儲序號。請設(shè)置一個菜單，包括叫 號和排號兩個選項。若選擇叫號，則輸出并刪除隊首元素；若選擇排號，則順序生成一個序號，加 入隊列，并輸出該序號和前面有多少人等候。實驗說明：1 類型定義循環(huán)隊列示例#define MAXQSIZE 100 /隊列的最大長度typedef struct QElemType *base ;int front ;int rear;SqQueue ;鏈隊列示例typedef struct QNodeQElemType data;struct QNode *n ext;QNode, *Queu

41、ePtr;typedef struct QueuePtr front;QueuePtr rear;Lin kQueue;注意問題：1 重點理解隊列的算法思想，能夠根據(jù)實際情況選擇合適的存儲結(jié)構(gòu)。2 隊列的算法是后續(xù)實驗的基礎(chǔ)（樹、圖、查找、排序等）。實驗05二叉樹的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：二叉樹的存儲、建立、遍歷及其應(yīng)用。目的要求：i.掌握二叉樹的存儲實現(xiàn)。2 掌握二叉樹的遍歷思想。3 掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。實驗內(nèi)容:(1)從鍵盤上輸入數(shù)據(jù)，建立二叉鏈表。(2)前序遍歷、中序遍歷、后序遍歷二叉樹:遞歸算法。(3)前序遍歷、中序遍歷、后序遍歷二叉樹:非遞歸算法。

42、(4)借助隊列實現(xiàn)二叉樹的層次遍歷。(5)在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。(6)*綜合訓(xùn)練：家族關(guān)系查詢系統(tǒng)：建立家族關(guān)系數(shù)據(jù)庫，可以實現(xiàn)家族成員的添加，可以查詢家族成員的雙親、祖 先、兄弟、孩子和后代等信息。實驗說明：1 .類型定義/二叉鏈表存儲#define TEIemType char元素類型typedef struct BiTNodeTEIemType data;struct BiTNode *lchild, *rchild; BiTNode, *BiTree;注意問題：1 注意理解遞歸算法的執(zhí)行步驟，重點理解如何利用棧結(jié)構(gòu)實現(xiàn)非遞歸算法。2 注意字符類型數(shù)據(jù)在輸入時的

43、處理。實驗06哈夫曼編碼實驗學(xué)時：4學(xué)時實驗類型：綜合型實驗背景知識：二叉樹的應(yīng)用、哈夫曼樹。目的要求：掌握哈夫曼樹和哈夫曼編碼的基本思想和算法的程序?qū)崿F(xiàn)。實驗內(nèi)容：(1 )修理牧場：農(nóng)夫要修理牧場的一段柵欄，他測量了柵欄，發(fā)現(xiàn)需要N塊木頭，每塊木頭長度為整數(shù)Li個長度單位，于是他購買了一條很長的、能鋸成N塊的木頭，即該木頭的長度是Li的總和。但是農(nóng)夫自己沒有鋸子，請人鋸木頭的酬金跟這段木頭的長度成正比。為簡單起見，不妨就設(shè)酬金等于所鋸木頭的長度。例如，要將長度為20的木頭鋸成長度為8、7和5的三段，第一次鋸木頭花費20,將木頭鋸成12和8;第二次鋸木頭花費 12，將長度為12的木頭鋸成7和5

44、，總花費為32。 如果第一次將木頭鋸成 15和5，則第二次鋸木頭花費 15，總花費為35 (大于32 )。請編寫程序幫助農(nóng)夫計算將木頭鋸成N塊的最少花費。首先輸入一個正整數(shù)N ( NW 1(4)，表示要將木頭鋸成 N塊。接著給出N個正整數(shù)Li (Li 50 ,表示每段木塊的長度。輸出一個整數(shù)，即將木頭鋸成N塊的最少花費。例如：輸入：84 5 1 2 1 3 1 1輸出：49* (2)壓縮軟件：給定一篇文章，只含有英文大小寫字母和空格，以.txt格式存儲，統(tǒng)計該文件中各種字符的頻率，對各字符進行Huffman編碼，將該文件翻譯成Huffman編碼文件，再將 Huffman編碼文件翻譯成源文件。實

45、驗說明：1 參考類型定義雙親孩子表示法typedef struct un sig ned intweight;un sig ned intpare nt, Ichild, rchild; HTNode, *Huffma nTree;/動態(tài)分配數(shù)組存儲哈夫曼樹typedef char * * Huffma nCode;/動態(tài)分配數(shù)組存儲哈夫曼編碼表注意問題：1 遞歸算法的靈活應(yīng)用。2 多級指針的使用。實驗07圖的兩種存儲和遍歷實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：圖的存儲、遍歷及其應(yīng)用。目的要求：1 掌握圖的存儲思想及其存儲實現(xiàn)。2 掌握圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。實驗內(nèi)容：(

46、1 )鍵盤輸入數(shù)據(jù)，分別建立一個有向圖和一個無向圖的鄰接表。(2) 輸出該鄰接表。(3) 在有向圖的鄰接表的基礎(chǔ)上計算各頂點的度，并輸出。(4) 采用鄰接表存儲實現(xiàn)無向圖的深度優(yōu)先遍歷。(5) 采用鄰接表存儲實現(xiàn)無向圖的廣度優(yōu)先遍歷。(6) 在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。(7) *綜合訓(xùn)練地下迷宮探索：假設(shè)有一個地下通道迷宮，它的通道都是直的，而通道所有交叉點(包括通道的端輸入格式:輸入第一行給出三個正整數(shù)，分別表示地下迷宮的節(jié)點數(shù)N ( 1NK 1000 ,表示通道所有交叉點和端點)、邊數(shù) M (M 3000,表示通道數(shù))和探索起始節(jié)點編號 S (節(jié)點從1到N編號)。隨后的

47、 M行對應(yīng)M條邊(通道)，每行給出一對正整數(shù)，分別是該條邊直接連通的兩個節(jié)點的編號。輸出格式：若可以點亮所有節(jié)點的燈，則輸出從S開始并以S結(jié)束的包含所有節(jié)點的序列，序列中相鄰的節(jié)點一定有邊(通道)；否則雖然不能點亮所有節(jié)點的燈，但還是輸出點亮部分燈的節(jié)點序列，最后輸 出0,此時表示迷宮不是連通圖。由于深度優(yōu)先遍歷的節(jié)點序列是不唯一的，為了使得輸出具有唯一的結(jié)果，我們約定以節(jié)點小 編號優(yōu)先的次序訪問（點燈）。在點亮所有可以點亮的燈后，以原路返回的方式回到起點。輸入樣例：6 8 11 22 33 44 55 66 43 61 5輸出樣例：1 2 3 4 5 6 5 4 3 2 1實驗說明：1 類型

48、定義（鄰接表存儲）#define MAX_VERTEX_NUM 20/ 頂點最大個數(shù)typedef struct ArcNodeintadjvex;struct ArcNode *n extarc;intweight;邊的權(quán)值A(chǔ)rcNode;表結(jié)點#define VertexType int / 頂點元素類型typedef struct VNodeVertexType data;ArcNode *firstarc;VNode, AdjListMAX_VERTEX_NUM; /typedef structAdjList vertices;in t vex num, arcnum; / 頂點的實際

49、數(shù)，邊的實際數(shù)in t kin d;ALGraph;2 上述類型定義可以根據(jù)實際情況適當(dāng)調(diào)整。3 算法4、5分別利用棧、隊列實現(xiàn)非遞歸算法。注意問題：1 注意理解各算法實現(xiàn)時所采用的存儲結(jié)構(gòu)。2 注意區(qū)別正、逆鄰接。實驗08最小生成樹、拓撲排序和最短路徑實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：圖的存儲、遍歷及其應(yīng)用。目的要求：掌握圖的常見應(yīng)用算法的思想及其程序?qū)崿F(xiàn)。實驗內(nèi)容：（1）鍵盤輸入數(shù)據(jù)，分別建立一個有向圖的鄰接表和一個無向圖的鄰接矩陣。（2）輸出該鄰接表和鄰接矩陣。（3 ）以有向圖的鄰接表為基礎(chǔ)輸出它的拓撲排序序列。（4） 以無向圖的鄰接矩陣為基礎(chǔ)實現(xiàn)最小生成樹的PRIM算法。（5）

50、以有向圖的鄰接矩陣為基礎(chǔ)實現(xiàn)Dijkstra 算法輸出單源點到其它頂點的最短路徑。（6）在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。（7）*綜合訓(xùn)練：校園導(dǎo)航1）問題描述：在給出校園各主要建筑的名稱信息及有路線連通的建筑之間的距離（或行進時間）的基礎(chǔ)上，利用校 園導(dǎo)航系統(tǒng)計算出給定的起點到終點之間距離最近（或行進時間最短）的行進路線。2 ）設(shè)計要求：文件讀入或鍵盤方式讀入校園主要建筑信息及建筑間的距離（或行進時間）信息。創(chuàng) 建完地圖后，以文件形式保存，以免重復(fù)創(chuàng)建。計算出給定的起點到終點之間距離最近（或行進時間最 短）的行進路線，并輸出該路線（包括經(jīng)過哪些建筑）及其總距離（或總行進時間）。

51、實驗說明：1 類型定義鄰接表存儲見實驗 07鄰接矩陣存儲示例#define MAX_VERTEX_NUM 20/ 頂點最大個數(shù)typedef enum DG, DN, UDG, UDN GraphKind;typedef struct ArcCellVRType adj;intweight; /邊的權(quán)值A(chǔ)rcCell; AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;intvexnum, arcn um; / 頂點的實際數(shù)，邊的實際數(shù)GraphKind kind;MGraph;注意問題：注意理解各算法實現(xiàn)時所采用的存儲結(jié)構(gòu)。實驗09二叉排序樹的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：樹表查找。目的要求：掌握二叉排序樹、AVL樹的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)。實驗內(nèi)容：（1）隨機產(chǎn)生一組關(guān)鍵字，利用二叉排序樹的插入算法建立二叉排序樹，然后刪除某一指定關(guān)鍵字元素。（2）*建立AVL樹并實現(xiàn)刪除某一指定關(guān)鍵字元素。（3）*綜合訓(xùn)練：樹種統(tǒng)計隨著衛(wèi)星成像技術(shù)的應(yīng)用，自然資源研究機構(gòu)可以識別每一棵樹的