數(shù)據(jù)結(jié)構(gòu)與算法分析

《數(shù)據(jù)結(jié)構(gòu)與算法分析》

——課程內(nèi)容體系主要內(nèi)容

教學(xué)單元模塊具體教學(xué)內(nèi)容

緒論緒論部分是全書的預(yù)備知識，主要對ADL語言、數(shù)據(jù)結(jié)構(gòu)

與算法、算法分析基礎(chǔ)、OOP、和C++做了簡單介紹

基本數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)部分包括線性表、堆棧與隊列、數(shù)組、字符

串、整數(shù)集合類、樹（包括AVL樹、伸展樹等）、圖（包

括網(wǎng)絡(luò)流等問題的討論）、散列（Hash）等

典型算法典型算法部分主要介紹了若干典型算法的實現(xiàn)，并給出必

要的復(fù)雜性分析和比較過程，具體包括遞歸、排序、查找

和內(nèi)存管理等

復(fù)雜數(shù)據(jù)結(jié)構(gòu)復(fù)雜數(shù)據(jù)結(jié)構(gòu)部分主要包括優(yōu)先級隊列、不相交集合類和

文件結(jié)構(gòu)等

算法設(shè)計技巧典型算法設(shè)計技巧的介紹，主要包括貪婪算法、分治算法、

動態(tài)規(guī)劃、回溯算法和隨機化算法等

應(yīng)用應(yīng)用部分是上述數(shù)據(jù)結(jié)構(gòu)和典型算法的一些應(yīng)用示例，具

體包括事件驅(qū)動模擬、等價類、殘缺棋盤和圖象壓縮等問

題的討論，在課時允許的情況下還會介紹攤還分析、紅黑

樹等

《數(shù)據(jù)結(jié)構(gòu)與算法分析》

課程實踐內(nèi)容體系主要內(nèi)容

實踐教學(xué)實踐教學(xué)基本要求實踐教學(xué)具體內(nèi)容

單元模塊

趣味程序1.熟悉編程環(huán)境1.開學(xué)第一、二周布置若干趣味程序設(shè)計題目，如奇數(shù)階幻

設(shè)計實踐2.復(fù)習(xí)C語言程序陣算法、萬年歷算法、迷宮算法等。并完成：

設(shè)計的基本內(nèi)容2.隨機產(chǎn)生n個整數(shù),然后用一種排序算法將它們從小到大

排序。

3.試編一程序，用貪心法求解一般的著色問題。

鏈表應(yīng)用1.熟悉鏈表結(jié)構(gòu)1.試將本章介紹的兩種Josephus問題的求解過程在計算機

實驗2.掌握鏈表結(jié)構(gòu)上中實現(xiàn)，實現(xiàn)時要求輸出的不是整數(shù)，而是實際的人名。

的各種操作2.設(shè)A與B分別為兩個帶有頭結(jié)點的有序循環(huán)鏈表（所謂有

3.學(xué)會運用鏈表結(jié)序是指鏈接點按數(shù)據(jù)域值大小鏈接,本題不妨設(shè)按數(shù)據(jù)域

構(gòu)求解問題值從小到大排列），listl和list2分別為指向兩個鏈表

的指針。請寫出并在計算機上實現(xiàn)將這兩個鏈表合并為一

個帶頭結(jié)點的有序循環(huán)鏈表的算法。

棧與隊列1.熟悉棧和隊列結(jié)1.設(shè)計實現(xiàn)一個求解n階Hanoi塔問題的算法

應(yīng)用實驗構(gòu)提示：將n個圓盤由A依次移到C,B作為輔助塔座。當(dāng)

2.掌握棧和隊列結(jié)n=l時，可以直接完成。否則，將塔座A頂上的nT個圓

構(gòu)上的各種操作盤移動到塔座B上，用塔座C作為輔助塔座；然后移第n

3.學(xué)會運用棧和隊個圓盤；最后將塔座B上的n-1個圓盤移到塔座C上，并

列結(jié)構(gòu)求解問題用塔座A作為輔助塔座。

2.根據(jù)書中介紹的思想，設(shè)計并實現(xiàn)一個對簡化表達式求

值的系統(tǒng)。

3.在計算機上模擬實現(xiàn)農(nóng)夫過河問題的解。

文本文件1.熟悉字符串的操1.根據(jù)課堂介紹設(shè)計實現(xiàn)KMP算法

檢索實驗作2.試設(shè)計一個簡單的文本編輯器，使之具有對字符串的輸

2.學(xué)會運用字符串入、輸出、插入、刪除、查找和替換等功能

的操作進行文本3.設(shè)計實現(xiàn)一個通用的判定回文個數(shù)問題的算法程序

