《數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)》任務(wù)書

1、數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)任務(wù)書實(shí)驗(yàn)一動態(tài)鏈表的設(shè)計與應(yīng)用一、實(shí)驗(yàn)?zāi)康?、要?、掌握使用VC 6.0上機(jī)調(diào)試線性表的基本方法;2、掌握線性表的基本操作:插入、刪除、查找以及線性表合并等運(yùn)算在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的運(yùn)算。二、實(shí)驗(yàn)內(nèi)容1.輸入一組學(xué)生信息,建立一個單鏈表。2.遍歷該鏈表,輸出學(xué)生信息。3.查找某特定的學(xué)生,查找成功返回1,否則返回0。4.編寫在非遞減有序鏈表中插入一個元素使鏈表元素仍有序的函數(shù),并利用該函數(shù)建立一個非遞減有序單向鏈表。5.利用算法4建立兩個非遞減有序單向鏈表,然后合并成一個非遞增鏈表。*6.采用單向鏈表實(shí)現(xiàn)一元多項(xiàng)式的存儲并實(shí)現(xiàn)兩個多項(xiàng)式相加并輸出結(jié)果。7.編寫一個

2、主函數(shù),調(diào)試上述算法。*8.綜合訓(xùn)練:利用鏈表實(shí)現(xiàn)一個班級學(xué)生信息管理(數(shù)據(jù)錄入、插入、刪除、排序、查找等,并能夠?qū)崿F(xiàn)將數(shù)據(jù)存儲到文件中三、實(shí)驗(yàn)說明1.存儲定義#define MAXSIZE 100 /表中元素的最大個數(shù)typedef int ElemType;/元素類型typedef struct listElemType elemMAXSIZE;/靜態(tài)線性表int length; /表的實(shí)際長度SqList;/順序表的類型名2.建立順序表時可利用隨機(jī)函數(shù)自動產(chǎn)生數(shù)據(jù)。四、注意問題1.插入、刪除時元素的移動原因、方向及先后順序。2.了解不同的函數(shù)形參與實(shí)參的傳遞關(guān)系。一、實(shí)驗(yàn)?zāi)康?、要?.掌

3、握棧、隊列的思想及其存儲實(shí)現(xiàn)。2.掌握棧、隊列的常見算法的程序?qū)崿F(xiàn)。二、實(shí)驗(yàn)內(nèi)容1.采用鏈?zhǔn)酱鎯?shí)現(xiàn)棧的初始化、入棧、出棧操作。2.采用順序存儲實(shí)現(xiàn)棧的初始化、入棧、出棧操作。3.采用鏈?zhǔn)酱鎯?shí)現(xiàn)隊列的初始化、入隊、出隊操作。4.采用順序存儲實(shí)現(xiàn)循環(huán)隊列的初始化、入隊、出隊操作。5.在主函數(shù)中設(shè)計一個簡單的菜單,分別測試上述算法。*6.綜合訓(xùn)練:1利用棧實(shí)現(xiàn)表達(dá)式求值算法。2利用棧實(shí)現(xiàn)迷宮求解。三、實(shí)驗(yàn)說明1.基本要求:實(shí)現(xiàn)算法1、3或算法2、4即可。2.類型定義順序棧示例#define MAX 100 /棧的最大值typedef structElemType *base;int top;Sq

4、Stack;順序隊列示例#define MAX 100 /隊列的最大長度typedef structElemType *base;int front,rear;SqQueue;3.算法6的每個子功能盡可能寫成函數(shù)形式。四、注意問題1.重點(diǎn)理解棧、隊列的算法思想,能夠根據(jù)實(shí)際情況選擇合適的存儲結(jié)構(gòu)。2.注意算法6的各個函數(shù)之間值的傳遞情況。3.棧、隊列的算法是后續(xù)實(shí)驗(yàn)的基礎(chǔ)(廣義表、樹、圖、查找、排序等。一、實(shí)驗(yàn)?zāi)康?、要?.進(jìn)一步掌握指針變量的含義。2.掌握二叉樹的結(jié)構(gòu)特征,以及各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍。3.掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。4.掌握二叉樹的存儲實(shí)現(xiàn)。5.掌握二叉

