大數(shù)據(jù)結(jié)構(gòu)實驗指導書

1、數(shù)據(jù)結(jié)構(gòu)實驗指導書某某輕工業(yè)學院目錄前言2實驗01順序表的根本操作6實驗02單鏈表的根本操作17實驗03棧的根本操作30實驗04隊列的根本操作32實驗05二叉樹的根本操作34實驗06哈夫曼編碼36實驗07圖的兩種存儲和遍歷38實驗08最小生成樹、拓撲排序和最短路徑41實驗09二叉排序樹的根本操作43實驗10哈希表的生成44實驗11常用的內(nèi)部排序算法46附：實驗報告模板錯誤!未定義書簽。、八 、亠刖言數(shù)據(jù)結(jié)構(gòu)是計算機相關專業(yè)的一門核心根底課程，是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)與 其它系統(tǒng)程序和大型應用程序開發(fā)的重要根底，也是很多高?？佳袑I(yè)課之一。它主要介紹線性結(jié) 構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)三種邏輯

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

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

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

5、習過程中注意各種算法的理解，以便為考研做一定的準備。4、好的算法決定了好的程序，要有效地實現(xiàn)算法，就需要設計能夠有效表達和簡化算法的數(shù)據(jù)結(jié)構(gòu)，因此數(shù)據(jù)結(jié)構(gòu)是有效進展程序設計的根底，是每個程序員的必修課。五、實驗報告的書寫要求1、明確實驗的目的與要求。2、記錄實驗的輸入數(shù)據(jù)和輸出結(jié)果。3、說明實驗中出現(xiàn)的問題和解決過程。4、寫出實驗的體會和實驗過程中沒能解決的問題。5、實驗程序請構(gòu)建為多文件程序，每一個算法對應的函數(shù)原型聲明存放在頭文件的函數(shù)實現(xiàn)存放在源文件 *.c中；main()函數(shù)存放在另一個源文件中，該文件包含頭文件六、成績考評方法1、期末考試占70分，閉卷。2、 平時考評占30分。其中實

6、驗環(huán)節(jié)占 20分實驗準備、上機、報告、驗收等 分出勤、作業(yè)、測驗等。七、參考書目1、 數(shù)據(jù)結(jié)構(gòu)C語言版嚴蔚敏等 清華大學2、 數(shù)據(jù)結(jié)構(gòu)題集C語言版 嚴蔚敏等 清華大學*.h中，對應*.h即可。;平時占1020123、數(shù)據(jù)結(jié)構(gòu)與算法分析一一 C語言描述，Mark Allen Weiss 著，機械工業(yè)，實驗01順序表的根本操作實驗學時：2學時實驗類型：上機背景知識：順序表的插入、刪除與應用。目的要求：1 掌握順序存儲結(jié)構(gòu)的特點。2 掌握順序存儲結(jié)構(gòu)的常見算法。實驗內(nèi)容：編寫一個完整的程序，實現(xiàn)順序表的生成、插入、刪除、輸出等根本運算。(1) 建立一個順序表，含有 n個數(shù)據(jù)元素。(2) 輸出順序表。

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

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

9、;#in elude <stri ng.h>#in elude <math.h>#defi ne TRUE 1#define FALSE 0#defi ne OK 1#defi ne ERROR 0 typedef int Status;#ifndef SQLIST_H_INCLUDED#defi ne SQLIST_H_INCLUDED#i nclude "DS.h"typedef int ElemType;typedef structElemType *elem;int len gth;int listsize;SqList;void menu(

10、);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 AdjustList_Sq(SqL

11、ist & L);/*奇數(shù)排在偶數(shù)之前 */Status OrderList_sq(SqList & L, i nt n);/*插入法生成遞增有序表*/void MergeList_Sq(SqList La, SqList Lb, SqList &Lc );/*兩個非遞減有序表A 和 B，并把它們合并成一個非遞減有序表C*/#en dif / SQLIST_H_INCLUDED#in elude "SqList.h" void menu() printf("ttt順序表根本操作nn”)；printf("ttt1.建 立順序 表 n

