北大數(shù)據(jù)結(jié)構(gòu)課件,內(nèi)部資料,精品

1、teaching and research 教學(xué)與研究計(jì)算機(jī)教育 2004.2/3 第 89 頁數(shù)據(jù)結(jié)構(gòu)課程的知識(shí)體系和教學(xué)實(shí)踐張銘許卓群楊冬青唐世渭 /文一、數(shù)據(jù)結(jié)構(gòu)知識(shí)體系計(jì)算機(jī)科學(xué)已經(jīng)深入應(yīng)用到各個(gè)領(lǐng)域，不僅有效地解決了各種工程和科學(xué)計(jì)算中的數(shù)值計(jì)算問題，而且也有效地解決了許多文本處理、信息檢索、數(shù)據(jù)庫管理、圖像識(shí)別、人工智能等非數(shù)值的數(shù)據(jù)處理問題。數(shù)據(jù)結(jié)構(gòu) 有助于程序員更有效地組織數(shù)據(jù)、設(shè)計(jì)高效的算法、完成 高質(zhì)量的程序以滿足錯(cuò)綜復(fù)雜的實(shí)際需要。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科的重要分支研究領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)和算法在計(jì)算機(jī)學(xué)科中的地位十分重要， 其他計(jì)算機(jī)科學(xué)領(lǐng)域及有關(guān)的應(yīng)用軟件都要使用到各種數(shù)據(jù)結(jié)構(gòu)

2、。數(shù)據(jù)結(jié)構(gòu)是算法分析與設(shè)計(jì)、操作系統(tǒng)、軟件工程、數(shù)據(jù)庫概論、編譯技術(shù)、計(jì)算機(jī)圖形學(xué)、人機(jī)交互等專業(yè)基礎(chǔ)課和專業(yè)課程的先行課程。語言編譯要使用棧、散列表及語法樹； 操作系統(tǒng)中用隊(duì)列、存儲(chǔ)管理表及目錄樹等；數(shù)據(jù)庫系統(tǒng)運(yùn)用線性表，多鏈表及索引樹等進(jìn)行數(shù)據(jù)管理；而在人工智能領(lǐng)域，依求解問題性質(zhì)的差異將涉及到各種不同的數(shù)據(jù)結(jié)構(gòu)，如廣義表，集合、搜索樹及各種有向圖等等。美國 ieee 和 acm 的教學(xué)計(jì)劃cc2001 把算法與數(shù)據(jù)結(jié)構(gòu)列入計(jì)算機(jī)以及信息技術(shù)相關(guān)學(xué)科專業(yè)的本科必修基礎(chǔ)課程。在我國，數(shù)據(jù)結(jié)構(gòu)已經(jīng)作為理工科非計(jì)算機(jī)專業(yè)必修的信息技術(shù)基礎(chǔ)課程之一。世界上許多科技人員對(duì)學(xué)習(xí)、研究數(shù)據(jù)結(jié)構(gòu)都非常重視

3、，對(duì)于從事計(jì)算機(jī)科學(xué)及其應(yīng)用的科技工作者來說，數(shù)據(jù)結(jié)構(gòu)更是必須透徹地掌握的重要基礎(chǔ)。1數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算從字面上來看，數(shù)據(jù)結(jié)構(gòu)就是指數(shù)據(jù)間的相互關(guān)系。具體到計(jì)算機(jī)環(huán)境，談到任何一種結(jié)構(gòu)時(shí)，都自然地聯(lián)系著作用在這種類型的數(shù)據(jù)上的運(yùn)算（即函數(shù)），為了在計(jì)算機(jī)上執(zhí)行這些運(yùn)算，我們有必要把這些數(shù)據(jù)以某種方式存儲(chǔ)在計(jì)算機(jī)中。因此，我們可以認(rèn)為，所謂數(shù)據(jù)結(jié)構(gòu)， 就是由某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的存儲(chǔ)方法被存儲(chǔ)于計(jì)算機(jī)中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合。也就是說，數(shù)據(jù)結(jié)構(gòu)具有三個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。常見邏輯關(guān)系有：線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖結(jié)構(gòu)和文件結(jié)構(gòu)

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

