數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)試驗(yàn)指導(dǎo)書

1、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)驗(yàn)指導(dǎo)書西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院計(jì)算機(jī)系2019.2數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)是計(jì)算機(jī)類相關(guān)專業(yè)的一門核心基礎(chǔ)課程，也是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，更是考研專業(yè)課之一。主要介紹線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)、集合四種基本邏輯結(jié)構(gòu)及存儲(chǔ)實(shí)現(xiàn)，在此基礎(chǔ)上介紹一些典型的算法設(shè)計(jì)技術(shù)和時(shí)間效率分析。課程的主要任務(wù)是培養(yǎng)學(xué)生的算法設(shè)計(jì)能力及良好的程序設(shè)計(jì)習(xí)慣。通過學(xué)習(xí)，要求學(xué)生掌握典型算法的設(shè)計(jì)思想及程序?qū)崿F(xiàn)，能夠根據(jù)實(shí)際問題選取合適的存儲(chǔ)方案設(shè)計(jì)出簡潔、高效、實(shí)用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開發(fā)打下良好的基礎(chǔ)。學(xué)習(xí)該課程，實(shí)驗(yàn)是一個(gè)關(guān)鍵的環(huán)節(jié)；在理解算法的基礎(chǔ)上，上機(jī)實(shí)驗(yàn)是最佳途徑。

2、因此，實(shí)驗(yàn)環(huán)節(jié)的好壞是能否學(xué)好本課程的關(guān)鍵。為了更好地配合學(xué)生實(shí)驗(yàn)，特編寫本實(shí)驗(yàn)指導(dǎo)書。第1章實(shí)驗(yàn)指導(dǎo)1.1 實(shí)驗(yàn)意義實(shí)驗(yàn)是對(duì)學(xué)生的一種全面綜合訓(xùn)練。是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。通常，實(shí)驗(yàn)題中的問題比平時(shí)的習(xí)題復(fù)雜得多，也更接近實(shí)際。實(shí)驗(yàn)著眼于原理與應(yīng)用的結(jié)合點(diǎn)，使學(xué)生學(xué)會(huì)如何把書上學(xué)到的知識(shí)用于解決實(shí)際問題，培養(yǎng)軟件工作所需要的動(dòng)手能力；另一方面，能使書上知識(shí)變“活”，起到深化理解和靈活掌握教學(xué)內(nèi)容的目的。平時(shí)的練習(xí)較偏重于如何編寫功能單一的“小”算法，而實(shí)驗(yàn)題是軟件設(shè)計(jì)的綜合訓(xùn)練，包括問題分析、總體結(jié)構(gòu)設(shè)計(jì)、用戶界面設(shè)計(jì)、程序設(shè)計(jì)基本技能和技巧，多人合作，以至

3、一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，還有很重要的一點(diǎn)是：機(jī)器是比任何教師都嚴(yán)厲的檢查者。1.2 實(shí)驗(yàn)步驟常用軟件開發(fā)方法，是將軟件開發(fā)過程劃分為分析、設(shè)計(jì)、實(shí)現(xiàn)和維護(hù)四個(gè)階段。雖然數(shù)據(jù)結(jié)構(gòu)課程中的實(shí)驗(yàn)題目遠(yuǎn)不如實(shí)際問題中的復(fù)雜程度高，但為培養(yǎng)一個(gè)軟件工作者所應(yīng)具備的科學(xué)工作方法和作風(fēng)，也應(yīng)該遵循以下五個(gè)步驟來完成實(shí)驗(yàn)題目：1.問題分析和任務(wù)定義設(shè)計(jì)之前，首先應(yīng)該充分分析和理解問題，明確問題要求做什么，限制條件是什么等。本步驟強(qiáng)調(diào)的是做什么，而不是怎么做。對(duì)問題的描述應(yīng)該避開算法和所涉及的數(shù)據(jù)類型，而對(duì)所需完成的任務(wù)作出明確的回答。例如：輸入數(shù)據(jù)的類型、值的范圍以及輸入的形式；輸出數(shù)

