數(shù)據(jù)結(jié)構(gòu)與算法實習-實驗指導書

1、數(shù)據(jù)結(jié)構(gòu)與算法課程實習實驗指導書 上海第二工業(yè)大學計算機與信息學院軟件工程系目錄實驗一 順序表的基本操作2實驗二 鏈表的基本操作3實驗三 二叉樹的基本操作4實驗四 綜合應(yīng)用5附錄A 實驗報告示例10附錄B 實驗報告封面、評語得分表13附錄C 最后要提交的文檔形式15實驗一 順序表的基本操作【實驗目的】 1、 掌握順序存儲的概念，學會對順序表的基本操作。2、 加深對順序存儲數(shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實際問題的能力?！緦嶒炐再|(zhì)】 設(shè)計型實驗 【實驗內(nèi)容】 1、實現(xiàn)順序表顯示； 2、實現(xiàn)順序表插入； 3、實現(xiàn)順序表查找（顯示比較次數(shù)）； 4、實現(xiàn)順序表刪除（顯示移動次數(shù)）； 5、實現(xiàn)順序表排序（分

2、別實現(xiàn)簡單選擇、快速，顯示比較次數(shù)、移動次數(shù)）； 6、實現(xiàn)順序表的折半查找（顯示比較次數(shù)）； 7、編程實現(xiàn)一個順序表的就地逆置，即利用原表的存儲空間將順序表逆置； 8、順序表有序插入（顯示比較次數(shù)、移動次數(shù)）， 屏幕提示后，從鍵盤輸入一個元素值，在經(jīng)過排序的線性表中插入這個元素； 屏幕顯示比較次數(shù)和移動次數(shù)，應(yīng)有溢出判斷和報告； 9、要求以較高的效率實現(xiàn)刪除順序表中元素值在x到y(tǒng)(x和y自定)之間的所有元素； 10、編程實現(xiàn)將兩個非遞減的順序表進行合并，要求同樣的數(shù)據(jù)元素只出現(xiàn)一次； *11、編程實現(xiàn)順序表的shell排序（步長為5，3，1）； *12、編程實現(xiàn)堆排序算法； *13、利用三元組

3、順序表存儲矩陣，實現(xiàn)矩陣的轉(zhuǎn)置（請獨立寫程序?qū)崿F(xiàn)）。【實驗環(huán)境】 VC+ 6.0【實驗要求】 將如上文件保存在命名為“學號+姓名”的文件夾中并上傳到指定的服務(wù)器。實驗二 鏈表的基本操作【實驗目的】 1、 掌握鏈表的概念，學會對鏈表進行操作。2、 加深對鏈式存儲結(jié)構(gòu)的理解，逐步培養(yǎng)解決實際問題的編程能力。 【實驗性質(zhì)】 設(shè)計型實驗 【實驗內(nèi)容】 1、實現(xiàn)單鏈表的創(chuàng)建； 2、實現(xiàn)單鏈表的顯示； 3、實現(xiàn)單鏈表的查找（顯示比較次數(shù)）； 4、實現(xiàn)單鏈表的插入； 5、實現(xiàn)單鏈表的刪除（顯示比較次數(shù)）； 6、對已創(chuàng)建的鏈表（數(shù)據(jù)不限）進行直接插入排序； 7、將鏈接存儲線性表逆置，即最后一個結(jié)點變成第1個結(jié)

4、點，原來倒數(shù)第2個結(jié)點變成第2個結(jié)點，如此等等； 8、生成有序的兩個單鏈表A和B（鏈表的數(shù)據(jù)和個數(shù)自定），其首結(jié)點指針分別為a和b，要求將兩個單鏈表合并為一個有序的單鏈表C，其首結(jié)點指針為c，并且合并后的單鏈表的數(shù)據(jù)不重復； 9、將一個首結(jié)點指針為a的單鏈表A分解成兩個單鏈表A和B，其首結(jié)點指針分別為a和b，使得鏈表A中含有原鏈表A中序號為奇數(shù)的元素，而鏈表B中含有原鏈表A中序號為偶數(shù)的元素，且保持原來的相對順序； 10、請編程實現(xiàn)鏈棧的基本操作函數(shù)，并通過調(diào)用這些基本函數(shù)，實現(xiàn)十進制和八進制轉(zhuǎn)換的功能?！緦嶒灜h(huán)境】 VC+ 6.0【實驗要求】 將如上文件保存在命名為“學號+姓名”的文件夾中并