5、交通圖可以用數(shù)據(jù)結(jié)構(gòu)的圖來形象化地表示：用結(jié)點(diǎn)表示城市，用邊表示連接城市的高速公路；web 網(wǎng)頁的關(guān)系也可以表示為圖：web 網(wǎng)頁作為結(jié)點(diǎn)，網(wǎng)頁之間的鏈接作為邊。圖是一種最通用的邏輯結(jié)構(gòu)，實(shí)際上，圖? 樹 ? 二叉樹 ? 線性表。常見的存儲(chǔ)方法有：順序方法、鏈接方法、索引方法、散列方法。其中，索引存儲(chǔ)又分為線性和樹形兩種。文件結(jié)構(gòu)的索引則往往用樹形結(jié)構(gòu)。對(duì)于一種數(shù)據(jù)結(jié)構(gòu)，往往需要定義一些運(yùn)算。例如，建立數(shù)據(jù)結(jié)構(gòu)、清除數(shù)據(jù)結(jié)構(gòu)、teaching and research 教學(xué)與研究計(jì)算機(jī)教育 2004.2/3 第 90 頁插入一個(gè)新數(shù)據(jù)元素、刪除某個(gè)數(shù)據(jù)元素、修改某個(gè)數(shù)據(jù)元素、排序、檢索等。作為

6、最常用的算法，排序和檢索歷來是數(shù)據(jù)結(jié)構(gòu)討論中的重點(diǎn)問題。排序算法最能夠體現(xiàn)算法的魅力，它對(duì)算法速度要求非常高，其中內(nèi)排序主要考慮的是怎樣減少關(guān)鍵碼之間的比較次數(shù)和記錄交換次數(shù)，以提高排序速度。可以證明所有基于比較的排序算法的時(shí)間代價(jià)是(nlog n)，這也是排序問題的時(shí)間代價(jià)；而外排序則考慮外存的特性，盡量減少訪外操作，以提高排序速度。檢索則考慮怎樣提高檢索速度，這往往是與存儲(chǔ)方法有關(guān)的。例如，我們可以利用索引存儲(chǔ)來加快檢索。散列表、b 樹和 b+樹等高效的數(shù)據(jù)結(jié)構(gòu)都具有極好的檢索性能。2算法的效率問題每一種數(shù)據(jù)結(jié)構(gòu)與其相關(guān)的算法都有時(shí)間、空間開銷和效率等問題。每當(dāng)面臨一個(gè)新的設(shè)計(jì)問題時(shí)， 設(shè)

7、計(jì)者都應(yīng)該要權(quán)衡時(shí)間空間開銷，設(shè)計(jì)出更有效的數(shù)據(jù)結(jié)構(gòu)和算法，以適應(yīng)問題的需要。基本問題包括： 對(duì)于給定的一類問題，最好的算法是什么？需要多少存儲(chǔ)空間和時(shí)間？空間與時(shí)間的折衷方案是什么？存取數(shù)據(jù)最好的方法是什么？最好算法的最壞情況是什么？平均來說， 算法的運(yùn)行好到何種程度？算法一般化到何種程度即什么類型的問題可以用類似的方法處理？這就涉及到算法分析技術(shù)，許多數(shù)據(jù)結(jié)構(gòu)教材都揉合了一些基本的算法分析技術(shù)，這有助于讀者根據(jù)問題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)，并對(duì)時(shí)間空間復(fù)雜性進(jìn)行必要的控制。3抽象數(shù)據(jù)類型事實(shí)上，數(shù)據(jù)結(jié)構(gòu)的三個(gè)側(cè)面，以數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算定義更為重要。因?yàn)楹芏鄷r(shí)候人們并不關(guān)心數(shù)據(jù)的存儲(chǔ)

8、結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)。1983 年 aho 等人把數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)與實(shí)現(xiàn)細(xì)節(jié)剝離，定義了抽象數(shù)據(jù)類型（簡稱“adt ” ）的概念。抽象數(shù)據(jù)類型是定義了一組運(yùn)算的數(shù)學(xué)模型。例如棧結(jié)構(gòu)，棧中元素的數(shù)學(xué)特性(即邏輯結(jié)構(gòu) )表現(xiàn)為線性表，它們是有序的；棧的主要運(yùn)算是進(jìn)棧(push)、出棧 (pop)、判?？?(isempty)等。這里我們并不涉及棧的存儲(chǔ)方式以及棧中元素的類型等。這種抽象的數(shù)據(jù)類型可以在較高級(jí)的算法中直接引用，而不用考慮它的實(shí)現(xiàn)細(xì)節(jié)。這就使得設(shè)計(jì)者可以在不同的設(shè)計(jì)階段采用不同的抽象數(shù)據(jù)類型作為設(shè)計(jì)的基礎(chǔ)，在適當(dāng)?shù)某橄髮哟紊峡紤]程序的結(jié)構(gòu)和算法，從而很好地支持了邏輯設(shè)計(jì)和物理實(shí)現(xiàn)的分離，支

