數(shù)據(jù)結(jié)構(gòu)試驗指導(dǎo)書修訂版

1、數(shù)據(jù)結(jié)構(gòu) 實驗指導(dǎo)書鄭州輕工業(yè)學(xué)院2016.02.20目錄、八前言實驗 01 順序表的基本操作 5實驗 02 單鏈表的基本操作 13實驗 03 棧的基本操作 21實驗 04 隊列的基本操作 23實驗 05 二叉樹的基本操作 25實驗 06 哈夫曼編碼 26實驗 07 圖的兩種存儲和遍歷 28實驗 08 最小生成樹、拓撲排序和最短路徑 31實驗 09 二叉排序樹的基本操作 33實驗 10 哈希表的生成 34實驗 11 常用的內(nèi)部排序算法 35附：實驗報告模板 錯 誤！未定義書簽。3數(shù)據(jù)結(jié)構(gòu) 是計算機相關(guān)專業(yè)的一門核心基礎(chǔ)課程，是編譯原理、 操作系統(tǒng)、 數(shù)據(jù)庫系統(tǒng)及其 它系統(tǒng)程序和大型應(yīng)用程序開發(fā)

2、的重要基礎(chǔ)， 也是很多高?？佳袑I(yè)課之一。它主要介紹線性結(jié)構(gòu)、 樹型結(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)練過程，

3、通過算 法設(shè)計和上機實踐的訓(xùn)練， 能夠培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計能力。 學(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、每

4、次實驗前學(xué)生必須根據(jù)實驗內(nèi)容認真準備實驗程序及調(diào)試時所需的輸入數(shù)據(jù)。2、在指導(dǎo)教師的幫助下能夠完成實驗內(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)盡量完

5、成 （至少完成 70%，否則實驗不合格）。3、數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學(xué)考試的專業(yè)課之一，希望有志于考研的學(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)存放在

6、源文件 *.c 中； main（） 函數(shù)存放在另一個源文件中，該文件包含頭文件*.h 即可。六、成績考評辦法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è)出版社， 2012。實驗 01 順序表的基本操作實驗學(xué)時 ：2 學(xué)時 實驗類型： 上機 背景知識 ：順序表的插入、刪除及

7、應(yīng)用。目的要求 ：1掌握順序存儲結(jié)構(gòu)的特點。2掌握順序存儲結(jié)構(gòu)的常見算法。實驗內(nèi)容：編寫一個完整的程序，實現(xiàn)順序表的生成、插入、刪除、輸出等基本運算。（ 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)

8、一個班級學(xué)生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等）。實驗說明：1請構(gòu)建多文件程序，算法 1至算法 6對應(yīng)的函數(shù)原型聲明存放在頭文件 SqList.h 中， 對應(yīng)的 函數(shù)實現(xiàn)存放在源文件 SqList.c中；main（）函數(shù)存放在另一個源文件中，該文件包含頭文件SqList.h即可。2類型定義#define MAXSIZE 100/表中元素的最大個數(shù)typedef int ElemType; /元素類型typedef structElemType *elem; /線性表int length;/表的實際長度int listsize; /當(dāng)前分配的存儲容量SqList;/順序表的類型名53建

9、立順序表時可利用隨機函數(shù)自動產(chǎn)生數(shù)據(jù)。注意問題：1、 插入、刪除時元素的移動原因、方向及先后順序。2、 理解函數(shù)形參與實參的傳遞關(guān)系。部分源代碼：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;SqList.h#ifndef SQLIST_H_INCLUDED#define SQLIST_H_I

10、NCLUDED#include "DS.h"typedef int ElemType;typedef structElemType *elem;int length;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,i

11、nt i,ElemType &e);/* 刪除第 i 個元素 */Status DeleteListX_Sq(SqList &L,ElemType x);/* 刪除值為 x 的元素 */Status AdjustList_Sq(SqList &L);/* 奇數(shù)排在偶數(shù)之前 */Status OrderList_sq(SqList &L, int n);/* 插入法生成遞增有序表 */void MergeList_Sq(SqList La, SqList Lb, SqList &Lc );/* 兩個非遞減有序表 A 和 B ，并把它們合并成一 個非遞減有序

12、表 C*/ #endif / SQLIST_H_INCLUDEDSqList.cpp#include "SqList.h" void menu()printf("ttt 順序表基本操作 nn");printf("ttt1. 建 立 順 序 表 n"); printf("ttt2. 遍 歷 順 序 表 n");printf("ttt3. 刪除 第 i 個 元 素 n"）;printf("ttt4. 刪 除 值 為 x 的 元 素 n"); printf("ttt5.

