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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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