4、據(jù)的類型、值的范圍及輸出的形式；若是會(huì)話式的輸入，那么結(jié)束標(biāo)志是什么，是否接受非法的輸入，對(duì)非法輸入的回答方式是什么等。還應(yīng)為調(diào)試程序準(zhǔn)備好測試數(shù)據(jù)，包括合法的輸入數(shù)據(jù)和非法形式的輸入數(shù)據(jù)。2 .邏輯設(shè)計(jì)和詳細(xì)設(shè)計(jì)邏輯設(shè)計(jì)，定義相應(yīng)的數(shù)據(jù)類型，并按以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序和各個(gè)抽象數(shù)據(jù)類型。詳細(xì)設(shè)計(jì)，定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)，寫出各個(gè)函數(shù)的偽碼算法。在這個(gè)過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，數(shù)據(jù)操作的規(guī)格說明盡可能明確具體。作為邏輯設(shè)計(jì)的結(jié)果，應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)操作的功能說明)

5、，各主要模塊的算法，畫出模塊之間的調(diào)用關(guān)系圖。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和操作的進(jìn)一步求精，寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，寫出函數(shù)形式的偽碼算法。在求精的過程中，應(yīng)該盡量避免陷入具體編程語言的語法細(xì)節(jié)，不必過早給出輔助的數(shù)據(jù)結(jié)構(gòu)和局部變量等。注：設(shè)計(jì)不是編碼。3 .編碼實(shí)現(xiàn)和靜態(tài)檢查編碼是把詳細(xì)設(shè)計(jì)結(jié)果編寫為具體的程序。在上機(jī)之前，嚴(yán)格的靜態(tài)檢查是必不可少的。靜態(tài)檢查的通常做法如下：(1) 用設(shè)計(jì)好的測試數(shù)據(jù)，逐步執(zhí)行程序(逐個(gè)測試每一個(gè)模塊的正確性)；(2) 需深入理解程序的執(zhí)行邏輯，再加入一些注解和斷言。4 .上機(jī)準(zhǔn)備和上機(jī)調(diào)試上機(jī)準(zhǔn)備包括以下幾個(gè)方面：(1)注意同一種高級(jí)語言不同版本之間的

6、語法差別。(2)熟悉語言的集成開發(fā)環(huán)境IDE(參閱用戶手冊)，尤其熟悉常用操作的快捷鍵。(3)掌握調(diào)試工具的用法，設(shè)計(jì)測試數(shù)據(jù)并手工執(zhí)行得出正確結(jié)果。(4)上機(jī)調(diào)試程序時(shí)要帶該語言的教材、參考手冊。調(diào)試最好逐個(gè)模塊進(jìn)行，自底向上即先調(diào)試低層的函數(shù)；調(diào)試過程中借助開發(fā)環(huán)境提供的各種調(diào)試功能，提高調(diào)試效率。調(diào)試中遇到的各種異?，F(xiàn)象往往是預(yù)料不到的，此時(shí)應(yīng)確定疑點(diǎn)，通過修改程序來證實(shí)或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成風(fēng)格良好的源程序清單和執(zhí)行結(jié)果。5.撰寫實(shí)驗(yàn)報(bào)告按實(shí)驗(yàn)報(bào)告的具體要求和規(guī)范撰寫。1.3 實(shí)驗(yàn)報(bào)告按照西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院上機(jī)實(shí)驗(yàn)報(bào)告要求撰寫實(shí)驗(yàn)報(bào)告。1.4 實(shí)驗(yàn)

7、考核實(shí)驗(yàn)成績構(gòu)成，如下：編程技術(shù)：30%測試分析：20%實(shí)驗(yàn)報(bào)告：50%第2章實(shí)驗(yàn)內(nèi)容2.1實(shí)驗(yàn)1線性表應(yīng)用一、順序表目的要求1 .掌握線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)。2 .掌握線性表順序存儲(chǔ)結(jié)構(gòu)的常見算法。實(shí)驗(yàn)內(nèi)容1 .輸入一組整型元素序列（不少于10個(gè)），建立順序表。2 .在該順序表中進(jìn)行順序查找某一元素，查找成功返回1,否則返回0。3 .判斷該順序表中元素是否對(duì)稱，對(duì)稱返回1,否則返回0。4 .實(shí)現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前，即表的前面為奇數(shù)，后面為偶數(shù)。5 .輸入整型元素序列（不少于10個(gè)），利用有序表插入算法建立一個(gè)有序表。6 .利用算法5建立兩個(gè)非遞減有序表，并把它們合并成一個(gè)非遞減有

