第一篇：006A1060《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱

課程英文名稱：Data Structure

課程編號(hào)：006A1060

學(xué)時(shí)：54＋18（實(shí)驗(yàn)）

學(xué)分：4.0分

一、課程教學(xué)對(duì)象

本教學(xué)大綱適用于五邑大學(xué)信息學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的普通本科生數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)。

二、課程性質(zhì)、目的和任務(wù)

數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)必修的專業(yè)基礎(chǔ)課，是計(jì)算機(jī)專業(yè)學(xué)科的核心課程。是編譯原理、操作系統(tǒng)等課程的基礎(chǔ)。

數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計(jì)算機(jī)硬件（特別是編碼理論、存儲(chǔ)裝置和存取方法等）的研究范圍，而且和計(jì)算機(jī)軟件的研究有著更密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問題。在研究信息檢索時(shí)也必須考慮如何組織數(shù)據(jù)，以便查找和存取數(shù)據(jù)元素更為方便。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)不僅是一般程序設(shè)計(jì)（特別是非數(shù)值計(jì)算的程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、人工智能、數(shù)據(jù)系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。同時(shí)，數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。

值得注意的是，數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)，一方面，面向各專門領(lǐng)域中特殊問題的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，如多維圖形數(shù)據(jù)結(jié)構(gòu)等；另一方面，從抽象數(shù)據(jù)類型的觀點(diǎn)來討論數(shù)據(jù)結(jié)構(gòu)，已成為一種新的趨勢(shì)，越來越被人們所重視。

根據(jù)我校“培養(yǎng)高素質(zhì)應(yīng)用型創(chuàng)新人才”的人才培養(yǎng)的層次定位，以及我院生源的實(shí)際情況，本課程在專業(yè)培養(yǎng)目標(biāo)中的定位：一是要滿足后繼專業(yè)課程的基本需要；二是要為今后研制開發(fā)各種應(yīng)用軟件打下扎實(shí)的理論和實(shí)踐基礎(chǔ)，使學(xué)生在編程能力方面得到比較系統(tǒng)的訓(xùn)練，以適應(yīng)計(jì)算機(jī)學(xué)科專業(yè)對(duì)應(yīng)用型、復(fù)合型人才培養(yǎng)的要求。

為此，本課程強(qiáng)調(diào)理論和實(shí)踐的統(tǒng)一，突出對(duì)學(xué)生的動(dòng)手能力的培養(yǎng)。在對(duì)學(xué)生進(jìn)行基本數(shù)據(jù)結(jié)構(gòu)的技術(shù)、理論、設(shè)計(jì)等各種技能培養(yǎng)的同時(shí)，突出對(duì)學(xué)生進(jìn)行將實(shí)際問題轉(zhuǎn)化為基本數(shù)據(jù)結(jié)構(gòu)的問題的分析能力。鼓勵(lì)學(xué)生學(xué)以致用，將學(xué)到的知識(shí)用以解決實(shí)際問題。在教學(xué)方法上應(yīng)用現(xiàn)代教育技術(shù)，采用多媒體課件形式輔助教學(xué)，對(duì)抽象的數(shù)據(jù)結(jié)構(gòu)輔之以形象的動(dòng)畫，不僅能提高學(xué)生的學(xué)習(xí)興趣，也加深了學(xué)生對(duì)抽象概念的理解。運(yùn)用網(wǎng)絡(luò)教學(xué)平臺(tái)輔助教學(xué)，加強(qiáng)教學(xué)過程的師生互動(dòng)，對(duì)課程實(shí)施規(guī)范化管理。

本課程的目標(biāo)：適應(yīng)計(jì)算機(jī)學(xué)科各個(gè)專業(yè)發(fā)展的需要，使學(xué)生掌握基本數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，了解數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系及優(yōu)劣，培養(yǎng)學(xué)生設(shè)計(jì)及選擇有效的算法、設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)的能力，并具有初步的算法分析能力。在教學(xué)過程中，將后續(xù)課程中常用到的基本知識(shí)，如《編譯原理》中用到的線性表、棧、查找樹，《操作系統(tǒng)》中用到隊(duì)列、目錄樹等，作為本課程的重點(diǎn)，注重學(xué)生分析問題、解決問題能力及自主創(chuàng)新能力的培養(yǎng)，使本課程在處理知識(shí)面的寬度和深度上，既滿足作為學(xué)科基礎(chǔ)課的要求又達(dá)到一定的水平。

三、對(duì)先修課的要求

高級(jí)程序設(shè)計(jì)語言、離散數(shù)學(xué)是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的主要先修課程。具體要求如下： 1． 掌握程序設(shè)計(jì)語言的基本概念。

2． 掌握結(jié)構(gòu)化程序設(shè)計(jì)的的基本原理、良好的設(shè)計(jì)習(xí)慣，并具備較好的程序調(diào)試能力。3． 掌握離散數(shù)學(xué)的基本理論。4．具有一定的邏輯思維和推理能力

四、課程的主要內(nèi)容、基本要求和學(xué)時(shí)分配建議（總學(xué)時(shí)數(shù): 54）

本課程著重介紹數(shù)據(jù)結(jié)構(gòu)的基本概念、基本算法以及各種常用數(shù)據(jù)結(jié)構(gòu)，主要包括線性表、棧和隊(duì)列和串、廣義表、樹和二叉樹、圖、排序、查找等內(nèi)容。闡明各種數(shù)據(jù)結(jié)構(gòu)的內(nèi)在邏輯關(guān)系、存儲(chǔ)結(jié)構(gòu)和相應(yīng)運(yùn)算。本課程計(jì)劃總學(xué)時(shí)為72學(xué)時(shí)，理論課54學(xué)時(shí)，實(shí)驗(yàn)18學(xué)時(shí)，授課學(xué)時(shí)（理論課54學(xué)時(shí)）分配如下： 第1章

緒論(6學(xué)時(shí))

主要內(nèi)容：

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)類型等概念術(shù)語的確定含義；抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法；描述算法的偽代碼方法；算法設(shè)計(jì)的基本要求以及從時(shí)間和空間角度分析算法的方法。

學(xué)習(xí)要求：

1．?dāng)?shù)據(jù)結(jié)構(gòu)的興起和發(fā)展（C）

2．?dāng)?shù)據(jù)結(jié)構(gòu)的研究對(duì)象

（A）

3．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念

（A）

4．抽象數(shù)據(jù)類型的概念

（B）

5．算法的特性和基本方法（B）

6．算法時(shí)間復(fù)雜度的方法（B）

第2章線性表(6學(xué)時(shí))

主要內(nèi)容：

線性表的邏輯結(jié)構(gòu)定義、抽象數(shù)據(jù)類型定義和各種存儲(chǔ)結(jié)構(gòu)的描述方法；在線性表的兩類存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作；稀疏多項(xiàng)式的抽象數(shù)據(jù)類型定義、表示和加法的實(shí)現(xiàn)。

學(xué)習(xí)要求：

1．線性表的定義及其邏輯特征

（A）

2．線性表的抽象數(shù)據(jù)類型定義

（B）

3．順序表的存儲(chǔ)結(jié)構(gòu)、基本操作算法及其時(shí)間性能

（A）

4．各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表操作的基本方法及其時(shí)間性能

（A）

5．靜態(tài)鏈表和間接尋址的存儲(chǔ)方法

（B）

6．順序表類、單鏈表類與線性表處向數(shù)據(jù)類型之間的關(guān)系

（B）第3章

特殊線性表——棧、隊(duì)列和串(6學(xué)時(shí))

主要內(nèi)容：

棧和隊(duì)列的結(jié)構(gòu)特性，在兩種存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)棧和隊(duì)列的基本操作，以及棧和隊(duì)列在程序設(shè)計(jì)中的應(yīng)用。串的數(shù)據(jù)類型定義；串的3種存儲(chǔ)表示；定長順序存儲(chǔ)結(jié)構(gòu)、塊鏈存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用；串的模式匹配算法。

學(xué)習(xí)要求：

1．棧的定義及其操作特性

（A）

2．棧的抽象數(shù)據(jù)類型定義

（B）

3．順序棧和鏈棧的實(shí)現(xiàn)方法

（A）

4．隊(duì)列的定義及其操作特性

（A）

5．隊(duì)列的抽象數(shù)據(jù)類型定義

（B）

6．順序隊(duì)列和鏈隊(duì)列的實(shí)現(xiàn)方法

（A）

7．串的定義及其基本概念

（B）

8．串的存儲(chǔ)方法、BF算法的執(zhí)行過程

（B）

第4章

廣義線性表——多維數(shù)組合廣義表(4學(xué)時(shí))

主要內(nèi)容：

數(shù)組是一種十分常用的數(shù)據(jù)結(jié)構(gòu)，大多數(shù)程序設(shè)計(jì)語言都支持?jǐn)?shù)組類型。本章重點(diǎn)介紹數(shù)組的內(nèi)部實(shí)現(xiàn)，即如何在計(jì)算機(jī)內(nèi)部處理數(shù)組，其中的主要問題是數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址。廣義表示一種特殊的數(shù)據(jù)結(jié)構(gòu)，它兼有線性表、樹、圖等結(jié)構(gòu)的特點(diǎn)。

學(xué)習(xí)要求：

1．?dāng)?shù)組的定義、存儲(chǔ)結(jié)構(gòu)及尋址方法

（A）

2．矩陣壓縮存儲(chǔ)的基本思想

（B）

3．特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法及尋址方法（A）

4．三元組順序表的轉(zhuǎn)置運(yùn)算

（B）

5．廣義表的定義及其基本概念（A）

6．廣義表的存儲(chǔ)結(jié)構(gòu)

（B）

7．廣義表的基本運(yùn)算

（C）第5章

樹和二叉樹(8學(xué)時(shí))

主要內(nèi)容：

二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；二叉樹的遍歷和線索化以及遍歷算法的各種描述形式；樹和森林的定義、存儲(chǔ)結(jié)構(gòu)、與二叉樹樹的轉(zhuǎn)換、遍歷；樹的多種應(yīng)用。本章是課程的重點(diǎn)內(nèi)容之一。

學(xué)習(xí)要求：

1．樹的定義及其基本術(shù)語

（A）

2．樹的抽象數(shù)據(jù)類型定義

（B）

3．樹的各種存儲(chǔ)方法

（A）

4．樹和森林的遍歷方法

（A）

5．二叉樹的定義及特點(diǎn)、二叉樹的基本性質(zhì)

（A）