9、持封裝和信息隱蔽。大多數(shù)教材都是以數(shù)據(jù)的邏輯結(jié)構(gòu)為主線，順序介紹線性結(jié)構(gòu)、樹形結(jié)構(gòu)、 圖結(jié)構(gòu)和文件結(jié)構(gòu)。在介紹每種數(shù)據(jù)結(jié)構(gòu)時(shí)，再討論其存儲(chǔ)結(jié)構(gòu)以及相關(guān)的算法。例如對(duì)于線性表，如果考慮到存儲(chǔ)，可以分為數(shù)組和鏈表；考慮到運(yùn)算的特殊性，則可以分為向量、棧和隊(duì)列。對(duì)于一些比較重要的算法，再列出單獨(dú)的章節(jié)來討論，例如排序、 檢索、 索引、存儲(chǔ)管理等。二、數(shù)據(jù)結(jié)構(gòu)的教學(xué)目的peter jdenning 等人認(rèn)為，計(jì)算機(jī)學(xué)科分為理論、抽象、設(shè)計(jì)這三個(gè)形態(tài)。我們把數(shù)據(jù)結(jié)構(gòu)課程所涉及的主要方面整理為：1. 理論(1) 算法的數(shù)學(xué)基礎(chǔ)。例如，有關(guān)圖論、組合論等，特別是遞歸、遞推、歸納等分析方法。(2) 算法的時(shí)間

10、和空間度量。2抽象(1) 排序、檢索等重要問題類的有效算法，以及最好、最差和一般性能的分析比較。(2) 重要數(shù)據(jù)結(jié)構(gòu)技術(shù)，例如分治法(二分檢索、快速排序、歸并排序)、貪心算法（huffman 編碼、 prim 算法、 kruskal 算法、 dijstra 算法） 、動(dòng)態(tài)規(guī)劃（ prim 算法、teaching and research 教學(xué)與研究計(jì)算機(jī)教育 2004.2/3 第 91 頁dijstra 算法、 floyd 算法、最佳二叉搜索樹） 、棧的引用（深度優(yōu)先周游）、隊(duì)列的應(yīng)用（廣度優(yōu)先周游） 。3設(shè)計(jì)(1) 掌握并靈活應(yīng)用常用的基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型、各種基本存儲(chǔ)方法及其主要的算

11、法，例如線性結(jié)構(gòu)（包括一維數(shù)組、鏈表、棧、隊(duì)列、字符串等）、二叉樹、樹、圖、文件；(2) 排序、檢索、索引等重要問題類的算法的選擇、實(shí)現(xiàn)和測試。例如，各種排序方法的實(shí)驗(yàn)時(shí)間比較，散列、倒排索引、b 樹等應(yīng)用。(3) 存儲(chǔ)管理的實(shí)現(xiàn)與測試。例如可利用空間表、無用單元收集、伙伴系統(tǒng)。數(shù)據(jù)結(jié)構(gòu)這門課程不僅僅要讓學(xué)生掌握那些鏈表、樹、圖是如何實(shí)現(xiàn)的。設(shè)置這門課程有三個(gè)目的：第一個(gè)目的是讓學(xué)生懂得“數(shù)據(jù)結(jié)構(gòu)算法程序”；第二個(gè)目的是培養(yǎng)數(shù)據(jù)抽象的能力； 第三個(gè)目的是使得學(xué)生把數(shù)據(jù)結(jié)構(gòu)和算法理論與編程實(shí)踐相結(jié)合，能夠在實(shí)際的工程實(shí)踐中靈活地予以應(yīng)用。在達(dá)到前兩個(gè)目的時(shí)，學(xué)生就基本具備了解決現(xiàn)實(shí)未知問題的能力

