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

2、構(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è)計能力。學(xué)習(xí)這門課程，習(xí)

3、題和實驗是兩個關(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)容認真準(zhǔn)備實驗程序及調(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è)課之一，希望有志于考研的學(xué)

5、生能夠在學(xué)習(xí)過程中注意各種算法的理解，以便為考研做一定的準(zhǔn)備。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即可。六、成績考評辦法1、期末考試占70分，

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

7、含有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.h中，對應(yīng)的函數(shù)實現(xiàn)存放在源文件SqList.c

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

9、h>#include <stdlib.h>#include <string.h>#include <math.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;SqList.h#ifndef SQLIST_H_INCLUDED#define SQLIST_H_INCLUDED#include "DS.h"typedef int ElemType;typedef struct ElemType *elem; int length;

10、int listsize;SqList;void menu();Status InitList_Sq(SqList &L, int n);/*初始化順序表*/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

11、 AdjustList_Sq(SqList &L);/*奇數(shù)排在偶數(shù)之前*/Status OrderList_sq(SqList &L, int n);/*插入法生成遞增有序表*/void MergeList_Sq(SqList La, SqList Lb, SqList &Lc );/*兩個非遞減有序表A和B，并把它們合并成一個非遞減有序表C*/#endif / SQLIST_H_INCLUDEDSqList.cpp#include "SqList.h"void menu() printf("ttt 順序表基本操作nn"); p

12、rintf("ttt1.建 立 順 序 表n"); printf("ttt2.遍 歷 順 序 表n"); printf("ttt3.刪 除 第 i 個 元 素n"); printf("ttt4.刪 除 值 為 x 的 元 素n"); printf("ttt5.奇 數(shù) 排 在 偶 數(shù) 之 前n"); printf("ttt6.插 入 法 生 成 遞 增 有 序 表n"); printf("ttt7.兩個非遞減有序表La和Lb合并成非遞減有序表Lcn"); p