6．二叉樹的各種存儲(chǔ)結(jié)構(gòu)方法、遍歷方法及實(shí)現(xiàn)（A）

7．樹、森林與二叉樹樹的轉(zhuǎn)換方法

（A）

8．哈夫曼樹的構(gòu)造方法和哈夫曼編碼方法

（A）

9．哈夫曼樹的構(gòu)造算法

（B）

第6章

圖(8學(xué)時(shí))

主要內(nèi)容：

圖的定義和術(shù)語；圖的四種存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法、鄰接表、十字鏈表和鄰接多重表；圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索；圖的連通性：連通分量和最小生成樹；拓?fù)渑判蚝完P(guān)鍵路徑；兩類求最短路徑問題的解法。

學(xué)習(xí)要求：

1．圖的定義及其基本術(shù)語

（A）

2．圖的鄰接矩陣和鄰接表存儲(chǔ)（A）

3．圖的遍歷方法及其在鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)

（A）

4． 無向圖和有向圖的連通性

（B）

5． Prim算法和Kruskal算法的基本思想和求解過程

（A）6． Prim算法和Kruskal算法的C++描述

（B）

7． Dijkstra算法和Floyd算法的基本思想和求解過程

（A）8． 拓?fù)渑判虻亩x及拓?fù)渑判蛩惴?/p>

（A）9． 關(guān)鍵路徑的定義及求解過程

（A）10．關(guān)鍵路徑算法

（B）第7章

查找技術(shù)(6學(xué)時(shí))

主要內(nèi)容：

討論查找表(包括靜態(tài)查找表和動(dòng)態(tài)查找表)的各種實(shí)現(xiàn)方法：順序表、有序表、二叉排序樹、平衡二叉樹和散列表；以及關(guān)于衡量查找表的主要操作—查找的查找效率的平均查找長度的討論。

學(xué)習(xí)要點(diǎn)：

1．查找的基本概念以及查找算法的時(shí)間性能分析

（B）

2．順序表和折半查找技術(shù)

（A）

3．二叉排序樹的定義、查找算法及時(shí)間性能

（A）

4．平衡二叉樹的定義及調(diào)整方法

（A）

5．平衡二叉樹的插入算法

（C）

6．散列的基本思想和基本概念

（A）

7．散列技術(shù)中處理沖突的方法

（A）

8．散列技術(shù)的查找性能

（B）第8章

排序技術(shù)(8學(xué)時(shí))

學(xué)習(xí)內(nèi)容：

討論和比較各種內(nèi)部排序方法：插入排序、交換排序、選擇排序、堆排序和歸并排序的基本思想、算法特點(diǎn)、排序過程以及它們的進(jìn)間復(fù)雜度分析。

學(xué)習(xí)要點(diǎn)：

1．排序的定義以及評(píng)價(jià)排序算法的標(biāo)準(zhǔn)

（A）

2．直接插入排序算法及其時(shí)間性能

（A）

3．希爾排序

（B）

4．起泡排序算法及其時(shí)間性能

（A）

5．快速排序算法及其時(shí)間性能和空間性能

（A）

6．簡單選擇排序算法及其時(shí)間性能

（A）

7．堆的定義及構(gòu)建堆的方法、堆排序算法及其時(shí)間性能

（A）

8．二路歸并排序算法及其時(shí)間性能和空間性能

（A）

9．各種排序方法的比較及結(jié)論

（A）課程實(shí)踐活動(dòng)成果展示課(2學(xué)時(shí))

對(duì)課程涉及的線性表、樹、圖及查找排序算法等核心內(nèi)容，要求學(xué)生結(jié)合實(shí)際問題進(jìn)行自主選題，利用課外學(xué)習(xí)團(tuán)隊(duì)完成相應(yīng)原理的動(dòng)畫制作，相應(yīng)算法的編寫與實(shí)現(xiàn)。為每個(gè)團(tuán)隊(duì)提供展示作品的舞臺(tái)，相互交流，進(jìn)行評(píng)比，教師點(diǎn)評(píng)及總結(jié)。

五、實(shí)驗(yàn)內(nèi)容和實(shí)驗(yàn)要求（學(xué)時(shí)數(shù): 18）

1.基本要求

數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性較強(qiáng)的課程，每個(gè)學(xué)生必須完成一定數(shù)量的上機(jī)作業(yè)。通過上機(jī)作業(yè)，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和存儲(chǔ)表示，基本數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法、上機(jī)操作等基本技能和科學(xué)作風(fēng)方面接受比較系統(tǒng)的、嚴(yán)格的訓(xùn)練。

本課程始終堅(jiān)持理論和實(shí)際相結(jié)合的原則，布置足夠多的習(xí)題和較大型的上機(jī)實(shí)踐題。為了鞏固課堂所學(xué)知識(shí)，要求學(xué)生課內(nèi)、課外時(shí)間比達(dá)到1：1.5~1：2，以便更好地鞏固基本算法，提高分析和設(shè)計(jì)算法的能力，為后續(xù)課程的學(xué)習(xí)打好基礎(chǔ)。2．實(shí)驗(yàn)教學(xué)安排

實(shí)驗(yàn)一 線性表

（2學(xué)時(shí)）

了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；掌握這兩種存儲(chǔ)結(jié)構(gòu)的描述方法；掌握線性表的基本操作（查找、插入、刪除）；考慮時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行算法設(shè)計(jì)。實(shí)驗(yàn)二 棧

（2學(xué)時(shí)）

理解棧的定義、特點(diǎn)及與線性表的異同； 熟悉順序棧的組織方法，棧滿、棧空的判斷條件及其描述；掌握棧的基本操作（進(jìn)棧、退棧等）。

實(shí)驗(yàn)三 隊(duì)列

（2學(xué)時(shí)）

理解隊(duì)列的定義、特點(diǎn)及與線性表的異同； 熟悉隊(duì)列的組織方法，隊(duì)列滿、隊(duì)列空的判斷條件及其描述； 掌握隊(duì)列的基本操作（入隊(duì)、出隊(duì)等）。實(shí)驗(yàn)四 二叉樹

（2學(xué)時(shí)）

掌握二叉樹的結(jié)構(gòu)特性和二叉鏈表的存儲(chǔ)結(jié)構(gòu)；理解二叉樹、完全二叉樹、滿二叉樹的概念和存儲(chǔ)特點(diǎn)；掌握二叉樹遍歷的遞歸和非遞歸方法。實(shí)驗(yàn)五 哈夫曼樹

（2學(xué)時(shí)）

理解哈夫曼樹的概念、結(jié)構(gòu)特性和哈夫曼編碼原理；掌握構(gòu)造哈夫曼樹的基本方法；掌握運(yùn)用哈夫曼樹進(jìn)行哈夫曼編碼的方法。

實(shí)驗(yàn)六 圖的存儲(chǔ)

（2學(xué)時(shí)）

理解圖的基本概念、圖的結(jié)構(gòu)特性；掌握鄰接表表示圖的基本方法；掌握連通圖遍歷的基本的方法。實(shí)驗(yàn)七 圖的應(yīng)用

（2學(xué)時(shí)）

理解拓?fù)渑判虻幕靖拍詈屯負(fù)渑判虻膶?shí)用意義；掌握AOV網(wǎng)解決拓?fù)渑判騿栴}的基本方法。理解最小生成樹的基本概念和實(shí)用意義；掌握利用MST性質(zhì)構(gòu)造最小生成樹的prim算法和Kruskal算法。

實(shí)驗(yàn)八 查找

（2學(xué)時(shí)）

理解查找表的基本概念，定義、分類和各類的特點(diǎn)；掌握哈希表的構(gòu)造方法以及解決沖突的方法；掌握哈希存儲(chǔ)和哈希查找的基本思想及有關(guān)方法。實(shí)驗(yàn)九 排序

（2學(xué)時(shí)）

理解各類內(nèi)部排序的基本思想；掌握各類內(nèi)部排序的基本方法；了解各類內(nèi)部排序的優(yōu)缺點(diǎn)。

六、教材及參考書

1．理論課教材

理論課教材：

王紅梅等．?dāng)?shù)據(jù)結(jié)構(gòu)（C++版）[M] ．北京：清華大學(xué)出版社，2007 實(shí)驗(yàn)課教材：

王紅梅等． 數(shù)據(jù)結(jié)構(gòu)（C++版）學(xué)習(xí)輔導(dǎo)和實(shí)驗(yàn)指導(dǎo)[M] ．北京：清華大學(xué)出版社，2006 2．主要參考文獻(xiàn)

[1] 許卓群．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：高等教育出版社，2006 [2] 殷人昆．?dāng)?shù)據(jù)結(jié)構(gòu)C＋＋實(shí)現(xiàn)[M]．北京：清華大學(xué)出版社，2006 [3] 黃國瑜，葉乃菁．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：清華大學(xué)出版社，2005

[4] 胡學(xué)剛．?dāng)?shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)指導(dǎo)[M]．北京：清華大學(xué)出版社，2004 [5] 胡元義，鄧亞玲，徐睿琳．?dāng)?shù)據(jù)結(jié)構(gòu)課程輔導(dǎo)與習(xí)題解析[M]．北京：人民郵電出版社，2003 [6] 羅文，王苗，石強(qiáng)．?dāng)?shù)據(jù)結(jié)構(gòu)習(xí)題解答與實(shí)驗(yàn)指導(dǎo)[M]．北京：中國鐵道出版社，2003 [7] 王曉東．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）[M]．北京：電子工業(yè)出版社，2007 [8] 陳慧南．?dāng)?shù)據(jù)結(jié)構(gòu)——使用C++語言描述[M]．北京：人民郵電出版社，2006 [9] 呂國英．算法設(shè)計(jì)與分析[M]．北京：清華大學(xué)出版社，2006 [10] Sartaj Sahni．Data Structures, Algorithms and Applications in C++[M]．北京：機(jī)械工業(yè)出版社，2003 [11] William Ford．Data Structure with C++[M]．北京：清華大學(xué)出版社，2001 [12] 蘇光奎．?dāng)?shù)據(jù)結(jié)構(gòu)導(dǎo)學(xué)[M]．北京：清華大學(xué)出版社，2002 [13] 嚴(yán)蔚敏等．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）[M]．北京：清華大學(xué)出版社，2002 [14]（美）Michael T.Goodrich，Roberto Tamassia著．霍紅衛(wèi)譯．算法分析與設(shè)計(jì)[M]．北京：人民郵電出版社 [15]（美）Bruno R.Preiss著．胡廣斌等譯．?dāng)?shù)據(jù)結(jié)構(gòu)與算法—面向?qū)ο蟮腃++設(shè)計(jì)模式 [M]．北京： 電子工業(yè)出版社

