數(shù)據結構與算法分析

《數(shù)據結構與算法分析》

——課程內容體系主要內容

教學單元模塊具體教學內容

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

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

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

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

括網絡流等問題的討論）、散列（Hash）等

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

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

和內存管理等

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

文件結構等

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

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

應用應用部分是上述數(shù)據結構和典型算法的一些應用示例，具

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

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

樹等

《數(shù)據結構與算法分析》

課程實踐內容體系主要內容

實踐教學實踐教學基本要求實踐教學具體內容

單元模塊

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

設計實踐2.復習C語言程序陣算法、萬年歷算法、迷宮算法等。并完成：

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

排序。

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

鏈表應用1.熟悉鏈表結構1.試將本章介紹的兩種Josephus問題的求解過程在計算機

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

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

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

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

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

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

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

應用實驗構提示：將n個圓盤由A依次移到C,B作為輔助塔座。當

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

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

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

列結構求解問題用塔座A作為輔助塔座。

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

值的系統(tǒng)。

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

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

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

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

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

檢索和查詢。

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

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

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

廣義表結構上的

各種操作

3.學會運用稀疏矩

陣和廣義表結構

求解問題

樹結構實1.熟悉樹和二叉樹1.設計一個程序，根據二叉樹的先根序列和對稱序序列創(chuàng)

驗結構建一棵用左右指針表示的二叉樹

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

結構上的各種操的編碼

作3.設計一個程序，把中綴表達式轉換成一棵二叉樹，然后

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

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

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

AVL樹的相關算法

圖結構實L熟悉圖結構采用兩種不同的圖的表示方法,實現(xiàn)拓撲排序和關鍵路徑的

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

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

3.學會運用圖結構的最短完成時間是多少？哪些活動是關鍵活動？說明哪項

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

構對于算法效率的影響。

q2.vs

55》a“翁a??■飛

二*

V?1

散列表實1.熟悉散列表結構試根據全年級學生的姓名，構造一個散列表，選擇適當?shù)纳?/p>

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

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

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

法

3.學會運用散列

結構求解問題

航班信息1.掌握查找與排序對于直接插入排序、直接選擇排序、起泡排序、Shell排序、

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

索實驗設2.學會選用和設計要求：

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

查找與排序算法500三種。

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

3.對實習的結果做比較分析。

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

課程實驗參考教材:

?魏開平等編著.數(shù)據結構輔導與實驗.清華大學出版社，2006年第1版

?瞿有甜，《數(shù)據結構與算法分析》實驗指導書，2004.9

《數(shù)據結構與算法分析》

課程設計內容體系主要內容

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

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

所需的動手能力、獨立解決問題的能力。該課程設計側重軟件設計的綜合訓練，

包括問題分析、總體結構設計、用戶界面設計、程序設計基本技能和技巧、多人

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

一、課程設計要求

學生必須仔細閱讀《數(shù)據結構與算法分析》課程設計方案，認真主動完成課

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

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

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

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

要上3-4小時的機來調試C語言設計的程序，總共至少要上機調試程序30小時。

二、數(shù)據結構課程設計的具體內容

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

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

（1）運動會分數(shù)統(tǒng)計**

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

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

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

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

功能要求：

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

?能統(tǒng)計各學?？偡郑?/p>

?可以按學校編號、學校總分、男女團體總分排序輸出；

?可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前

三或前五名的學校。

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

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

輸出形式：有中文提示，各學校分數(shù)為整形

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

關的功能要求。

存儲結構：學生自己根據系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)

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

計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構；

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

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

寫明；

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

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

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

體數(shù)據自定）

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

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

查詢飛機航班情況；

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

果該航班已經無票，可以提供相關可選擇航班；

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

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

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

要求：根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序

完成功能；

（3）文章編輯**

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

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

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

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

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

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

氏々口

付萬。

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

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

章；

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

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

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

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

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

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

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

的編號。

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

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

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

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

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

（5）猴子選大王**

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

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

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

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

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

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

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

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

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

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

（7）赫夫曼樹的建立

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

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

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

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

進方法；

（8）紙牌游戲**

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

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

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

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

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

（9）圖的建立及輸出

任務：建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網、無向

網，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存

儲結構中，而后輸出圖的鄰接矩陣。

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

效果

三、上交相關