12、");printf("ttt2.遍歷順序表 n");printf("ttt3.刪除第 i 個元 素n");printf("ttt4.刪 除值為 x 的元 素n");printf("ttt5.奇數(shù)排在偶數(shù)之前n");prin tf("ttt6.插入法 生成遞 增有序 表n ”)；Lcn");printf("ttt7.兩個非遞減有序表La和Lb合并成非遞減有序表printf("ttt0.退出 nn”)；/*初始化順序表*/Status In itList_Sq(SqLi

13、st & L, i nt n)L.elem=(ElemType*)malloc( n*sizeof(ElemType);if(!L.elem) exit(OVERFLOW);L.le ngth=O;L.listsize=n;return OK;/*建立順序表*/Status CreateList_Sq(SqList &L)int n, i;printf("請輸入順序表長度:");sca nf("%d", &n);if(I nitList_Sq(L, n)printf("請輸入%d個元素：”,n);for(i = 0; i

14、 < n; i+)scan f("%d", & L.elemi);L.len gth+;return OK;elsereturn ERROR;/*輸出順序表*/void PrintList_Sq(SqList L)int i;printf("順序表中元素為:n ”);for(i = 0; i < L.len gth; i+)prin tf("%d ", L.elemi);prin tf("n");/*刪除第i個元素*/Status DeleteList_Sq(SqList &L,int i,Ele

15、mType &e) ElemType *p, *q;if( (i<1) | (i>L.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;ERROR*/*刪除值為x的元素，刪除成功返回OK,刪除失敗返回Status DeleteListX_Sq(SqList & L,ElemType x)ElemType *p, *q;/*奇數(shù)排在偶數(shù)之前*/Status Adj

16、ustList_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(SqList La, SqList Lb, SqList &Lc )ElemType *pa, *pb, *pc, *pa_last, *pb_last;pa =

17、La.elem; pb = Lb.elem;Lci stsize = Lcen gth = La.len gth+Lb .len 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 - 1;while (pa <= pa_last && pb <= pb_last)if (*pa <=

18、*pb) *pc+ = else *pc+ = *pb+;while(pa <= pa_last) *pc+while(pb <= pb_last) *pc+#i nclude "SqList.h"int mai n()int choice, n, i, x;SqList L, La, Lb, Lc;while(1)men u();printf("選擇你的操作: scan f("%d",&choice); switch(choice)*pa+;=*pa+;=*pb+;");case 1:if(CreateList_

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

20、quot;%d", &x);if(DeleteListX_Sq(L, x)printf("刪除成功 n”);elseprintf("刪除失敗 n”);Prin tList_Sq(L);break;case 5:AdjustList_Sq(L);printf("新鏈表為:n ”);Prin tList_Sq(L);break;case 6:printf("請輸入順序表長度:");sca nf("%d", &n);if(OrderList_sq(L, n)printf("值有序順序表為：n&q

21、uot;);Prin tList_Sq(L);elseprintf("順序表創(chuàng)建失敗n");break;case 7:printf("請輸入順序表La的長度:");sca nf("%d", &n);OrderList_sq(La, n);printf("請輸入順序表Lb的長度:");sca nf("%d", &n);OrderList_sq(Lb, n);MergeList_Sq(La, Lb, Lc);printf("合并后的順序表為：n");Prin tL

22、ist_Sq(Lc);break;case 0:return 0;default:printf("輸入錯誤，請重新輸入n");實驗02單鏈表的根本操作實驗學時：2學時實驗類型：上機背景知識：單鏈表的插入、刪除與應用。目的要求：1 掌握單鏈表的存儲特點與其實現(xiàn)。2 掌握單鏈表的插入、刪除算法與其應用算法的程序?qū)崿F(xiàn)。實驗內(nèi)容: 編寫一個完整的程序，實現(xiàn)單鏈表的生成、插入、刪除、輸出等根本操作。（1）隨機產(chǎn)生或鍵盤輸入一組元素，建立一個帶頭結(jié)點的單向鏈表無序。（2）計算單鏈表的長度，遍歷單鏈表。（3）把單鏈表中的元素逆置不允許申請新的結(jié)點空間。（4）在單鏈表中刪除所有值為偶數(shù)的元

23、素結(jié)點。（5）編寫在非遞減有序單鏈表中插入一個元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建 立一個非遞減有序單鏈表。（6）*利用算法5建立兩個非遞減有序單鏈表，然后合并成一個非遞增有序鏈表。（7）*利用算法5建立兩個非遞減有序單鏈表，然后合并成一個非遞減有序鏈表。（8）*利用算法1建立的鏈表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)盡量利用的存儲空間。(9)*米用單鏈表實現(xiàn)-兀多項式的存儲并實現(xiàn)兩個多項式相加并輸出結(jié)果。(10)在主函數(shù)中設計個簡單的菜單，分別調(diào)試上述算法。(11)*綜合訓練：1利用鏈表實現(xiàn)一個班級學生信息管理數(shù)據(jù)錄入、插入、刪除、排序、查找等，并能夠?qū)崿F(xiàn)將數(shù)

24、據(jù)存儲到文件中2約瑟夫環(huán)問題：設有 n個人圍坐在圓桌周圍，從某個位置開始編號為 1, 2, 3,，n,坐在 編號為1的位置上的人從1開始報數(shù)，數(shù)到 m的人便出列；下一個第 m+1個人又從1開始 報數(shù)，數(shù)到 m的人便是第二個出列的人；如此重復下去，直到最后一個人出列為止，得到一個出列的編號順序。例如，當 n=8, m=4時，假如從第一個位置數(shù)起，如此出列的次序為4, 8，5，2，1，3，7，6。試編寫程序確定出列的順序。要求用不帶頭結(jié)點的單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出個人編號。實驗說明:1 類型定義typedef int ElemType;/ 元素類型typedef st

25、ruct 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)的根底，一定要注意對這局部常見算法的理解。局部源代碼：#in clude <stdio.h>#in clude <stdlib.h>#in clude <stri ng.h>#in clude <ma