七、考核方式

以閉卷考試為主，結(jié)合平時(shí)作業(yè)及自主應(yīng)用和設(shè)計(jì)綜合評(píng)定成績。各部分分配比例為： 期末考試成績70%，平時(shí)作業(yè)及考勤10%，實(shí)驗(yàn)10%，自主設(shè)計(jì)作品或期中考核10%。

執(zhí)筆人： 白明

編寫日期： 2007-10-31 7

第二篇：數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)與算法》教學(xué)大綱

課程編號(hào)：030816 適用專業(yè)：教育技術(shù)學(xué) 總學(xué)時(shí)數(shù)：64

學(xué) 分：4 編制單位：茂名學(xué)院理學(xué)院教育與信息技術(shù)系 編制時(shí)間：2008年6月20日

一、課程地位、性質(zhì)和任務(wù)

《數(shù)據(jù)結(jié)構(gòu)與算法》課程是計(jì)算機(jī)相關(guān)學(xué)科專業(yè)的基礎(chǔ)課程中的一門重要的核心課程。通過本課程的教學(xué)，使學(xué)生知道求解非數(shù)值類問題的基本模型（表、樹、圖），模型的特點(diǎn)和適用場(chǎng)合，能夠根據(jù)問題設(shè)計(jì)和選擇好的算法，為學(xué)習(xí)后續(xù)的操作系統(tǒng)、編譯原理和軟件工程等專業(yè)課程，設(shè)計(jì)應(yīng)用程序打下基礎(chǔ)。

本課程以提高學(xué)生的計(jì)算機(jī)應(yīng)用能力和綜合素質(zhì)為目標(biāo)，通過課程教學(xué)，為學(xué)生構(gòu)建數(shù)據(jù)結(jié)構(gòu)與算法方面的知識(shí)體系，使學(xué)生一方面能夠根據(jù)問題選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)高效的算法，提高程序設(shè)計(jì)能力，另一方面，在工程應(yīng)用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個(gè)方面，提高學(xué)生的程序設(shè)計(jì)能力。

二、與其他課程的關(guān)系

先修課：程序設(shè)計(jì)基礎(chǔ)、離散數(shù)學(xué)、計(jì)算機(jī)組成原理、計(jì)算機(jī)文化基礎(chǔ)

三、教學(xué)內(nèi)容、課時(shí)安排和基本要求

（一）教學(xué)部分 第1章 緒論（2學(xué)時(shí)）1.1什么是數(shù)據(jù)結(jié)構(gòu) 1.2 基本概念和術(shù)語

1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)

1.4 算法和算法分析（算法及其設(shè)計(jì)的要求，算法效率的度量，算法的存儲(chǔ)空間需求）1.5 問題求解

基本要求：

了解：抽象數(shù)據(jù)類型，算法設(shè)計(jì)方法與算法分析。

掌握：數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)、算法的基本概念；問題求解的方法與步驟 重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)和算法的概念，算法的描述形式和評(píng)價(jià)方法，問題求解的一般步驟 難點(diǎn)：評(píng)價(jià)算法的標(biāo)準(zhǔn)和評(píng)價(jià)方法，最壞情況和平均情況的區(qū)分。

第2章 線性表（8學(xué)時(shí)）2.1 線性表的類型定義 2.2 線性表的順序表示和實(shí)現(xiàn)

2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（線性鏈表，循環(huán)鏈表，雙向鏈表）2.4 一元多項(xiàng)式的表示及相加

基本要求：

了解：兩種存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）及一元多項(xiàng)式的表示及相加。

掌握：要求熟練掌握處理線性表的各種算法。為后繼章節(jié)的學(xué)習(xí)打基礎(chǔ)。重點(diǎn)：各種算法。難點(diǎn)：鏈表的理解。

第3章 棧與隊(duì)列（4學(xué)時(shí)）

3.1 棧（定義，棧的表示和實(shí)現(xiàn)）

3.2 棧的應(yīng)用舉例（數(shù)制轉(zhuǎn)換，括號(hào)匹配的檢驗(yàn)，行編輯程序，迷宮求解，表達(dá)式求值）

3.3 棧與遞歸的實(shí)現(xiàn)

3.4 隊(duì)列及其實(shí)現(xiàn)（定義，鏈隊(duì)列，循環(huán)隊(duì)列）3.5 *離散事件模擬

教學(xué)要求：熟練掌握棧和隊(duì)列的特性和在不同存儲(chǔ)結(jié)構(gòu)前提下的算法實(shí)現(xiàn)。棧和隊(duì)列是表最基本和重要的數(shù)據(jù)結(jié)構(gòu)，是數(shù)據(jù)結(jié)構(gòu)課程的基礎(chǔ)。

基本要求：

了解： 棧和隊(duì)列的定義及其實(shí)現(xiàn)。

掌握： 熟練掌握棧和隊(duì)列的特性和在不同存儲(chǔ)結(jié)構(gòu)前提下的算法實(shí)現(xiàn)。重點(diǎn)： 棧和隊(duì)列的算法實(shí)現(xiàn)。難點(diǎn)： 棧和隊(duì)列的算法實(shí)現(xiàn)。

第4章 串（2學(xué)時(shí)）4.1 串類型的定義

4.2 串的表示和實(shí)現(xiàn)（定長順序存儲(chǔ)，堆分配存儲(chǔ)，串的塊鏈存儲(chǔ)）4.3 串的模式匹配算法（求子串位置的定位函數(shù)，模式匹配的一種改進(jìn)算法）4.4 串操作應(yīng)用舉例（文本編輯，建立詞索引表）

基本要求：

了解：串的基本概念及主要操作和運(yùn)算。掌握：掌握串的基本概念和運(yùn)算。重點(diǎn)：主要操作和運(yùn)算。難點(diǎn)：模式匹配及串的應(yīng)用。

第5章 數(shù)組（2學(xué)時(shí)）5.1 數(shù)組的定義

5.2 數(shù)組的順序表示和實(shí)現(xiàn)

5.3 矩陣的壓縮存儲(chǔ)（特殊矩陣，稀疏矩陣）5.4 廣義表的定義 5.5 廣義表的存儲(chǔ)結(jié)構(gòu) 5.6 m元多項(xiàng)式的表示

5.7 廣義表的遞歸算法（求廣義表的深度，復(fù)制廣義表，建立廣義表的存儲(chǔ)結(jié)構(gòu)）

基本要求：

了解：了解作為抽象數(shù)據(jù)類型的數(shù)組和C語言的數(shù)組。認(rèn)識(shí)到數(shù)組可以作為順序存儲(chǔ)結(jié)構(gòu)用于順序表、字符串和稀疏矩陣的實(shí)現(xiàn)。也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

掌握：掌握基本概念和算法。重點(diǎn)：算法。

難點(diǎn)：廣義表的遞歸算法。

第6章 樹與二叉樹（15學(xué)時(shí)）6.1 樹的定義和基本術(shù)語

6.2 二叉樹（二叉樹的定義，二叉樹的性質(zhì)，二叉樹的存儲(chǔ)結(jié)構(gòu)）6.3 遍歷二叉樹和線索二叉樹（遍歷二叉樹，線索二叉樹）

6.4 樹和森林（樹的存儲(chǔ)結(jié)構(gòu)，森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷）6.5 樹與等價(jià)問題

6.6 赫夫曼樹及其應(yīng)用（最優(yōu)二叉樹（赫夫曼樹），赫夫曼編碼）6.7 回溯法與樹的遍歷 6.8 樹的計(jì)數(shù)

基本要求：

了解：理解樹與森林的定義與術(shù)語。

掌握：熟練掌握二叉樹性質(zhì)和遍歷算法，掌握樹與森林的孩子兄弟存儲(chǔ)表示和遍歷。掌握哈夫曼樹構(gòu)造的方法和算法。重點(diǎn)： 樹的存儲(chǔ)結(jié)構(gòu)和遍歷算法。難點(diǎn)：哈夫曼樹構(gòu)造的方法和算法

第7章 圖（11學(xué)時(shí)）7.1 圖的定義和術(shù)語

7.2 圖的存儲(chǔ)結(jié)構(gòu)（數(shù)組表示法，鄰接表，十字鏈表，鄰接多重表）7.3 圖的遍歷（深度優(yōu)先搜索，廣度優(yōu)先搜索）

7.4 圖的連通性問題（無向圖的連通分量和生成樹，有向圖的強(qiáng)連通分量，最小生成樹，關(guān)節(jié)點(diǎn)和重連通分量）

7.5 有向無環(huán)圖及其應(yīng)用（拓?fù)渑判颍P(guān)鍵路徑）

7.6 最短路徑（從某個(gè)源點(diǎn)到其余各項(xiàng)點(diǎn)的最短路徑，每一對(duì)頂點(diǎn)之間的最短路徑）基本要求：

了解：圖的基本概念和相關(guān)術(shù)語。

掌握：圖的兩種主要存儲(chǔ)結(jié)構(gòu)及遍歷算法。掌握最小生成樹、最短路徑和活動(dòng)網(wǎng)算法的思想。

重點(diǎn)：圖的兩種主要存儲(chǔ)結(jié)構(gòu)及遍歷算法。難點(diǎn)：圖的遍歷算法，最短路徑算法。

第8章 查找（8學(xué)時(shí)）

9.1 靜態(tài)查找表（順序表，有序表，靜態(tài)樹表，索引順序表）9.2 動(dòng)態(tài)查找表（二叉排序樹和平衡二叉樹，B_樹和B+樹，鍵樹）9.3 哈希表（定義，構(gòu)造方法，處理沖突的方法，查找及其分析）

基本要求：

了解： 各種查找法的基本概念及實(shí)現(xiàn)的基本思想。

掌握：熟練掌握搜索結(jié)構(gòu)的折半查找、二叉搜索樹、平衡二叉樹主要搜索算法。掌握哈希表查找算法。重點(diǎn)：各種算法的基本思想及實(shí)現(xiàn)。難點(diǎn)：哈希表查找算法。

第9章 內(nèi)部排序（8學(xué)時(shí)）10.1 概述

10.2 插入排序（直接插入，其他插入，希爾）10.3 交換排序（冒泡排序、快速排序）10.4 選擇排序（簡單，樹形，堆）10.5 歸并排序

