12計(jì)科數(shù)據(jù)結(jié)構(gòu)與算法試驗(yàn)大綱

1、數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)教學(xué)大綱課程編號(hào)：B課程類別：專業(yè)基礎(chǔ)必修課實(shí)驗(yàn)學(xué)時(shí)：實(shí)驗(yàn)16學(xué)時(shí)學(xué) 分：4適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、計(jì)算機(jī)科學(xué)與技術(shù)(數(shù)字媒體藝術(shù))一、實(shí)驗(yàn)教學(xué)目的和任務(wù)數(shù)據(jù)結(jié)構(gòu)與算法是信息與計(jì)算科學(xué)專業(yè)中一門(mén)重要的專業(yè)基礎(chǔ)課程。當(dāng)用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題時(shí)，就要涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對(duì)象， 通過(guò)這兩方面內(nèi)容的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下了厚實(shí)的知識(shí)基礎(chǔ)，同時(shí)也提供了必要的技能訓(xùn)練。因此，數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)應(yīng)用專業(yè)中具有舉足輕重的作用。本課程的任務(wù)是：通過(guò)實(shí)踐，學(xué)生對(duì)常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實(shí)現(xiàn)方法的理 論得到進(jìn)

2、一步的掌握，并對(duì)在不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)不同的運(yùn)算方式和技巧有所體會(huì)。二、實(shí)驗(yàn)教學(xué)基本要求本課程是一門(mén)實(shí)踐性很強(qiáng)的專業(yè)課，只有了解這門(mén)課程的特點(diǎn)和基本要求，學(xué)習(xí)時(shí)才能做到有的放矢，舉一反三，基本要求主要有以下幾個(gè)方面：(1)認(rèn)真閱讀掌握和實(shí)驗(yàn)相關(guān)的指導(dǎo)書(shū)內(nèi)容。(2)自己編程，可以參考別人的程序設(shè)計(jì)方法，但不得抄襲別人的程序。(3)程序有錯(cuò)誤時(shí)，盡量先自己調(diào)試，在自己能力達(dá)不到時(shí)， 可請(qǐng)教同學(xué)或詢問(wèn)老師。(4)及時(shí)完成實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)教學(xué)內(nèi)容數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)分五個(gè)實(shí)驗(yàn)項(xiàng)目，實(shí)驗(yàn)的具體內(nèi)容見(jiàn)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo) 書(shū)，每個(gè)實(shí)驗(yàn)項(xiàng)目完成后要提交一份電子實(shí)驗(yàn)報(bào)告，每份實(shí)驗(yàn)報(bào)告至少包括實(shí)驗(yàn)項(xiàng)目中的四個(gè)實(shí)

3、驗(yàn)任務(wù)，電子實(shí)驗(yàn)報(bào)告模板見(jiàn)附錄1。實(shí)驗(yàn)一線性表的實(shí)驗(yàn)1、實(shí)驗(yàn)?zāi)康募耙螅?1) 了解線性表的順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法，掌握用在VC環(huán)境下上機(jī)調(diào)試順序表和單鏈表的基本方法。(2)掌握順序表的插入、刪除、查找、求表長(zhǎng)以及有序順序表的合并算法的實(shí)現(xiàn)(3)掌握單鏈表、循環(huán)鏈表的插入、刪除、查找、求表長(zhǎng)以及有序單鏈表的合并算法的 實(shí)現(xiàn)(4)討論單鏈表和順序表在設(shè)計(jì)上的差別。2、實(shí)驗(yàn)內(nèi)容及學(xué)時(shí)分配：(4學(xué)時(shí))(1)順序表基本操作的實(shí)現(xiàn)(2)有序順序表的合并，已知順序表la和lb中的數(shù)據(jù)元素按非遞減有序排列，將 la和lb表中的數(shù)據(jù)元素，合并成為一個(gè)新的非遞減有序順序表lc ,并且不破壞la和lb表(3)