12、，再輔以必要的綜合上機(jī)項(xiàng)目訓(xùn)練，可以達(dá)到第三個(gè)目的?？偠灾?，通過數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)，學(xué)生需要掌握以下四個(gè)方面的知識(shí)和能力：（1）掌握并靈活應(yīng)用常用的基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型、各種基本存儲(chǔ)方法、主要的算法， 例如線性結(jié)構(gòu)、二叉樹、樹、圖、文件；（2）掌握并簡單應(yīng)用常用的排序、檢索和索引算法和方法； （3）掌握基本的算法設(shè)計(jì)和分析技術(shù)，并對(duì)自己設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行簡單的分析； （4）在進(jìn)行程序設(shè)計(jì)、調(diào)試、測試的課程項(xiàng)目訓(xùn)練（即上機(jī)實(shí)習(xí)訓(xùn)練）過程中，要求學(xué)生綜合應(yīng)用所學(xué)到的數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)，學(xué)會(huì)分析研究數(shù)據(jù)對(duì)象的特性，以便選擇合適的數(shù)據(jù)結(jié)構(gòu)和存貯結(jié)構(gòu)以及相應(yīng)的算法，合理地組織數(shù)據(jù)、 有效地

13、表示數(shù)據(jù)、 有效地處理數(shù)據(jù)，書寫的程序結(jié)構(gòu)清楚、正確易讀，提高程序設(shè)計(jì)的質(zhì)量。三、數(shù)據(jù)結(jié)構(gòu)教材編寫思路1987 年高教社出版的許卓群等編寫的數(shù)據(jù)結(jié)構(gòu)被很多高校的計(jì)算機(jī)系采用為數(shù)據(jù)結(jié)構(gòu)課程主教材。該書已經(jīng)連續(xù)再印刷近二十次，并于1992 獲得教育部教材優(yōu)秀獎(jiǎng)和國家教材優(yōu)秀獎(jiǎng)。在多年的使用過程中，國內(nèi)很多讀者建議更新部分內(nèi)容，補(bǔ)充一些電子教案，并希望在算法的偽代碼編碼風(fēng)格方面，由類pascal 改為類 c+ 語言。我們采納這些建議，由北京大學(xué)信息科學(xué)技術(shù)學(xué)院許卓群、楊冬青、唐世渭、張銘這四位多年從事數(shù)據(jù)結(jié)構(gòu)教學(xué)和研究的教員一起修訂數(shù)據(jù)結(jié)構(gòu)教材。作者圍繞中國計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程ccc2002 和

14、美國 ieee 和 acm 的教學(xué)計(jì)劃cc2001 所規(guī)定的基本知識(shí)點(diǎn)，參考國內(nèi)外的最新數(shù)據(jù)結(jié)構(gòu)教材，編寫第二版數(shù)據(jù)結(jié)構(gòu)。1第二版的主要修訂原則z基本內(nèi)容和知識(shí)點(diǎn)不做大的變動(dòng)，不增加難度。z考慮采用最廣為程序員所使用的c+語言作為算法描述語言，從而使得抽象數(shù)據(jù)類型(adt) 的概念得到更自然的體現(xiàn)，更本質(zhì)地體現(xiàn)數(shù)據(jù)結(jié)構(gòu)的思想，而且所定義的數(shù)據(jù)結(jié)構(gòu)類能夠方便地被重用。z為了保證教材的易讀性，盡量回避c/c+中比較麻煩的內(nèi)容，例如c 的指針的指針的指針等折磨人的東西，c+的類的繼承、虛函數(shù)等。z使用參數(shù)化的模板（template） ，從而提高算法中數(shù)據(jù)類型的通用性，支持高效的代碼重用。在后面的章節(jié)

15、中，盡量使用stl (standard template library ，標(biāo)準(zhǔn) c+ 類庫)所提供的棧、隊(duì)列等基本數(shù)據(jù)結(jié)構(gòu)。teaching and research 教學(xué)與研究計(jì)算機(jī)教育 2004.2/3 第 92 頁z刪除原來的逆轉(zhuǎn)鏈周游二叉樹、robson 周游算法、 siklossy 周游算法、 關(guān)鍵路徑等內(nèi)容。z增加了 patricia 樹、伸展樹等復(fù)雜樹結(jié)構(gòu)，k-d 樹、pr 四分樹、 r* 樹等空間數(shù)據(jù)結(jié)構(gòu)。z每一章中都增補(bǔ)了比較多的綜合上機(jī)實(shí)習(xí)題（即項(xiàng)目實(shí)習(xí)）。z為了配合教材的發(fā)行，我們將編寫概念清晰、內(nèi)容充實(shí)的多媒體演示講稿以及用標(biāo)準(zhǔn) c+模板編寫的可執(zhí)行的源程序代碼。出版

