第一篇：數(shù)據(jù)結(jié)構(gòu)課程的知識體系和教學實踐

數(shù)據(jù)結(jié)構(gòu)課程的知識體系和教學實踐－－張銘 許卓群 楊冬青 唐世渭

一、數(shù)據(jù)結(jié)構(gòu)知識體系

計算機科學已經(jīng)深入應用到各個領(lǐng)域，不僅有效地解決了各種工程和科學計算中的數(shù)值計算問題，而且也有效地解決了許多文本處理、信息檢索、數(shù)據(jù)庫管理、圖像識別、人工智能等非數(shù)值的數(shù)據(jù)處理問題。數(shù)據(jù)結(jié)構(gòu)有助于程序員更有效地組織數(shù)據(jù)、設計高效的算法、完成高質(zhì)量的程序以滿足錯綜復雜的實際需要。

數(shù)據(jù)結(jié)構(gòu)是計算機學科的重要分支研究領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)和算法在計算機學科中的地位十分重要，其他計算機科學領(lǐng)域及有關(guān)的應用軟件都要使用到各種數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是算法分析與設計、操作系統(tǒng)、軟件工程、數(shù)據(jù)庫概論、編譯技術(shù)、計算機圖形學、人機交互等專業(yè)基礎課和專業(yè)課程的先行課程。語言編譯要使用棧、散列表及語法樹；操作系統(tǒng)中用隊列、存儲管理表及目錄樹等；數(shù)據(jù)庫系統(tǒng)運用線性表，多鏈表及索引樹等進行數(shù)據(jù)管理；而在人工智能領(lǐng)域，依求解問題性質(zhì)的差異將涉及到各種不同的數(shù)據(jù)結(jié)構(gòu)，如廣義表，集合、搜索樹及各種有向圖等等。

美國IEEE和ACM的教學計劃CC2001把《算法與數(shù)據(jù)結(jié)構(gòu)》列入計算機以及信息技術(shù)相關(guān)學科專業(yè)的本科必修基礎課程。在我國，《數(shù)據(jù)結(jié)構(gòu)》已經(jīng)作為理工科非計算機專業(yè)必修的信息技術(shù)基礎課程之一。世界上許多科技人員對學習、研究數(shù)據(jù)結(jié)構(gòu)都非常重視，對于從事計算機科學及其應用的科技工作者來說，數(shù)據(jù)結(jié)構(gòu)更是必須透徹地掌握的重要基礎。

1．數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算

從字面上來看，數(shù)據(jù)結(jié)構(gòu)就是指數(shù)據(jù)間的相互關(guān)系。具體到計算機環(huán)境，談到任何一種結(jié)構(gòu)時，都自然地聯(lián)系著作用在這種類型的數(shù)據(jù)上的運算（即函數(shù)），為了在計算機上執(zhí)行這些運算，我們有必要把這些數(shù)據(jù)以某種方式存儲在計算機中。因此，我們可以認為，所謂數(shù)據(jù)結(jié)構(gòu)，就是由某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的存儲方法被存儲于計算機中，并在這些數(shù)據(jù)上定義了一個運算的集合。也就是說，數(shù)據(jù)結(jié)構(gòu)具有三個方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算。

常見邏輯關(guān)系有：線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖結(jié)構(gòu)和文件結(jié)構(gòu)。其中，線性結(jié)構(gòu)是最簡單的數(shù)據(jù)結(jié)構(gòu)，例如，程序設計語言中往往都會介紹的線性表（包括數(shù)組和鏈表）、棧、隊列、向量、字符串等。其中，字符串就是每個結(jié)點都是單個字符的線性表。實際上多維數(shù)組和廣義表也是線性結(jié)構(gòu)的推廣。另外，文件其本質(zhì)也是線性結(jié)構(gòu)，不過由于存儲在外存中，對文件數(shù)據(jù)的訪問速度非常慢，因此，仔細研究文件結(jié)構(gòu)和基于文件的外排序也是很有必要的。二叉樹和樹是非常重要的數(shù)據(jù)結(jié)構(gòu)，其應用十分靈活而廣泛。二叉樹可以看作是樹的特例。例如，語言編譯中要用到語法樹，操作系統(tǒng)有目錄樹，數(shù)據(jù)庫系統(tǒng)需要用索引樹等進行數(shù)據(jù)管理，而在人工智能領(lǐng)域，需要用到搜索樹等。許多真實世界的問題都可以圖來抽象地定義。例如，一張交通圖可以用數(shù)據(jù)結(jié)構(gòu)的圖來形象化地表示：用結(jié)點表示城市，用邊表示連接城市的高速公路；Web網(wǎng)頁的關(guān)系也可以表示為圖：Web網(wǎng)頁作為結(jié)點，網(wǎng)頁之間的鏈接作為邊。圖是一種最通用的邏輯結(jié)構(gòu)，實際上，圖?樹?二叉樹?線性表。

常見的存儲方法有：順序方法、鏈接方法、索引方法、散列方法。其中，索引存儲又分為線性和樹形兩種。文件結(jié)構(gòu)的索引則往往用樹形結(jié)構(gòu)。

對于一種數(shù)據(jù)結(jié)構(gòu)，往往需要定義一些運算。例如，建立數(shù)據(jù)結(jié)構(gòu)、清除數(shù)據(jù)結(jié)構(gòu)、插入一個新數(shù)據(jù)元素、刪除某個數(shù)據(jù)元素、修改某個數(shù)據(jù)元素、排序、檢索等。作為最常用的算法，排序和檢索歷來是數(shù)據(jù)結(jié)構(gòu)討論中的重點問題。排序算法最能夠體現(xiàn)算法的魅力，它對算法速度要求非常高，其中內(nèi)排序主要考慮的是怎樣減少關(guān)鍵碼之間的比較次數(shù)和記錄交換次數(shù)，以提高排序速度。可以證明所有基于比較的排序算法的時間代價是Θ(nlog n)，這也是排序問題的時間代價；而外排序則考慮外存的特性，盡量減少訪外操作，以提高排序速度。檢索則考慮怎樣提高檢索速度，這往往是與存儲方法有關(guān)的。例如，我們可以利用索引存儲來加快檢索。散列表、B樹和B+樹等高效的數(shù)據(jù)結(jié)構(gòu)都具有極好的檢索性能。

2．算法的效率問題

每一種數(shù)據(jù)結(jié)構(gòu)與其相關(guān)的算法都有時間、空間開銷和效率等問題。每當面臨一個新的設計問題時，設計者都應該要權(quán)衡時間空間開銷，設計出更有效的數(shù)據(jù)結(jié)構(gòu)和算法，以適應問題的需要。

基本問題包括：對于給定的一類問題，最好的算法是什么？需要多少存儲空間和時間？空間與時間的折衷方案是什么？存取數(shù)據(jù)最好的方法是什么？最好算法的最壞情況是什么？平均來說，算法的運行好到何種程度？算法一般化到何種程度——即什么類型的問題可以用類似的方法處理？

