“數(shù)據(jù)結(jié)構(gòu)”教學(xué)與教材研究

1、“數(shù)據(jù)結(jié)構(gòu)”教學(xué)與教材研究摘 要：本文回顧了著者三十多年來從事“數(shù)據(jù)結(jié)構(gòu)”教學(xué)與研究的主要經(jīng)歷，重點(diǎn)介紹了對該課程的教材建設(shè)方面的主要工作，指出與時(shí)俱進(jìn)、精益求精地編寫教材是提高教學(xué)水平的基礎(chǔ)和關(guān)鍵?！娟P(guān)鍵詞】：Ap:數(shù)據(jù)結(jié)構(gòu)；算法；程序設(shè)計(jì)語言；程序設(shè)計(jì)方法；教材一、前言194年2月14日，世界上第一臺電子數(shù)字計(jì)算機(jī)ENIACft美國賓夕法尼亞大學(xué)誕生。早期計(jì)算機(jī)主要用于數(shù)值計(jì)算，處理的對象是“無結(jié)構(gòu)”的數(shù)據(jù)（例如整數(shù)和浮點(diǎn)數(shù)），它們和處理這些數(shù)據(jù)的程序（根據(jù)計(jì)算機(jī)指令系統(tǒng)編寫的代碼）都采用二進(jìn)制表示形式存儲在計(jì)算機(jī)的存儲器中。 20 世紀(jì) 50 年代開始的“程序設(shè)計(jì)語言”研究，改變了原始的

2、使用機(jī)器語言編程的方式，語言的“使用手冊”給計(jì)算機(jī)的使用者提供了一個(gè)非常高級的“虛擬機(jī)”，使得程序員可以方便快捷地描述需要的數(shù)據(jù)和處理數(shù)據(jù)的程序；然后通過語言的“編譯器”把它們成功地轉(zhuǎn)換為計(jì)算機(jī)內(nèi)部的二進(jìn)制代碼。高級語言的研究成果，打破了計(jì)算機(jī)只能進(jìn)行科學(xué)計(jì)算的限制?！罢Z言編譯系統(tǒng)”通過計(jì)算機(jī)成功地完成從高級語言的模型到計(jì)算機(jī)硬件語言模型的轉(zhuǎn)換，打開了計(jì)算機(jī)系統(tǒng)軟件研究的大門；同時(shí)也提出許多相對比較復(fù)雜的結(jié)構(gòu)化數(shù)據(jù)的需求（例如棧、散列表和二叉樹等），促進(jìn)了數(shù)據(jù)結(jié)構(gòu)的研究和發(fā)展。“數(shù)據(jù)結(jié)構(gòu)”的概念最早是由 C.A.R.Hoare 和 N.Wirth 在 196年提出。大量關(guān)于程序設(shè)計(jì)理論的研究表

3、明：為了系統(tǒng)而科學(xué)地構(gòu)造大型復(fù)雜的程序，必須對這些程序中所包含的數(shù)據(jù)結(jié)構(gòu)進(jìn)行深入的研究。1968年，美國教授D.E.Knuth 在他的名著計(jì)算機(jī)程序設(shè)計(jì)技巧（第 1 卷基本算法 第二章信息結(jié)構(gòu)）中首次系統(tǒng)地研究并整理了當(dāng)時(shí)經(jīng)常使用的主要數(shù)據(jù)結(jié)構(gòu)與相關(guān)的算法，為數(shù)據(jù)結(jié)構(gòu)課程的開設(shè)提供了豐富的素材（他本人也因此書的成就，在 1974 年獲得計(jì)算機(jī)界最高科學(xué)成就獎(jiǎng)“圖靈獎(jiǎng)”）。自 20 世紀(jì) 70 年代起，“數(shù)據(jù)結(jié)構(gòu)”在西方國家的大學(xué)中，被普遍列為計(jì)算機(jī)本科的必修課程。二、不同時(shí)期的教材1978年著者已有10年從事系統(tǒng)軟件開發(fā)的豐富經(jīng)驗(yàn)，參加了北京大學(xué)計(jì)算機(jī)系的籌備和創(chuàng)建。在擔(dān)任數(shù)據(jù)庫教研組組長期間