檢索和查詢。

稀疏矩陣1.熟悉稀疏矩陣和1.設(shè)計實現(xiàn)兩個普通矩陣相乘的算法

和廣義表廣義表結(jié)構(gòu)2.實現(xiàn)用三元組表示法實現(xiàn)稀疏矩陣相加及轉(zhuǎn)置算法

實驗2.掌握稀疏矩陣和3.設(shè)計實現(xiàn)兩個N次一元多項式相加的算法程序

廣義表結(jié)構(gòu)上的

各種操作

3.學(xué)會運用稀疏矩

陣和廣義表結(jié)構(gòu)

求解問題

樹結(jié)構(gòu)實1.熟悉樹和二叉樹1.設(shè)計一個程序，根據(jù)二叉樹的先根序列和對稱序序列創(chuàng)

驗結(jié)構(gòu)建一棵用左右指針表示的二叉樹

2.掌握樹和二叉樹2.根據(jù)哈夫曼算法創(chuàng)建哈夫曼樹，并求樹中每個外部結(jié)點

結(jié)構(gòu)上的各種操的編碼

作3.設(shè)計一個程序，把中綴表達式轉(zhuǎn)換成一棵二叉樹，然后

3.學(xué)會運用樹和二通過后序遍歷計算表達式的值

叉樹結(jié)構(gòu)求解問4.設(shè)計實現(xiàn)一個完成對BST樹進行插入、刪除、查找操作

題的算法，并希望有部分同學(xué)能進一步把該算法改寫為針對

AVL樹的相關(guān)算法

圖結(jié)構(gòu)實L熟悉圖結(jié)構(gòu)采用兩種不同的圖的表示方法,實現(xiàn)拓?fù)渑判蚝完P(guān)鍵路徑的

驗2.掌握圖結(jié)構(gòu)上的求解過程。使用實現(xiàn)f的算法對于下圖所示的A0E網(wǎng)，求出各

各種操作活動的可能的最早開始時間和最晚開始時間。輸出整個工程

3.學(xué)會運用圖結(jié)構(gòu)的最短完成時間是多少？哪些活動是關(guān)鍵活動？說明哪項

求解問題活動提高速度后能導(dǎo)致整個工程提前完成?分析不同存儲結(jié)

構(gòu)對于算法效率的影響。

q2.vs

55》a“翁a??■飛

二*

V?1

散列表實1.熟悉散列表結(jié)構(gòu)試根據(jù)全年級學(xué)生的姓名，構(gòu)造一個散列表，選擇適當(dāng)?shù)纳?/p>

驗2.掌握散列函數(shù)的列函數(shù)和解決碰撞方法，設(shè)計并實現(xiàn)插入、刪除和查找算法，

生成方法，掌握統(tǒng)計碰撞發(fā)生的次數(shù)。（用拉鏈法解決碰撞時負(fù)載因子取2,

常規(guī)沖突處理辦用開地址法時取1/2）

法

3.學(xué)會運用散列

結(jié)構(gòu)求解問題

航班信息1.掌握查找與排序?qū)τ谥苯硬迦肱判?、直接選擇排序、起泡排序、Shell排序、

查詢與檢的各種算法快速排序和堆排序等六種算法進行上機實習(xí)。

索實驗設(shè)2.學(xué)會選用和設(shè)計要求：

計實際問題所需的1.被排序的對象由計算機隨機生成，長度分別取20,100,

查找與排序算法500三種。

2.算法中增加比較次數(shù)和移動次數(shù)的統(tǒng)計功能。

3.對實習(xí)的結(jié)果做比較分析。

4.設(shè)計實現(xiàn)一個航班信息查詢與檢索系統(tǒng)

課程實驗參考教材:

?魏開平等編著.數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與實驗.清華大學(xué)出版社，2006年第1版

?瞿有甜，《數(shù)據(jù)結(jié)構(gòu)與算法分析》實驗指導(dǎo)書，2004.9

《數(shù)據(jù)結(jié)構(gòu)與算法分析》

課程設(shè)計內(nèi)容體系主要內(nèi)容

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》課程，可使學(xué)生深化理解書本知識，致力于用學(xué)過的

理論知識和上機取得的實踐經(jīng)驗，解決具體、復(fù)雜的實際問題，培養(yǎng)軟件工作者

所需的動手能力、獨立解決問題的能力。該課程設(shè)計側(cè)重軟件設(shè)計的綜合訓(xùn)練，

包括問題分析、總體結(jié)構(gòu)設(shè)計、用戶界面設(shè)計、程序設(shè)計基本技能和技巧、多人

合作，以至一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。

一、課程設(shè)計要求