26、th.h>#defi ne TRUE 1#defi ne FALSE 0#defi ne OK 1#defi ne ERROR 0 typedef int Status;#i nclude "DS.h"typedef int Elemtype;typedef struct NodeElemtype data; struct Node *n ext; Ln ode,*L in kList;void menu();/*菜單*/Status Ini t_Li nklist(Li nkList &L);/*初始化空表*/Status Creat_L in klist(

27、L in kList &L);/*尾插法建立單鏈表*/void Disp_Li nklist(Li nkList L);/*單鏈表遍歷*/int len gth_Li nklist(L in kList 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);/*在有序單鏈表 L中插入元素 x,鏈表仍然有序*/Status CreatOr

28、der_Li nklist(Li nkList & L);/* 創(chuàng)建非遞減有序單鏈表*/Lavoid MergeDesce nd_L in klist(Li nkList La, Li nkList Lb, Li nkList & Lc);/* 兩個非遞減有序單鏈表和Lb合并成一個非遞增有序鏈表Lc*/void MergeAsce nd_L in klist(Li nkList La, Li nkList Lb, Li nkList & Lc); /*兩個非遞減有序單鏈表LaLb合并成一個非遞減有序鏈表Lc*/Lbvoid Split_Linklist(LinkList

29、 La, LinkList &Lb);/*鏈表 La 按值分解成兩個鏈表，La 全部為奇數(shù)，全部為偶數(shù)*/#i nclude "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");p