4、單鏈表基本操作的實(shí)現(xiàn)(4)有序單鏈表的合并，已知單鏈表la和lb中的數(shù)據(jù)元素按非遞減有序排列，將 la和lb中的數(shù)據(jù)元素，合并為一個(gè)新的單鏈表lc,lc中的數(shù)據(jù)元素仍按非遞減有序排歹U,要求不破壞la表和lb表的結(jié)構(gòu)。(5)約瑟夫環(huán)問(wèn)題，設(shè)有 N個(gè)人圍坐一圈，現(xiàn)從某個(gè)人開(kāi)始報(bào)數(shù)，數(shù)到M的人出列，接著從出列的下一個(gè)人開(kāi)始重新報(bào)數(shù)，數(shù)到M的人以出列，如此下去，直到所有人都出列為此。試設(shè)計(jì)確定他們的出列次序序列的程序。選擇單向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬整個(gè)過(guò)程，并依次輸出列的各人的編號(hào)。(6)編程實(shí)現(xiàn)兩個(gè)循環(huán)單鏈表的合并。實(shí)驗(yàn)二 棧、隊(duì)列的實(shí)現(xiàn)及應(yīng)用1、實(shí)驗(yàn)?zāi)康募耙螅?1)掌握棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

5、和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際背景下靈活運(yùn)用。(2)掌握棧和隊(duì)列的特點(diǎn)，即先進(jìn)后出與先進(jìn)先出的原則。(3)掌握棧和隊(duì)列的基本操作實(shí)現(xiàn)方法。2、實(shí)驗(yàn)內(nèi)容及學(xué)時(shí)分配：(2學(xué)時(shí))(1)實(shí)現(xiàn)棧的順序存儲(chǔ)(2)利用棧實(shí)現(xiàn)數(shù)制轉(zhuǎn)換(3)實(shí)現(xiàn)循環(huán)隊(duì)列的順序存儲(chǔ)(4)順序串的基本操作實(shí)驗(yàn)三二叉樹(shù)的操作及應(yīng)用1、實(shí)驗(yàn)?zāi)康募耙螅?1)進(jìn)一步掌握指針變量、動(dòng)態(tài)變量的含義。(2)掌握二叉樹(shù)的結(jié)構(gòu)特性，以及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)和適用范圍。(3)掌握用指針類型描述、訪問(wèn)和處理二叉樹(shù)的運(yùn)算。2、實(shí)驗(yàn)內(nèi)容及學(xué)時(shí)分配：(4學(xué)時(shí))(1)以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，試編寫(xiě)前序、中序、后序及層次順序遍歷二叉樹(shù)的算法。(2)以二叉鏈表作存儲(chǔ)結(jié)構(gòu)

6、，試編寫(xiě)計(jì)算二叉樹(shù)深度、所有結(jié)點(diǎn)總數(shù)、葉子結(jié)點(diǎn)數(shù)、雙 孩子結(jié)點(diǎn)個(gè)數(shù)、單孩子結(jié)點(diǎn)個(gè)數(shù)的算法(3)編寫(xiě)按中序順序建立一棵二叉樹(shù)的非遞歸算法的C語(yǔ)言源程序，并且用非遞歸方式遍歷二叉樹(shù)(先序、中序或后序)，輸出遍歷序列。(4)赫夫曼樹(shù)與赫夫曼編碼，利用Huffman編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳 數(shù)據(jù)預(yù)先編碼，在接受端將傳來(lái)的數(shù)據(jù)編碼進(jìn)行譯碼(復(fù)原)。對(duì)于有些信道，每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫(xiě)一個(gè)Huffman的編譯碼系統(tǒng)。給定一組權(quán)值 7, 9, 5, 6, 10, 1, 13, 15, 4

7、, 8,構(gòu)造一棵赫夫曼 樹(shù)，并計(jì)算帶權(quán)路徑長(zhǎng)度 WPL實(shí)驗(yàn)四圖的操作及應(yīng)用1、實(shí)驗(yàn)?zāi)康募耙螅?1)熟練掌握?qǐng)D的鄰接矩陣和鄰接表的存儲(chǔ)方式；(2)實(shí)現(xiàn)圖的一些基本運(yùn)算，特別是深度遍歷和廣度遍歷；(3)掌握以圖為基礎(chǔ)的一些常用算法，如最小生成樹(shù)、拓?fù)渑判?、最短路徑?、實(shí)驗(yàn)內(nèi)容及學(xué)時(shí)分配：(2學(xué)時(shí))(1)定義鄰接矩陣存儲(chǔ)結(jié)構(gòu)或鄰接表存儲(chǔ)結(jié)構(gòu)。(2)按照建立一個(gè)帶權(quán)有向圖的操作需要，編寫(xiě)在鄰接矩陣或鄰接表存儲(chǔ)結(jié)構(gòu)下，帶權(quán)有向圖基本操作的實(shí)現(xiàn)函數(shù)(如初始化圖、在圖中插入一個(gè)結(jié)點(diǎn)、 在圖中插入一條邊、在圖中尋找序號(hào)為 v的結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)、在圖中尋找序號(hào)為v1結(jié)點(diǎn)的鄰接結(jié)點(diǎn)v2的下一個(gè)鄰接結(jié)點(diǎn)、圖