13、奇 數(shù) 排 在 偶 數(shù) 之 前 n");printf("ttt6. 插 入 法 生 成 遞 增 有 序 表 n");printf（"ttt7. 兩個非遞減有序表 La 和 Lb 合并成非遞減有序表 Lcn"）;printf("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.li

14、stsize=n;return OK;/* 建立順序表 */Status CreateList_Sq(SqList &L)int n, i;printf(" 請輸入順序表長度： ");scanf("%d", &n);if(InitList_Sq(L, n)printf(" 請輸入 %d 個元素： ", n);for(i = 0; i < n; i+)scanf("%d", &L.elemi);L.length+;return OK;elsereturn ERROR;/* 輸出順序表 *

15、/void PrintList_Sq(SqList L)int i;printf(" 順序表中元素為： n");for(i = 0; i < L.length; i+)printf("%d ", L.elemi);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.ele

16、mi-1);e = *p;q = L.elem+L.length-1;for(+p; p <= q; +p) *(p-1) = *p;-L.length;return OK;/*刪除值為 x 的元素，刪除成功返回 OK ，刪除失敗返回 ERROR*/Status DeleteListX_Sq(SqList &L,ElemType x)ElemType *p, *q;/* 奇數(shù)排在偶數(shù)之前 */Status AdjustList_Sq(SqList &L)ElemType *p, *q;int temp;return OK;/*插入法生成遞增有序表，有序表生成成功返回OK

17、，失敗返回 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 = La.elem; pb = Lb.elem;Lc.listsize = Lc.length = La.length+Lb.length;pc = Lc.elem

18、= (ElemType *)malloc(Lc.listsize * sizeof(ElemType);if (!Lc.elem) exit (OVERFLOW);pa_last = La.elem + La.length - 1;pb_last = Lb.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 <=

19、 pb_last) *pc+ = *pb+;main.cpp#include "SqList.h"int main()int choice, n, i, x;SqList L, La, Lb, Lc;while(1)menu();printf(" 選擇你的操作： ");scanf("%d",&choice);switch(choice)case 1:if(CreateList_Sq(L)printf(" 順序表創(chuàng)建成功 n"); elseprintf(" 順序表創(chuàng)建失敗 n"); bre

20、ak;case 2:PrintList_Sq(L);break;case 3:printf(" 請輸入刪除元素的位置： "); scanf("%d", &i);if(DeleteList_Sq(L, i, x)printf(" 被刪除元素值為： %dn",x); elseprintf(" 刪除失敗 n");break;case 4:printf(" 請輸入刪除元素值： ");scanf("%d", &x);if(DeleteListX_Sq(L, x)prin

21、tf(" 刪除成功 n"); elseprintf(" 刪除失敗 n");PrintList_Sq(L);break;case 5:AdjustList_Sq(L);printf(" 新鏈表為： n");PrintList_Sq(L);break;case 6:printf(" 請輸入順序表長度： ");scanf("%d", &n);if(OrderList_sq(L, n)printf(" 值有序順序表為： n");PrintList_Sq(L);elseprin

22、tf(" 順序表創(chuàng)建失敗 n");break;case 7:printf(" 請輸入順序表 La 的長度： ");scanf("%d", &n);OrderList_sq(La, n);printf(" 請輸入順序表 Lb 的長度： "); scanf("%d", &n);OrderList_sq(Lb, n);MergeList_Sq(La, Lb, Lc);printf(" 合并后的順序表為： n");PrintList_Sq(Lc); break;cas

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

24、素結(jié)點。（ 5） 編寫在非遞減有序單鏈表中插入一個元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個非遞減有序單鏈表。（6） * 利用算法 5 建立兩個非遞減有序單鏈表，然后合并成一個非遞增有序鏈表。（7） * 利用算法 5 建立兩個非遞減有序單鏈表，然后合并成一個非遞減有序鏈表。（ 8） * 利用算法 1 建立的鏈表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的存儲空間）。（ 9） * 采用單鏈表實現(xiàn)一元多項式的存儲并實現(xiàn)兩個多項式相加并輸出結(jié)果。（ 10） 在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。（ 11） * 綜合訓(xùn)練：1）利用鏈表實現(xiàn)一個班級學(xué)生信

25、息管理 （數(shù)據(jù)錄入、插入、刪除、排序、查找等，并能夠 實現(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, 7, 6。試編寫程序確定出列的順序。要求用不帶頭結(jié)點的單向循環(huán)鏈表作為存儲 結(jié)構(gòu)模擬此過程,按照出列順序打印出個人編號。#

26、實驗說明：1類型定義typedef int ElemType; / 元素類型typedef struct nodeElemType data;struct node *next;LinkNode, *LinkList;2為了算法實現(xiàn)簡單，建議采用帶頭結(jié)點的單鏈表。注意問題：1重點理解鏈式存儲的特點及指針的含義。2注意比較順序存儲與鏈式存儲的各自特點。3注意比較帶頭結(jié)點、無頭結(jié)點鏈表實現(xiàn)插入、刪除算法時的區(qū)別。4單鏈表的操作是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，一定要注意對這部分常見算法的理解。部分源代碼：DS.h#include <stdio.h>#include <stdlib.h>#i

27、nclude <string.h>#include <math.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;LinkList.h#include "DS.h"typedef int Elemtype;typedef struct Node Elemtype data; struct Node *next; Lnode,*LinkList;void menu();Status Init_Linklist(LinkList &L); St

28、atus Creat_Linklist(LinkList &L); void Disp_Linklist(LinkList L); int length_Linklist(LinkList L); void Reverse_Linklist(LinkList L);/*菜單 */* 初始化空表 */* 尾插法建立單鏈表 */* 單鏈表遍歷 */* 計算單鏈表長度 */* 單鏈表逆置 */* 刪除值為偶數(shù)的結(jié)點 */void DelEven_Linklist(LinkList L);19Status Insert_Linklist(LinkList L, int x);Status Cr

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

30、LinkList La, LinkList &Lb); 全部為偶數(shù) */*鏈表La按值分解成兩個鏈表，La全部為奇數(shù)La 和和 LbLbLinkList.cpp#include "LinkList.h"void menu()printf("ttt單鏈表基本操作 nn");printf("ttt1.建立單鏈表 n");printf("ttt2.遍歷單鏈表 n");printf("ttt3.計算鏈表長 度 n");printf("ttt4.鏈表逆置 n ”)；printf(&quo

31、t;ttt5.刪除偶數(shù)節(jié) 點 n");printf("ttt6.生成值有序單 鏈 表 n");printf("ttt7.合并生成降序鏈表n");printf("ttt8. 合 并 生 成 升 序 鏈 表 n"); printf("ttt9. 分 解 鏈 表 n");printf("ttt0. 退 出 nn");/* 初始化空表 */Status Init_Linklist(LinkList &L)L=(LinkList)malloc(sizeof(Lnode);if(!L) r

32、eturn ERROR;L->next=NULL;return OK;/* 尾插法建立單鏈表 */Status Creat_Linklist(LinkList &L) int x;LinkList p,rear;Init_Linklist(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->n

33、ext = p;rear = p;rear->next = NULL;return OK;/* 單鏈表遍歷 */void Disp_Linklist(LinkList L)LinkList p;p = L->next; while(p)printf("%d ", p->data); p = p->next; printf("n");/* 計算單鏈表長度 */int length_Linklist(LinkList L)int count = 0; /*count 表示單鏈表長度 */ LinkList p;return count

34、;/* 單鏈表逆置 */void Reverse_Linklist(LinkList L)LinkList p, q ;/* 刪除值為偶數(shù)的結(jié)點 */void DelEven_Linklist(LinkList L)LinkList p, q;ERROR*/* 在有序單鏈表中插入元素，鏈表仍然有序，插入成功返回OK ，插入失敗返回Status Insert_Linklist(LinkList L, int x)/*創(chuàng)建非遞減有序單鏈表，創(chuàng)建成功返回 OK ，創(chuàng)建失敗返回 ERROR*/ Status CreatOrder_Linklist(LinkList &L)/*兩個非遞減有序單鏈

35、表La和Lb合并成一個非遞增有序鏈表Lc*/void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc)/*兩個非遞減有序單鏈表 La 和 Lb 合并成一個非遞減有序鏈表 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->

36、data <= pb->data)pc->next = pa; pc = pa; pa = pa->next;elsepc->next = pb; pc = pb; pb = pb->next;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 choi

37、ce, length;LinkList L, La, Lb, Lc;while(1)menu();printf(" 選擇你的操作： ");scanf("%d",&choice);switch(choice)case 1:if(Creat_Linklist(L)printf(" 單鏈表創(chuàng)建成功 n");elseprintf(" 單鏈表創(chuàng)建失敗 n"); break;case 2:Disp_Linklist(L);break;case 3:length = length_Linklist(L);printf(&

38、quot; 單鏈表長度為： %dn",length); break;case 4:Reverse_Linklist(L);printf(" 逆置后的鏈表為： n");Disp_Linklist(L);break;case 5:DelEven_Linklist(L);printf(" 新鏈表為： n");Disp_Linklist(L);break;case 6:if(CreatOrder_Linklist(L)printf(" 值有序鏈表為： n");Disp_Linklist(L);elseprintf(" 單鏈

39、表創(chuàng)建失敗 n");break;case 7:CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeDescend_Linklist(La, Lb, Lc);printf(" 合并后的新鏈表為： n");Disp_Linklist(Lc); break;case 8:CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeAscend_Linklist(La, Lb, Lc);printf(" 合并后的新鏈表為： n");Disp_Linkli

40、st(Lc); break;case 9:Creat_Linklist(L);Split_Linklist(L, Lb);printf(" 分裂后的新鏈表為： n");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)棧的初始化

41、、入棧、出棧操作。（ 2）采用鏈式存儲實現(xiàn)棧的初始化、入棧、出棧操作。（ 3）在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。（ 4）* 綜合訓(xùn)練：1） 堆棧操作合法性：假設(shè)以S和X分別表示入棧和出棧操作。如果根據(jù)一個僅由S和X構(gòu)成的序列，對一個空堆棧進行操作，相應(yīng)操作均可行（如沒有出現(xiàn)刪除時棧空）且最后狀態(tài) 也是?？?，則稱該序列是合法的堆棧操作序列。請編寫程序，輸入S 和 X 序列，判斷該序列是否合法。2）括號匹配檢驗：假設(shè)表達式中允許包括兩種括號：圓括號和方括號，其嵌套的順序隨意， 即（） 或（） 等為正確的格式， （） 或（） 等均為不正確格式。輸入一個表達式，判斷其 中的括號是否能正確

42、匹配。3）表達式轉(zhuǎn)換：算術(shù)表達式有前綴表示法、中綴表示法和后綴表示法等形式。日常使用的算術(shù)表達式是采用中綴表示法，即二元運算符位于兩個運算數(shù)中間。請設(shè)計程序?qū)⒅芯Y表達 式轉(zhuǎn)換為后綴表達式。輸入在一行中給出不含空格的中綴表達式，可包含+、-、*、 以及左右括號 （），表達式不超過 20 個字符。在一行中輸出轉(zhuǎn)換后的后綴表達式，要求不同對象 （運算數(shù)、運算符號）之間以空格分隔，但結(jié)尾不得有多余空格。實驗說明：1 類型定義順序棧示例#define MAX 100 / 棧的最大值typedef structSElemType *base；SElemType *top ；21實驗 04 隊列的基本操作i

43、nt stacksize；SqStack ；鏈棧示例typedef int ElemType; /元素類型typedef struct snodeSElemType data; struct snode *next;StackNode, *LinkStack;2算法 4 的每個子功能盡可能寫成函數(shù)形式。注意問題：1重點理解棧的算法思想，能夠根據(jù)實際情況選擇合適的存儲結(jié)構(gòu)。 2注意算法 4 的各個函數(shù)之間值的傳遞情況。3棧的算法是后續(xù)實驗的基礎(chǔ)（樹、圖、查找、排序等）。25實驗學(xué)時： 2 學(xué)時 實驗類型： 上機 背景知識 ： 循環(huán)隊列、鏈隊列，入隊、出隊。目的要求：1掌握隊列的思想及其存儲實現(xiàn)。

44、 2掌握隊列的常見算法的程序?qū)崿F(xiàn)。實驗內(nèi)容：（ 1） 采用順序存儲實現(xiàn)循環(huán)隊列的初始化、入隊、出隊操作。（ 2） 采用鏈式存儲實現(xiàn)隊列的初始化、入隊、出隊操作。（ 3） 在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。（ 4） *綜合訓(xùn)練：銀行排隊系統(tǒng)模擬 : 請用一個隊列來模擬銀行排隊系統(tǒng)，隊列中存儲序號。請設(shè)置一個菜單， 包括叫號和排號兩個選項。若選擇叫號，則輸出并刪除隊首元素；若選擇排號，則順序生成一 個序號，加入隊列，并輸出該序號和前面有多少人等候。實驗說明：1類型定義 循環(huán)隊列示例 #define MAXQSIZE 100 / 隊列的最大長度 typedef struct QElem

45、Type *base ；int front ；int rear；SqQueue ；鏈隊列示例typedef struct QNodeQElemType data;struct QNode *next;QNode, *QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;注意問題：1重點理解隊列的算法思想，能夠根據(jù)實際情況選擇合適的存儲結(jié)構(gòu)。 2隊列的算法是后續(xù)實驗的基礎(chǔ)（樹、圖、查找、排序等）。實驗 06 哈夫曼編碼實驗學(xué)時： 2 學(xué)時實驗類型： 上機背景知識 ： 二叉樹的存儲、建立、遍歷及其應(yīng)用。目的要求：1掌握二叉樹的

46、存儲實現(xiàn)。2掌握二叉樹的遍歷思想。 3掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。實驗內(nèi)容：1)從鍵盤上輸入數(shù)據(jù)，建立二叉鏈表。2)前序遍歷、中序遍歷、后序遍歷二叉樹：遞歸算法。3)前序遍歷、中序遍歷、后序遍歷二叉樹：非遞歸算法。4)借助隊列實現(xiàn)二叉樹的層次遍歷。5)在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。6)*綜合訓(xùn)練：家族關(guān)系查詢系統(tǒng)：建立家族關(guān)系數(shù)據(jù)庫，可以實現(xiàn)家族成員的添加，可以查詢家族成員的雙 親、祖先、兄弟、孩子和后代等信息。實驗說明：1類型定義 / 二叉鏈表存儲#define TElemType char / 元素類型typedef struct BiTNodeTElemType d

47、ata;struct BiTNode *lchild, *rchild; BiTNode, *BiTree;注意問題：1注意理解遞歸算法的執(zhí)行步驟。2注意字符類型數(shù)據(jù)在輸入時的處理。3重點理解如何利用棧結(jié)構(gòu)實現(xiàn)非遞歸算法。實驗學(xué)時： 4 學(xué)時實驗類型： 綜合型實驗背景知識 ： 二叉樹的應(yīng)用、哈夫曼樹。目的要求：掌握哈夫曼樹和哈夫曼編碼的基本思想和算法的程序?qū)崿F(xiàn)。實驗內(nèi)容：( 1)修理牧場：農(nóng)夫要修理牧場的一段柵欄，他測量了柵欄，發(fā)現(xiàn)需要N 塊木頭，每塊木頭長度為整數(shù) Li 個長度單位，于是他購買了一條很長的、能鋸成 N 塊的木頭，即該木頭的長度是 Li 的總和。但是農(nóng)夫自己沒有鋸子，請人鋸木頭

48、的酬金跟這段木頭的長度成正比。為簡單起見，不妨 就設(shè)酬金等于所鋸木頭的長度。例如，要將長度為 20 的木頭鋸成長度為 8、7 和 5 的三段，第 一次鋸木頭花費 20 ，將木頭鋸成 12 和 8；第二次鋸木頭花費 12，將長度為 12 的木頭鋸成 7 和 5，總花費為 32。如果第一次將木頭鋸成15 和 5，則第二次鋸木頭花費 15，總花費為 35(大于32)。請編寫程序幫助農(nóng)夫計算將木頭鋸成 N 塊的最少花費。首先輸入一個正整數(shù)N ( N< 104),表示要將木頭鋸成N塊。接著給出N個正整數(shù)Li(Li w 50，表示每段木塊的長度。輸出一個整數(shù)，即將木頭鋸成N塊的最少花費。例如：輸入：

49、84 5 1 2 1 3 1 1輸出：49* ( 2)壓縮軟件： 給定一篇文章，只含有英文大小寫字母和空格，以 .txt 格式存儲，統(tǒng)計該文件中各種字符的頻 率，對各字符進行 Huffman 編碼，將該文件翻譯成 Huffman 編碼文件，再將 Huffman 編碼文件 翻譯成源文件。實驗說明：1 參考類型定義/雙親孩子表示法typedef struct 27unsigned int weight;unsigned int parent, lchild, rchild; HTNode, *HuffmanTree;/ 動態(tài)分配數(shù)組存儲哈夫曼樹typedef char * * HuffmanCod

50、e; / 動態(tài)分配數(shù)組存儲哈夫曼編碼表注意問題：1遞歸算法的靈活應(yīng)用。2多級指針的使用。33實驗07圖的兩種存儲和遍歷實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：圖的存儲、遍歷及其應(yīng)用。目的要求：1 掌握圖的存儲思想及其存儲實現(xiàn)。2 掌握圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。實驗內(nèi)容：(1) 鍵盤輸入數(shù)據(jù)，分別建立一個有向圖和一個無向圖的鄰接表。(2) 輸出該鄰接表。(3) 在有向圖的鄰接表的基礎(chǔ)上計算各頂點的度，并輸出。(4) 采用鄰接表存儲實現(xiàn)無向圖的深度優(yōu)先遍歷。(5) 采用鄰接表存儲實現(xiàn)無向圖的廣度優(yōu)先遍歷。(6) 在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。(7) *綜合訓(xùn)練地

51、下迷宮探索：假設(shè)有一個地下通道迷宮，它的通道都是直的，而通道所有交叉點(包括通道 的端點)上都有一盞燈和一個開關(guān)。請問你如何從某個起點開始在迷宮中點亮所有的燈并回到 起點？輸入格式:輸入第一行給出三個正整數(shù)，分別表示地下迷宮的節(jié)點數(shù)N (1<NK 1000,表示通道所有交叉點和端點)、邊數(shù)M ( MK 3000，表示通道數(shù))和探索起始節(jié)點編號 S (節(jié)點從1到N編號)。 隨后的M行對應(yīng)M條邊(通道)，每行給出一對正整數(shù)，分別是該條邊直接連通的兩個節(jié)點 的編號。輸出格式：若可以點亮所有節(jié)點的燈，則輸出從S開始并以S結(jié)束的包含所有節(jié)點的序列，序列中相鄰的節(jié)點一定有邊(通道)；否則雖然不能點亮

52、所有節(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類型定義（鄰接表存儲）#define MAX_VERTEX_NUM 20/頂點最大個數(shù)typedef struct ArcNodeintadjvex;struct ArcNode *nextarc;intweig

53、ht; /邊的權(quán)值A(chǔ)rcNode; /表結(jié)點#define VertexType int /頂點元素類型typedef struct VNodeVertexType data;ArcNode *firstarc;VNode, AdjListMAX_VERTEX_NUM; /typedef structAdjList vertices;int vexnum, arcnum; / 頂點的實際數(shù)，邊的實際數(shù)int kind;ALGraph;2上述類型定義可以根據(jù)實際情況適當(dāng)調(diào)整。3算法 4、5 分別利用棧、隊列實現(xiàn)非遞歸算法。注意問題：1注意理解各算法實現(xiàn)時所采用的存儲結(jié)構(gòu)。2注意區(qū)別正、逆鄰接。實

54、驗 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）以有向圖的鄰接矩陣為基礎(chǔ)實現(xiàn)Dijkstra 算法輸出單源點到其它頂點的最短路徑。（6）在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。（7）*綜合訓(xùn)練：校園導(dǎo)航1）問題描述： 在給出校園各主要建筑的名稱

55、信息及有路線連通的建筑之間的距離（或行進時間）的基礎(chǔ)上， 利用校園導(dǎo)航系統(tǒng)計算出給定的起點到終點之間距離最近（或行進時間最短）的行進路線。信息。2）設(shè)計要求： 文件讀入或鍵盤方式讀入校園主要建筑信息及建筑間的距離（或行進時間）創(chuàng)建完地圖后，以文件形式保存，以免重復(fù)創(chuàng)建。計算出給定的起點到終點之間距離最近（或行進 時間最短）的行進路線，并輸出該路線（包括經(jīng)過哪些建筑）及其總距離（或總行進時間）。 實驗說明：1類型定義鄰接表存儲見實驗 07鄰接矩陣存儲示例#define MAX_VERTEX_NUM 20/頂點最大個數(shù)typedef enum DG, DN, UDG , UDN GraphKind

56、;typedef struct ArcCellVRType adj;int weight; /邊的權(quán)值A(chǔ)rcCell; AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum, arcnum; / 頂點的實際數(shù)，邊的實際數(shù) GraphKind kind;MGraph;注意問題：注意理解各算法實現(xiàn)時所采用的存儲結(jié)構(gòu)。實驗 09 二叉排序樹的基本操作實驗學(xué)時： 2 學(xué)時 實驗類型： 上機 背景知識： 樹表查找。目的要求：掌握二叉排序樹、 AVL 樹的查找、插入、刪除、建立算