30、rin tf("ttt6.生成值有序單鏈表n");prin tf("ttt7.合并生成降序鏈表n");生成升序表 n");printf("ttt9.分鏈表n");printf("ttt0.退出 nn");/*初始化空表*/Status Ini t_Li nklist(Li nkList &L) L=(Li nkList)malloc(sizeof(L no de);if(!L) return ERROR;L-> next=NULL;return OK;/*尾插法建立單鏈表*/Status C

31、reat_Linklist(LinkList &L)int x;Lin kList p,rear;In it_Li nklist(L);rear = L;printf("輸入-1表示輸入完畢n");while(scanf("%d"，&x),x != -1)p = (Lin kList)malloc(sizeof(L no de); if(!p) return ERROR;p->data = x;rear- >n ext = p;rear = p;rear->next = NULL;return OK;/*單鏈表遍歷*/v

32、oid Disp_Linklist(LinkList L)Lin kList p;p = L_>n ext;while(p)prin tf("%d ", p->data); p = p_>n ext;prin tf("n");/*計算單鏈表長度*/int len gth_Li nklist(L in kList L)int count = 0; /*count表示單鏈表長度*/Lin kList p;retur n count;/*單鏈表逆置*/void Reverse_L in klist(L in kList L)Lin kList

33、 p, q ;/*刪除值為偶數(shù)的結(jié)點*/void DelEven_L in klist(Li nkList L)Lin kList p, q;/*在有序單鏈表中插入元素，鏈表仍然有序，插入成功返回Status Insert_Linklist(LinkList L, int x)OK，插入失敗返回ERROR*/*創(chuàng)建非遞減有序單鏈表，創(chuàng)建成功返回OK，創(chuàng)建失敗返回ERROR*/Status CreatOrder_Linklist(LinkList &L)/*兩個非遞減有序單鏈表La和Lb合并成一個非遞增有序鏈表Lc*/void MergeDesce nd_Lin klist(L in k

34、List La, Lin kList Lb, Lin kList &Lc)/*兩個非遞減有序單鏈表La和Lb合并成一個非遞減有序鏈表Lc*/void MergeAsce nd_Lin klist(L in kList La, Lin kList 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 <= pb->data)pc->n ext = pa; pc = p

35、a; pa = pa->n ext;elsepc->n ext = pb; pc = pb; pb = pb->n ext;pc->next = pa ? pa : pb;free(Lb);/*鏈表La按值分解成兩個鏈表，La全部為奇數(shù),Lb全部為偶數(shù)*/void Split_Linklist(LinkList La, LinkList &Lb)main .cpp#in clude "Li nkList.h" int mai n()int choice, le ngth;Lin kList L, La, Lb, Lc;while(1)men

36、u();printf(”選擇你的操作：");scan f("%d",&choice);switch(choice)case 1:if(Creat_L in klist(L)printf("單鏈表創(chuàng)建成功n");elseprintf("單鏈表創(chuàng)建失敗n"); break;case 2:Disp_Li nklist(L);break;case 3:len gth = len gth_L in klist(L);printf("單鏈表長度為:%dn",le ngth);break;case 4:Reve

37、rse_L in klist(L);printf("逆置后的鏈表為：n");Disp_Li nklist(L);break;case 5:DelEven_L in klist(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_Li nklist(La);C

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

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

40、試上述算法。(4)*綜合訓練：1） 堆棧操作合法性：假設以 S和X分別表示入棧和出棧操作。如果根據(jù)一個僅由S和X構(gòu) 成的序列，對一個空堆棧進展操作，相應操作均可行如沒有出現(xiàn)刪除時?？涨易詈鬆顟B(tài)也是?？眨绱朔Q該序列是合法的堆棧操作序列。請編寫程序，輸入S和X序列，判斷該序列是否合法。2）括號匹配檢驗：假設表達式中允許包括兩種括號：圓括號和方括號，其嵌套的順序隨意，即()或()等為正確的格式，()或()等均為不正確格式。輸入一個表達式，判斷其中的括號是否能正確匹配。3) 表達式轉(zhuǎn)換：算術表達式有前綴表示法、中綴表示法和后綴表示法等形式。日常使用的算術表達式是采用中綴表示法，即二元運算符位于兩個運

41、算數(shù)中間。請設計程序?qū)⒅芯Y表達式轉(zhuǎn)換為后綴表達式。輸入在一行中給出不含空格的中綴表達式，可包含+、-、*、以與左右括號()，表達式不超過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;st

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

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

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

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

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

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

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

49、序?qū)崿F(xiàn)。實驗內(nèi)容：(1)鍵盤輸入數(shù)據(jù)，分別建立一個有向圖和一個無向圖的鄰接表。(2)輸出該鄰接表。(3)在有向圖的鄰接表的根底上計算各頂點的度，并輸出。(4)采用鄰接表存儲實現(xiàn)無向圖的深度優(yōu)先遍歷。(5)采用鄰接表存儲實現(xiàn)無向圖的廣度優(yōu)先遍歷。(6)在主函數(shù)中設計一個簡單的菜單，分別調(diào)試上述算法。(7)*綜合訓練地下迷宮探索：假設有一個地下通道迷宮，它的通道都是直的，而通道所有交叉點包括通道 的端點上都有一盞燈和一個開關。請問你如何從某個起點開始在迷宮中點亮所有的燈并回到 起點？輸入格式：輸入第一行給出三個正整數(shù)，分別表示地下迷宮的節(jié)點數(shù)N 1<NK 1000 ,表示通道所有交叉點和端點