8、的深度優(yōu)先遍歷、圖的廣度優(yōu)先遍歷等)。(3)設(shè)計(jì)一個(gè)測(cè)試主函數(shù)，首先創(chuàng)建一個(gè)圖(有n個(gè)結(jié)點(diǎn)和e條邊)，然后打印圖的n個(gè)結(jié)點(diǎn)信息和e條邊信息，最后分別打印出圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的結(jié) 點(diǎn)信息序列。湖北理工學(xué)院計(jì)算機(jī)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)教學(xué)大綱實(shí)驗(yàn)五 查找與排序1、實(shí)驗(yàn)?zāi)康募耙螅?1)掌握查找的不同方法，并能用高級(jí)語(yǔ)言實(shí)現(xiàn)查找算法。(2)熟練掌握順序表的查找方法和有序順序表的折半查找算法以及靜態(tài)查找樹(shù)的構(gòu)造 方法和查找算法。(3)掌握二叉排序樹(shù)的生成、插入、刪除、輸出運(yùn)算。(4)掌握常用的排序方法，并能用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法。(5)深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活

9、運(yùn)用。(6) 了解各種方法的排序過(guò)程及依據(jù)的原則，并掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。2、實(shí)驗(yàn)內(nèi)容及學(xué)時(shí)分配：(4學(xué)時(shí))(1)作為輸入給定的是已分類的數(shù)列：a1,a2,a3, , an,以及隨后的問(wèn)題序列:b1, b2, b3, bn 。請(qǐng)編寫(xiě)一個(gè)程序，首先順序存儲(chǔ)數(shù)列a1,a2,a3, ,an,然后用折半查找法對(duì)每個(gè)問(wèn)題bi找出使aj等于bi的一切j ,當(dāng)沒(méi)有這樣的j及有多個(gè)這樣的j時(shí)，程序也應(yīng)能夠正常工作。(2)給定一個(gè)用無(wú)序鏈表表示的集合，需要在其上執(zhí)行operator+( ), operator*(),operator- ( ), Contains(x), AddMember (

10、x), DelMember(x), Min(),試給出所有這些函數(shù)的實(shí)現(xiàn)。(3)用序列(46, 88, 45, 39, 70, 58, 101, 10, 66, 34)建立一個(gè)排序二叉樹(shù)，編 程實(shí)現(xiàn)二叉排序樹(shù)的建立、查找、中序遍歷算法，計(jì)算和輸出每次查找所需和關(guān)鍵 字進(jìn)行比較的次數(shù)，以及在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。(4)設(shè)計(jì)一個(gè)程序讀入一個(gè)字符串，統(tǒng)計(jì)該字符串中出現(xiàn)的字符及其次數(shù)，然后以表的形式輸出結(jié)果。要求用一個(gè)二叉樹(shù)來(lái)保存處理結(jié)果，字符串中的每個(gè)不同的字符用樹(shù)中不同的結(jié)點(diǎn)描述，每個(gè)結(jié)點(diǎn)包含四個(gè)域，格式為：字符、該字符的出現(xiàn)次數(shù)、 指向ASCII碼小于該字符的左子樹(shù)指針、指向AS