這就涉及到算法分析技術(shù)，許多數(shù)據(jù)結(jié)構(gòu)教材都揉合了一些基本的算法分析技術(shù)，這有助于讀者根據(jù)問題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)，并對時間空間復雜性進行必要的控制。

3．抽象數(shù)據(jù)類型

事實上，數(shù)據(jù)結(jié)構(gòu)的三個側(cè)面，以數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的運算定義更為重要。因為很多時候人們并不關(guān)心數(shù)據(jù)的存儲結(jié)構(gòu)和運算的具體實現(xiàn)。1983年Aho等人把數(shù)據(jù)結(jié)構(gòu)的存儲與實現(xiàn)細節(jié)剝離，定義了抽象數(shù)據(jù)類型（簡稱“ADT”）的概念。抽象數(shù)據(jù)類型是定義了一組運算的數(shù)學模型。例如棧結(jié)構(gòu)，棧中元素的數(shù)學特性(即邏輯結(jié)構(gòu))表現(xiàn)為線性表，它們是有序的；棧的主要運算是進棧(push)、出棧(pop)、判棧空(isEmpty)等。這里我們并不涉及棧的存儲方式以及棧中元素的類型等。這種抽象的數(shù)據(jù)類型可以在較高級的算法中直接引用，而不用考慮它的實現(xiàn)細節(jié)。這就使得設計者可以在不同的設計階段采用不同的抽象數(shù)據(jù)類型作為設計的基礎，在適當?shù)某橄髮哟紊峡紤]程序的結(jié)構(gòu)和算法，從而很好地支持了邏輯設計和物理實現(xiàn)的分離，支持封裝和信息隱蔽。

大多數(shù)教材都是以數(shù)據(jù)的邏輯結(jié)構(gòu)為主線，順序介紹線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖結(jié)構(gòu)和文件結(jié)構(gòu)。在介紹每種數(shù)據(jù)結(jié)構(gòu)時，再討論其存儲結(jié)構(gòu)以及相關(guān)的算法。例如對于線性表，如果考慮到存儲，可以分為數(shù)組和鏈表；考慮到運算的特殊性，則可以分為向量、棧和隊列。對于一些比較重要的算法，再列出單獨的章節(jié)來討論，例如排序、檢索、索引、存儲管理等。

二、數(shù)據(jù)結(jié)構(gòu)的教學目的

Peter J．Denning等人認為，計算機學科分為理論、抽象、設計這三個形態(tài)。我們把數(shù)據(jù)結(jié)構(gòu)課程所涉及的主要方面整理為：

1.理論

(1)算法的數(shù)學基礎。例如，有關(guān)圖論、組合論等，特別是遞歸、遞推、歸納等分析方法。(2)算法的時間和空間度量。2．抽象(1)排序、檢索等重要問題類的有效算法，以及最好、最差和一般性能的分析比較。

(2)重要數(shù)據(jù)結(jié)構(gòu)技術(shù)，例如分治法(二分檢索、快速排序、歸并排序)、貪心算法（Huffman編碼、Prim算法、Kruskal算法、Dijstra算法）、動態(tài)規(guī)劃（Prim算法、Dijstra算法、Floyd算法、最佳二叉搜索樹）、棧的引用（深度優(yōu)先周游）、隊列的應用（廣度優(yōu)先周游）。3．設計

(1)掌握并靈活應用常用的基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型、各種基本存儲方法及其主要的算法，例如線性結(jié)構(gòu)（包括一維數(shù)組、鏈表、棧、隊列、字符串等）、二叉樹、樹、圖、文件；

(2)排序、檢索、索引等重要問題類的算法的選擇、實現(xiàn)和測試。例如，各種排序方法的實驗時間比較，散列、倒排索引、B樹等應用。(3)存儲管理的實現(xiàn)與測試。例如可利用空間表、無用單元收集、伙伴系統(tǒng)。

數(shù)據(jù)結(jié)構(gòu)這門課程不僅僅要讓學生掌握那些鏈表、樹、圖是如何實現(xiàn)的。設置這門課程有三個目的：第一個目的是讓學生懂得“數(shù)據(jù)結(jié)構(gòu)＋算法＝程序”；第二個目的是培養(yǎng)數(shù)據(jù)抽象的能力；第三個目的是使得學生把數(shù)據(jù)結(jié)構(gòu)和算法理論與編程實踐相結(jié)合，能夠在實際的工程實踐中靈活地予以應用。

在達到前兩個目的時，學生就基本具備了解決現(xiàn)實未知問題的能力，再輔以必要的綜合上機項目訓練，可以達到第三個目的。

總而言之，通過數(shù)據(jù)結(jié)構(gòu)課程的教學，學生需要掌握以下四個方面的知識和能力：（1）掌握并靈活應用常用的基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型、各種基本存儲方法、主要的算法，例如線性結(jié)構(gòu)、二叉樹、樹、圖、文件；（2）掌握并簡單應用常用的排序、檢索和索引算法和方法；（3）掌握基本的算法設計和分析技術(shù)，并對自己設計的數(shù)據(jù)結(jié)構(gòu)和算法進行簡單的分析；（4）在進行程序設計、調(diào)試、測試的課程項目訓練（即上機實習訓練）過程中，要求學生綜合應用所學到的數(shù)據(jù)結(jié)構(gòu)和算法知識，學會分析研究數(shù)據(jù)對象的特性，以便選擇合適的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)以及相應的算法，合理地組織數(shù)據(jù)、有效地表示數(shù)據(jù)、有效地處理數(shù)據(jù)，書寫的程序結(jié)構(gòu)清楚、正確易讀，提高程序設計的質(zhì)量。

三、數(shù)據(jù)結(jié)構(gòu)教材編寫思路

北京大學計算機系許卓群、張乃孝、楊冬青、唐世渭于1987年編寫的《數(shù)據(jù)結(jié)構(gòu)》（高等教育出版社出版）曾被很多高校計算機專業(yè)用為數(shù)據(jù)結(jié)構(gòu)課程教材。該書已重印多次，并于1992獲得教育部教材優(yōu)秀獎和國家教材優(yōu)秀獎。隨著計算機技術(shù)的發(fā)展和應用，很多讀者建議教材要能及時體現(xiàn)新的教學內(nèi)容，建設配套的教學資源，并希望在算法的偽代碼編碼風格方面，由類PASCAL改為類C++語言。

針對這些建議，結(jié)合北京大學計算機科學與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程建設的實際情況，許卓群、楊冬青、唐世渭、張銘等多年從事《數(shù)據(jù)結(jié)構(gòu)》教學和研究的教師一起新編了《數(shù)據(jù)結(jié)構(gòu)與算法》教材。新書以中國計算機科學與技術(shù)學科教程CCC2002和美國IEEE和ACM的教學計劃CC2001所規(guī)定的基本知識點為主要內(nèi)容，同時參考并吸收了國內(nèi)外最新數(shù)據(jù)結(jié)構(gòu)教材的優(yōu)點。主要編寫原則和編寫大綱的考慮如下。