4、，按系主任張士龍教授的安排，負(fù)責(zé)“數(shù)據(jù)結(jié)構(gòu)”等新課的建設(shè)。從此圍繞數(shù)據(jù)結(jié)構(gòu)開展的工作，包括學(xué)習(xí)與研究、講課與編寫教材等，三十多年一直沒有停息。其中花費(fèi)時(shí)間和精力最多的是根據(jù)教學(xué)和科研的需要編寫了下面4 本教材（以 8 種不同版本出版）。第一本教材：數(shù)據(jù)結(jié)構(gòu)1979年教育部在南京大學(xué)召開了第一次全國計(jì)算機(jī)系教學(xué)大綱研討會，著者帶著起草的“數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱”和“數(shù)據(jù)庫教學(xué)大綱”與系主任一起參加了會議。會上充分肯定了我們的工作，并建議我們分工負(fù)責(zé)編寫數(shù)據(jù)結(jié)構(gòu)教材。根據(jù)這個(gè)大綱的修改稿，著者組織教研組內(nèi)的老師共同編寫了第一本數(shù)據(jù)結(jié)構(gòu)講義。1980年起，這本講義在校內(nèi)外（包括南京大學(xué)、中山大學(xué)等國內(nèi)著名

5、高校）廣泛試用，三易其稿。 1987 年由高等教育出版社正式出版（此書 1992 年獲國家教委頒發(fā)的全國優(yōu)秀教材獎(jiǎng)）。第二本教材：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)1985年，“北京市自學(xué)考試委員會”開設(shè)計(jì)算機(jī)專業(yè)。作為數(shù)據(jù)結(jié)構(gòu)課程的考試委員，著者邀請楊冬青和邵維忠兩位老師共同編寫了這本自學(xué)考試教材。 1991 年由北京大學(xué)出版社出版，第二年臺灣儒林出版公司用繁體字出版。第三本教材：數(shù)據(jù)結(jié)構(gòu)C+W面向?qū)ο蟮耐緩绞兰o(jì) 90 年代，面向?qū)ο蟮恼Z言和方法開始流行。根據(jù)教學(xué)和科研的需要，著者與裘宗燕老師合作編寫了該教材。 1998年作為國家“九五”重點(diǎn)教材由高等教育出版社出版， 201 年出修訂版。第四本教材：算法與數(shù)據(jù)結(jié)

6、構(gòu)1998年，著者由北京大學(xué)校長聘任，主持全校理科主干基礎(chǔ)課“算法與數(shù)據(jù)結(jié)構(gòu)”，考慮到不同專業(yè)的需要，組織理科教師共同編寫了一本適合理科各專業(yè)通用的新教材。該書列為“面向 21 世紀(jì)教材”， 202 年由高等教育出版社出版，獲評“北京市高等教育教材”； 20 年出第二版，列為“十一五”國家級規(guī)劃教材，獲評教育部“普通高等教育教材”； 20 年再次修改并附著者教學(xué)光盤，出第三版。回顧三十多年來圍繞數(shù)據(jù)結(jié)構(gòu)教學(xué)方面的工作，深深體會到與時(shí)俱進(jìn)、精益求精地編寫教材是提高教學(xué)水平的基礎(chǔ)和關(guān)鍵。三、數(shù)據(jù)結(jié)構(gòu)教材需要與時(shí)俱進(jìn)計(jì)算機(jī)科學(xué)是一門高速發(fā)展的新興科學(xué)，它的研究內(nèi)容和研究方法都在不斷發(fā)展。“結(jié)構(gòu)”可以