11、CII碼大于該字符的右子樹(shù)指針。因此程序的功能是依次從輸入字符串中取出一個(gè)字符，把它們插入到樹(shù)中(新出現(xiàn)字符)或修改原樹(shù)中相應(yīng)結(jié)點(diǎn)的“出現(xiàn)次數(shù)域”(已出現(xiàn)字符)。(5)請(qǐng)編寫(xiě)一個(gè)算法，在基于單鏈表表示的待排序排序碼序列上進(jìn)行簡(jiǎn)單選擇排序。(6)采用靜態(tài)單鏈表作為存儲(chǔ)表示。用 Vector0作為表頭結(jié)點(diǎn)，各待排序數(shù)據(jù)對(duì)象從 Vector1開(kāi)始存放。算法的思想是每趟在原始鏈表中摘下排序碼最大的結(jié)點(diǎn)(幾個(gè)排序碼相等時(shí)為最前面的結(jié)點(diǎn))，把它插入到結(jié)果鏈表的最前端。由于在原始鏈表 中摘下的排序碼越來(lái)越小，在結(jié)果鏈表前端插入的排序碼也越來(lái)越小，最后形成的結(jié)果鏈表中的結(jié)點(diǎn)將按排序碼非遞減的順序有序鏈接。四、

12、實(shí)驗(yàn)項(xiàng)目與學(xué)時(shí)分配序號(hào)實(shí)驗(yàn)項(xiàng)目名稱學(xué)時(shí)實(shí)驗(yàn)類型實(shí)驗(yàn)主要儀器設(shè)備備注實(shí)驗(yàn)一 線性表的實(shí)驗(yàn)4設(shè)計(jì)性必做實(shí)驗(yàn)二棧、隊(duì)列的實(shí)現(xiàn)及應(yīng)用2設(shè)計(jì)性必做實(shí)驗(yàn)三二叉樹(shù)的操作及應(yīng)用4設(shè)計(jì)性必做實(shí)驗(yàn)四 圖的操作及應(yīng)用2設(shè)計(jì)性必做實(shí)驗(yàn)五查找與排序4設(shè)計(jì)性必做五、實(shí)驗(yàn)考核辦法與成績(jī)?cè)u(píng)定10%實(shí)驗(yàn)考實(shí)驗(yàn)成績(jī)由實(shí)驗(yàn)報(bào)告、實(shí)驗(yàn)考試兩部份組成。實(shí)驗(yàn)報(bào)告占課程總成績(jī)的試成績(jī)占課程總成績(jī)的 10%六、實(shí)驗(yàn)教材（或參考書(shū)、指導(dǎo)書(shū)）教材：1嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）M.（第三版）北京：清華大學(xué)出版社.1997參考書(shū)：Sartaj Sahni. Data Structure, Algorithms, and Applicati

13、on in C+. The McGraw-Hill Company Inc.1998 M（第一版）（數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用一一 C+遮言描述.北京：機(jī)械工業(yè)出版社.1999Willan Ford,Willian Topp. Data Structures with C+. New Jersey:Prentice HallInc, Adivision Simon & Schuster Company,1996 M（第一版）（數(shù)據(jù)結(jié)本CC+詡言描述.北京：清華大學(xué)出版社，19974徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C/C+描述）M.（第一版）北京：清華大學(xué)出版社.19995陳慧南.數(shù)據(jù)結(jié)構(gòu)（使用 C+語(yǔ)言描

14、述）M.（第一版）南京：東南大學(xué)出版社.20016殷人昆，陶永雷，謝若陽(yáng)等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+苗述）M.（第一版）北京：清華大學(xué)出版社.1999執(zhí)筆人：祁文青審核人：祁文青（蓋章）2011年9月1日湖北理工學(xué)院計(jì)算機(jī)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)教學(xué)大綱附錄1:實(shí)驗(yàn)報(bào)告模板實(shí)驗(yàn)一 線性表的實(shí)驗(yàn)實(shí)驗(yàn)課程名：數(shù)據(jù)結(jié)構(gòu)專業(yè)班級(jí)： 學(xué)號(hào)： 姓名： 實(shí)驗(yàn)時(shí)間：一 實(shí)驗(yàn)地點(diǎn)：.指導(dǎo)教師：一、實(shí)驗(yàn)?zāi)康暮鸵蠖?shí)驗(yàn)內(nèi)容任務(wù)1* (任務(wù)名稱)1、實(shí)驗(yàn)內(nèi)容(寫(xiě)出簡(jiǎn)要原理、公式及其應(yīng)用條件等，若無(wú)，可只寫(xiě)實(shí)驗(yàn)內(nèi)容)2、實(shí)驗(yàn)步驟(寫(xiě)出實(shí)驗(yàn)操作的總體思路、操作規(guī)范和操作主要注意事項(xiàng)，準(zhǔn)確無(wú) 誤地記錄原始數(shù)據(jù)。若為程序設(shè)計(jì)類課程，