數(shù)據結構與算法設計試驗指導書

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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