50、、邊數(shù)M M < 3000,表示通道數(shù)和探索起始節(jié)點編號 S節(jié)點從1到N編號。隨后的M行對應M條邊通道，每行給出一對正整數(shù)，分別是該條邊直接連通的兩個節(jié)點的 編號。輸出格式：假如可以點亮所有節(jié)點的燈，如此輸出從S開始并以S完畢的包含所有節(jié)點的序列，序列中相鄰的節(jié)點一定有邊通道；否如此雖然不能點亮所有節(jié)點的燈，但還是輸出點亮局部燈 的節(jié)點序列，最后輸出 0,此時表示迷宮不是連通圖。由于深度優(yōu)先遍歷的節(jié)點序列是不唯一的，為了使得輸出具有唯一的結(jié)果，我們約定以節(jié) 點小編號優(yōu)先的次序訪問點燈。在點亮所有可以點亮的燈后，以原路返回的方式回到起點。 輸入樣例：3 44 55 66 41 5輸出樣例：

51、1 2 3 4 5 6 5 4 3 2 1實驗說明：1 類型定義鄰接表存儲#define MAX_VERTEX_NUM 20/ 頂點最大個數(shù)typedef struct Arodeint adjvex;struct Arode *n extarc;int weight; /邊的權值Arode;/表結(jié)點#define VertexType int/頂點元素類型typedef struct VNodeVertexType data;Arode *firstarc;VNode, AdjListMAX_VERTEX_NUM; /typedef structAdjList vertices;int ve

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

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

54、7鄰接矩陣存儲示例#define MAX_VERTEX_NUM 20/ 頂點最大個數(shù)typedef enum DG, DN, UDG, UDN GraphKind;typedef struct ArcCellVRType adj;int weight;/邊的權值ArcCell; AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arum;頂點的實際數(shù)，邊的實際數(shù)GraphK ind ki nd;MGraph;注意問題：注意理解各算法實現(xiàn)時所采用的存儲結(jié)構(gòu)。實驗09二叉排序樹的根本操作實驗學時：2學時 實驗類型：上機背景知識：樹表查找。目的要求：掌握二叉排序樹、AVL樹的查找、插入、刪除、建立算法的思想與程序?qū)崿F(xiàn)。實驗內(nèi)容：（1）隨機產(chǎn)生一組關鍵字，利用二叉排序樹的插入算法建立二叉排序樹，然后刪除某一