16、社可以考慮帶光盤發(fā)行，或提供網(wǎng)站。2第二版新大綱的考慮第一版完全按照邏輯結(jié)構(gòu)的角度來安排內(nèi)容。每一種數(shù)據(jù)結(jié)構(gòu)都有一些比較復(fù)雜的算法。作者在給輔修數(shù)據(jù)結(jié)構(gòu)的外系學(xué)生使用該教材時(shí)，只能選擇一些比較淺顯的內(nèi)容，學(xué)生們感覺跳躍性比較大。而在使用該教材給計(jì)算機(jī)專業(yè)的學(xué)生講課時(shí)，又常常感覺到樹和圖等基本數(shù)據(jù)結(jié)構(gòu)太靠后，已經(jīng)快到學(xué)期結(jié)束了，不好給學(xué)生布置大的上機(jī)實(shí)習(xí)題?？紤]到數(shù)據(jù)結(jié)構(gòu)這門課程基本知識(shí)點(diǎn)的劃分，根據(jù)我們多年教學(xué)經(jīng)驗(yàn)，作者對(duì)第二版的目錄進(jìn)行了比較大的調(diào)整。第二版以中國計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程ccc2002 中的 pf3 基本數(shù)據(jù)結(jié)構(gòu)、 al1算法分析基礎(chǔ)、al3 基本算法為核心內(nèi)容，分為基本數(shù)據(jù)

17、結(jié)構(gòu)、排序和檢索、高級(jí)數(shù)據(jù)結(jié)構(gòu)這三個(gè)部分。首先，第一部分（共6 章）從邏輯結(jié)構(gòu)的角度系統(tǒng)地介紹各種基本數(shù)據(jù)結(jié)構(gòu)，即概論、線性表(包括向量、棧和隊(duì)列)、字符串、二叉樹、樹和圖。概論討論了數(shù)據(jù)結(jié)構(gòu)的定義、抽象數(shù)據(jù)類型和基本的算法分析技術(shù)。然后，第二部分（共4章）從算法的角度討論排序、檢索和索引算法， 索引算法新增加了關(guān)于文本文件的倒排索引，倒排索引是當(dāng)前信息檢索和搜索引擎技術(shù)的關(guān)鍵技術(shù)。考慮到計(jì)算機(jī)學(xué)科的應(yīng)用性以及學(xué)生靈活應(yīng)用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題的需要，第三部分（共2 章）介紹了數(shù)據(jù)結(jié)構(gòu)的高級(jí)主題，例如廣義表和稀疏矩陣等更復(fù)雜的線性表結(jié)構(gòu)，trie 結(jié)構(gòu)、 avl 樹、伸展樹等復(fù)雜樹結(jié)構(gòu)，k-d

18、樹、pr 四分樹、 r* 樹等空間數(shù)據(jù)結(jié)構(gòu)，把存儲(chǔ)管理作為線性結(jié)構(gòu)的典型應(yīng)用予以介紹，把決策樹和博弈樹作為樹型結(jié)構(gòu)的典型應(yīng)用加以介紹。最后附錄布置了一個(gè)學(xué)期綜合上機(jī)實(shí)習(xí)題“搜索引擎” ，并簡單介紹了其中涉及的圖搜索、倒排索引等技術(shù)。其中第一部分是最基本的內(nèi)容，教員可以根據(jù)學(xué)生的程度選擇第二部分、第三部分一些內(nèi)容來講解。 該教材能夠適應(yīng)不同的讀者的學(xué)習(xí)需要以及教員的教學(xué)安排，特別為教師安排上機(jī)實(shí)習(xí)提供了極大的方便。四、教學(xué)策略數(shù)據(jù)結(jié)構(gòu)課程中， 既有很多靈活的與離散數(shù)學(xué)（尤其是圖論、 組合數(shù)學(xué)） 有關(guān)的證明題，又有大量算法設(shè)計(jì)題。而且該課程對(duì)程序設(shè)計(jì)能力的要求很高，需要學(xué)生動(dòng)手編寫實(shí)習(xí)題以應(yīng)用并掌