10.6 基數(shù)排序（多關(guān)鍵字，鏈?zhǔn)剑?0.7 排序算法分析

基本要求：

了解：基數(shù)排序，排序算法分析方法

掌握：排序的基本概念，插入排序，交換排序，選擇排序，歸并排序重點(diǎn)：內(nèi)部排序算法

難點(diǎn)：基數(shù)排序（多關(guān)鍵字，鏈?zhǔn)剑?/p>

第10章 *外部排序（2學(xué)時(shí)）11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡歸并的實(shí)現(xiàn) 11.4 置換-選擇排序 11.5 最佳歸并樹

基本要求：

了解：外部排序的基本概念和相關(guān)術(shù)語。

掌握：基本掌握外排算法的基本思想，不同排序方法的比較。重點(diǎn)：外部排序算法 難點(diǎn)：多路平衡歸并的實(shí)現(xiàn) 第11章 算法設(shè)計(jì)的一般方法（2學(xué)時(shí)）

1．重點(diǎn)

（1）有效算法的概念，問題固有難度的概念；

（2）遞歸法；分治法；平衡原則；貪心法；動(dòng)態(tài)規(guī)劃的基本原理；（3）搜索-回溯法的基本原理和本質(zhì).2．難點(diǎn)

（1）問題固有難度的概念；

（2）遞歸分治法的效率分析（寫出時(shí)間耗費(fèi)的遞推式，并求解）；（3）動(dòng)態(tài)規(guī)劃法中的狀態(tài)轉(zhuǎn)移方程的確定。

（二）實(shí)驗(yàn)、實(shí)習(xí)部分

課程安排五個(gè)類別的實(shí)驗(yàn)，實(shí)驗(yàn)時(shí)數(shù)為12課時(shí)，其中： 實(shí)驗(yàn)

一、線性鏈表及運(yùn)算 2課時(shí) 實(shí)驗(yàn)

二、棧和隊(duì)列 2課時(shí) 實(shí)驗(yàn)

三、樹和二叉樹 4課時(shí) 實(shí)驗(yàn)

四、圖及其應(yīng)用 2課時(shí) 實(shí)驗(yàn)

五、查找與排序 2課時(shí)

四、課程考核方式

閉卷考試70%、平時(shí)作業(yè)與實(shí)驗(yàn)30%

五、建議教材和教學(xué)參考書 參考教材：

1、《數(shù)據(jù)結(jié)構(gòu)》（C語言描述）高等教育出版社 耿國華主編

2、《數(shù)據(jù)結(jié)構(gòu)》（C語言版）清華大學(xué)出版社 嚴(yán)蔚敏，吳偉民編者

3、《數(shù)據(jù)結(jié)構(gòu)題集》（C語言版）清華大學(xué)出版社 嚴(yán)蔚敏，吳偉民編者

4、《數(shù)據(jù)結(jié)構(gòu)》算法實(shí)現(xiàn)及解析（第二版）西安電子科技大學(xué)出版社 高一凡

六、說明

1、因課時(shí)安排少，教學(xué)內(nèi)容多。建議采用多媒體教學(xué)。

2、由于本課程內(nèi)容較多，在實(shí)際教學(xué)中可根據(jù)大綱內(nèi)容，進(jìn)行適當(dāng)調(diào)整。

第三篇：數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱

中央廣播電視大學(xué)“開放教育試點(diǎn)”計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)（本科）

《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱

第一部分 大綱說明

一、課程的性質(zhì)和任務(wù)

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生的一門必修課程。本課程介紹如何組織各種數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)、傳遞和轉(zhuǎn)換。內(nèi)容包括：數(shù)組、鏈接表、棧和隊(duì)列、遞歸、樹與森林、圖、堆與優(yōu)先級(jí)隊(duì)列、集合與搜索結(jié)構(gòu)、排序、索引與散列結(jié)構(gòu)等。課程采用面向?qū)ο蟮挠^點(diǎn)討論數(shù)據(jù)結(jié)構(gòu)技術(shù)，并以兼有面向過程和面向?qū)ο箅p重特色的C++語言作為算法的描述工具，強(qiáng)化數(shù)據(jù)結(jié)構(gòu)基本知識(shí)和面向?qū)ο蟪绦蛟O(shè)計(jì)基本能力的雙基訓(xùn)練。為后續(xù)計(jì)算機(jī)專業(yè)課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。

二、先修課要求

面向?qū)ο蟪绦蛟O(shè)計(jì)、計(jì)算機(jī)數(shù)學(xué)(離散數(shù)學(xué))。

三、課程的教學(xué)基本要求

1、掌握重要數(shù)據(jù)結(jié)構(gòu)的概念、使用方法及實(shí)現(xiàn)技術(shù)；

2、學(xué)會(huì)做簡單的算法分析，包括算法的時(shí)間代價(jià)和空間代價(jià)。

四、教學(xué)方法和教學(xué)形式建議

電視授課為主，結(jié)合面授輔導(dǎo)、面授或電子郵件答疑，進(jìn)行必要的上機(jī)實(shí)驗(yàn)。

五、課程教學(xué)要求的層次

1、熟練掌握：要求學(xué)生能夠全面、深入理解和熟練掌握所學(xué)內(nèi)容，并能夠用其知識(shí)分析、設(shè)計(jì)和解答相關(guān)的應(yīng)用問題。

2、掌握：要求學(xué)生能夠較好地理解和掌握，并且能夠做簡單的分析。

3、了解：要求學(xué)生能夠一般地了解的所學(xué)內(nèi)容。

六、課程實(shí)驗(yàn)

實(shí)驗(yàn)內(nèi)容和要求由省級(jí)電大作出具體規(guī)定，從2004年春開始按該課程實(shí)驗(yàn)教材規(guī)定進(jìn)行。

第二部分 多種媒體教材一體化總體設(shè)計(jì)初步方案

一、學(xué)時(shí)分配

課程教學(xué)總學(xué)時(shí)數(shù)為 72學(xué)時(shí)，4學(xué)分，其中講授學(xué)時(shí)48，實(shí)驗(yàn)24

教 學(xué) 內(nèi) 容

講授學(xué)時(shí)

實(shí)驗(yàn)學(xué)時(shí)

一、數(shù)據(jù)結(jié)構(gòu)基本概念及算法分析

3學(xué)時(shí)

2學(xué)時(shí)

二、數(shù)組

3學(xué)時(shí)

2學(xué)時(shí)

三、鏈表

3學(xué)時(shí)

3學(xué)時(shí)

四、棧和隊(duì)列

3學(xué)時(shí)

2學(xué)時(shí)

五、遞歸

3學(xué)時(shí)

2學(xué)時(shí)

六、樹與森林

9學(xué)時(shí)

4學(xué)時(shí)

七、集合與搜索

5學(xué)時(shí)

2學(xué)時(shí)

八、圖

7學(xué)時(shí)

4學(xué)時(shí)

九、排序

7學(xué)時(shí)

3學(xué)時(shí)

十、索引與散列結(jié)構(gòu)

5學(xué)時(shí)

二、教學(xué)環(huán)節(jié)

1、電視教學(xué)

本課程是計(jì)算機(jī)專業(yè)基礎(chǔ)課，內(nèi)容多且?guī)в幸欢ǖ某橄笮?，學(xué)習(xí)起來有一定難度。為保證教學(xué)效果，采取電視集中授課方式。聘請(qǐng)有經(jīng)驗(yàn)的教師擔(dān)任主講教師，盡可能利用多種媒體進(jìn)行教學(xué)，使學(xué)生能夠很快掌握課程的主要知識(shí)和解決問題的方法。

2、面授輔導(dǎo)或答疑

本課程教學(xué)過程中，面授輔導(dǎo)和答疑是必不可少的教學(xué)環(huán)節(jié)。各地方電大應(yīng)聘請(qǐng)有經(jīng)驗(yàn)、認(rèn)真負(fù)責(zé)的教師任教，以習(xí)題課、專題討論或答疑的方式，對(duì)課程中的重要概念和典型問題的解決方法進(jìn)行總結(jié)和深入討論，鞏固和加深課堂內(nèi)學(xué)到的知識(shí)。面授輔導(dǎo)或答疑安排兩周一次為宜。必要時(shí)可采用電子郵件方式直接與主講教師聯(lián)系進(jìn)行答疑。

3、自學(xué)與練習(xí)

自學(xué)是獲取知識(shí)的重要手段。教師講課只是起到拋磚引玉的作用，關(guān)鍵還在于學(xué)生的自學(xué)。為達(dá)到自學(xué)的效果，除讀懂教科書中所講內(nèi)容外，還需大量做題。其目的是要通過做題弄懂、加深對(duì)概念的理解，提高程序設(shè)計(jì)，解決問題的能力。為此，安排一定的實(shí)驗(yàn)上機(jī)學(xué)時(shí)。要求學(xué)生珍惜實(shí)驗(yàn)機(jī)時(shí)，真正做到學(xué)有所獲。

學(xué)生在上機(jī)做實(shí)驗(yàn)前，應(yīng)事先將程序、調(diào)試數(shù)據(jù)、上機(jī)操作順序準(zhǔn)備好，并提前使用這些調(diào)試數(shù)據(jù)人工執(zhí)行過。目的是提高上機(jī)的效率和成功率，嚴(yán)禁抄襲或拷貝他人的成果，自覺培養(yǎng)科學(xué)、嚴(yán)謹(jǐn)?shù)淖黠L(fēng)。

除學(xué)校提供的時(shí)間外，要求課外學(xué)生利用自己可能擁有的計(jì)算機(jī)條件，完成更多的練習(xí)，不通過大量的實(shí)踐，能力和知識(shí)水平得不到有效得提高。

4、考試

考試是對(duì)學(xué)生掌握知識(shí)水平的檢驗(yàn)。本著多練多考的原則，各地方電大可以再平時(shí)多做一些小考。要求考試內(nèi)容緊扣大綱要求，既要能夠檢驗(yàn)學(xué)生的掌握情況，又要體現(xiàn)水平。因此，不要出難題、怪題，但也不要過于簡單，適當(dāng)有一些編程題。

課程考試具體規(guī)定請(qǐng)參看該課程考核說明。

第三部分 教學(xué)內(nèi)容和教學(xué)要求

一、數(shù)據(jù)結(jié)構(gòu)基本概念及簡單的算法分析 3學(xué)時(shí)

1、教學(xué)內(nèi)容：