7、解釋為：（ 1）把某些成分（成員、元素、原子等）按一定的規(guī)律或方式組織在一起的實(shí)體；或（2）把某些成分組織在一起的方式。 “數(shù)據(jù)結(jié)構(gòu)”從字面上可以理解為就是以數(shù)據(jù)為成員的結(jié)構(gòu)。在早期關(guān)于數(shù)據(jù)結(jié)構(gòu)的論文中，一個(gè)數(shù)據(jù)結(jié)構(gòu)多數(shù)情況下是指一個(gè)“實(shí)體”，而不是指“方式”。用通俗的程序語言的術(shù)語來講，一個(gè)數(shù)據(jù)結(jié)構(gòu)就可以看成一個(gè)結(jié)構(gòu)化的數(shù)據(jù)。然而，計(jì)算機(jī)科學(xué)研究數(shù)據(jù)結(jié)構(gòu)的目的是為了在計(jì)算機(jī)中有效地表示和處理客觀世界的各種不同對象。所以我們關(guān)心的是這些數(shù)據(jù)結(jié)構(gòu)如何存儲在計(jì)算機(jī)中，并且能有效地完成各種需要的操作。隨著計(jì)算機(jī)科學(xué)的發(fā)展，對于數(shù)據(jù)結(jié)構(gòu)的教學(xué)與研究也逐步從“實(shí)體”，提高到“方式”，直到“抽象數(shù)據(jù)類型的

8、實(shí)現(xiàn)”。教材應(yīng)該正確反映計(jì)算機(jī)科學(xué)的發(fā)展水平前面提到的第一本教材，基本反映了 20 世紀(jì) 70 年代的認(rèn)識水平。當(dāng)時(shí)數(shù)據(jù)結(jié)構(gòu)的許多概念還十分模糊，即使像“?！焙汀瓣?duì)列”這些最基本的結(jié)構(gòu)，它們的操作定義都不完全統(tǒng)一。許多教材對于什么是“數(shù)據(jù)結(jié)構(gòu)”都沒有解釋。我們考察了 20 世紀(jì) 70 年代有影響的幾本著作。其中 H.A.Maurer 用一個(gè)二元組 B= K， R 來形式地定義一個(gè)數(shù)據(jù)結(jié)構(gòu)B,其中K是結(jié)點(diǎn)有限集合，而R是K上的關(guān)系的有限 集合。 C.C.Gotlieb 和 L.R.Gotlieb 則將數(shù)據(jù)結(jié)構(gòu)的定義擴(kuò)充成一個(gè)五元組：V, O, G M S。其中V是所討論的結(jié)構(gòu)中成員取值的集合，O

9、是結(jié)構(gòu)中成員 可執(zhí)行的運(yùn)算的集合，G是兩個(gè)構(gòu)成名字的文法，M是結(jié)構(gòu)中各成員存放位置的集 合， S 是 L（ G） M 的映射。根據(jù)數(shù)據(jù)結(jié)構(gòu)研究的目的和應(yīng)用的需要，我們認(rèn)為提到一種數(shù)據(jù)結(jié)構(gòu)離不開以下三個(gè)方面：（1）構(gòu)成數(shù)據(jù)結(jié)構(gòu)的成員之間固有的邏輯關(guān)系；（2）將數(shù)據(jù)存儲在計(jì)算機(jī)中的表示方法；（ 3）在計(jì)算機(jī)中對數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算或處理。將這三方面分別簡稱為數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運(yùn)算，所以在第一本教材中我們明確采用這三者的統(tǒng)一（三位一體）來非形式地定義“數(shù)據(jù)結(jié)構(gòu)”的概念。第二本數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)以上一本教材內(nèi)容為基礎(chǔ)，根據(jù)N.Wirth 教授提出的“算法+數(shù)據(jù)結(jié)構(gòu)=程序”關(guān)系，把程序理解為在數(shù)據(jù)的某些