8、序表。7 .在主函數(shù)中設(shè)計(jì)一個(gè)簡單菜單，調(diào)用上述算法。實(shí)驗(yàn)說明1 .算法1至算法6的有關(guān)函數(shù)用頭文件方式存儲(chǔ)，主函數(shù)包含該頭文件。2 .存儲(chǔ)定義constintMAXSIZE=15;/表中元素的最大個(gè)數(shù)typedefintElemType;/元素類型typedefstructlistElemTypeelemMAXSIZE;/靜態(tài)分配intlength;/表的實(shí)際長度SqList;/順序表的類型名3 .建立順序表時(shí)，利用隨機(jī)函數(shù)自動(dòng)產(chǎn)生數(shù)據(jù)。二、單向鏈表目的要求1 .掌握單鏈表的存儲(chǔ)特點(diǎn)及其實(shí)現(xiàn)。2 .掌握單鏈表的插入與刪除算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容1 .隨機(jī)產(chǎn)生或鍵盤輸入一組元素（不少于10個(gè)元

9、素），建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表。2 .把單鏈表中的元素逆置（不允許申請(qǐng)新的結(jié)點(diǎn)空間）。3 .刪除單鏈表中所有的偶數(shù)元素結(jié)點(diǎn)。4 .編寫在非遞減有序鏈表中插入一個(gè)元素使鏈表元素仍有序的函數(shù)，利用該函數(shù)建立一個(gè)非遞減有序單鏈表。5 .利用算法4建立兩個(gè)非遞減有序單鏈表，然后合并成一個(gè)非遞增鏈表。6 .把算法1建立的鏈表分解成兩個(gè)鏈表，其中一個(gè)全部為奇數(shù)，另一個(gè)全部為偶數(shù)（盡量利用已有存儲(chǔ)空間）。7 .在主函數(shù)中設(shè)計(jì)一個(gè)簡單菜單，調(diào)用上述算法。實(shí)驗(yàn)說明1 .結(jié)點(diǎn)類型定義typedefintElemType;/元素類型typedefstructLNode(ElemTypedata;structLNod

10、e*next;LNode,*pLinkList;2 .為了簡單，采用帶頭結(jié)點(diǎn)的單鏈表。三、雙向鏈表目的要求1 .掌握雙向鏈表的存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)。2 .掌握雙向鏈表的插入與刪除算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容1 .利用尾插法建立一個(gè)雙向鏈表。2 .遍歷雙向鏈表。3 .實(shí)現(xiàn)雙向鏈表中刪除一個(gè)指定元素。4 .在非遞減有序雙向鏈表中實(shí)現(xiàn)插入元素e仍有序的算法。5 .判斷雙向鏈表中元素是否對(duì)稱，若對(duì)稱返回1,否則返回0。6 .設(shè)元素為正整型，實(shí)現(xiàn)算法把所有奇數(shù)排列在偶數(shù)之前。7 .在主函數(shù)中設(shè)計(jì)一個(gè)簡單菜單，調(diào)用上述算法。實(shí)驗(yàn)說明1.雙向鏈表的類型定義structDuLNodetypedefintElemTyp