13、rintf("ttt0.退 出nn");/*初始化順序表*/Status InitList_Sq(SqList &L, int n) L.elem=(ElemType*)malloc(n*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=n; return OK;/*建立順序表*/Status CreateList_Sq(SqList &L) int n, i; printf("請輸入順序表長度："); scanf("%d", &a

14、mp;n); if(InitList_Sq(L, n) printf("請輸入%d個元素：", n); for(i = 0; i < n; i+) scanf("%d", &L.elemi); L.length+; return OK; else return ERROR;/*輸出順序表*/void PrintList_Sq(SqList L) int i; printf("順序表中元素為：n"); for(i = 0; i < L.length; i+) printf("%d ", L.ele

15、mi); printf("n");/*刪除第i個元素*/Status DeleteList_Sq(SqList &L,int i,ElemType &e)ElemType *p, *q;if( (i<1) | (i>L.length) ) return ERROR;p = &(L.elemi-1);e = *p; q = L.elem+L.length-1;for(+p; p <= q; +p) *(p-1) = *p;-L.length;return OK;/*刪除值為x的元素，刪除成功返回OK，刪除失敗返回ERROR*/Stat

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

17、qList La, SqList Lb, SqList &Lc ) ElemType *pa, *pb, *pc, *pa_last, *pb_last; pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length+Lb.length; pc = Lc.elem = (ElemType *)malloc(Lc.listsize * sizeof(ElemType); if (!Lc.elem) exit (OVERFLOW); pa_last = La.elem + La.length - 1; pb_last = L

18、b.elem + Lb.length - 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#include "SqList.h"int main() int choice, n, i, x; SqList L, La, Lb, Lc; while(1)

19、menu(); printf("選擇你的操作："); scanf("%d",&choice); switch(choice) case 1: if(CreateList_Sq(L) printf("順序表創(chuàng)建成功n"); else printf("順序表創(chuàng)建失敗n"); break; case 2: PrintList_Sq(L); break; case 3: printf("請輸入刪除元素的位置："); scanf("%d", &i); if(Delete

20、List_Sq(L, i, x) printf("被刪除元素值為：%dn",x); else printf("刪除失敗n"); break; case 4: printf("請輸入刪除元素值："); scanf("%d", &x); if(DeleteListX_Sq(L, x) printf("刪除成功n"); else printf("刪除失敗n"); PrintList_Sq(L); break; case 5: AdjustList_Sq(L); printf

21、("新鏈表為：n"); PrintList_Sq(L); break; case 6: printf("請輸入順序表長度："); scanf("%d", &n); if(OrderList_sq(L, n) printf("值有序順序表為：n"); PrintList_Sq(L); else printf("順序表創(chuàng)建失敗n"); break; case 7: printf("請輸入順序表La的長度："); scanf("%d", &n);

22、 OrderList_sq(La, n); printf("請輸入順序表Lb的長度："); scanf("%d", &n); OrderList_sq(Lb, n); MergeList_Sq(La, Lb, Lc); printf("合并后的順序表為：n"); PrintList_Sq(Lc); break; case 0: return 0; default: printf("輸入錯誤，請重新輸入n"); 實驗02 單鏈表的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：單鏈表的插入、刪除及應(yīng)用。目的要

23、求： 1掌握單鏈表的存儲特點及其實現(xiàn)。 2掌握單鏈表的插入、刪除算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。實驗內(nèi)容： 編寫一個完整的程序，實現(xiàn)單鏈表的生成、插入、刪除、輸出等基本操作。（1） 隨機產(chǎn)生或鍵盤輸入一組元素，建立一個帶頭結(jié)點的單向鏈表（無序）。（2） 計算單鏈表的長度，遍歷單鏈表。（3） 把單鏈表中的元素逆置（不允許申請新的結(jié)點空間）。（4） 在單鏈表中刪除所有值為偶數(shù)的元素結(jié)點。（5） 編寫在非遞減有序單鏈表中插入一個元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個非遞減有序單鏈表。（6） * 利用算法5建立兩個非遞減有序單鏈表，然后合并成一個非遞增有序鏈表。（7） * 利用算法5建立兩個非遞

24、減有序單鏈表，然后合并成一個非遞減有序鏈表。（8） * 利用算法1建立的鏈表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的存儲空間）。（9） * 采用單鏈表實現(xiàn)一元多項式的存儲并實現(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開始報

25、數(shù)，數(shù)到m的人便是第二個出列的人；如此重復(fù)下去，直到最后一個人出列為止，得到一個出列的編號順序。例如，當(dāng)n=8，m=4時，若從第一個位置數(shù)起，則出列的次序為4，8，5，2，1，3，7，6。試編寫程序確定出列的順序。要求用不帶頭結(jié)點的單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出個人編號。實驗說明： 1類型定義 typedef int ElemType; /元素類型 typedef struct node ElemType data; struct node *next; LinkNode, *LinkList; 2為了算法實現(xiàn)簡單，建議采用帶頭結(jié)點的單鏈表。注意問題：1重點理解鏈?zhǔn)酱鎯?/p>

26、的特點及指針的含義。 2注意比較順序存儲與鏈?zhǔn)酱鎯Φ母髯蕴攸c。 3注意比較帶頭結(jié)點、無頭結(jié)點鏈表實現(xiàn)插入、刪除算法時的區(qū)別。 4單鏈表的操作是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，一定要注意對這部分常見算法的理解。部分源代碼：DS.h#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;LinkList.h#include &qu

27、ot;DS.h"typedef int Elemtype;typedef struct Node Elemtype data;struct Node *next;Lnode,*LinkList;void menu(); /*菜單*/Status Init_Linklist(LinkList &L); /*初始化空表*/Status Creat_Linklist(LinkList &L); /*尾插法建立單鏈表*/void Disp_Linklist(LinkList L); /*單鏈表遍歷*/int length_Linklist(LinkList L); /*計算單

28、鏈表長度*/void Reverse_Linklist(LinkList L); /*單鏈表逆置*/void DelEven_Linklist(LinkList L); /*刪除值為偶數(shù)的結(jié)點*/Status Insert_Linklist(LinkList L, int x); /*在有序單鏈表L中插入元素x，鏈表仍然有序*/Status CreatOrder_Linklist(LinkList &L); /*創(chuàng)建非遞減有序單鏈表*/void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc); /*兩個

29、非遞減有序單鏈表La和Lb合并成一個非遞增有序鏈表Lc*/void MergeAscend_Linklist(LinkList La, LinkList Lb, LinkList &Lc); /*兩個非遞減有序單鏈表La和Lb合并成一個非遞減有序鏈表Lc*/void Split_Linklist(LinkList La, LinkList &Lb); /*鏈表La按值分解成兩個鏈表，La全部為奇數(shù)，Lb全部為偶數(shù)*/LinkList.cpp#include "LinkList.h"void menu() printf("ttt 單鏈表基本操作nn&

30、quot;); printf("ttt1.建 立 單 鏈 表n"); printf("ttt2.遍 歷 單 鏈 表n"); printf("ttt3.計 算 鏈 表 長 度n"); printf("ttt4.鏈 表 逆 置n"); printf("ttt5.刪 除 偶 數(shù) 節(jié) 點n"); printf("ttt6.生 成 值 有 序 單 鏈 表n"); printf("ttt7.合 并 生 成 降 序 鏈 表n"); printf("ttt8.合

31、 并 生 成 升 序 鏈 表n"); printf("ttt9.分 解 鏈 表n"); printf("ttt0.退 出nn");/*初始化空表*/Status Init_Linklist(LinkList &L) L=(LinkList)malloc(sizeof(Lnode); if(!L) return ERROR;L->next=NULL;return OK;/*尾插法建立單鏈表*/Status Creat_Linklist(LinkList &L) int x; LinkList p,rear; Init_Lin

32、klist(L); rear = L; printf("輸入-1表示輸入結(jié)束n"); while(scanf("%d",&x),x != -1) p = (LinkList)malloc(sizeof(Lnode); if(!p) return ERROR; p->data = x; rear->next = p; rear = p; rear->next = NULL; return OK;/*單鏈表遍歷*/void Disp_Linklist(LinkList L) LinkList p; p = L->next; w

33、hile(p) printf("%d ", p->data); p = p->next; printf("n");/*計算單鏈表長度*/int length_Linklist(LinkList L) int count = 0; /*count表示單鏈表長度*/ LinkList p; return count;/*單鏈表逆置*/void Reverse_Linklist(LinkList L) LinkList p, q ; /*刪除值為偶數(shù)的結(jié)點*/void DelEven_Linklist(LinkList L) LinkList p,

34、 q; /*在有序單鏈表中插入元素，鏈表仍然有序，插入成功返回OK，插入失敗返回ERROR*/Status Insert_Linklist(LinkList L, int x) ;/*創(chuàng)建非遞減有序單鏈表，創(chuàng)建成功返回OK，創(chuàng)建失敗返回ERROR*/Status CreatOrder_Linklist(LinkList &L) /*兩個非遞減有序單鏈表La和Lb合并成一個非遞增有序鏈表Lc*/void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc) /*兩個非遞減有序單鏈表La和Lb合并成一個非遞減有序

35、鏈表Lc*/void MergeAscend_Linklist(LinkList La, LinkList Lb, LinkList &Lc) LinkList pa, pb, pc; pa = La->next; pb = Lb->next; pc = Lc = La; while(pa && pb) if(pa->data <= pb->data) pc->next = pa; pc = pa; pa = pa->next; else pc->next = pb; pc = pb; pb = pb->next;

36、pc->next = pa ? pa : pb; free(Lb);/*鏈表La按值分解成兩個鏈表，La全部為奇數(shù)，Lb全部為偶數(shù)*/void Split_Linklist(LinkList La, LinkList &Lb) main.cpp#include "LinkList.h"int main() int choice, length; LinkList L, La, Lb, Lc; while(1) menu(); printf("選擇你的操作："); scanf("%d",&choice); swit

37、ch(choice) case 1: if(Creat_Linklist(L) printf("單鏈表創(chuàng)建成功n"); else printf("單鏈表創(chuàng)建失敗n"); break; case 2: Disp_Linklist(L); break; case 3: length = length_Linklist(L); printf("單鏈表長度為：%dn",length); break; case 4: Reverse_Linklist(L); printf("逆置后的鏈表為：n"); Disp_Linklis

38、t(L); break; case 5: DelEven_Linklist(L); printf("新鏈表為：n"); Disp_Linklist(L); break; case 6: if(CreatOrder_Linklist(L) printf("值有序鏈表為：n"); Disp_Linklist(L); else printf("單鏈表創(chuàng)建失敗n"); break; case 7: CreatOrder_Linklist(La); CreatOrder_Linklist(Lb); MergeDescend_Linklist(L

39、a, Lb, Lc); printf("合并后的新鏈表為：n");Disp_Linklist(Lc); break; case 8: CreatOrder_Linklist(La); CreatOrder_Linklist(Lb); MergeAscend_Linklist(La, Lb, Lc); printf("合并后的新鏈表為：n");Disp_Linklist(Lc); break; case 9: Creat_Linklist(L); Split_Linklist(L, Lb); printf("分裂后的新鏈表為：n");

40、Disp_Linklist(L); Disp_Linklist(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） 采用鏈?zhǔn)酱鎯崿F(xiàn)棧的初始化、入棧、出棧操作。（3） 在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。（4） * 綜合訓(xùn)練：1） 堆棧操作合法性：假設(shè)以S和X分別表

41、示入棧和出棧操作。如果根據(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)換為后綴表達式。輸入在一行中給出不含

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

43、inkStack;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） 采用鏈?zhǔn)酱鎯崿F(xiàn)隊列的初始化、入隊、出隊操作。（3） 在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。（4） *綜合訓(xùn)練：銀行排

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

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

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

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