10、特定的結(jié)構(gòu)和表示的基礎(chǔ)上對于算法的描述。算法與數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)中相輔相成、不可分割的兩個(gè)方面。為了適合于自學(xué)考試大綱的要求，參考了 A.V.Aho 教授 20 世紀(jì) 80年代的教材，采用以數(shù)據(jù)結(jié)構(gòu)為主線、算法為輔線的結(jié)構(gòu)編寫，使得內(nèi)容更加緊湊、重點(diǎn)更加突出。第三本教材數(shù)據(jù)結(jié)構(gòu) C+W面向?qū)ο蟮耐緩绞窃诿嫦驅(qū)ο蟮恼Z言和方法開始流行的 20 世紀(jì) 90 年代，采用面向?qū)ο蟮脑O(shè)計(jì)方法講解數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。參考 Budd 的工作，由簡到繁、從易到難，系統(tǒng)地引入各種抽象數(shù)據(jù)類型的概念和實(shí)現(xiàn)，并在全書最后，用類圖方式總結(jié)了各種經(jīng)典的抽象數(shù)據(jù)類型在教材中的相互關(guān)系。最后一本算法與數(shù)據(jù)結(jié)構(gòu)參考了 Kurt M

11、ehlhorn 等人的觀點(diǎn)，把“數(shù)據(jù)結(jié)構(gòu)”定義為“抽象數(shù)據(jù)類型的物理實(shí)現(xiàn)”。提出“物理實(shí)現(xiàn)”的意圖是強(qiáng)調(diào)本課程關(guān)心的“實(shí)現(xiàn)”應(yīng)具體到可以用計(jì)算機(jī)的兩個(gè)最重要的物理量（主機(jī)的運(yùn)行時(shí)間和內(nèi)存的存儲空間）來權(quán)衡。這一觀點(diǎn)突出了抽象數(shù)據(jù)類型在數(shù)據(jù)結(jié)構(gòu)教學(xué)中的地位，包含了數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο蠹夹g(shù)的內(nèi)在聯(lián)系。使讀者可以從更高的層次理解數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系，也容易解釋數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)與運(yùn)算的三者關(guān)系。后兩本教材都反映了 20 世紀(jì) 90 年代的理解水平。其共同之處是：都強(qiáng)調(diào)了數(shù)據(jù)結(jié)構(gòu)是“抽象數(shù)據(jù)類型的實(shí)現(xiàn)”，前一本使用的是面向?qū)ο蟮膶?shí)現(xiàn)方法，而后一本為了突出講解實(shí)現(xiàn)的物理效率，沒有采用面向?qū)ο蟮姆椒ā?/p>

12、教材內(nèi)容既要相對穩(wěn)定又要逐步更新需要指出的是，盡管計(jì)算機(jī)科學(xué)的發(fā)展使得數(shù)據(jù)結(jié)構(gòu)的地位和作用產(chǎn)生了許多變化，但是數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的目的并沒有大的改變。所以教材的內(nèi)容是基本穩(wěn)定的。第一本教材按“邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運(yùn)算和應(yīng)用”四個(gè)層次的結(jié)構(gòu)組建架構(gòu)。全書共18 章，除第一章概論外分為四大部分：第一部分是線性結(jié)構(gòu)，包括順序表、鏈表與動(dòng)態(tài)存儲管理、串、內(nèi)排序和線性表的檢索等五章；第二部分是樹形結(jié)構(gòu)，包括樹形結(jié)構(gòu)的概念、樹形結(jié)構(gòu)的存儲、二叉樹周游算法、樹目錄和樹形結(jié)構(gòu)的其他應(yīng)用等五章；第三部分是復(fù)雜結(jié)構(gòu)，包括圖和多維數(shù)組與廣義表兩章；第四部分是文件結(jié)構(gòu)，包括順序文件、散列文件、索引順序文件、倒排文件和外排序

