數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(校正)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(校正)/數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(校正)《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書鄭州輕工業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)目錄前言.2實(shí)驗(yàn)01次序表的基本操作4實(shí)驗(yàn)02單鏈表的基本操作5實(shí)驗(yàn)03棧的基本操作7實(shí)驗(yàn)04隊(duì)列的基本操作8實(shí)驗(yàn)05二叉樹的基本操作9實(shí)驗(yàn)06哈夫曼編碼10實(shí)驗(yàn)07圖的兩種儲藏和遍歷11實(shí)驗(yàn)08最小生成樹、拓?fù)渑判蚝妥疃搪窂?12實(shí)驗(yàn)09二叉排序樹的基本操作13實(shí)驗(yàn)10哈希表的生成14實(shí)驗(yàn)11常用的內(nèi)部排序算法151數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)前言《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)相關(guān)專業(yè)的一門核心基礎(chǔ)課程，也是很多高校考研專業(yè)課之一。它主要介紹線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的儲藏實(shí)現(xiàn)，在此基礎(chǔ)上介紹一些典型算法及其時、空效率解析。這門課程的主要任務(wù)是培養(yǎng)學(xué)生的算法設(shè)計(jì)能力及優(yōu)異的程序設(shè)計(jì)習(xí)慣。經(jīng)過學(xué)習(xí)，要修業(yè)生可以掌握典型算法的設(shè)計(jì)思想及程序?qū)崿F(xiàn)，可以依照實(shí)責(zé)問題采用合適的儲藏方案，設(shè)計(jì)出簡潔、高效、合用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開發(fā)打下優(yōu)異的基礎(chǔ)。學(xué)習(xí)這門課程，習(xí)題和實(shí)驗(yàn)是兩個重點(diǎn)環(huán)節(jié)。學(xué)生理解算法，上機(jī)實(shí)驗(yàn)是最正確的路子之一。因此，實(shí)驗(yàn)環(huán)節(jié)的利害是學(xué)生能否學(xué)好《數(shù)據(jù)結(jié)構(gòu)》的重點(diǎn)。為了更好地配合學(xué)生實(shí)驗(yàn)，特編寫實(shí)驗(yàn)指導(dǎo)書。一、實(shí)驗(yàn)?zāi)康母玫睦斫馑惴ǖ乃枷?、培養(yǎng)編程能力。二、實(shí)驗(yàn)要求1、每次實(shí)驗(yàn)前學(xué)生必定依照實(shí)驗(yàn)內(nèi)容認(rèn)真準(zhǔn)備實(shí)驗(yàn)程序及調(diào)試時所需的輸入數(shù)據(jù)。2、在指導(dǎo)教師的幫助下可以完成實(shí)驗(yàn)內(nèi)容，得出正確的實(shí)驗(yàn)結(jié)果。3、實(shí)驗(yàn)結(jié)束后總結(jié)實(shí)驗(yàn)內(nèi)容、書寫實(shí)驗(yàn)報告。4、遵守實(shí)驗(yàn)室規(guī)章制度、不缺席、準(zhǔn)時上、下機(jī)。5、實(shí)驗(yàn)學(xué)時內(nèi)必定做數(shù)據(jù)結(jié)構(gòu)的相關(guān)內(nèi)容，不同樣意上網(wǎng)聊天或玩游戲，如發(fā)現(xiàn)上述現(xiàn)象，取消本次上機(jī)資格，平時成績扣10分。6、實(shí)驗(yàn)報告有一次不合格，扣5分，兩次以上不合格者，平時成績以零分記。三、實(shí)驗(yàn)環(huán)境VC++6.0或其他C++相關(guān)的編譯環(huán)境。四、說明1、本實(shí)驗(yàn)的全部算法中元素種類可以依照實(shí)質(zhì)需要選擇。2、實(shí)驗(yàn)題目中帶＊者為較高要求，學(xué)生可自選；其他部分為基本內(nèi)容，應(yīng)盡量完成（最少完成70%，否則實(shí)驗(yàn)不合格）。3、數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學(xué)考試的專業(yè)課之一，希望有志于考研的學(xué)生可以在學(xué)習(xí)過程中注意各種算法的理解，以便為考研做必然的準(zhǔn)備。五、實(shí)驗(yàn)報告的書寫要求1、明確實(shí)驗(yàn)的目的及要求;2、記錄實(shí)驗(yàn)的輸入數(shù)據(jù)和輸出結(jié)果;2數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)3、說明實(shí)驗(yàn)中出現(xiàn)的問題和解決過程;、寫出實(shí)驗(yàn)的領(lǐng)悟和實(shí)驗(yàn)過程中沒能解決的問題。六、成績考評方法1、期末考試占70分，閉卷。2、平時考評占30分。其中實(shí)驗(yàn)環(huán)節(jié)占20分（實(shí)驗(yàn)準(zhǔn)備、上機(jī)、報告、查收等）；平時占10分（出勤、作業(yè)、測試等）七、參照書目1、《數(shù)據(jù)結(jié)構(gòu)》（Ｃ語言版）嚴(yán)蔚敏等清華大學(xué)初版社2、《數(shù)據(jù)結(jié)構(gòu)題集》（C語言版）嚴(yán)蔚敏等清華大學(xué)初版社3、《數(shù)據(jù)結(jié)構(gòu)與算法解析——C語言描述》，MarkAllenWeiss著，機(jī)械工業(yè)初版社，20123數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)01次序表的基本操作實(shí)驗(yàn)學(xué)時：2學(xué)時背景知識：次序表的插入、刪除及應(yīng)用。目的要求：．掌握次序儲藏結(jié)構(gòu)的特點(diǎn)。．掌握次序儲藏結(jié)構(gòu)的常有算法。實(shí)驗(yàn)內(nèi)容：編寫一個完滿的程序，實(shí)現(xiàn)次序表的生成、插入、刪除、輸出等基本運(yùn)算。1）建立一個次序表，含有n個數(shù)據(jù)元素。2）輸出次序表及次序表的長度。（3）在次序表中刪除值為x的結(jié)點(diǎn)也許刪除給定地址i的結(jié)點(diǎn)。4）實(shí)現(xiàn)把該表中全部奇數(shù)排在偶數(shù)從前，即表的前面為奇數(shù)，后邊為偶數(shù)。5）將次序表按升序排序。6）輸入整型元素序列，利用有序表插入算法建立一個有序表。（7）*利用算法6建立兩個非遞減有序表A和B，并把它們合并成一個非遞減有序表C。（8）在主函數(shù)中設(shè)計(jì)一個簡單的菜單，分別測試上述算法。綜合訓(xùn)練：利用次序表實(shí)現(xiàn)一個班級學(xué)生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等）。實(shí)驗(yàn)說明：1．算法1至算法7可以以頭文件的方式儲藏，源文件實(shí)現(xiàn)該頭文件的包含即可。2．儲藏定義#defineMAXSIZE100//表中元素的最大個數(shù)typedefintElemType;//元素種類typedefstruct{ElemType*elem;//線性表intlength;//表的實(shí)質(zhì)長度intlistsize;//當(dāng)前分配的儲藏容量}SqList;//次序表的種類名．建立次序表時可利用隨機(jī)函數(shù)自動產(chǎn)生數(shù)據(jù)。注意問題：1、插入、刪除時元素的搬動原因、方向及先后次序。2、理解函數(shù)形參加實(shí)參的傳達(dá)關(guān)系。4數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)02單鏈表的基本操作實(shí)驗(yàn)學(xué)時：2學(xué)時背景知識：單鏈表的插入、刪除及應(yīng)用。目的要求：1．掌握單鏈表的儲藏特點(diǎn)及其實(shí)現(xiàn)。2．掌握單鏈表的插入、刪除算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：編寫一個完滿的程序，實(shí)現(xiàn)單鏈表的生成、插入、刪除、輸出等基本操作。1）隨機(jī)產(chǎn)生或鍵盤輸入一組元素，建立一個帶頭結(jié)點(diǎn)的單向鏈表（無序）。2）計(jì)算單鏈表的長度，遍歷單鏈表。3）把單鏈表中的元素逆置（不同樣意申請新的結(jié)點(diǎn)空間）。4）在單鏈表中刪除全部值為偶數(shù)的元素結(jié)點(diǎn)。5）編寫在非遞減有序單鏈表中插入一個元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個非遞減有序單鏈表。6）*利用算法5建立兩個非遞減有序單鏈表，爾后合并成一個非遞加有序鏈表。7）*利用算法5建立兩個非遞減有序單鏈表，爾后合并成一個非遞減有序鏈表。8）*利用算法1建立的鏈表，實(shí)現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的儲藏空間）。9）*采用單鏈表實(shí)現(xiàn)一元多項(xiàng)式的儲藏并實(shí)現(xiàn)兩個多項(xiàng)式相加并輸出結(jié)果。10）在主函數(shù)中設(shè)計(jì)一個簡單的菜單，分別調(diào)試上述算法。11）*綜合訓(xùn)練：1）利用鏈表實(shí)現(xiàn)一個班級學(xué)生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等，并可以實(shí)現(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ù)起，則出列的次序?yàn)?，8，5，2，1，3，7，6。試編寫程序確定出列的次序。要求用不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表作為儲藏結(jié)構(gòu)模擬此過程，依照出列次序打印出個人編號。實(shí)驗(yàn)說明：1．種類定義#include"stdio.h"typedefintElemType;//元素種類typedefstructnode{ElemTypedata;structnode*next;}LinkNode,*LinkList;2．為了算法實(shí)現(xiàn)簡單，建議采用帶頭結(jié)點(diǎn)的單鏈表。5數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)注意問題：1．重點(diǎn)理解鏈?zhǔn)絻Σ氐奶攸c(diǎn)及指針的含義。2．注意比較次序儲藏與鏈?zhǔn)絻Σ氐母髯蕴攸c(diǎn)。3．注意比較帶頭結(jié)點(diǎn)、無頭結(jié)點(diǎn)鏈表實(shí)現(xiàn)插入、刪除算法時的差異。4．單鏈表的操作是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，必然要注意對這部分的常有算法的理解。6數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)03棧的基本操作實(shí)驗(yàn)學(xué)時：２學(xué)時背景知識：次序棧、鏈棧，入棧、出棧。目的要求：．掌握棧的思想及其儲藏實(shí)現(xiàn)。．掌握棧的常有算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：1）采用次序儲藏實(shí)現(xiàn)棧的初始化、入棧、出棧操作。2）采用鏈?zhǔn)絻Σ貙?shí)現(xiàn)棧的初始化、入棧、出棧操作。3）在主函數(shù)中設(shè)計(jì)一個簡單的菜單，分別測試上述算法。4）*綜合訓(xùn)練：1)利用棧實(shí)現(xiàn)表達(dá)式求值算法。利用棧實(shí)現(xiàn)迷宮求解。實(shí)驗(yàn)說明：．種類定義次序棧示例#defineMAX100//棧的最大值typedefstruct{SElemType*base；SElemType*top；intstacksize；}SqStack；鏈棧示例typedefintElemType;//元素種類typedefstructsnode{SElemTypedata;structsnode*next;}StackNode,*LinkStack;2．算法4的每個子功能盡可能寫成函數(shù)形式。注意問題：1．重點(diǎn)理解棧的算法思想，可以依照實(shí)質(zhì)情況選擇合適的儲藏結(jié)構(gòu)。2．注意算法4的各個函數(shù)之間值的傳達(dá)情況。3．棧的算法是后續(xù)實(shí)驗(yàn)的基礎(chǔ)（樹、圖、查找、排序等）。7數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)04隊(duì)列的基本操作實(shí)驗(yàn)學(xué)時：２學(xué)時背景知識：循環(huán)隊(duì)列、鏈隊(duì)列，入隊(duì)、出隊(duì)。目的要求：．掌握隊(duì)列的思想及其儲藏實(shí)現(xiàn)。．掌握隊(duì)列的常有算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：1）采用次序儲藏實(shí)現(xiàn)循環(huán)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。2）采用鏈?zhǔn)絻Σ貙?shí)現(xiàn)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。3）在主函數(shù)中設(shè)計(jì)一個簡單的菜單，分別測試上述算法。實(shí)驗(yàn)說明：1．種類定義循環(huán)隊(duì)列示例#defineMAXQSIZE100//隊(duì)列的最大長度typedefstruct{QElemType*base；intfront；intrear；}SqQueue；鏈隊(duì)列示例typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;注意問題：1．重點(diǎn)理解隊(duì)列的算法思想，可以依照實(shí)質(zhì)情況選擇合適的儲藏結(jié)構(gòu)。2．隊(duì)列的算法是后續(xù)實(shí)驗(yàn)的基礎(chǔ)（樹、圖、查找、排序等）。8數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)05二叉樹的基本操作實(shí)驗(yàn)學(xué)時：2學(xué)時背景知識：二叉樹的儲藏、建立、遍歷及其應(yīng)用。目的要求：1．掌握二叉樹的儲藏實(shí)現(xiàn)。2．掌握二叉樹的遍歷思想。3．掌握二叉樹的常有算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：1）從鍵盤上輸入數(shù)據(jù)，建立二叉鏈表。2）前序遍歷、中序遍歷、后序遍歷二叉樹：遞歸算法。3）前序遍歷、中序遍歷、后序遍歷二叉樹：非遞歸算法。4）借助隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷。5）在主函數(shù)中設(shè)計(jì)一個簡單的菜單，分別調(diào)試上述算法。實(shí)驗(yàn)說明：１．種類定義//二叉鏈表儲藏#defineTElemTypechar//元素種類typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;注意問題：．注意理解遞歸算法的執(zhí)行步驟。．注意字符種類數(shù)據(jù)在輸入時的辦理。．重點(diǎn)理解如何利用棧結(jié)構(gòu)實(shí)現(xiàn)非遞歸算法。9數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)06哈夫曼編碼實(shí)驗(yàn)學(xué)時：4學(xué)時（綜合型實(shí)驗(yàn)）背景知識：二叉樹的應(yīng)用、哈夫曼樹。目的要求：掌握哈夫曼樹和哈夫曼編碼的基本思想和算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：1）為N個權(quán)值設(shè)計(jì)哈夫曼編碼。2）試編寫一個將百分制分?jǐn)?shù)變換為五級分制的程序。要求其時間性能盡可能好（即平均比較次數(shù)盡可能少）。假設(shè)學(xué)生成績的分布情況以下：分?jǐn)?shù)0-5960-6970-7980-8990-100比率0.050.150.400.300.10實(shí)驗(yàn)說明：１．種類定義//雙親孩子表示法typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動向分配數(shù)組儲藏哈夫曼樹typedefchar**HuffmanCode;//動向分配數(shù)組儲藏哈夫曼編碼表注意問題：．遞歸算法的靈便應(yīng)用。．多級指針的使用。10數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)07圖的兩種儲藏和遍歷實(shí)驗(yàn)學(xué)時：2學(xué)時背景知識：圖的儲藏、遍歷及其應(yīng)用。目的要求：１．掌握圖的儲藏思想及其儲藏實(shí)現(xiàn)。２．掌握圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：1）鍵盤輸入數(shù)據(jù)，分別建立一個有向圖和一個無向圖的毗鄰表。2）輸出該毗鄰表。3）在有向圖的毗鄰表的基礎(chǔ)上計(jì)算各極點(diǎn)的度，并輸出。4）采用毗鄰表儲藏實(shí)現(xiàn)無向圖的深度優(yōu)先遍歷。5）采用毗鄰表儲藏實(shí)現(xiàn)無向圖的廣度優(yōu)先遍歷。6）在主函數(shù)中設(shè)計(jì)一個簡單的菜單，分別調(diào)試上述算法。實(shí)驗(yàn)說明：１．種類定義（毗鄰表儲藏）#defineMAX_VERTEX_NUM20//極點(diǎn)最大個數(shù)typedefstructArcNode{intadjvex;structArcNode*nextarc;intweight;//邊的權(quán)值}ArcNode;//表結(jié)點(diǎn)#defineVertexTypeint//極點(diǎn)元素種類typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];//typedefstruct{AdjListvertices;intvexnum,arcnum;//極點(diǎn)的實(shí)質(zhì)數(shù)，邊的實(shí)質(zhì)數(shù)intkind;}ALGraph;２．上述種類定義可以依照實(shí)質(zhì)情況合適調(diào)整。３．算法4、5分別利用棧、隊(duì)列實(shí)現(xiàn)非遞歸算法。注意問題：１．注意理解各算法實(shí)現(xiàn)時所采用的儲藏結(jié)構(gòu)。２．注意差異正、逆毗鄰。11數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)08最小生成樹、拓?fù)渑判蚝妥疃搪窂綄?shí)驗(yàn)學(xué)時：2學(xué)時背景知識：圖的儲藏、遍歷及其應(yīng)用。目的要求：掌握圖的常有應(yīng)用算法的思想及其程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：1）鍵盤輸入數(shù)據(jù)，分別建立一個有向圖和的毗鄰表和一個無向圖的毗鄰矩陣。2）輸出該毗鄰表和毗鄰矩陣。3）以有向圖的毗鄰表為基礎(chǔ)輸出它的拓?fù)渑判蛐蛄小?）以無向圖的毗鄰矩陣為基礎(chǔ)實(shí)現(xiàn)最小生成樹的PRIM算法。5）以有向圖的毗鄰矩陣為基礎(chǔ)實(shí)現(xiàn)Dijkstra算法輸出單源點(diǎn)到其他極點(diǎn)的最短路徑。6）在主函數(shù)中設(shè)計(jì)一個簡單的菜單，分別調(diào)試上述算法。實(shí)驗(yàn)說明：１．種類定義毗鄰表儲藏見實(shí)驗(yàn)07毗鄰矩陣儲藏示例#defineMAX_VERTEX_NUM20//極點(diǎn)最大個數(shù)typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcCell{VRTypeadj;intweight;//邊的權(quán)值}ArcCell;AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;//極點(diǎn)的實(shí)質(zhì)數(shù)，邊的實(shí)質(zhì)數(shù)GraphKindkind;}MGraph;注意問題：注意理解各算法實(shí)現(xiàn)時所采用的儲藏結(jié)構(gòu)。12數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)09二叉排序樹的基本操作實(shí)驗(yàn)學(xué)時：2學(xué)時背景知識：樹表查找。目的要求：掌握二叉排序樹、AVL樹的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：1）隨機(jī)產(chǎn)生一組重點(diǎn)字，利用二叉排序樹的插入算法建立二叉排序樹，爾后刪除某一指定重點(diǎn)字元素。2）*建立AVL樹并實(shí)現(xiàn)刪除某一指定重點(diǎn)字元素。實(shí)驗(yàn)說明：．儲藏定義拜會實(shí)驗(yàn)05二叉鏈表的儲藏。．各種重點(diǎn)字?jǐn)?shù)據(jù)輸入可利用隨機(jī)函數(shù)自動產(chǎn)生，以便節(jié)約上機(jī)時間。注意問題：．注意建立二叉排序樹時同樣元素的辦理。．注意理解動向查找看法。13數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)10哈希表的生成實(shí)驗(yàn)學(xué)時：2學(xué)時背景知識：哈希查找。目的要求：掌握哈希儲藏結(jié)構(gòu)的思想，能選擇合適的哈希函數(shù)，實(shí)現(xiàn)不同樣矛盾辦理方法的哈希表的查找、建立。實(shí)驗(yàn)內(nèi)容：1）設(shè)計(jì)哈希函數(shù)及辦理矛盾的方法；2）鍵盤輸入數(shù)據(jù)，利用設(shè)計(jì)的哈希函數(shù)及線性探測法