1．新編《數(shù)據(jù)結(jié)構(gòu)與算法》教材的主要編寫原則

? 以中國計算機科學與技術(shù)學科教程CCC2002和美國IEEE和ACM的教學計劃CC2001所規(guī)定的基本知識點為主要內(nèi)容。

? 考慮采用最廣為程序員所使用的C++語言作為算法描述語言，從而使得抽象數(shù)據(jù)類型(ADT)的概念得到更自然的體現(xiàn)，更本質(zhì)地體現(xiàn)數(shù)據(jù)結(jié)構(gòu)的思想，而且所定義的數(shù)據(jù)結(jié)構(gòu)類能夠方便地被重用。

? 為了保證教材的易讀性，盡量回避C/C++中比較麻煩的內(nèi)容，例如C的指針的指針的指針等折磨人的東西，C++的類的繼承、虛函數(shù)等。? 使用參數(shù)化的模板（template），從而提高算法中數(shù)據(jù)類型的通用性，支持高效的代碼重用。在后面的章節(jié)中，盡量使用STL(Standard Template Library，標準C++類庫)所提供的棧、隊列等基本數(shù)據(jù)結(jié)構(gòu)。? 刪掉逆轉(zhuǎn)鏈周游二叉樹、Robson周游算法、Siklossy周游算法、關(guān)鍵路徑等內(nèi)容，并增加Patricia樹、伸展樹等復雜樹結(jié)構(gòu)，k-d樹、PR四分樹、R*樹等空間數(shù)據(jù)結(jié)構(gòu)。

? 每章中均提供適量的綜合上機實習題（即項目實習）。? 為了配合教材的使用，我們將編寫概念清晰、內(nèi)容充實的多媒體演示講稿以及用標準C++模板編寫的可執(zhí)行的源程序代碼，同時建設了課程教學網(wǎng)站。

2．新編教材大綱的考慮

考慮到數(shù)據(jù)結(jié)構(gòu)這門課程基本知識點的劃分，根據(jù)我們多年教學經(jīng)驗，作者對新編教材的內(nèi)容做了精心的安排。新書以中國計算機科學與技術(shù)學科教程CCC2002中的PF3基本數(shù)據(jù)結(jié)構(gòu)、AL1算法分析基礎、AL3基本算法為核心內(nèi)容，分為基本數(shù)據(jù)結(jié)構(gòu)、排序和檢索、高級數(shù)據(jù)結(jié)構(gòu)三個部分。第一部分（共6章）從邏輯結(jié)構(gòu)的角度系統(tǒng)地介紹各種基本數(shù)據(jù)結(jié)構(gòu)，即概論、線性表(包括向量、棧和隊列)、字符串、二叉樹、樹和圖。概論討論了數(shù)據(jù)結(jié)構(gòu)的定義、抽象數(shù)據(jù)類型和基本的算法分析技術(shù)。第二部分（共4章）從算法的角度討論排序、檢索和索引算法，索引算法新增加了關(guān)于文本文件的倒排索引，倒排索引是當前信息檢索和搜索引擎技術(shù)的關(guān)鍵技術(shù)。考慮到計算機學科的應用性以及學生靈活應用數(shù)據(jù)結(jié)構(gòu)解決實際問題的需要，第三部分（共2章）介紹了數(shù)據(jù)結(jié)構(gòu)的高級主題，例如廣義表和稀疏矩陣等更復雜的線性表結(jié)構(gòu)，Trie結(jié)構(gòu)、AVL樹、伸展樹等復雜樹結(jié)構(gòu)，k-d樹、PR四分樹、R*樹等空間數(shù)據(jù)結(jié)構(gòu)，把存儲管理作為線性結(jié)構(gòu)的典型應用予以介紹，把決策樹和博弈樹作為樹型結(jié)構(gòu)的典型應用加以介紹。最后附錄布置了一個學期綜合上機實習題“搜索引擎”，并簡單介紹了其中涉及的圖搜索、倒排索引等技術(shù)。

其中第一部分是最基本的內(nèi)容，教師可以根據(jù)學生的程度選擇第二部分、第三部分一些內(nèi)容來講解。該教材能夠適應不同讀者的學習需要以及教師的教學安排，特別為教師安排上機實習提供了極大的方便。

四、教學策略

數(shù)據(jù)結(jié)構(gòu)課程中，既有很多靈活的與離散數(shù)學（尤其是圖論、組合數(shù)學）有關(guān)的證明題，又有大量算法設計題。而且該課程對程序設計能力的要求很高，需要學生動手編寫實習題以應用并掌握數(shù)據(jù)結(jié)構(gòu)知識。對于計算機專業(yè)的學生來說，學習《數(shù)據(jù)結(jié)構(gòu)》之前應該先修《計算引論》（或稱“計算概論”，“計算機文化基礎”）、《面向?qū)ο蟪绦蛟O計實習》、《集合論與圖論》這三門課程。對于只有“計算概論”基礎的非計算機專業(yè)的學生，可以適當減少數(shù)學證明的要求，不要求設計比較復雜的算法。

為做好“數(shù)據(jù)結(jié)構(gòu)”這門重要主干基礎課程的教學工作，作者以熱忱的工作態(tài)度、以科研工作的鉆研精神認真投入教學研究，投入了大量精力和時間，建立了全新的教學體系，盡力完善各個教學環(huán)節(jié)。

1.啟發(fā)式教學，培養(yǎng)學生的創(chuàng)造性思維和主動學習精神

在數(shù)據(jù)結(jié)構(gòu)教學中，對于每種數(shù)據(jù)結(jié)構(gòu)都從其數(shù)學特性入手，先介紹其抽象數(shù)據(jù)類型，然后再討論其不同的存儲方法。與學生一起討論研究不同存儲方法的可能算法，結(jié)合算法分析來討論各種存儲方法和算法的利弊，摒棄那些不適宜的方法。這樣，充分調(diào)動了學生思維積極性，學到了數(shù)據(jù)結(jié)構(gòu)的思維方法以及從事科研的基本方法。

2.與科研結(jié)合，在教學中引進新的理論和技術(shù)內(nèi)容

盡量把科研中涉及到的與《數(shù)據(jù)結(jié)構(gòu)》課程相關(guān)的新理論和技術(shù)、優(yōu)秀論文介紹給學生，拓展了教學內(nèi)容。例如，給學生講解“搜索引擎”中的數(shù)據(jù)結(jié)構(gòu)技術(shù)（主要涉及到圖搜索、排序和索引技術(shù)），講解當前網(wǎng)絡和數(shù)據(jù)庫的研究熱點“XML（擴展標記語言）”。

3.加強實踐環(huán)節(jié)的訓練