11、e;/元素類型typedefElemTypedata;DuLNode*prior,*next;DuLNode,*pDuLinkList;四、棧與隊(duì)列目的要求1 .掌握棧、隊(duì)列的思想及其存儲(chǔ)實(shí)現(xiàn)。2 .掌握棧、隊(duì)列的常見算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容1 .采用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。2 .采用順序存儲(chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。3 .采用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。4 .采用順序存儲(chǔ)實(shí)現(xiàn)循環(huán)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。5 .在主函數(shù)中設(shè)計(jì)一個(gè)簡單菜單，調(diào)用上述算法。實(shí)驗(yàn)說明1 .順序棧類型定義constintMAX=20;/棧的最大值typedefstructEle

12、mType*base;inttop;SqStack;2 .順序隊(duì)列類型定義constintMAX=20;/隊(duì)列的最大長度typedefstruct（ElemType*base;intfront,rear;SqQueue;2.2實(shí)驗(yàn)2二叉樹應(yīng)用目的要求1 .掌握二叉樹的存儲(chǔ)實(shí)現(xiàn)。2 .掌握二叉樹的遍歷思想。3 .掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容1 .輸入字符序列，建立二叉鏈表。2 .中序遍歷二叉樹：遞歸算法。3 .中序遍歷二叉樹：非遞歸算法。（最好也實(shí)現(xiàn)先序，后序非遞歸算法）4 .求二叉樹的高度。5 .求二叉樹的葉子數(shù)。6 .借助隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷。7 .在主函數(shù)中設(shè)計(jì)一個(gè)簡單的菜

13、單，調(diào)用上述算法。實(shí)驗(yàn)說明1 .類型定義二叉鏈表存儲(chǔ)#defineElemTypechar/元素類型typedefstructBiTNode（ElemTypedata;BiTNode*Lchild,*Rchild;BiTNode,*pBiTree;2 .元素類型可根據(jù)實(shí)際需要選取。3 .3實(shí)驗(yàn)3圖的應(yīng)用目的要求1 .掌握?qǐng)D的存儲(chǔ)策略及其存儲(chǔ)實(shí)現(xiàn)。2 .掌握?qǐng)D的深度、廣度優(yōu)先遍歷的算法策略及其程序?qū)崿F(xiàn)。3 .掌握?qǐng)D的常見算法策略及其程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容1 .鍵入或隨機(jī)生成數(shù)據(jù)，建立一個(gè)有向圖的鄰接表。2 .輸出該鄰接表。3 .以有向圖鄰接表為基礎(chǔ)上，計(jì)算各頂點(diǎn)的度并輸出。4 .以有向圖鄰接表為基礎(chǔ)

14、，輸出其拓?fù)渑判蛐蛄小? .采用鄰接表存儲(chǔ)，實(shí)現(xiàn)無向圖的非遞歸DFS遍歷。6 .采用鄰接表存儲(chǔ)，實(shí)現(xiàn)無向圖的BFS優(yōu)先遍歷。7 .判斷無向圖任意兩個(gè)頂點(diǎn)間是否有路徑，若有則輸出路徑上的頂點(diǎn)序歹U。8 .在主函數(shù)中設(shè)計(jì)一個(gè)簡單的菜單，調(diào)用上述算法。實(shí)驗(yàn)說明1 .類型定義（鄰接表存儲(chǔ)）constintMAX_VERTEX_NUM=8;/頂點(diǎn)的最大個(gè)數(shù)typedefstructArcNode;(intadjvex;structArcNode*nextarc;intweight;/邊的權(quán)ArcNode;/表結(jié)點(diǎn)typedefVertexTypeint;/頂點(diǎn)元素類型typedefstructVNode

15、(intdegree,indegree;/頂點(diǎn)的度，入度VertexTypedata;ArcNode*firstarc;VNode/*頭結(jié)點(diǎn)*/,AdjListMAX_VERTEX_NUM;typedefstruct(AdjListvertices;intvexnum,arcnum;/頂點(diǎn)的實(shí)際數(shù)，邊的實(shí)際數(shù)ALGraph;2 .上述類型定義可根據(jù)情況適當(dāng)調(diào)整。2.4實(shí)驗(yàn)4集合應(yīng)用一、排序算法目的要求1 .掌握常見排序算法的策略、適用條件和程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容2 .實(shí)現(xiàn)選擇排序、插入排序和冒泡排序。3 .實(shí)現(xiàn)快速排序的非遞歸算法（可借助棧實(shí)現(xiàn)）。4 .實(shí)現(xiàn)堆排序算法。5 .實(shí)現(xiàn)折半插入排序。6 .采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)：選擇排序、插入排序和冒泡排序。7 .在主函數(shù)中設(shè)計(jì)一個(gè)簡單菜單，調(diào)用上述算法。實(shí)驗(yàn)說明1.類型定義constintMAXSIZE=20;/參加排序元素的最大個(gè)數(shù)typedefstructlistintkey;RedType;typedefstructRedTyperMAXSIZE+1;intlength;/參加排序元素的實(shí)際個(gè)數(shù)SqList;二、查找算法目的要求1 .掌握折半查找算法的思想及程序?qū)崿F(xiàn)。2 .掌握BST的建立、查找、插入、刪除算法策略及其程序?qū)崿F(xiàn)。3 .選擇合適的散列函數(shù)，實(shí)現(xiàn)不同沖突處理方法的散列表建立與查找。實(shí)驗(yàn)內(nèi)