5、上傳到指定的服務(wù)器。實驗三 二叉樹的基本操作【實驗目的】 1、 掌握二叉樹的概念，學會對二叉鏈表進行操作。2、 加深對鏈式存儲結(jié)構(gòu)的理解，逐步培養(yǎng)解決實際問題的編程能力?！緦嶒炐再|(zhì)】 設(shè)計型實驗 【實驗內(nèi)容】 1、實現(xiàn)二叉樹的創(chuàng)建； 2、用遞歸方法分別先序、中序、后序遍歷以Tree為根指針的二叉樹； 3、編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目； 4、編寫遞歸算法，計算二叉樹的深度； 5、編寫遞歸算法，將二叉樹中所有結(jié)點的左、右子樹相互交換； 6、使用數(shù)組elem中的隨機數(shù)序列（以0表示結(jié)束，不包括0），生成以Tree為根指針的二叉排序樹； 7、在以Tree為根指針的二叉排序樹中查找結(jié)點； 8

6、、從以Tree為根指針的二叉排序樹中刪除結(jié)點（適用各種位置的結(jié)點）； 9、用非遞歸算法，先序遍歷以Tree為根指針的二叉樹； 提示：用數(shù)組 BiTNode *stackmax 構(gòu)成堆棧，利用這個堆棧實現(xiàn)功能。 10、用凹入表示法的表示以Tree為根指針的二叉樹，例如：/ 324/ 123/ 746/ 690/ 567 11、用廣義表表示以Tree為根指針的二叉樹，例如/ (324(123(746,690),567) 12、對以Tree為根指針的二叉樹，從根結(jié)點開始，逐層從左到右輸出各結(jié)點的數(shù)據(jù)。 提示：用數(shù)組 BiTNode *queuemax 構(gòu)成隊列，利用這個隊列實現(xiàn)功能 13、根據(jù)Huf

7、fman編碼原理，使用數(shù)組elem中的隨機數(shù)序列（以0表示結(jié)束，不包括0）作為結(jié)點的權(quán)重，生成赫夫曼樹，以及赫夫曼編碼，計算平均帶權(quán)徑長度。 14、（1）隨機生成二叉樹。 （2）生成并保存先（后）序、中序輸出序列。 （3）按照保存的一對輸出序列恢復出二叉樹。（4）生成先（后）序輸出序列?！緦嶒灜h(huán)境】 VC+ 6.0【實驗要求】 將如上文件保存在命名為“學號+姓名”的文件夾中并上傳到指定的服務(wù)器。實驗四 綜合應(yīng)用一、運動會分數(shù)統(tǒng)計問題描述參加運動會的n個學校編號為1n。比賽分成m個男子項目和w個女子項目，項目編號分別為1m和m+1m+w。由于各項目參加人數(shù)差別較大，有些項目取前五名，得分順序為7

8、，5，3，2，1；還有些項目只取前三名，得分順序為5，3，2。寫一個統(tǒng)計程序產(chǎn)生各種成績單和得分報表?；疽螽a(chǎn)生各學校的成績單，內(nèi)容包括各校所取得的每項成績的項目號、名次（成績）、姓名和得分；產(chǎn)生團體總分報表，內(nèi)容包括校號、男子團體總分、女子團體總分和團體總分。測試數(shù)據(jù)對于n=4,m=3,w=2，編號為奇數(shù)的項目取前五名，編號為偶數(shù)的項目取前三名，設(shè)計一組實例數(shù)據(jù)。實現(xiàn)提示可以假設(shè)n<=20,m<=30,w<=20，姓名長度不超過20個字符。每個項目結(jié)束時，將其編號、類型符（區(qū)分取前五名還是前三名）輸入，并按名次順序輸入運動員姓名、校名（和成績）。選作內(nèi)容允許用戶指定某項目

9、采取其他名次取法。二、一元稀疏多項式簡單計算器問題描述設(shè)計一個一元稀疏多項式簡單計算器基本要求一元稀疏多項式簡單計算器的基本功能是：（1）輸入并建立多項式；（2）輸出多項式，輸出形式為整數(shù)序列：n,c1,e1,c2,e2,cn,en，其中n是多項式的項數(shù)，ci和ei分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列；（3）多項式a和b相加，建立多項式a+b；（4）多項式a和b相減，建立多項式a-b。測試數(shù)據(jù)（1）（2x+5x3-3.1x11）+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)（2）(6x-3-X+4.4X2-1.2X9)-(-6X-3+5.4X2-X2+7.8X15)