北京大學計算機系歷來十分重視實踐環(huán)節(jié)的訓練。《數(shù)據(jù)結(jié)構(gòu)》課程一直為每學期4學分/每周4學時，每位學生的上機實習時間每學期約80小時。從2003屆北京大學信息學院計算機專業(yè)的學生開始，《數(shù)據(jù)結(jié)構(gòu)》將改為兩門課程，即《算法與數(shù)據(jù)結(jié)構(gòu)》和《數(shù)據(jù)結(jié)構(gòu)實習》，在同一個學期講授，分別為每學期3學分/每周3學時，每學期2學分/每周2學時。改革的目的主要是加強上機實踐，每位學生的數(shù)據(jù)結(jié)構(gòu)上機實習時間增加為每學期120小時。

數(shù)據(jù)結(jié)構(gòu)是一門理論和實踐結(jié)合比較緊密的課程，每周都布置6道書面作業(yè)或小程序?qū)嵙暎ㄈ珜W期約70道），每個學期布置6道大的上機實習題（其中最后一道是2-3人合作的學期綜合上機實習題，例如“搜索引擎”、“XML數(shù)據(jù)管理”等）。組織助教認真檢查習題和上機題，并編寫了參考答案公布在網(wǎng)上。

4.采用新的教育技術(shù)，提高教學效果； 建立了一個高質(zhì)量的課程網(wǎng)站http://db.pku.edu.cn/mzhang/ds/index.htm。網(wǎng)站主要內(nèi)容有：多媒體演示講稿、標準C++模板編寫的可執(zhí)行的源程序代碼、習題和上機題及其參考答案。課程網(wǎng)站還有一個BBS討論版，每個學期都會有約700個數(shù)據(jù)結(jié)構(gòu)主題討論。教員每周都組織助教講解習題中的問題和難點，并組織學生討論習題和上機題中的問題、以及各種不同解法及其效率。

5.嚴格要求，教書育人，培養(yǎng)好學風。

為了防止學生抄襲上一屆的作業(yè)和上機題，每一屆都重新布置新的書面習題和上機題。另外，還要求學生在提交的書面作業(yè)、電子版程序和報告中，都寫上“誠實代碼”——“我XXX真誠地保證：我自己獨立地完成了整個作業(yè)和程序從分析、設計到編碼的所有工作。我沒有抄襲任何其他人的作業(yè)。”學生紛紛反映這種自己以人格保證的形式，大大減少了抄襲現(xiàn)象。

五、結(jié)束語

作者試用新教材給電子商務專業(yè)學生授課，把最基本的內(nèi)容安排在前6章講解完，然后簡單介紹了第7章的內(nèi)排序，其他內(nèi)容讓感興趣的學生自學。該專業(yè)的學生們反映課程內(nèi)容非常充實，知識點掌握得很牢固。在給北大信息學院計算機專業(yè)的二年級本科生試用新教材時，在接近一半的學期課程時間就講完了前6章，重要的章節(jié)都可以安排比較綜合的上機實習題；在開始講解排序與檢索的同時，可以開始安排學期綜合上機實習題；最后第11-12章比較高級的數(shù)據(jù)結(jié)構(gòu)內(nèi)容只是講座性的內(nèi)容，沒有上機實習的壓力，而學生也面臨期末考始復習了。從學生評估以及系領(lǐng)導對往屆學生的調(diào)查情況來看，到了高年級以后，學生們都反映數(shù)據(jù)結(jié)構(gòu)是知識拓展非常廣、非常有用的課程。

作者希望，通過數(shù)據(jù)結(jié)構(gòu)的學習，學生們能養(yǎng)成嚴謹?shù)目茖W作風，學到科學的思維方法，提高設計高質(zhì)量程序的能力，奠定扎實的軟件開發(fā)基礎。

第二篇：《數(shù)據(jù)結(jié)構(gòu)》課程教學反思

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

(2006-10-02 20:31:34)轉(zhuǎn)載▼

教學反思，是教師以自己的教學活動過程為思考對象，對自己的某種教學行為、決策以及由此產(chǎn)生的結(jié)果進行審視和分析的活動。實踐證明，由教師本人對教學實踐及其成敗得失進行反思，有利于教師及時總結(jié)自己的教學經(jīng)驗，培養(yǎng)教師學習、研究的意識，促使教師更好地實現(xiàn)教學理論與教學實踐的結(jié)合，提高教師的教學能力與水平。

以上是一段從網(wǎng)絡摘抄的語句，其實對教學反思是怎樣一回事認識并不是很深刻，就像學生前些日子詢問的說課，懂得說課，但并不知道怎樣跟學生解釋什么是說課，只記得一句從網(wǎng)絡上看到的話“授課主要是怎樣講，說課主要是為什么這樣講”。

要對上一個月的教學進行反思，是上星期就一直想進行的事情，但始終覺得找不到充實的時間或者是找不到很好的思路。要進行教學反思，主要還應該是對《數(shù)據(jù)結(jié)構(gòu)》課程的反思，畢竟它是一門基礎、核心的專業(yè)課程，而且也是系里第一次的開課。

對課程的反思：

1、很重要。數(shù)據(jù)結(jié)構(gòu)是幾乎所有軟件方向?qū)I(yè)課的基礎，學C語言讓你知道了什么是編程，而數(shù)據(jù)結(jié)構(gòu)告訴你該怎么去編程。用網(wǎng)上一個例子來說，數(shù)據(jù)結(jié)構(gòu)讓你知道怎樣從一個地方到另一個的路，而C語言等讓你知道選擇什么樣的交通工具去走這些路，你不懂得去北京的路，給神六你坐也到達不了。

2、很多點。既然培養(yǎng)數(shù)據(jù)的處理能力，又要培養(yǎng)算法設計思路，還要培養(yǎng)實際的應用能力。有點兼顧不過來，理解算法思想倒是能達到的要求，但在實際應用能力的培養(yǎng)上，存在難度。

3、很難學。教師艱難的教，學生吃力的學。理解算法的思想，但如何放到實際中始終是難題，教師難找到合適的方法，學生接受能力有限，經(jīng)驗受制，受程序語言不熟練等影響。

對教師的反思：

1、經(jīng)驗不足。畢竟剛從大學畢業(yè)回來，教學經(jīng)驗欠缺，且系里也是第一次開這樣的課程。對數(shù)據(jù)結(jié)構(gòu)這門課本身理解不透，特別在實踐方面接觸較少，進行過的無非是大學時一些作業(yè)。因此在教師教學方法和學生接受能力間找一個結(jié)合點是一直苦苦探索的問題，直到現(xiàn)在仍是沒有一個明確有方向。

2、目標過大。接受這個可以說是苦差的教學任務后，其實我的有埋怨過，但我更多是考慮如何去實現(xiàn)某些目標。讓學生理解數(shù)據(jù)結(jié)構(gòu)的算法思想，培養(yǎng)學生算法設計的思路，加強數(shù)據(jù)結(jié)構(gòu)的實用性。從一個月的教學情況，目標定得過高了，特別是實踐環(huán)節(jié)上，過高估計自己的教學能力，也過高估計學生的學習能力。但我直到現(xiàn)在，特別是在實踐上，我找不到說服自己放棄的理由，畢竟總覺得學習了思想，不能在編程上實現(xiàn)，或者說是學會了例子，不會變通，算不上學會。我懷疑教學目標，但又放不開手。