什么是數(shù)據(jù)結(jié)構(gòu)

抽象數(shù)據(jù)類型及面向?qū)ο蟾拍睿簲?shù)據(jù)類型；數(shù)據(jù)抽象與抽象數(shù)據(jù)類型；面向?qū)ο蟮母拍?；用于描述?shù)據(jù)結(jié)構(gòu)的語言

數(shù)據(jù)結(jié)構(gòu)的抽象層次

算法定義

性能分析與度量：算法的性能標(biāo)準(zhǔn)；算法的后期測(cè)試；算法的事前估計(jì)；空間復(fù)雜度度量；時(shí)間復(fù)雜度度量；時(shí)間復(fù)雜度的漸進(jìn)表示法；漸進(jìn)的空間復(fù)雜度

2、教學(xué)要求：

了解：什么是數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系

了解：什么是數(shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)抽象和信息隱蔽原則。了解什么是面向?qū)ο?/p>

了解：算法的定義、算法的特性、算法的時(shí)間代價(jià)、算法的空間代價(jià)

掌握：用C++語言描述算法的方法，能夠使用C++語言編寫程序

二、數(shù)組 3學(xué)時(shí)

1、教學(xué)內(nèi)容：

作為抽象數(shù)據(jù)類型的數(shù)組：數(shù)組的定義和初始化；作為抽象數(shù)據(jù)類型的數(shù)組；數(shù)組的順序存儲(chǔ)方式

順序表：順序表的定義和特點(diǎn)；順序表的類定義；順序表的查找、插入和刪除；使用順序表的事例

字符串：字符串的抽象數(shù)據(jù)類型；字符串操作的實(shí)現(xiàn)；字符串的模式匹配

2、教學(xué)要求：

了解：線性表的邏輯結(jié)構(gòu)特性，以及線性表的兩種存儲(chǔ)實(shí)現(xiàn)方式

了解：作為抽象數(shù)據(jù)類型的數(shù)組的定義，數(shù)組的按行順序存儲(chǔ)與按列順序存儲(chǔ)

熟練掌握：順序表的定義與實(shí)現(xiàn)，包括搜索、插入、刪除算法的實(shí)現(xiàn)及其平均比較次數(shù)的計(jì)算，掌握應(yīng)用順序表作為集合的簡單操作

了解：稀疏矩陣的定義及其數(shù)組實(shí)現(xiàn)

熟練掌握：字符串的定義及實(shí)現(xiàn)

三、鏈表 3學(xué)時(shí)

1、教學(xué)內(nèi)容：

單鏈表：單鏈表的結(jié)構(gòu)；單鏈表的類定義；單鏈表中的插入與刪除；帶表頭結(jié)點(diǎn)的單鏈表；用模板定義的單鏈表類；靜態(tài)鏈表

循環(huán)鏈表：循環(huán)鏈表的類定義；用循環(huán)鏈表解約瑟夫問題；

多項(xiàng)式及其相加：多項(xiàng)式的類定義；多項(xiàng)式的加法

雙向鏈表

2、教學(xué)要求：

了解：鏈表與數(shù)組一樣，是一種實(shí)現(xiàn)級(jí)結(jié)構(gòu)。有動(dòng)態(tài)鏈表和靜態(tài)鏈表之分

了解：鏈表有單鏈表、循環(huán)單鏈表、雙向鏈表之分

了解：單鏈表的結(jié)構(gòu)、特點(diǎn)

掌握：單鏈表的類定義、構(gòu)造函數(shù)、單鏈表的插入與刪除算法

了解：帶表頭結(jié)點(diǎn)的單鏈表的優(yōu)點(diǎn)和類定義及相應(yīng)操作的實(shí)現(xiàn)

熟練掌握：用模板定義的單鏈表類

了解：循環(huán)鏈表的特點(diǎn)，循環(huán)鏈表的類定義，以及用循環(huán)鏈表解決問題的方法

掌握：雙向鏈表的特點(diǎn)，雙向鏈表的類定義及相關(guān)操作的實(shí)現(xiàn)，用雙向鏈表解決問題的方法。

四、棧和隊(duì)列 3學(xué)時(shí)

1、教學(xué)內(nèi)容：

棧：棧的抽象數(shù)據(jù)類型；棧的順序存儲(chǔ)表示；棧的鏈接存儲(chǔ)表示

表達(dá)式求值：中綴表達(dá)式求值；中綴表示到后綴表示的轉(zhuǎn)換

隊(duì)列 ：隊(duì)列的抽象數(shù)據(jù)類型；隊(duì)列的順序存儲(chǔ)表示；隊(duì)列的鏈接存儲(chǔ)表示；隊(duì)列的應(yīng)用舉例

優(yōu)先級(jí)隊(duì)列：優(yōu)先級(jí)隊(duì)列的定義；優(yōu)先級(jí)隊(duì)列的存儲(chǔ)表示

2、教學(xué)要求：

熟練掌握：棧的定義、特性和棧的抽象數(shù)據(jù)類型，棧的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。特別注意?？蘸蜅M的條件

了解：在表達(dá)式計(jì)算時(shí)棧是如何使用的，重點(diǎn)了解用后綴表示計(jì)算表達(dá)式及中綴表示改后綴表示的方法和算法思路

熟練掌握：隊(duì)列的定義、特性和隊(duì)列的抽象數(shù)據(jù)類型，隊(duì)列的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況

掌握：優(yōu)先級(jí)隊(duì)列的定義、特性和優(yōu)先級(jí)隊(duì)列的抽象數(shù)據(jù)類型，優(yōu)先級(jí)隊(duì)列的插入與刪除算法

五、遞歸 3學(xué)時(shí)

1、教學(xué)內(nèi)容：

遞歸的概念：遞歸問題的求解

遞歸過程與遞歸工作棧：單向遞歸和尾遞歸的迭代實(shí)現(xiàn)；一般遞歸問題利用棧實(shí)現(xiàn)非遞歸解法

廣義表：廣義表的概念；廣義表的表示及操作；廣義表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)；廣義表的訪問算法；廣義表的遞歸算法

2、教學(xué)要求：

掌握：遞歸的概念。包括什么是遞歸，有那些種類的遞歸，遞歸問題的遞歸求解方法

掌握：遞歸過程的機(jī)制與利用遞歸工作棧實(shí)現(xiàn)遞歸的方法

了解：迷宮問題的遞歸求解思路及如何利用棧實(shí)現(xiàn)迷宮問題的非遞歸解法

掌握：利用遞歸解決問題的分治法和回溯法

掌握：廣義表的定義及其實(shí)現(xiàn)方法

掌握：廣義表的遞歸算法

六、樹與森林 9學(xué)時(shí)

1、教學(xué)內(nèi)容：

樹和森林的概念：樹的定義；樹的術(shù)語；樹的抽象數(shù)據(jù)類型

二叉樹：二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類型

二叉樹的表示：順序表示；二叉鏈表表示

遍歷二叉樹：中序遍歷；前序遍歷；后序遍歷；應(yīng)用二叉樹遍歷的事例；二叉樹的計(jì)數(shù)

線索化二叉樹：線索；中序線索化二叉樹

堆：堆的定義；堆的建立；堆的插入與刪除；堆的調(diào)整算法

樹與森林：樹的存儲(chǔ)表示；森林與二叉樹的轉(zhuǎn)換；遍歷樹；遍歷森林

霍夫曼樹：路徑長度；霍夫曼樹；霍夫曼編碼

2、教學(xué)要求：

了解：樹和森林的概念。包括樹的定義、樹的術(shù)語、樹的抽象數(shù)據(jù)類型

掌握：二叉樹的概念、性質(zhì)及二叉樹的表示

熟練掌握：二叉樹的遍歷方法

掌握：線索化二叉樹的特性及尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法

熟練掌握：堆的定義，堆的建立、堆的插入與刪除、堆的向上和向下調(diào)整等算法以及用來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方法

掌握：樹與森林的實(shí)現(xiàn)，重點(diǎn)在用二叉樹實(shí)現(xiàn)

掌握：森林與二叉樹的轉(zhuǎn)換；樹的遍歷算法

掌握：二叉樹的計(jì)數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法

掌握：霍夫曼樹的實(shí)現(xiàn)方法、構(gòu)造霍夫曼編碼的方法及帶權(quán)路徑長度的計(jì)算

七、集合與搜索 5學(xué)時(shí)

1、教學(xué)內(nèi)容：

集合及其表示：集合基本概念；以集合為基礎(chǔ)的抽象數(shù)據(jù)類型；用位向量實(shí)現(xiàn)集合抽象據(jù)類型；用有序鏈表實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型

并查集：并查集的定義；并查集的實(shí)現(xiàn)

簡單的搜索結(jié)構(gòu)：搜索的概念；靜態(tài)搜索結(jié)構(gòu)；順序搜索；基于有序順序表的順序搜索和折半搜索

二叉搜索樹：二叉搜索樹的定義；二叉搜索樹上的搜索；二叉搜索樹的插入；二叉搜索樹的刪除

AVL樹：AVL樹定義；平衡化旋轉(zhuǎn)；AVL樹的插入和刪除；AVL樹高度

2、教學(xué)要求：

掌握：集合的基本概念及其表示方法，包括位數(shù)組及有序鏈表的表示及其相關(guān)操作的實(shí)現(xiàn)算法

掌握：利用并查集實(shí)現(xiàn)集合的方法

熟練掌握：靜態(tài)搜索表的順序搜索和折半搜索算法及其性能分析方法

熟練掌握：二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法

掌握：AVL樹的平衡化旋轉(zhuǎn)、構(gòu)造、插入、刪除時(shí)的調(diào)整方法及其性能分析

八、圖 7學(xué)時(shí)

1、教學(xué)內(nèi)容：

圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型

圖的存儲(chǔ)表示：鄰接矩陣；鄰接表；鄰接多重表

圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；關(guān)節(jié)點(diǎn)與重連通分量

最小生成樹：kruskul算法；prim算法

單源最短路徑問題：dijkstra算法

活動(dòng)網(wǎng)絡(luò)：AOV網(wǎng)絡(luò)與拓?fù)渑判颍籄OE網(wǎng)絡(luò)與關(guān)鍵路徑

2、教學(xué)要求：

理解：圖的基本概念和圖的抽象數(shù)據(jù)類型

掌握：圖的3種存儲(chǔ)表示：鄰接矩陣、鄰接表和鄰接多重表。對(duì)于前兩種，要求掌握典型操作，如構(gòu)造、求根、找第一個(gè)鄰接頂點(diǎn)、找下一個(gè)鄰接頂點(diǎn)等操作的實(shí)現(xiàn)算法