10、=(-7.8X15-1.2X9+12X-3-X)（3）(1+X+X2+X3+X4+X5)+(-X3-X4)=(1+X+X2+X5)（4）(X+X3)+(-X-X3)=0實現(xiàn)提示用帶表頭結(jié)點的單鏈表存儲多項式。選作內(nèi)容（1） 計算多項式在X處的值。（2） 計算多項式a的導函數(shù)a。（3） 多項式a和b相乘，建立乘積多項式ab。（4） 多項式的輸出形式為類數(shù)學表達式。例如，多項式-3x8+6x3-18的輸出形式為-3x8+6x3-18。注意，系數(shù)為1的非零次項的輸出形式中略去系數(shù)1，如1x8的輸出形式為x8。（5） 計算器的仿真界面。三、停車場管理問題描述設(shè)停車場是一個可停放n輛汽車的狹長通道，且只

11、有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛停放在車場的最北端），若車廠內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短繳納費用。試為停車場編制按上述要求進行管理的模擬程序?；疽笠詶ＤM停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或

12、“離去”信息、汽車牌照號碼以及到達或離去的時刻。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)繳納的費用（在便道上停留的時間不收費）。/棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。測試數(shù)據(jù)設(shè)n=2，輸入數(shù)據(jù)為（A,1,5）,（A,2,10）,（D,1,15）,（A,3,20）,（A,4,25）,（A,5,30）,（D,2,35）,（D,4,40）,（E,0,0）。其中A表示到達；D表示離去；E表示結(jié)束。實現(xiàn)提示需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)

13、按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車牌照號碼和進入停車場的時刻。選作內(nèi)容（1） 兩個棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少。（2） 汽車可有不同種類，則他們的占地面積不同，收費標準也不同，如1輛客車和1.5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當于3輛小汽車的占地面積。（3） 汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。（4） 停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思考如何修改結(jié)構(gòu)以滿足這種要求。四、航空客運訂票系統(tǒng)問題描述航空客運訂票的業(yè)務(wù)活動包括：查詢航線、客票預訂和辦理退票等。試設(shè)計一個航空

14、客運訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計算機來完成。基本要求（1） 每條航線所涉及的信息有：終點站名、航班號、飛機型號、飛行周日（星期幾）、乘員定額?、余票量、已定票的客戶名單（包括姓名、訂票量、艙位等級1，2或3）以及等候替補的客戶名單（包括姓名、所需票量）；（2） 作為示意系統(tǒng)，全部數(shù)據(jù)可以只放在內(nèi)存中；（3） 系統(tǒng)能實現(xiàn)的操作和功能如下：查詢航線：根據(jù)旅客提出的終點站名輸出下列信息：航班號、飛機號、星期幾飛行，最近一天航班的日期和余票額；承辦定票業(yè)務(wù)：根據(jù)客戶提出的要求（航班號、訂票數(shù)額）查詢該航班票額情況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出座位號；若以滿員或余票額少于定票額，則需重新詢