3、時間欠缺。由于教學任務的限制，上機實踐時間比較少，是以對學生把所學的思想轉(zhuǎn)化為算法進而轉(zhuǎn)化為程序的指導不足。一個月才開了一次實踐課，本來已經(jīng)足夠，但對學生的實際情況來說，這還是很欠缺的。

對學生的反思：

1、思想重視不夠。首先，作為師范生不重視這些難度偏深的課程；其次，作為計算機學生不重視這些偏向理論的課程；再次，在難學面前退卻，沒有足夠的學習興趣、信心和耐心。特別在對待操作作業(yè)上，一個月過去，第一次的作業(yè)完成幾乎為零。

2、語言能力較差。盡管上學期學習了C語言，不說程序設計能力，且說C語言的基礎知識掌握都是較差的。還是那句，把實踐當成了死記硬背來考試，把知識當成了例子來學習。欠缺獨立思考，欠缺獨立編程。

3、自主協(xié)作不行。不能自覺的進行學習，什么都要教師在課堂上講，或者只局限于課本，不懂得利用網(wǎng)絡或參考書進行知識的拓展。也沒有形成協(xié)作學習的氛圍，同學間的交流不夠，論壇學習的方法不懂。這歸于兩個原因，一個自覺性問題，一個班級氛圍問題。

4、素質(zhì)起點不好。這是我一直不想談及的問題，畢竟我反復的強調(diào)過，他們大專生和本科生差別不大，在大學里都是一個新的起點，但在突出的個體上可以這樣考慮，從整體上差異總還會存在的。盡管我承認這差異，但我依然否定他們說的智商等先天因素，這些只會是借口。我說的差異，首先就是自覺性，這一點在他們過分追求自由中散失；其次是空閑時間的自由度，學校安排課程過多，時間上和精力上有限；再次是學習氛圍，那種泡圖書館和學術(shù)爭論的氛圍欠缺；最后是課程的關(guān)聯(lián)大，一些關(guān)聯(lián)課程如C語言掌握得較差。

對教學的展望：

1、能盡量在課堂教學中貫穿操作實踐，引導學生把算法結(jié)合數(shù)據(jù)結(jié)構(gòu)形成程序，但受時間限制較大，只能盡量起到牽引作用，一切還看學生課余時間進行。

2、督促完成第一次作業(yè)，畢竟數(shù)據(jù)結(jié)構(gòu)的思想很多都體現(xiàn)在這次線性表實踐作業(yè)中，能真正獨立思考去完成，對以后課程的學習，相對會輕松很多。接著再進行更高一層次的，利用這些算法去解決實際的問題。

3、引導學生形成自主學習能力的自我培養(yǎng)及協(xié)作學習的氛圍形成。畢竟這兩個能力是計算機專業(yè)學生培養(yǎng)的重點之一。

4、細化目標，畢竟這門課是難學的，逐步進行目標，首先，讓學生了解數(shù)據(jù)結(jié)構(gòu)的邏輯特點，各種操作的算法思想；其次，讓學生運用編程語言編寫程序?qū)崿F(xiàn)這些算法；最后，把這些編程思想和設計思路運用到實際應用中解決問題。

5、加強師生交流，了解學生想法，了解學生遇到的問題，更好的有目的的教學。

以此為反思，但愿能更好的進行以后的教學！

第三篇：課程感想-數(shù)據(jù)結(jié)構(gòu)

轉(zhuǎn)眼間半學期已經(jīng)過去了，接觸數(shù)據(jù)結(jié)構(gòu)這門課已經(jīng)八周了。在這一段時間的學習中，我對這門課從剛開始的一竅不通到現(xiàn)在已經(jīng)可以運用所學的知識解決一定的問題，大致知道了數(shù)據(jù)結(jié)構(gòu)的思想和作用。

首先對于數(shù)據(jù)結(jié)構(gòu)，我的認識一直在發(fā)生改變，一開始的時候連邏輯結(jié)構(gòu)和物理結(jié)構(gòu)都分不清，到最后能將總表上的內(nèi)容熟記于心，并加以運用，這樣的進步離不開老師的細心教導和同學們的熱心幫助。在我的認識中，計算機技術(shù)早已經(jīng)成為新世紀的必修技能。很慶幸我選的專業(yè)可以在計算機上有所進階，為自己在日后的競爭中多添一份籌碼。“數(shù)據(jù)結(jié)構(gòu)”是計算機程序設計的重要理論技術(shù)基礎，它不僅是計算機科學的核心課程，而且已經(jīng)成為其他理工專業(yè)的熱門選修課。

在這門課程里，我首先認識了什么是數(shù)據(jù)、什么是數(shù)據(jù)結(jié)構(gòu)以及抽象數(shù)據(jù)類型這些基本的概念，然后開始學習數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)的部分。線性表是學習的第一站，我逐漸發(fā)現(xiàn)，每開啟一個新的邏輯結(jié)構(gòu)，就會相應的講它的存儲結(jié)構(gòu)以及相應的運算。在學習線性表的過程中，我弄明白了很多東西，發(fā)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)已經(jīng)比c語言高出一個高度了更加宏觀地去用c語言，c語言就像是處理數(shù)據(jù)結(jié)構(gòu)的其中一種工具一樣。學習完線性表之后，就像有了一個模板，之后的棧和隊列是進出的方式有所修改各有特色了。學到樹的時候，眼前一亮，覺得這樣的類比方式很有意思，有點像高中生物遺傳學上的系譜圖。二叉樹的遍歷讓我覺得就像小時候玩智力游戲一樣，還有二叉樹中例如求深度這樣的高度提煉規(guī)律又是需要我去努力思考認真總結(jié)的??這門課讓我第一次覺得大學還真的有題要想的這么費腦子。

老師上課的方式也很有效率。剛開始的時候我被一大堆概念搞暈了，但是想著就是一堆概念而已課下也就沒再去細細研究。結(jié)果上課老師提問的時候果然沒有答上來，之后每次課前課后都要爭取做到預習復習，鞏固課上學的知識。不過學知識當然也不是為了應付老師的提問，既然選擇了智能，以后這條路要走的順暢，還少不了數(shù)據(jù)結(jié)構(gòu)的知識。