5、樹的遍歷思想。6.掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。二、實(shí)驗(yàn)內(nèi)容1.輸入字符序列,建立二叉樹。2.中序遍歷二叉樹:遞歸算法。3.中序遍歷二叉樹:非遞歸算法。(最好也能實(shí)現(xiàn)先序,后序非遞歸算法4.求二叉樹的高度 。5.求二叉樹的葉子個數(shù)。*6.將二叉鏈表視為森林的孩子兄弟鏈表,計算森林中葉子個數(shù)。*7.建立中序線索二叉樹,并實(shí)現(xiàn)中序遍歷。8.借助隊列實(shí)現(xiàn)二叉樹的層次遍歷。9.在主函數(shù)中設(shè)計一個簡單的菜單,分別調(diào)試上述算法。三、實(shí)驗(yàn)說明1.類型定義 /二叉鏈表存儲#define ElemType char/元素類型typedef struct BiTNodeElemType data;struct

6、BiTNode *lchild,*rchild;BiTNode,*BiTree;2.元素類型可以根據(jù)實(shí)際情況選取。四、注意問題1.注意理解遞歸算法的執(zhí)行步驟。2.注意字符類型數(shù)據(jù)在輸入時的處理。3.重點(diǎn)理解如何利用棧結(jié)構(gòu)實(shí)現(xiàn)非遞歸算法。實(shí)驗(yàn)四赫夫曼編碼與壓縮一、實(shí)驗(yàn)?zāi)康?、要求熟練掌握二叉樹?yīng)用(Huffman編碼的基本算法實(shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容1. 統(tǒng)計字符串中字符的種類以及各類字符的個數(shù)的函數(shù)2. 實(shí)現(xiàn)構(gòu)造Huffman樹的函數(shù)3. 實(shí)現(xiàn)Huffman編碼的函數(shù)4. 建立正文的編碼文件的函數(shù)5.代碼文件的譯碼函數(shù)6.在主函數(shù)中設(shè)計一個簡單的菜單,分別調(diào)試上述算法。7. 綜合訓(xùn)練:輸入一段文本, 統(tǒng)

7、計其中字符出現(xiàn)頻率, 設(shè)計實(shí)現(xiàn)相應(yīng)的Huffman樹和Huffman碼, 并完成對該段文本的編碼與譯碼。三、實(shí)驗(yàn)說明typedef struct int weight; /權(quán)值int lchild , rchild , parent; /左右孩子及雙親指針HTNode; /樹中結(jié)點(diǎn)類型typedef HTNode HuffmanTreem+1; /0號單元不用實(shí)驗(yàn)五最短路徑算法的實(shí)現(xiàn)與應(yīng)用一、實(shí)驗(yàn)?zāi)康?、要?.掌握圖的存儲思想及其存儲實(shí)現(xiàn)。2.掌握圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。3.掌握圖的常見應(yīng)用算法的思想及其程序?qū)崿F(xiàn)。二、實(shí)驗(yàn)內(nèi)容1.鍵盤輸入數(shù)據(jù),建立一個有向圖的鄰接表。2.輸