15、問客戶要求。若需要，可登記排隊候補；承辦退票業(yè)務(wù)：根據(jù)客戶提供的情況（日期、航班），為客戶辦理退票手續(xù)，然后查詢該航班是否有人排隊候補，首先詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊候補的客戶。測試數(shù)據(jù)自行指定。實現(xiàn)提示兩個客戶名單可分別由線性表和隊列實現(xiàn)。為查找方便，已訂票客戶的線性表應(yīng)按客戶姓名有序，并且，為插入和刪除方便，應(yīng)以鏈表作為存儲結(jié)構(gòu)，由于預約人數(shù)無法預計，隊列也應(yīng)以鏈表作為存儲結(jié)構(gòu)。整個系統(tǒng)需匯總各條航線的情況登錄在一張線性表上，由于航線基本不變，可采用順序存儲結(jié)構(gòu)，并按航班有序或按終點站名有序。每條航線是這張表上的一個記錄，包含上述

16、8個域，其中乘員名單域為指向乘員名單鏈表的頭指針，等候替補的客戶名單域為分別指向隊頭和隊尾的指針。選作內(nèi)容 當客戶訂票要求不能滿足時，系統(tǒng)可向客戶提供到達同一目的地的其它航線情況。還可以充分發(fā)揮自己的想象力，增加系統(tǒng)的功能和其他服務(wù)項目。五、簡單行編輯程序問題描述文本編輯程序是利用計算機進行文字加工的基本軟件工具，實現(xiàn)對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟，也不總能實現(xiàn)。一種解決方法是逐段編輯。任何時刻只能把待編輯的文件的一段放在內(nèi)存中，稱為活區(qū)。試按照這種方法實現(xiàn)一個簡單

17、的行編輯程序。設(shè)文件每行不超過320個字符，很少超過80個字符?；疽髮崿F(xiàn)以下4條基本編輯命令：（1） 行插入。格式：i<行號><回車><文本>.<回車>將文本插入活區(qū)中第<行號>行之后。（2） 行刪除。格式：d<行號1><空格><行號2><回車>刪除活區(qū)中第<行號1>行（到第<行號2>行）。例如“d10”和“d10 14”（3） 活區(qū)切換。格式：n<回車>將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。（4） 活區(qū)顯示。格式：p<

18、回車>逐頁的（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶決定是否繼續(xù)顯示以后各頁（如果存在）。印出的每一行要前置行號和一個空格符，行號固定占4位，增量為1。 各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū)第一行行號減一，表示插入當前屏幕中第一行之前，否則命令參數(shù)非法。測試數(shù)據(jù)自行設(shè)定，注意測試將活區(qū)刪空等特殊情況。實現(xiàn)提示（1） 設(shè)活區(qū)的大小用行數(shù)ActiveMaxLen（可設(shè)為100）來描述。考慮到文本文件行長通常為正態(tài)分布，且峰值在60到70之間，用320*ActiveMaxLen大小的字符數(shù)組實現(xiàn)存儲將造成大量浪費，可以以標準行塊為單位為各行分配存

19、儲，每個標準行塊可含81個字符。這些行塊可以組成一個數(shù)組，也可以利用動態(tài)鏈表連接起來。一行文字可能占多個行塊。行尾可用一個特殊的ASCII字符（如(012)8）標識。此外，還應(yīng)記住活區(qū)起始行號。行插入將引起隨后各行行號的順序下推。（2） 初始化函數(shù)包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過ActiveMaxLen-x。x的值可以自定，例如20。（3） 在執(zhí)行行插入命令的過程中，每接收到一行時都要檢查活區(qū)大小是否已達ActiveMaxLen。如果是，則為了在插入這一行之后仍保持活區(qū)大小不超過ActiveMaxLen，應(yīng)