結(jié)課的時候老師布置了幾道編程的題目，一開始看到書上題目里直接有代碼，就趕緊往c語言的軟件里敲，結(jié)果發(fā)現(xiàn)運行不成，和同學們交流了之后才知道，可能是調(diào)取數(shù)據(jù)庫的問題，書上的函數(shù)編譯器無法識別，于是我發(fā)現(xiàn)我們的主要任務是集中火力把書上提供的功能函數(shù)的功能寫出來，換言之，就是構(gòu)造出這些個函數(shù)然后再使用它們?nèi)崿F(xiàn)功能。在編程的過程中出現(xiàn)了很多的問題，比如指針本來就是c語言中的靈魂，難點中的難點，在數(shù)據(jù)結(jié)構(gòu)的編程中幾乎全部都要用到指針，讓我不得不又翻開c語言的教材去復習指針的相關(guān)知識。另外，編出來的程序有時候自己看不出來錯誤但是編譯器就是報錯，又請教了班里一些已經(jīng)完成的同學，在他們的意見指導下，改進自己的代碼最終運行成功實現(xiàn)功能了。尤其是二叉樹的那道題，因為書上沒有講如何輸入二叉樹，我就在思考無果之后去查資料，才了解c語言是這樣和二叉樹聯(lián)系在一起的。當年創(chuàng)造出數(shù)據(jù)結(jié)構(gòu)的人真的是非常厲害。經(jīng)過這次的編程，我覺得自己不僅撿起來了上學期學的c語言，也加深了對數(shù)據(jù)結(jié)構(gòu)和c語言的理解。我們現(xiàn)在掌握的數(shù)據(jù)結(jié)構(gòu)的知識，就如同我偶然在圖書館看到數(shù)據(jù)結(jié)構(gòu)的書架一樣，只是這個龐大、精深體系中的冰山一角而已，就像老師說的，編程類的知識，老師只是把你帶進門，想要真正掌握還是要自己下很多功夫的。

轉(zhuǎn)眼間數(shù)據(jù)結(jié)構(gòu)這門課已經(jīng)接近尾聲，很多人都說編程是一條孤獨的、枯燥的路，其實我感覺編程還挺好玩，每編一個程序都像是一場斗智斗勇的冒險，一頭扎進去就是好幾個小時，也會經(jīng)常和同學分享一下自己的思路或者見解，越學越覺得智慧殿堂無窮無盡。有時候我以為我自己設計的已經(jīng)比較簡潔比較巧妙了，聽了別人的更是醍醐灌頂，覺得自己傻透了。

在這一段時間的學習里，我們同學之前互相溝通交流，互相幫助過得也很愉快，和劉老師相處的也非常融洽，希望老師在日后的生活教學中多注意身體，老師在教我們之前生了一場病，如果不是這樣，老師上課的風采應該更甚。在以后的學習中，我也會繼續(xù)探究數(shù)據(jù)結(jié)構(gòu)的奇妙世界，學無止境，爭取在數(shù)據(jù)的道路上更上一層樓！

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

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

一、課程基本概況

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

課程名稱（英文）： Data Structures

課程編號：B09042

課程總學時：60（其中，講課48，實驗12）

課程學分：3

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

開設學期：4

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

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

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

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

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

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

本門課程共60學時，其中理論教學48學時，實驗教學12學時。其中，理論教學部分：

第一章

緒論

（一）目的要求

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

（二）教學內(nèi)容 本章知識點：

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

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

3.計算語句頻度和估算算法時間復雜度的方法（掌握）。

（三）重點與難點

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

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

第二章

線性表

（一）目的要求

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

（二）教學內(nèi)容 本章知識點：

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

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

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

（三）重點與難點

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

第三章 棧和隊列

（一）目的要求

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

（二）教學內(nèi)容 本章知識點： 1.棧和隊列的特點(掌握)；

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

（三）重點與難點

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

第四章 串

（一）目的要求

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

（二）教學內(nèi)容 本章知識點：

1.串的七種基本運算的定義（了解）；

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

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

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

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

（一）目的要求

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

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

3.理解稀疏矩陣的兩種存儲方式的特點和適用范圍，領(lǐng)會以三元組表示稀疏矩陣時進行運算采用的處理方法(掌握)；

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

（三）重點與難點

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

第六章 樹和二叉樹

（一）目的要求

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

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

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

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

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

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

第七章 圖

（一）目的要求

理解圖的基本概念；圖的存儲結(jié)構(gòu)；掌握圖的遍歷及應用{最小生成樹，最短路徑等}；拓撲排序和關(guān)鍵路徑。

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

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

4.應用圖的遍歷算法求各種簡單路徑問題（比如，最小生成樹、最短路徑、拓撲排序、關(guān)鍵路徑等）(掌握)。

（三）重點與難點

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

第八章

動態(tài)存儲管理

（一）目的要求

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

（二）教學內(nèi)容 本章知識點：

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

2.無用單元收集時的標志算法（了解）。

（三）重點與難點

存儲器分配策略和算法、無用單元收集時的標志算法

第九章

查找

（一）目的要求

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

（二）教學內(nèi)容 本章知識點：

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

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

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

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

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

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

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

（三）重點與難點

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

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

第十章

內(nèi)部排序

（一）目的要求

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

（二）教學內(nèi)容 本章知識點：

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

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

（三）重點與難點

重點：各種排序方法的特點及其應用；實現(xiàn)排序的各種算法。難點：各種排序算法的時間復雜度分析。

十一章

外部排序

（一）目的要求

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

（二）教學內(nèi)容 本章知識點：

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

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

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

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

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

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

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

（三）重點與難點

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

實踐教學部分：上機實驗分4個專題，每個專題可提供2~4個難度不等的題目供選。

實驗一

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

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

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

（三）實驗教學基本要求

通過實例，使學生掌握棧和隊列兩種特殊的線性結(jié)構(gòu)，掌握棧和隊列的特點。實驗后學生提交實驗報告。

（四）實驗設備和材料 計算機。

（五）實驗學時 4學時

實驗二

教學計劃編制問題

（一）實驗內(nèi)容

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

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

（三）實驗教學基本要求

通過實例，使學生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應用圖結(jié)構(gòu)解決具體問題。實驗后學生提交實驗報告。

（四）實驗設備和材料 計算機。

（五）實驗學時 2學時

實驗三

最小生成樹問題

（一）實驗內(nèi)容

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

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

（三）實驗教學基本要求

通過實例，使學生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應用圖結(jié)構(gòu)解決具體問題。實驗后學生提交實驗報告。

（四）實驗設備和材料 計算機。

（五）實驗學時 2學時

實驗四

哈希表設計

（一）實驗內(nèi)容

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

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

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

（四）實驗設備和材料 計算機

（五）實驗學時 4學時

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

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

考試采用閉卷方式。總成績由平時成績和考試成績組成。平時成績占30%，考試成績占70%。

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

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

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

七、建議教材與參考教材

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

嚴蔚敏等

清華大學出版社

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

嚴蔚敏等

清華大學出版社

1999

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

李春葆

清華大學出版社

2004

八、負責人

撰稿人：劉景匯、李玉香

審稿人：

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

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

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

Data Structure 執(zhí)筆人：

編寫日期：

一、課程基本信息

1.課程編號：

2.課程性質(zhì)/類別： 必修課 / 專業(yè)主干課

3.學時/學分： 48 學時（另實驗16學時）/ 4 學分