熟練掌握：圖的兩種遍歷算法與求解連通性問題的方法。包括深度優(yōu)先搜索和廣度優(yōu)先搜索算法、求連通分量的方法(不要求算法)

理解：求解關(guān)節(jié)點(diǎn)及構(gòu)造重連通圖的方法(不要求算法)

掌握：構(gòu)造最小生成樹的Prim算法和Kruskal算法，要求理解算法

理解：如何用Dijkstra方法求解單源最短路徑問題(不要求算法)

熟練掌握：活動(dòng)網(wǎng)絡(luò)的拓?fù)渑判蛩惴?/p>

掌握：求解關(guān)鍵路徑的方法

九、排序 7學(xué)時(shí)

1、教學(xué)內(nèi)容：

概述

插入排序：直接插入排序；折半插入排序；鏈表插入排序；希爾排序

交換排序：起泡排序；快速排序

選擇排序：直接選擇排序；錦標(biāo)賽排序；堆排序

歸并排序：歸并；迭代的歸并排序算法；遞歸的鏈表歸并排序

基數(shù)排序：多關(guān)鍵碼排序；鏈?zhǔn)交鶖?shù)排序

外排序：外排序的基本過程；k路平衡歸并；初始?xì)w并段的生成；最佳歸并樹

2、教學(xué)要求：

掌握：排序的基本概念和性能分析方法

掌握：插入排序、交換排序、選擇排序、歸并排序等內(nèi)排序的方法及其性能分析方法

了解：基數(shù)排序方法及其性能分析方法

掌握：多路平衡歸并等外排序方法及敗者樹構(gòu)造方法

掌握：生成初始?xì)w并段及敗者樹構(gòu)造方法

掌握：最佳歸并樹的建立方法

十、索引與散列結(jié)構(gòu) 5學(xué)時(shí)

1、教學(xué)內(nèi)容：

靜態(tài)索引結(jié)構(gòu)：線性索引；倒排索引；m路靜態(tài)查找樹

動(dòng)態(tài)索引結(jié)構(gòu)：動(dòng)態(tài)的m路查找樹；B樹的定義；B樹的插入；B樹的刪除；B+樹

散列：散列表與散列方法；散列函數(shù)；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析

2、教學(xué)要求：

熟練掌握：靜態(tài)索引結(jié)構(gòu)，包括線性索引、倒排索引、靜態(tài)索引樹的搜索和構(gòu)造方法

熟練掌握：動(dòng)態(tài)索引結(jié)構(gòu)，包括B樹、B+樹的搜索和構(gòu)造方法

熟練掌握：散列法，包括散列函數(shù)的構(gòu)造、解決沖突的方法

第四篇：數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱

數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱

一、課程基本概況

課程名稱：數(shù)據(jù)結(jié)構(gòu)

課程名稱（英文）： Data Structures

課程編號(hào)：B09042

課程總學(xué)時(shí)：60（其中，講課48，實(shí)驗(yàn)12）

課程學(xué)分：3

課程分類：專業(yè)選修課

開設(shè)學(xué)期：4

適用專業(yè)：計(jì)算機(jī)網(wǎng)絡(luò)工程本科

先修課程：集合論，圖論，高級(jí)語言（結(jié)構(gòu)或記錄，指針）

后續(xù)課程：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等

二、課程的性質(zhì)、目的和任務(wù)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的一門核心專業(yè)課程，是軟件課程中非常重要的一門課程，在整個(gè)專業(yè)教學(xué)中占有十分重要的地位，是一門理論性非常強(qiáng)的課程。通過課堂教學(xué)、課外練習(xí)和上機(jī)實(shí)習(xí)，使學(xué)生了解數(shù)據(jù)對(duì)象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實(shí)世界問題在計(jì)算機(jī)中如何表示和處理的能力以及培養(yǎng)良好的程序設(shè)計(jì)技能，為后續(xù)課程的學(xué)習(xí)和科研工作的參與打下良好的基礎(chǔ)。

三、主要內(nèi)容、重點(diǎn)及深度

本門課程共60學(xué)時(shí)，其中理論教學(xué)48學(xué)時(shí)，實(shí)驗(yàn)教學(xué)12學(xué)時(shí)。其中，理論教學(xué)部分：

第一章

緒論

（一）目的要求

了解數(shù)據(jù)結(jié)構(gòu)的意義與發(fā)展過程、數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中的作用、學(xué)習(xí)本課程的目的、任務(wù)及要求。理解數(shù)據(jù)結(jié)構(gòu)的基本概念；算法設(shè)計(jì)；掌握算法的時(shí)間和空間復(fù)雜度。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.相關(guān)的基本概念(掌握)；

2.算法五大要素(掌握)；

3.計(jì)算語句頻度和估算算法時(shí)間復(fù)雜度的方法（掌握）。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義；算法的描述方法。

難點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義；算法與程序的區(qū)別；時(shí)間復(fù)雜度及其計(jì)算。

第二章

線性表

（一）目的要求

掌握線性表的邏輯結(jié)構(gòu)；線性表的存儲(chǔ)結(jié)構(gòu)及操作的實(shí)現(xiàn)；理解一元多項(xiàng)式的表示；

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.線性表的邏輯結(jié)構(gòu)(掌握)；2.線性表的存儲(chǔ)結(jié)構(gòu)(掌握)；

3.線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)基本操作的方法(掌握)；

4.從時(shí)間和空間復(fù)雜度的角度比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：線性表的概念；線性表的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其常用算法。難點(diǎn)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其常用算法；雙向循環(huán)鏈表。

第三章 棧和隊(duì)列

（一）目的要求

掌握棧的定義，表示及實(shí)現(xiàn)；表達(dá)式求值；棧與遞歸過程；隊(duì)列的定義、表示及實(shí)現(xiàn)。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)： 1.棧和隊(duì)列的特點(diǎn)(掌握)；

2.在兩種存儲(chǔ)結(jié)構(gòu)上棧的基本操作的實(shí)現(xiàn)(掌握)； 3.循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算(熟練掌握)； 4.遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：堆棧和隊(duì)列的概念；遞歸的定義；循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算。難點(diǎn)：遞歸的編程實(shí)現(xiàn)；循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算。

第四章 串

（一）目的要求

了解串的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)；掌握串操作的實(shí)現(xiàn)(重點(diǎn)難點(diǎn)BF和KMP算法)串的應(yīng)用。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.串的七種基本運(yùn)算的定義（了解）；

2.利用這些基本運(yùn)算來實(shí)現(xiàn)串的其它各種運(yùn)算的方法(掌握)； 3.在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法(掌握)；

4.KMP算法，熟悉NEXT函數(shù)和改進(jìn)NEXT函數(shù)的定義和計(jì)算(掌握)； 5.串名的存儲(chǔ)映象和在堆存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)串操作的方法(理解)。

（三）重點(diǎn)與難點(diǎn) 重點(diǎn)：串定義和存儲(chǔ)方法；串的操作 難點(diǎn)：串操作實(shí)現(xiàn)方法

第五章 數(shù)組和廣義表

（一）目的要求

掌握數(shù)組的存儲(chǔ)結(jié)構(gòu)；稀疏矩陣的表示及操作的實(shí)現(xiàn)；廣義表的定義和存儲(chǔ)結(jié)構(gòu)；廣義表的遞歸算法。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：1.數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法(掌握)； 2.矩陣實(shí)現(xiàn)壓縮存儲(chǔ)時(shí)的下標(biāo)變換(掌握)；

3.理解稀疏矩陣的兩種存儲(chǔ)方式的特點(diǎn)和適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行運(yùn)算采用的處理方法(掌握)；

4.廣義表的定義及其存儲(chǔ)結(jié)構(gòu)，學(xué)會(huì)廣義表的表頭，表尾分析方法(掌握)； 5.學(xué)習(xí)編制廣義表的遞歸算法(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：多維數(shù)組元素存儲(chǔ)地址的計(jì)算；稀疏矩陣的三元組表示；廣義表的存儲(chǔ)定義、操作。難點(diǎn)：稀疏矩陣的三元組表示；廣義表的存儲(chǔ)定義、操作。

第六章 樹和二叉樹

（一）目的要求

了解樹的基本概念；理解二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)；遍歷二叉樹和線索二叉樹；理解樹的存儲(chǔ)結(jié)構(gòu)和遍歷；集合的一種表示方法；掌握哈夫曼樹及其應(yīng)用；

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)： 1.二叉樹的結(jié)構(gòu)特點(diǎn)(理解)；

2.二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍(掌握)； 3.按各種次序遍歷二叉樹的遞歸和非遞歸算法(掌握)；

4.二叉樹的線索化，在中序線索樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法(掌握)； 5.樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)(掌握)； 6.編寫樹的各種運(yùn)算的算法(掌握)；

7.建立最優(yōu)二叉樹和哈夫曼編碼的方法(掌握)。

（三）重點(diǎn)與難點(diǎn) 重點(diǎn)：二叉樹的概念、性質(zhì)；二叉樹的遍歷方式；構(gòu)造二叉排序樹。難點(diǎn)：二叉樹的遍歷方式；二叉排序樹的構(gòu)造方法；二叉樹的線索化。

第七章 圖

（一）目的要求

理解圖的基本概念；圖的存儲(chǔ)結(jié)構(gòu)；掌握?qǐng)D的遍歷及應(yīng)用{最小生成樹，最短路徑等}；拓?fù)渑判蚝完P(guān)鍵路徑。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)： 1.熟悉圖的各種存儲(chǔ)結(jié)構(gòu)；

2.了解實(shí)際問題與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系(掌握)； 3.遍歷圖的遞歸和非遞歸算法(掌握)；