19、握數(shù)據(jù)結(jié)構(gòu)知識(shí)。對(duì)于計(jì)算機(jī)專業(yè)的學(xué)生來說，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 之前應(yīng)該先修 計(jì)算引論 （或稱“計(jì)算概論” ， “計(jì)算機(jī)文化基礎(chǔ)” ） 、 面向?qū)ο蟪绦蛟O(shè)計(jì)實(shí)習(xí)、 集合論與圖論這三門課程。對(duì)于只有“計(jì)算概論”基礎(chǔ)的非計(jì)算機(jī)專業(yè)的學(xué)生，可以適當(dāng)減少數(shù)學(xué)證明的要求，不要求設(shè)計(jì)比較復(fù)雜的算法。為了搞好“數(shù)據(jù)結(jié)構(gòu)”這門重要主干基礎(chǔ)課程的教學(xué)工作，作者以熱忱的工作態(tài)度、以科研工作的鉆研精神認(rèn)真投入教學(xué)研究。投入了大量精力和時(shí)間，建立了全新的教學(xué)體系，盡力完善各個(gè)教學(xué)環(huán)節(jié)。1啟發(fā)式教學(xué)，培養(yǎng)學(xué)生的創(chuàng)造性思維和主動(dòng)學(xué)習(xí)精神在數(shù)據(jù)結(jié)構(gòu)教學(xué)中，對(duì)于每種數(shù)據(jù)結(jié)構(gòu)都從其數(shù)學(xué)特性入手，先介紹其抽象數(shù)據(jù)類型，然后再討論其不同的

20、存儲(chǔ)方法。與學(xué)生一起討論研究不同存儲(chǔ)方法的可能算法，結(jié)合算法分teaching and research 教學(xué)與研究計(jì)算機(jī)教育 2004.2/3 第 93 頁析來討論各種存儲(chǔ)方法和算法的利弊，摒棄那些不適宜的方法。這樣， 充分調(diào)動(dòng)了學(xué)生思維積極性，學(xué)到了數(shù)據(jù)結(jié)構(gòu)的思維方法以及從事科研的基本方法。2 與科研結(jié)合，在教學(xué)中引進(jìn)新的理論和技術(shù)內(nèi)容 盡量把科研中涉及到的與數(shù)據(jù)結(jié)構(gòu) 課程相關(guān)的新理論和技術(shù)、優(yōu)秀論文介紹給學(xué)生，拓展了教學(xué)內(nèi)容。例如，給學(xué)生講解“搜索引擎”中的數(shù)據(jù)結(jié)構(gòu)技術(shù)（主要涉及到圖搜索、排序和索引技術(shù)） ，講解當(dāng)前網(wǎng)絡(luò)和數(shù)據(jù)庫的研究熱點(diǎn)“xml （擴(kuò)展標(biāo)記語言） ” 。3加強(qiáng)實(shí)踐環(huán)節(jié)的

21、訓(xùn)練北京大學(xué)計(jì)算機(jī)系歷來十分重視實(shí)踐環(huán)節(jié)的訓(xùn)練。數(shù)據(jù)結(jié)構(gòu)課程一直為每學(xué)期4 學(xué)分/每周 4 學(xué)時(shí)，每位學(xué)生的上機(jī)實(shí)習(xí)時(shí)間每學(xué)期約80 小時(shí)。從2003 屆北京大學(xué)信息學(xué)院計(jì)算機(jī)專業(yè)的學(xué)生開始，數(shù)據(jù)結(jié)構(gòu)將改為兩門課程，即算法與數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)，在同一個(gè)學(xué)期講授，分別為每學(xué)期3 學(xué)分 /每周 3 學(xué)時(shí)，每學(xué)期2 學(xué)分 /每周 2 學(xué)時(shí)。改革的目的主要是加強(qiáng)上機(jī)實(shí)踐，每位學(xué)生的數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)習(xí)時(shí)間增加為每學(xué)期120小時(shí)。數(shù)據(jù)結(jié)構(gòu)是一門理論和實(shí)踐結(jié)合比較緊密的課程，每周都布置6 道書面作業(yè)或小程序?qū)嵙?xí)（全學(xué)期約70 道） ，每個(gè)學(xué)期布置6 道大的上機(jī)實(shí)習(xí)題（其中最后一道是2-3 人合作的學(xué)期綜合上機(jī)實(shí)習(xí)題，例如“搜索引擎”、 “ xml 數(shù)據(jù)管理”等） 。組織助教認(rèn)真檢查習(xí)題和上機(jī)題，并編寫了參考答案公布在網(wǎng)上。4采用新的教育技術(shù)，提高教學(xué)效果；建立了一個(gè)高質(zhì)量的