4.適用專業(yè)：計算機科學與技術(shù)、軟件工程、網(wǎng)絡工程、信息管理與信息系統(tǒng)等專業(yè)

二、課程教學目標及學生應達到的能力

數(shù)據(jù)結(jié)構(gòu)課程是計算機相關(guān)專業(yè)的專業(yè)基礎課、必修課程，主要介紹用計算機解決一系列問題特別是非數(shù)值信息處理問題時所用的各種組織數(shù)據(jù)的方法、存儲數(shù)據(jù)結(jié)構(gòu)的方法以及在各種結(jié)構(gòu)上執(zhí)行操作的算法。通過本課程的學習，要求學生掌握各種數(shù)據(jù)結(jié)構(gòu)的特點、存儲表示、運算方法以及在計算機科學中最基本的應用，培養(yǎng)、訓練學生選用合適的數(shù)據(jù)結(jié)構(gòu)和編寫質(zhì)量高、風格好的應用程序的能力，培養(yǎng)學生分析問題、解決問題的能力，并為后續(xù)課程的學習打下良好的理論基礎和實踐基礎。

三、課程教學內(nèi)容與基本要求

（一）緒論（3 學時）1．主要內(nèi)容：

（1）介紹什么是數(shù)據(jù)結(jié)構(gòu)；

（2）基本概念和術(shù)語: 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象，以及數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型；

（3）抽象數(shù)據(jù)類型的表示與實現(xiàn)；

（4）算法和算法分析: 算法的概念、算法設計的要求以及算法效率的度量。2．基本要求

（1）了解學習數(shù)據(jù)結(jié)構(gòu)的重要性；

（2）掌握數(shù)據(jù)結(jié)構(gòu)的定義及相關(guān)概念和術(shù)語；（3）了解抽象數(shù)據(jù)類型的定義、表示與實現(xiàn)方法；（4）理解算法的概念、特點并掌握度量其效率的基本方法。3．自學內(nèi)容：

類C語言的書寫規(guī)范。

（二）線性表（6 學時）1．主要內(nèi)容：

（1）線性表的抽象數(shù)據(jù)類型定義和相關(guān)概念：數(shù)據(jù)項、記錄、文件等；（2）線性表順序存儲表示和基本操作的實現(xiàn)；（3）線性表的鏈式存儲表示和基本操作的實現(xiàn)；

（4）稀疏多項式的抽象數(shù)據(jù)類型定義、表示和加法的實現(xiàn)。2．基本要求

（1）掌握線性表的定義和特點；

（2）熟練掌握線性表的順序存儲表示和插入、刪除、查找等實現(xiàn)算法；

（3）熟練掌握單鏈表、循環(huán)鏈表、雙向鏈表三種鏈表的表示，以及單鏈表的查找、插入、刪除、創(chuàng)建等實現(xiàn)算法。

3．自學內(nèi)容：

靜態(tài)鏈表。

（三）棧和隊列（5 學時）1．主要內(nèi)容：

（1）棧和隊列的結(jié)構(gòu)特性和抽象數(shù)據(jù)類型定義；（2）棧和隊列的順序存儲表示和實現(xiàn)；（3）棧和隊列的鏈式存儲表示和實現(xiàn)；（4）棧和隊列在程序設計中的應用。2．基本要求

（1）掌握棧和隊列兩種抽象數(shù)據(jù)類型的特點；

（2）掌握棧的兩種存儲表示和實現(xiàn)，特別注意棧滿棧空的條件；（3）掌握隊列的兩種存儲表示和實現(xiàn)，特別注意隊滿隊空的條件；（4）了解遞歸算法與棧的關(guān)系。3．自學內(nèi)容：

鏈棧，離散事件模擬

（四）串（3 學時）1．主要內(nèi)容：

（1）串的抽象數(shù)據(jù)類型定義；

（2）串的表示和實現(xiàn): 定長順序存儲結(jié)構(gòu)和堆分配存儲結(jié)構(gòu)；（3）串的各種基本操作的實現(xiàn)及其應用；（4）串的模式匹配操作。2．基本要求

（1）熟悉串的一些基本操作的定義，并能利用基本操作實現(xiàn)串的其它操作；（2）掌握串的定長順序存儲結(jié)構(gòu)以及基本操作的實現(xiàn)；（3）掌握串的堆分配存儲結(jié)構(gòu)以及基本操作的實現(xiàn)；（4）掌握串的簡單模式匹配算法，理解KMP算法。3．自學內(nèi)容：

串操作的應用實例。

（五）數(shù)組和廣義表（4 學時）1．主要內(nèi)容：

（1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實現(xiàn)；（2）特殊矩陣和稀疏矩陣的壓縮存儲；（3）廣義表的抽象數(shù)據(jù)類型定義和存儲結(jié)構(gòu)。2．基本要求

（1）了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法；（2）掌握對特殊矩陣進行壓縮存儲時的下標變換公式；

（3）熟悉稀疏矩陣的三元組順序表存儲結(jié)構(gòu)下的一般轉(zhuǎn)置和快速轉(zhuǎn)置算法；了解十字鏈表等存儲結(jié)構(gòu)；

（4）掌握廣義表的結(jié)構(gòu)特點、取表頭表尾操作，及其存儲表示方法。3．自學內(nèi)容：

采用十字鏈表存儲結(jié)構(gòu)創(chuàng)建稀疏矩陣。

（六）樹和二叉樹（10 學時）1．主要內(nèi)容：

（1）樹的抽象數(shù)據(jù)類型定義和基本術(shù)語；

（2）二叉樹的抽象數(shù)據(jù)類型定義、性質(zhì)和存儲結(jié)構(gòu)；（3）二叉樹的遍歷；

（4）線索二叉樹的定義、遍歷及線索化二叉樹；

（5）樹的存儲結(jié)構(gòu)、樹和森林的遍歷以及與二叉樹的轉(zhuǎn)換；（6）Huffman樹及其應用。2．基本要求

（1）掌握樹型結(jié)構(gòu)的特點和基本術(shù)語；

（2）熟練掌握二叉樹的性質(zhì)，了解相應的證明方法；

（3）了解二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，熟練掌握二叉鏈表存儲結(jié)構(gòu)；（4）熟練掌握二叉樹三種遍歷的遞歸算法和中序遍歷非遞歸算法，能靈活運用遍歷算法實現(xiàn)二叉樹的其他操作；

（5）熟練掌握二叉樹的線索化過程，以及在中序線索二叉樹上找結(jié)點的前驅(qū)與后繼的方法；

（6）熟悉樹的各種存儲結(jié)構(gòu)及其特點，掌握樹和森林與二叉樹的轉(zhuǎn)換方法；（7）了解Huffman樹的特性，掌握建立Huffman樹和Huffman編碼的方法。3．自學內(nèi)容：

先序、后序遍歷二叉樹非遞歸算法，層次遍歷二叉樹算法。

（七）圖（9 學時）1．主要內(nèi)容：（1）圖的定義和術(shù)語；