4.應(yīng)用圖的遍歷算法求各種簡單路徑問題（比如，最小生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑等）(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：圖的存儲(chǔ)結(jié)構(gòu)；圖的遍歷 難點(diǎn)：圖遍歷的算法；

第八章

動(dòng)態(tài)存儲(chǔ)管理

（一）目的要求

了解邊界標(biāo)識(shí)法和伙伴系統(tǒng)；無用單元收集和緊縮；

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.存儲(chǔ)器分配策略和算法（了解）；

2.無用單元收集時(shí)的標(biāo)志算法（了解）。

（三）重點(diǎn)與難點(diǎn)

存儲(chǔ)器分配策略和算法、無用單元收集時(shí)的標(biāo)志算法

第九章

查找

（一）目的要求

了解靜態(tài)查找表(順序表，有序表，索引順序表)；動(dòng)態(tài)查找表(二叉排序樹，平衡二叉樹，B-樹和B+樹)的建立和查找；掌握哈希表的建立，查找及分析；

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.順序查找、折半查找和索引查找的方法、應(yīng)用(掌握)；

2.二叉排序樹的構(gòu)造方法(掌握)；

3.二叉平衡樹的建立方法(掌握)；

4.B-樹，B+樹和鍵樹的特點(diǎn)以及它們的建立過程（理解）；

5.哈希表的構(gòu)造方法(掌握)；

6.按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)和失敗時(shí)的平均查找長度；

7.哈希表在查找不成功時(shí)的平均查找長度的計(jì)算方法(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：二叉排序樹的構(gòu)造方法、二叉平衡樹的建立方法；哈希表的構(gòu)造、應(yīng)用；

難點(diǎn)：二叉排序樹的構(gòu)造及應(yīng)用；哈希表的構(gòu)造方法；查找的平均長度。

第十章

內(nèi)部排序

（一）目的要求

掌握插入排序、交換排序(起泡排序，快速排序)、選擇排序(簡單選擇，樹形選擇，堆)、歸并排序、基數(shù)排序等算法。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.各種排序方法的特點(diǎn)并能靈活應(yīng)用(掌握)； 2.各種方法的排序過程(掌握)；

3.各種排序方法的時(shí)間復(fù)雜度分析(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：各種排序方法的特點(diǎn)及其應(yīng)用；實(shí)現(xiàn)排序的各種算法。難點(diǎn)：各種排序算法的時(shí)間復(fù)雜度分析。

十一章

外部排序

（一）目的要求

理解外部排序的基本方法；掌握敗者樹和多路平衡歸并的實(shí)現(xiàn)；置換--選擇排序；最佳歸并樹。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.外部排序的兩個(gè)過程(理解)；

2.外排過程中所需進(jìn)行外存讀/寫次數(shù)的計(jì)算方法(掌握)；

3.敗者樹的建立過程(掌握)；

4.實(shí)現(xiàn)多路歸并的算法(掌握)；

5.置換-選擇排序的過程(掌握)；

6.最佳歸并樹的構(gòu)造方法（熟悉）；

7.按最佳歸并樹的歸并方案進(jìn)行平衡歸并時(shí)，外存讀/寫次數(shù)的計(jì)算方法(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：外部排序過程和實(shí)現(xiàn)方法；多路并歸算法及其實(shí)現(xiàn)； 難點(diǎn)：最佳并歸樹的構(gòu)造方法及其應(yīng)用。

實(shí)踐教學(xué)部分：上機(jī)實(shí)驗(yàn)分4個(gè)專題，每個(gè)專題可提供2~4個(gè)難度不等的題目供選。

實(shí)驗(yàn)一

停車場(chǎng)管理系統(tǒng)

（一）實(shí)驗(yàn)內(nèi)容 以棧模擬車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。

（二）實(shí)驗(yàn)過程 編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。

（三）實(shí)驗(yàn)教學(xué)基本要求

通過實(shí)例，使學(xué)生掌握棧和隊(duì)列兩種特殊的線性結(jié)構(gòu)，掌握棧和隊(duì)列的特點(diǎn)。實(shí)驗(yàn)后學(xué)生提交實(shí)驗(yàn)報(bào)告。

（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)。

（五）實(shí)驗(yàn)學(xué)時(shí) 4學(xué)時(shí)

實(shí)驗(yàn)二

教學(xué)計(jì)劃編制問題

（一）實(shí)驗(yàn)內(nèi)容

假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個(gè)學(xué)期。編制一個(gè)教學(xué)計(jì)劃程序。

（二）實(shí)驗(yàn)過程編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。

（三）實(shí)驗(yàn)教學(xué)基本要求

通過實(shí)例，使學(xué)生熟悉圖的各種存儲(chǔ)結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實(shí)驗(yàn)后學(xué)生提交實(shí)驗(yàn)報(bào)告。

（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)。

（五）實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)

實(shí)驗(yàn)三

最小生成樹問題

（一）實(shí)驗(yàn)內(nèi)容

利用克魯斯卡爾算法求最小生成樹。以文本形式輸出樹中各條邊以及他們的權(quán)值。

（二）實(shí)驗(yàn)過程 編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容

（三）實(shí)驗(yàn)教學(xué)基本要求

通過實(shí)例，使學(xué)生熟悉圖的各種存儲(chǔ)結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實(shí)驗(yàn)后學(xué)生提交實(shí)驗(yàn)報(bào)告。

（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)。

（五）實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)

實(shí)驗(yàn)四

哈希表設(shè)計(jì)

（一）實(shí)驗(yàn)內(nèi)容

假設(shè)人名為中國人的漢語拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)再散列法處理沖突。

（二）實(shí)驗(yàn)過程 編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容

（三）實(shí)驗(yàn)教學(xué)基本要求 掌握索引技術(shù)的使用。

（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)

（五）實(shí)驗(yàn)學(xué)時(shí) 4學(xué)時(shí)

五、課程教學(xué)的基本要求和主要環(huán)節(jié)

本課程可采用課堂講授、課堂討論、習(xí)題課等進(jìn)行課堂教學(xué);條件允許可采用CAI、電子教案、幻燈片、參觀等進(jìn)行輔助教學(xué);每章布置3~6道習(xí)題以鞏固教學(xué);在課程后半程，安排3~4個(gè)上機(jī)實(shí)驗(yàn)，讓學(xué)生應(yīng)用數(shù)據(jù)結(jié)構(gòu)的理論、方法，分組設(shè)計(jì)幾個(gè)較大的軟件，使理論與實(shí)際相結(jié)合。

考試采用閉卷方式?？偝煽冇善綍r(shí)成績和考試成績組成。平時(shí)成績占30%，考試成績占70%。

六、本課程與其它課程的聯(lián)系與分工

先修課包括：集合論，圖論，高級(jí)語言（結(jié)構(gòu)或記錄，指針）；

后續(xù)課包括：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等。

七、建議教材與參考教材

《數(shù)據(jù)結(jié)構(gòu)》（C語言版）

嚴(yán)蔚敏等

清華大學(xué)出版社

1997 《數(shù)據(jù)結(jié)構(gòu)題集》

嚴(yán)蔚敏等

清華大學(xué)出版社

1999

《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》

李春葆

清華大學(xué)出版社

2004

八、負(fù)責(zé)人

撰稿人：劉景匯、李玉香

審稿人：

系（院）領(lǐng)導(dǎo)：

第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱

Data Structure Course Design

一、課程的性質(zhì)、教學(xué)目的和要求

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問題的能力。

二、設(shè)計(jì)要點(diǎn)

1．設(shè)計(jì)和調(diào)試過程要規(guī)范化。① 需求分析

將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語句的時(shí)間復(fù)雜度。

給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來。

對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。

如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）

源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。

程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。

2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書寫格式

① 設(shè)計(jì)題目（任選其一）②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式

可設(shè)2-3人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開課學(xué)期布置題目，然后在期末前兩周完成。

三．設(shè)計(jì)要求

學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要1周時(shí)間完成，1周中每天至少要上6-8小時(shí)的機(jī)來調(diào)試C語言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序30小時(shí)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來，作為評(píng)判成績的標(biāo)準(zhǔn)之一。

四．設(shè)計(jì)題目

1、校園導(dǎo)游程序

[問題描述]

用無向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題。

[基本要求]（1）查詢各景點(diǎn)的相關(guān)信息；

（2）查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。

（3）查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。

（4）增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。

[選作內(nèi)容]

（1）求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。

（2）區(qū)分機(jī)動(dòng)車道和人行道。

（3）實(shí)現(xiàn)導(dǎo)游圖的仿真界面。

2、算術(shù)表達(dá)式求值

[問題描述]

一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“#”，如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。

[基本要求]

（1）從鍵盤讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。

（2）顯示輸入序列和棧的變化過程。

[選作內(nèi)容]

擴(kuò)充運(yùn)算符集合。

引入變量操作數(shù)。

操作數(shù)類型擴(kuò)充到實(shí)數(shù)。

3、文學(xué)研究助手

[問題描述]

文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱為“文學(xué)研究助手”。[基本要求]

英文小說存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。[測(cè)試數(shù)據(jù)]

以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計(jì)的詞匯集。[實(shí)現(xiàn)提示]

設(shè)小說中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次，不必存多個(gè)相同的行號(hào)。

如果讀者希望達(dá)到選作部分（1）和（2）所提出的要求，則首先應(yīng)把KMP算法改寫成如下的等價(jià)形式，再將它推廣到多個(gè)模式的情形。[選作內(nèi)容]

（1）模式匹配要基于KMP算法。

（2）整個(gè)統(tǒng)計(jì)過程中只對(duì)小說文字掃描一遍以提高效率。

（3）假設(shè)小說中的每個(gè)單詞或者從行首開始，或者前置以一個(gè)空格符。利用單詞匹配特點(diǎn)另寫一個(gè)高效的統(tǒng)計(jì)程序，與KMP算法統(tǒng)計(jì)程序進(jìn)行效率比較。

（4）推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）

4.迷宮求解

[問題描述]

可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；

[基本要求]

含有兩個(gè)以上的迷宮圖，由用戶選擇哪一張迷宮圖； 實(shí)現(xiàn)深度優(yōu)先、廣度優(yōu)先兩種回溯法。

在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

[實(shí)現(xiàn)提示]

可以用一個(gè)二維數(shù)組存儲(chǔ)迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優(yōu)先和廣度優(yōu)先算法。

5.括號(hào)匹配的檢驗(yàn)

[問題描述]

假設(shè)表達(dá)式中允許有兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即CC或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。檢驗(yàn)括號(hào)是否匹配的方法可用“期待的緊迫程度”這個(gè)概念來描述。例如：考慮下列的括號(hào)序列：

[([ ] [ ])]

8