學(xué)生必須仔細(xì)閱讀《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程設(shè)計方案，認(rèn)真主動完成課

程設(shè)計的要求。有問題及時主動通過各種方式與教師聯(lián)系溝通。

學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好課程設(shè)計的時間計劃，

并在課程設(shè)計過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。

課程設(shè)計按照教學(xué)要求需要兩周時間完成，兩周中每天（按每周5天）至少

要上3-4小時的機來調(diào)試C語言設(shè)計的程序，總共至少要上機調(diào)試程序30小時。

二、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的具體內(nèi)容

本次課程設(shè)計完成如下模塊（共9個模塊，學(xué)生可以在其中至少挑選6個功

能塊完成，但有**號的模塊是必須要選擇的）

（1）運動會分?jǐn)?shù)統(tǒng)計**

任務(wù)：參加運動會有n個學(xué)校，學(xué)校編號為1...no比賽分成m個男子項

目，和w個女子項目。項目編號為男子1...m,女子m+1...m+wo不同的項

目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1,前三名的

積分分別為：5、3、2;哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）

功能要求：

?可以輸入各個項目的前三名或前五名的成績；

?能統(tǒng)計各學(xué)?？偡?；

?可以按學(xué)校編號、學(xué)?？偡帧⒛信畧F體總分排序輸出；

?可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们?/p>

三或前五名的學(xué)校。

規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校

的名稱，運動項目的名稱）

輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形

界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相

關(guān)的功能要求。

存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運動會的相關(guān)數(shù)

據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)

計的書上，請自學(xué)解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；

測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)

據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中

寫明；

（2）訂票系統(tǒng)

任務(wù)：通過此系統(tǒng)可以實現(xiàn)如下功能：

錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具

體數(shù)據(jù)自定）

查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵

達城市，航班票價，票價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，

查詢飛機航班情況；

訂票：可以訂票（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定），如

果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；

退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票

數(shù)量及航班情況，訂單要有編號。

修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件

要求：根據(jù)以上功能說明，設(shè)計航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計程序

完成功能；

（3）文章編輯**

功能：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲

一頁文章，每行最多不超過80個字符，共N行；

要求：（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)

計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后

面的字符前移。（4）存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；

輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點

氏々口

付萬。

輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"全部字母

數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字?jǐn)?shù)"（3）輸出刪除某一字符串后的文

章；

（4）約瑟夫環(huán)（Joseph）

任務(wù)：編號是1,2,……,n的n個人按照順時針方向圍坐一圈，每個人只

有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開

始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的

密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下

去，直到所有人全部出列為止。設(shè)計一個程序來求出出列順序。

要求：利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人

的編號。

測試數(shù)據(jù)：m的初值為20,n=7,7個人的密碼依次為3,1,7,2,4,7,4,

首先m=6,則正確的輸出是什么？

輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n,輸入每個人的密

碼，建立單循環(huán)鏈表。

輸出形式：建立一個輸出函數(shù)，將正確的輸出序列

（5）猴子選大王**

任務(wù)：一堆猴子都有編號，編號是1,2,3…m,這群猴子（m個）按照1-m

的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個，該猴子就要離開此圈，這樣

依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。

輸入數(shù)據(jù)：輸入m,nm,n為整數(shù)，n<m

輸出形式：中文提示按照m個猴子，數(shù)n個數(shù)的方法，輸出為大王的猴子

是幾號，建立一個函數(shù)來實現(xiàn)此功能

（6）建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）**

任務(wù)：要求能夠輸入樹的各個結(jié)點，并能夠輸出用不同方法遍歷的遍歷序列；

分別建立建立二叉樹存儲結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先

序遍歷序列的函數(shù)；

（7）赫夫曼樹的建立

任務(wù)：建立建立最優(yōu)二叉樹函數(shù)

要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹

在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸

入輸出、源程序、測試數(shù)據(jù)和結(jié)果、算法的時間復(fù)雜度、另外可以提出算法的改

進方法；

（8）紙牌游戲**

任務(wù)：編號為1-52張牌，正面向上，從第2張開始，以2為基數(shù)，是2的

倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3

的倍數(shù)的牌翻一次，直到最后一張牌；然后…從第4張開始，以4為基數(shù)，是4

的倍數(shù)的牌翻一次，直到最后一張牌；…再依次5的倍數(shù)的牌翻一次，6的，7

的直到以52為基數(shù)的翻過，輸出：這時正面向上的牌有哪些？

（9）圖的建立及輸出

任務(wù)：建立圖的存儲結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向

網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應(yīng)存

儲結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。

要求：給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，并給出遍歷過程的動態(tài)演示

效果

三、上交相關(guān)