（2）圖的四種存儲結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）、鄰接表、十字鏈表和鄰接多重表；（3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；（4）圖的連通性和最小生成樹；

（5）有向無環(huán)圖及其應用：拓撲排序和關(guān)鍵路徑；（6）最短路徑問題。2．基本要求

（1）熟悉圖的定義和術(shù)語；

（2）了解圖的存儲結(jié)構(gòu)，熟練掌握數(shù)組表示法（鄰接矩陣）和鄰接表存儲表示；（3）熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法；（4）掌握無向連通帶權(quán)圖的最小生成樹求解算法；

（5）了解有向無環(huán)圖、AOV網(wǎng)、AOE網(wǎng)及其在實際中的應用，熟悉拓撲排序算法和關(guān)鍵路徑算法；

（6）熟悉兩種最短路徑問題求解算法。3．自學內(nèi)容：

樹的先根遍歷算法與圖的深度優(yōu)先遍歷算法比較；

樹的層次遍歷算法與圖的廣度優(yōu)先遍歷算法比較。

（八）查找（4 學時）1．主要內(nèi)容：

（1）查找的基本概念和相關(guān)術(shù)語；

（2）靜態(tài)查找表：順序查找、折半查找和索引順序表查找；（3）動態(tài)查找表：二叉排序樹的查找、插入和刪除；（4）哈希表。2．基本要求

（1）了解查找的作用，熟悉相關(guān)術(shù)語；

（2）熟練掌握順序查找、折半查找和索引順序表查找；（3）熟練掌握二叉排序樹的特性、構(gòu)造和查找方法；

（4）熟練掌握哈希表的構(gòu)造方法，特別是哈希函數(shù)和處理沖突方法的選取；（5）通過分析等概率下的平均查找長度來衡量各種查找方法的效率。3．自學內(nèi)容：

平衡二叉樹。

（九）內(nèi)部排序（4 學時）1．主要內(nèi)容：

（1）排序的基本概念和相關(guān)術(shù)語；

（2）插入排序：直接插入排序、折半插入排序和希爾排序；（3）交換排序：起泡排序和快速排序；（4）選擇排序：簡單選擇排序和堆排序；（5）歸并排序：二路歸并排序；（6）基數(shù)排序：鏈式基數(shù)排序；（7）各種內(nèi)部排序方法的比較討論。2．基本要求

（1）了解排序作用，熟悉相關(guān)術(shù)語；

（2）掌握多種排序的基本思想、算法特點和排序過程，分析它們的時間復雜度、空間復雜度和穩(wěn)定性。

3．自學內(nèi)容：

二路插入排序、表插入排序和樹形選擇排序。

四、教學安排建議

1.作業(yè)練習 完成每章的教學后進行布置習題，使用教材配套的《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》。盡量選擇基礎的并且加注了標記的題，應注重于精，而不要求多。要求積極獨立完成所布置的習題，建議安排至少六次。

2.案例分析

可參考選擇以下一些案例：（1）學生通訊錄管理系統(tǒng)，（2）表達式求值問題（3）交通咨詢系統(tǒng)，等。3.專題研討

可參考選擇以下一些：（1）最小生成樹問題（2）航班信息查詢與檢索系統(tǒng)，（3）內(nèi)部排序算法比較，等。

4.實驗安排

為了達到理論與實際應用的結(jié)合，讓學生能將所學知識應用于實際問題的求解中，培養(yǎng)學生的實際動手能力，從而加深對概念及所學知識的理解，靈活、牢固掌握教材內(nèi)容，提高程序設計及解決實際問題的能力，實驗環(huán)節(jié)的安排非常重要。

建議實驗安排為八次，共16學時，分別如下：

實驗1 線性表的順序存儲結(jié)構(gòu)的實現(xiàn)(2學時)

實驗2 線性表的鏈式存儲結(jié)構(gòu)的實現(xiàn)(2學時)

實驗3 棧的算法實現(xiàn)(2學時)

實驗4 隊列的算法實現(xiàn)(2學時)

實驗5 串類型及操作(2學時)

實驗6 二叉樹的建立與遍歷(2學時)

實驗7 圖的建立與遍歷(2學時)

實驗8 查找與排序(2學時)注：教師可根據(jù)教學實際情況（如：學生情況及學時情況等），適當調(diào)整實踐教學內(nèi)容及學時分配。

五、課程考核

1.考核形式及成績評定辦法

本課程考核形式為：平時成績占40%，期末考試成績占60%。其中平時成績的結(jié)構(gòu)分包括：課堂表現(xiàn)10%、平時作業(yè)10%和實驗20%，期末考試為閉卷筆試考試：120分鐘，卷面分滿分100分。期末考試成績低于50分者，本課程成績按不及格論處。

2.本課程考核的基本要求

課堂表現(xiàn)10%：包括課堂考勤和課堂提問，如果缺課課時達到本課程教學時數(shù)的1/3，則取消考試資格。

平時作業(yè)10%：根據(jù)上交次數(shù)及完成情況進行評定。

實驗20%：根據(jù)各次實驗完成情況及實驗報告成績進行評定。

期末考試60%：本課程的期末考試考核內(nèi)容主要包括線性表、棧與隊列、串、數(shù)組與廣義表、樹與二叉樹、圖、查找和內(nèi)部排序。其中，線性表、二叉樹、圖、查找和內(nèi)部排序內(nèi)容為考核的重點。

六、本課程與其它課程的先行后續(xù)關(guān)系

先行課程：《高級程序設計語言》、《離散數(shù)學》

后續(xù)課程：《操作系統(tǒng)》、《編譯原理》、《數(shù)據(jù)庫理論》、《算法分析與設計》等

七、建議教材及教學參考書

1.教材：

嚴蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，清華大學出版，2012.5 嚴蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》，清華大學出版，2012.5 2.參考書：

[1] 許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構(gòu)》，高等教育出版社，2004.[2] 徐孝凱，《數(shù)據(jù)結(jié)構(gòu)簡明教程》，清華大學出版社，1995 [3] 陳文博，朱青，《數(shù)據(jù)結(jié)構(gòu)與算法》，機械工業(yè)出版社，1996 [4] 李云清，楊慶紅，揭安全編著，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），人民郵電出版社，2007.[5] 楊秀金主編，《數(shù)據(jù)結(jié)構(gòu)》，西安電子科技大學出版社，2002.[6] 李廉治，姜文清，郭福順，《數(shù)據(jù)結(jié)構(gòu)》，大連理工大學出版社，1989

[7] Aho A V, Hopcroft J E, Ullman J D.Data Structures and Algorithms.Addison-Wesley Publishing Company,Inc.,1983

[8] Baron R J, Shapiro L G.Data Structures and their Implementation.Van Nostrand Reinhold Company, 1980

[9] Esakov J, Weiss T.Data Structures: An Advanced Approach Using C.Prentice-Hall, Inc.,1989

[10] [美]S巴斯《計算機算法：設計和分析引論》朱洪等譯，復旦大學出版社，1985