當(dāng)計(jì)算機(jī)接受了第1個(gè)括號(hào)以后，他期待著與其匹配的第8個(gè)括號(hào)的出現(xiàn)，然而等來的卻是第2個(gè)括號(hào)，此時(shí)第1個(gè)括號(hào)“[”只能暫時(shí)靠邊，而迫切等待與第2個(gè)括號(hào)相匹配的 第7個(gè)括號(hào)“）”的出現(xiàn)，類似的，因只等來了第3個(gè)括號(hào)“[”，此時(shí)，其期待的緊迫程度較第2個(gè)括號(hào)更緊迫，則第2個(gè)括號(hào)只能靠邊，讓位于第3個(gè)括號(hào)，顯然第3個(gè)括號(hào)的期待緊迫程度高于第2個(gè)括號(hào)，而第2個(gè)括號(hào)的期待緊迫程度高于第1個(gè)括號(hào)；在接受了第4個(gè)括號(hào)之后，第3個(gè)括號(hào)的期待得到了滿足，消解之后，第2個(gè)括號(hào)的期待匹配就成了最急迫的任務(wù)了，??，依次類推?？梢娺@個(gè)處理過程正好和棧的特點(diǎn)相吻合。

[基本要求]

設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，若是左括號(hào)，則作為一個(gè)新的更急迫的期待壓入棧中，若是右括號(hào)，則或者是和當(dāng)前棧頂?shù)睦ㄌ?hào)相匹配，或者是不合法的情況，輸出“此串括號(hào)匹配不合法”。在初始和結(jié)束時(shí)，棧應(yīng)該是空的。

[測(cè)試數(shù)據(jù)]

輸入 #（[ ]（））#，結(jié)果“匹配”

輸入 #[（）]#，結(jié)果“此串括號(hào)匹配不合法”

#為起始和結(jié)束標(biāo)志。

6.停車場(chǎng)管理

[問題描述]

設(shè)停車場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車的狹長通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后開入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留的時(shí)間長短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。[測(cè)試數(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）。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束。[基本要求]

以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場(chǎng)內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。[實(shí)現(xiàn)提示]

需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場(chǎng)退出來的汽車，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號(hào)碼和進(jìn)入停車場(chǎng)的時(shí)刻。[選作內(nèi)容]

（1）兩個(gè)棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？

（2）汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車和1.5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當(dāng)于3輛小汽車的占地面積。

（3）汽車可以直接從便道上開走，此時(shí)排在它前面的汽車要先開走讓路，然后再依次排到隊(duì)尾。

（4）停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場(chǎng)的車低，請(qǐng)思考如何修改結(jié)構(gòu)以滿足這種要求。

7.簡單行編輯程序

[問題描述]

文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對(duì)文本文件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱為行編輯程序。

被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟(jì)，也不總能實(shí)現(xiàn)。一種解決方法是逐段地編輯。任何時(shí)刻只把待編輯文件的一段放在內(nèi)存，稱為活區(qū)。試按照這種方法實(shí)現(xiàn)一個(gè)簡單的行編輯程序。設(shè)文件每行不超過320個(gè)字符，很少超過80字符。[基本要求]

實(shí)現(xiàn)以下4條基本編輯命令：

（1）行插入。格式：i<行號(hào)><回車><文本><回車>

將<文本>插入活區(qū)中第<行號(hào)>行之后

（2）行刪除。格式：d<行號(hào)1>[□<行號(hào)2>]<回車>

刪除活區(qū)中第<行號(hào)1>行（到第<行號(hào)2>行）。兩種格式的例子是：“d10↙”和“d10□14↙”

（3）活區(qū)切換。格式：n<回車>

將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。

（4）活區(qū)顯示。格式：p<回車>

逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請(qǐng)用戶決定是否繼續(xù)顯示以后各頁（如果存在）。印出的每一行要前置以行號(hào)和一個(gè)空格符，行號(hào)固定占4位，增量為1。

各條命令中的行號(hào)均須在活區(qū)中各行行號(hào)范圍之內(nèi)，只有插入命令的行號(hào)可以等于活區(qū)第一行行號(hào)減1，表示插入當(dāng)前屏幕中第一行之前，否則命令參數(shù)非法。[測(cè)試數(shù)據(jù)]

由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)，如首行、尾行。[實(shí)現(xiàn)提示]

（1）設(shè)活區(qū)的大小用行數(shù)activemaxlen（可設(shè)為100）來描述。考慮到文本文件行長通常為正態(tài)分布，且峰值在60到70之間，用320×activemaxlen大小的字符數(shù)組實(shí)現(xiàn)存儲(chǔ)將造成大量浪費(fèi)。可以以標(biāo)準(zhǔn)行塊為單位為各行分配存儲(chǔ)，每個(gè)標(biāo)準(zhǔn)行塊含81個(gè)字符。這些行塊可以組成一個(gè)數(shù)組，也可以利用動(dòng)態(tài) 8 鏈表連接起來。一行文字可能占多個(gè)行塊。行尾可用一個(gè)特殊的ASCII字符（如(012)8）標(biāo)識(shí)。此外，還應(yīng)記住活區(qū)起始行號(hào)。行插入將引起隨后各行行號(hào)的順序下推。

（2）初始化過程包括：請(qǐng)用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過activemaxlen-x。x的值可以自定，例如20。

（3）在執(zhí)行行插入命令的過程中，每接收到一行時(shí)到要檢查活區(qū)大小是否已達(dá)activemaxlen。如果是，則為了在插入這一行之后仍保持活區(qū)大小不超過activemaxlen，應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點(diǎn)為第一行之前，則只得將新插入的這一行輸出。

（4）若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著結(jié)束編輯或開始編輯另一個(gè)文件。

（5）可令前三條命令執(zhí)行后自動(dòng)調(diào)用活區(qū)顯示。[選作內(nèi)容]

（1）對(duì)于命令格式非法等一切錯(cuò)誤作嚴(yán)格檢查和適當(dāng)處理。

（2）加入更復(fù)雜的編輯操作，如對(duì)某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配等，格式可以為S<行號(hào)>@<串1>@<串2><回車>和m<串><回車>。

8.圖遍歷的演示

[問題描述]

很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個(gè)程序，演示無向圖的遍歷操作。[基本要求]

以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集。[測(cè)試數(shù)據(jù)]

由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)，如單個(gè)結(jié)點(diǎn)。[實(shí)現(xiàn)提示]

設(shè)圖的結(jié)點(diǎn)不超過30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號(hào)表示（如果一個(gè)圖有n個(gè)結(jié)點(diǎn)，則它們的編號(hào)分別為1,2,?,n）。通過輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對(duì)，可以對(duì)邊的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點(diǎn)順序不能顛倒。

[選作內(nèi)容]

（1）借助于棧類型（自己定義和實(shí)現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實(shí)現(xiàn)。

（2）以鄰接多重表為存儲(chǔ)結(jié)構(gòu)建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再按凹入表或樹形打印生成樹

（3）實(shí)現(xiàn)有向圖的遍歷操作。

9、赫夫曼樹的建立

*問題描述：建立建立最優(yōu)二叉樹函數(shù)

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

在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

10、圖的建立及輸出

*問題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。

11、各種排序

*問題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。

*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。*輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列?

12、圖的遍歷

*問題描述：對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。

13、線性表的操作

*問題描述：利作鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。

14、編制一個(gè)求解迷宮通路的圖形界面演示程序。*問題描述：

1）輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。

2）根據(jù)用戶界面提示，用鍵盤輸入。Home鍵設(shè)置迷宮起點(diǎn)，End鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，Enter鍵添加墻，Del鍵刪除墻，完成后按F9鍵演示，Esc鍵退出。

3）橙色的實(shí)心小圓圈表示起點(diǎn)，綠色實(shí)心圓圈表示終點(diǎn)，空心圓圈表示足跡，紅色方塊表示墻。4）本程序只求出一條成功的通路，但若對(duì)求解函數(shù)MazePath稍加更改即可求得全部路徑。此外，因受圖形界面限制，不能保存或載入測(cè)試文件（此功能可在Maze_text中實(shí)現(xiàn)）。

5）當(dāng)未輸入起點(diǎn)時(shí)，消息顯示“Error： You must set Startplace.”；未輸入終點(diǎn)時(shí)，顯示“Error： You must set Endplace.” 找到路徑時(shí)，屏幕顯示足跡，并在消息框出現(xiàn)Path found，否則消去足跡，顯示Path not found.15．一元稀疏多項(xiàng)式計(jì)算器

*問題描述：一元多項(xiàng)式簡單計(jì)算器的基本功能是：（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,?,cn,en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第I項(xiàng)的系數(shù)和指數(shù)，序列指指數(shù)降序排列；（3）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；（4）多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。*實(shí)現(xiàn)提示：用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式，多項(xiàng)式的項(xiàng)數(shù)存在頭結(jié)點(diǎn)。

16．算術(shù)表達(dá)式求值演示

*問題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。

*基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。

*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。（2）在輸入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識(shí)別處理，以及相應(yīng)的運(yùn)算。（3）在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。

*選作內(nèi)容：（1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算；（2）運(yùn)算量可以是變量；（3）運(yùn)算量可以是實(shí)數(shù)類型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。

17．稀疏矩陣運(yùn)算器

*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。

*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。

*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀 疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。18．圖書管理

*問題描述：圖書管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書的采編入庫、清除庫存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。

*基本要求：（1）每種書的登記內(nèi)容至少包括書號(hào)、書名、作者、現(xiàn)存量和總庫存量等五4。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過書號(hào)（即關(guān)鍵字）進(jìn)行的，所以要用B樹對(duì)書號(hào)盡力索引，以獲得高效率。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：①采編入庫：新購入一種書，經(jīng)分類和確定書號(hào)后登記到圖書帳目中去。如果這種書在帳目中已有，則只將總庫存量增加。②清除庫存：某種書已無保留價(jià)值，將它從圖書帳目中注銷。③某種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號(hào)和歸還期限。④歸還：注銷對(duì)借閱者的登記，改變?cè)摃默F(xiàn)存量。⑤顯示：以凹入表的形式顯示B樹。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。下列B樹的打印格式如下所示：

19、文章編輯

*問題描述：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁文章，每行最多不超過80個(gè)字符，共N行。

*要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。

*存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；

*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。

*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；

50，52 70，72

20、回文判斷

[問題描述]

試寫一個(gè)算法，判斷依次讀入的一個(gè)以@為結(jié)束符的字母序列，是否為形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’，且序列2 是序列1的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘１+３&３－１’則不是。[實(shí)現(xiàn)提示]

首先，序列1進(jìn)棧，然后序列1出棧并與序列2比較。

21、建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問題描述：

要求能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；

五、參考書目

《數(shù)據(jù)結(jié)構(gòu) C語言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)》 高教出版社

《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社

《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社

計(jì)算機(jī)軟件教研室 2004年1月7日