20、將插入點之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點為第一行之前，則只得將新插入的這一行輸出。（4） 若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著結(jié)束編輯或開始編輯另一個文件。（5） 可令前三條命令執(zhí)行后自動調(diào)用活區(qū)顯示。選作內(nèi)容（1） 對于命令格式非法等一切錯誤作嚴格檢查和適當處理。（2） 加入更復雜的編輯操作，如對某行進行串替換；在活區(qū)內(nèi)進行模式匹配等，格式可以為S<行號><串1><串2><回車>和m<串><回車>?！緦嶒灜h(huán)境】 VC+ 6.0【實驗要求】 將如

21、上文件保存在命名為“學號+姓名”的文件夾中并上傳到指定的服務(wù)器。附錄A 實驗報告示例“學生通訊錄管理系統(tǒng)”的設(shè)計與實現(xiàn)一、 設(shè)計要求1、 問題描述紙質(zhì)的通訊錄已經(jīng)不能滿足大家的要求，容易丟失，查找困難等問題是紙質(zhì)通訊錄所不能克服的缺點。“學生通訊錄管理系統(tǒng)”是為了幫助老師、同學，或者其它一些需要使用通訊錄的人員進行管理和分析的一種應(yīng)用程序。2、 需求分析（1） 輸入數(shù)據(jù)建立通訊錄（2） 查詢通訊錄中滿足要求的信息（3） 插入新的通訊錄信息（4） 刪除不需要的通訊錄信息（5） 查看所有的通訊錄信息二、 概要設(shè)計為了實現(xiàn)需求分析中的功能，可以從3個方面著手設(shè)計1、 主界面設(shè)計為了實現(xiàn)學生通訊錄管理

22、系統(tǒng)各功能的管理，設(shè)計一個含有多個菜單項的主控菜單子程序以鏈接系統(tǒng)的各項子功能，方便用戶使用本系統(tǒng)。2、 存儲結(jié)構(gòu)設(shè)計本系統(tǒng)主要采用鏈表結(jié)構(gòu)類型來表示存儲在“學生通訊錄管理系統(tǒng)”中的信息。其中，鏈表結(jié)點有4個分量構(gòu)成：通訊錄成員學號、姓名、電話號碼、指向該結(jié)構(gòu)體的指針。此外，本系統(tǒng)還設(shè)置一個全局變量seat，表示成員序號。3、 系統(tǒng)功能設(shè)計本系統(tǒng)設(shè)置5個子功能：（1） 建立通訊錄系統(tǒng)：可以一次輸入多個成員的信息，建立通訊錄。（2） 插入通訊錄記錄：每次可以插入一個成員的信息。（3） 查詢通訊錄記錄：可以按兩種方式查詢所要的記錄，一是按學號查詢，二是按姓名查詢。（4） 刪除通訊錄記錄：可以按三種

23、方式刪除信息，按序號刪除，按學號刪除，按姓名刪除。（5） 顯示通訊錄記錄：可以查看通訊錄中所有成員信息。三、 模塊設(shè)計1、 模塊設(shè)計本程序包含兩個模塊：主程序模塊和鏈表操作模塊，其調(diào)用關(guān)系如下：主程序模塊鏈表操作模塊2、 系統(tǒng)子程序及功能設(shè)計本系統(tǒng)共設(shè)置10個子程序，各程序的函數(shù)名及功能說明如下：（1）LinkList CreateIncreLink() /鏈表的創(chuàng)建（2）deleteElem(LinkList L, int i) /從通訊錄中按序號刪除第i各元素（3）delName(LinkList L,char n ) /按姓名刪除通訊者紀錄（4）delNum(LinkList L, int n) /按學號刪除通訊者紀錄（5）void insertYouXu(LinkList L, LinkList Elem) /插入一條通訊錄（6）printList(LinkList L) /打印通訊錄（7）prior(LinkList L, LinkLis