13、等五章。全書概念清楚、內(nèi)容豐富、體系完整。第二本作為自學(xué)考試教材，內(nèi)容在第一本的基礎(chǔ)上加以精簡，并增加集合與字典結(jié)構(gòu)，把檢索歸入集合的基本運(yùn)算。在結(jié)構(gòu)上更加強(qiáng)調(diào)基礎(chǔ)、突出重點(diǎn)、適合自學(xué)。全書共分8章。第一章通過分析 午 一個(gè)實(shí)際問題的求解過程，引入抽象數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)和算法等重要概念作為全書的引論；第二章到第五章分別討論了表、樹、集合和圖等常見的各種數(shù)據(jù)結(jié)構(gòu)，一般均以抽象數(shù)據(jù)類型引路，重點(diǎn)討論抽象數(shù)據(jù)類型在計(jì)算機(jī)中各種不同的實(shí)現(xiàn)方法；第六章對鏈接表示所需要的動(dòng)態(tài)存儲管理問題作了系統(tǒng)的闡述；第七章綜述了外存上數(shù)據(jù)結(jié)構(gòu)的各種組織方式；第八章給出內(nèi)排序和外排序的各種算法。第三本由于采用了面向?qū)ο蟮?/p>

14、方法，在內(nèi)容上做了較大調(diào)整。增加了面向?qū)ο蟮姆椒ㄈ腴T和優(yōu)先隊(duì)列。全書共分 12章：第一章，緒論；第二章，C+W面向?qū)ο蟪醪?；第三章，字符串，本章定義了一種更安全可靠的字符串類型，同時(shí)也以字符串做例子，討論數(shù)據(jù)抽象和封裝的有關(guān)問題；第四章，向量，本章建立了一種安全可靠的向量數(shù)據(jù)類型，還給出了幾個(gè)主要的向量排序算法；第五章，動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)鏈表，主要討論了各種常用的鏈表結(jié)構(gòu)及其實(shí)現(xiàn)方法；第六章，棧和隊(duì)列，介紹了棧和隊(duì)列的抽象概念、具體實(shí)現(xiàn)及其應(yīng)用；第七章，樹和二叉樹，介紹了樹和二叉樹的概念，重點(diǎn)介紹二叉樹的實(shí)現(xiàn)及樹結(jié)構(gòu)用于快速檢索的一些技術(shù)；第八章，優(yōu)先隊(duì)列，主要介紹了堆和斜堆的概念以及通過它們實(shí)現(xiàn)優(yōu)

15、先隊(duì)列的方法；第九章，集合和字典；第十章，散列表；第十一章，圖；第十二章，文件。在附錄中用類圖方式給出本書介紹的主要抽象數(shù)據(jù)類型及其相互關(guān)系圖。第四本書作為北京大學(xué)主干課“算法與數(shù)據(jù)結(jié)構(gòu)”的通用教材。全書共分以下 10 章。第一章緒論；第二章線性表；第三章字符串；第四章棧與隊(duì)列；第五章二叉樹與樹；第六章集合與字典；第七章高級字典結(jié)構(gòu)；第八章排序，第九章圖；第十章算法分析Ap 與設(shè)計(jì)，主要給讀者概括地介紹算法的分析Ap和設(shè)計(jì)的主要技術(shù)。本書在編寫中注意到知識模塊的獨(dú)立性和相關(guān)性，不同專業(yè)的學(xué)生可以根據(jù)不同的需要進(jìn)行組合使用。在我們后編寫的兩本教材中，都大幅度減少了存儲管理和文件系統(tǒng)的內(nèi)容，其主要原因是它們應(yīng)該分別屬于“操作系統(tǒng)”和“數(shù)據(jù)庫”的教學(xué)范圍。“文件系統(tǒng)”又稱“物理數(shù)據(jù)庫”，主要講解數(shù)據(jù)庫的物理實(shí)現(xiàn)。在我們新編的教材中，只給出了與“字典類型”緊密相關(guān)的“索引文件”及“散列文件”介紹，也沒有給出實(shí)現(xiàn)代碼。算法描述語言要配合教學(xué)的需要數(shù)據(jù)結(jié)構(gòu)的教學(xué)內(nèi)容原本獨(dú)立于任何一種特定的程序設(shè)計(jì)語言，但是這門課程的教與學(xué)又離不開程序設(shè)計(jì)語言的支持。在這里語言是一種教學(xué)的工具。工具的選擇應(yīng)該有利于表達(dá)數(shù)據(jù)結(jié)構(gòu)的基本思想與算法的設(shè)計(jì)方法