8、出該鄰接表。3.以有向圖的鄰接表為基礎(chǔ)實(shí)現(xiàn)輸出它的拓?fù)渑判蛐蛄小?.采用鄰接表存儲實(shí)現(xiàn)無向圖的深度優(yōu)先非遞歸遍歷。5.采用鄰接表存儲實(shí)現(xiàn)無向圖的廣度優(yōu)先遍歷。6.采用鄰接矩陣存儲實(shí)現(xiàn)無向圖的最小生成樹的PRIM算法。7.在主函數(shù)中設(shè)計一個簡單的菜單,分別調(diào)試上述算法。8.綜合訓(xùn)練:以全國主要城市為圖的頂點(diǎn), 鐵路連接為圖的邊, 距離作為加權(quán), 設(shè)計完成一個最短路徑自動查找系統(tǒng). 輸入為出發(fā)城市和目標(biāo)城市, 輸出為最短路徑和距離。進(jìn)階:加入中國地圖作為背景,出發(fā)城市和目標(biāo)城市采用鼠標(biāo)點(diǎn)擊輸入。三、實(shí)驗(yàn)說明1.類型定義(鄰接表存儲#define MAX_VERTEX_NUM 8 /頂點(diǎn)最大個數(shù)ty

9、pedef struct ArcNodeint adjvex;struct ArcNode *nextarc;int weight; /邊的權(quán)ArcNode; /表結(jié)點(diǎn)#define VertexType int /頂點(diǎn)元素類型typedef struct VNodeint degree,indegree;/頂點(diǎn)的度,入度VertexType data;ArcNode *firstarc;VNode/*頭結(jié)點(diǎn)*/,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;/頂點(diǎn)的實(shí)際數(shù),邊的實(shí)際數(shù)ALGraph

10、;2.上述類型定義可以根據(jù)實(shí)際情況適當(dāng)調(diào)整。實(shí)驗(yàn)六 內(nèi)部排序算法的實(shí)現(xiàn)與比較 一、實(shí)驗(yàn)?zāi)康?、要?掌握常見的排序算法的思想及其適用條件。 掌握常見的排序算法的程序?qū)崿F(xiàn)。 二、實(shí)驗(yàn)內(nèi)容 輸入一組關(guān)鍵字序列分別實(shí)現(xiàn)下列排序: 1.實(shí)現(xiàn)簡單選擇排序、直接插入排序和冒泡排序。 2.實(shí)現(xiàn)希爾排序算法。 3.實(shí)現(xiàn)快速排序算法。 4.實(shí)現(xiàn)堆排序算法。 5.快速排序的非遞歸算法。 *6.實(shí)現(xiàn)折半插入排序。 *7.采用鏈?zhǔn)酱鎯?shí)現(xiàn)簡單選擇排序、直接插入排序和冒泡排序。 8.在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。 9綜合訓(xùn)練：采用幾組不同數(shù)據(jù)測試各個排序算法的性能（比較次數(shù)和移動次數(shù)） 。 三、實(shí)驗(yàn)說明

11、 1類型定義 #define MAXSIZE 100 /*參加排序元素的最大個數(shù)*/ typedef struct list int key; RedType; typedef struct RedType rMAXSIZE+1; int length; /*參加排序元素的實(shí)際個數(shù)*/ SqList; 2算法可以借助棧實(shí)現(xiàn)。 四、注意問題 1在 RedType 中增加一個數(shù)據(jù)項(xiàng)驗(yàn)證各種排序算法的穩(wěn)定性。 2注意理解各種算法的思想、了解算法的適用情況及時間復(fù)雜度，能夠根據(jù)實(shí)際情況選 擇合適的排序方法。 6 實(shí)驗(yàn)七 一、實(shí)驗(yàn)?zāi)康?、要?查找算法的實(shí)現(xiàn) 1掌握折半查找算法的思想及程序?qū)崿F(xiàn)。 2掌握二

12、叉排序樹、B 樹的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)。 3掌握散列存儲結(jié)構(gòu)的思想，實(shí)現(xiàn)不同沖突處理方法的散列表的查找、建立。 二、實(shí)驗(yàn)內(nèi)容 1利用實(shí)驗(yàn)一建立有序表，采用折半查找實(shí)現(xiàn)某一已知的關(guān)鍵字的查找。 2隨機(jī)產(chǎn)生一組關(guān)鍵字，利用二叉排序樹的插入算法建立二叉排序樹，然后刪除某一 指定關(guān)鍵字元素。 3建立 B 樹并實(shí)現(xiàn)刪除某一指定關(guān)鍵字元素。 4 已知散列函數(shù)為 H(key=key%p 為自定的常數(shù)） 沖突處理方法分別為線性探測法、 （p ， 外拉鏈法實(shí)現(xiàn)散列表的建立（利用插入算法實(shí)現(xiàn)） 。 三、實(shí)驗(yàn)說明 1存儲定義（散列表的外拉鏈法） #define n 9 typedef struct node int key; struct node *next; NODE; N