1.4 關(guān)于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)

計(jì)算機(jī)發(fā)展始終遵循摩爾（1965）法則：“芯片容量每18個(gè)月加倍”，新摩爾定理：“計(jì)算機(jī)性能每18個(gè)月提高一倍，價(jià)格每半年降低一半”，是否已經(jīng)到達(dá)極限？是否會(huì)不再遵循摩爾法則？楊振寧在西安科協(xié)2000年會(huì)議上，明確地答復(fù)了這個(gè)問(wèn)題：是什么原因促使芯片容量長(zhǎng)期成倍地增長(zhǎng)，新原理、新方法、新道理，是維持創(chuàng)新的源泉，創(chuàng)新是人類知識(shí)發(fā)展、生產(chǎn)發(fā)展的重要因素。

計(jì)算機(jī)機(jī)器性能價(jià)格比持續(xù)提高，硬件發(fā)展如此之快，是否沒(méi)有必要去追求提高算法的時(shí)間復(fù)雜度、沒(méi)有必要去追求節(jié)省算法占用存儲(chǔ)空間的數(shù)目呢？不是沒(méi)有必要，而是要求越來(lái)越高。原因之一是，由于機(jī)器性能價(jià)格比的提高，人們所面臨的處理問(wèn)題的問(wèn)題規(guī)模越來(lái)越大，要把過(guò)去不可能解決的問(wèn)題變得可能，必須要求高性能的算法；另一個(gè)原因是，即使在同一問(wèn)題規(guī)模情況下，算法性能好壞差別很大，一個(gè)是O(n)數(shù)量級(jí)，一種是O(2n)數(shù)量級(jí)，當(dāng)n=32時(shí)，2n的結(jié)果都已很大，即使n再增大一倍，2n幾乎都已經(jīng)無(wú)法表述，這不是硬件發(fā)展速度所能滿足的。由此說(shuō)明，硬件速度的提高決不是人們可以不重視算法性能的理由，而是人們追求高性能算法的動(dòng)力。圖1.8所示為數(shù)據(jù)結(jié)構(gòu)與其他課程關(guān)系圖。

1.數(shù)據(jù)結(jié)構(gòu)課程地位

明確提出數(shù)據(jù)結(jié)構(gòu)概念不過(guò)30多年，“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立課程在國(guó)外1968年開(kāi)始設(shè)立，我國(guó)從20世紀(jì)80年代初才開(kāi)始正式開(kāi)設(shè)“數(shù)據(jù)結(jié)構(gòu)”課程。“數(shù)據(jù)結(jié)構(gòu)”課程較系統(tǒng)地介紹了軟件設(shè)計(jì)中常用數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的存儲(chǔ)結(jié)構(gòu)和算法，系統(tǒng)地介紹了常用的查找和排序技術(shù)，并對(duì)各種結(jié)構(gòu)與技術(shù)進(jìn)行分析和比較，內(nèi)容非常豐富。數(shù)據(jù)結(jié)構(gòu)涉及多方面的知識(shí)，如計(jì)算機(jī)硬件范圍的存儲(chǔ)裝置和存取方法，軟件范圍中的文件系統(tǒng)、數(shù)據(jù)的動(dòng)態(tài)管理、信息檢索，以及數(shù)學(xué)范圍中關(guān)于集合、邏輯的知識(shí)，還有一些綜合性的知識(shí)（如數(shù)據(jù)類型、程序設(shè)計(jì)方法、數(shù)據(jù)表示、數(shù)據(jù)運(yùn)算、數(shù)據(jù)存取等），是計(jì)算機(jī)專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)的內(nèi)容將為操作系統(tǒng)、數(shù)據(jù)庫(kù)原理、編譯原理等后續(xù)課程的學(xué)習(xí)打下良好的基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)課程不僅講授數(shù)據(jù)信息在計(jì)算機(jī)中的組織和表示方法，還訓(xùn)練高效地解決復(fù)雜問(wèn)題程序設(shè)計(jì)的能力，因此數(shù)據(jù)結(jié)構(gòu)是數(shù)學(xué)、計(jì)算機(jī)硬件、計(jì)算機(jī)軟件三者之間的一門核心課程，“數(shù)據(jù)結(jié)構(gòu)”課程是計(jì)算機(jī)專業(yè)提高軟件設(shè)計(jì)水平的一門關(guān)鍵性課程。

數(shù)據(jù)結(jié)構(gòu)發(fā)展趨勢(shì)包括兩個(gè)方面：一方面，面向?qū)ｉT領(lǐng)域中特殊問(wèn)題的數(shù)據(jù)結(jié)構(gòu)的研究和發(fā)展，如圖形數(shù)據(jù)結(jié)構(gòu)、知識(shí)數(shù)據(jù)結(jié)構(gòu)、空間數(shù)據(jù)結(jié)構(gòu)；另一方面，從抽象數(shù)據(jù)類型的角度，用面向?qū)ο笥^點(diǎn)來(lái)討論數(shù)據(jù)結(jié)構(gòu)，已成為新的發(fā)展趨勢(shì)。

2.數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn)

“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)目標(biāo)要求學(xué)生學(xué)會(huì)分析數(shù)據(jù)對(duì)象特征，掌握數(shù)據(jù)組織方法和計(jì)算機(jī)的表示方法，以便為應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)算法，初步掌握算法時(shí)間、空間分析的技巧，培養(yǎng)良好的程序設(shè)計(jì)技能。

人類解決問(wèn)題的思維方式可分為兩大類：一類是推理方式，憑借公理系統(tǒng)思維方法，從抽象公理體系出發(fā)，演繹、歸納、推理，求證結(jié)果，解決特定問(wèn)題；另一類是算法方式，憑借算法構(gòu)造思維方式，從具體操作規(guī)范入手，通過(guò)操作過(guò)程的構(gòu)造和實(shí)施解決特定問(wèn)題。開(kāi)發(fā)一個(gè)優(yōu)秀的軟件系統(tǒng)過(guò)程中所憑借的思維方法本質(zhì)上不同于常規(guī)數(shù)學(xué)訓(xùn)練的公理系統(tǒng)思維方法，而是一種算法構(gòu)造性思維方法。系統(tǒng)開(kāi)發(fā)是創(chuàng)造性思維過(guò)程的實(shí)現(xiàn)，因而，對(duì)于一名開(kāi)發(fā)人員，只知道開(kāi)發(fā)工具的語(yǔ)言規(guī)則和簡(jiǎn)單使用過(guò)程是不夠的。首先要有科學(xué)方法指導(dǎo)開(kāi)發(fā)過(guò)程；然后在編程技術(shù)應(yīng)用技能上積累提高。讓學(xué)生理解、習(xí)慣、熟悉這一套算法構(gòu)造思維方法，是計(jì)算機(jī)軟件課程教學(xué)的重要內(nèi)容和主要難點(diǎn)。

“數(shù)據(jù)結(jié)構(gòu)”的學(xué)習(xí)過(guò)程是進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程。技能培養(yǎng)的重要程度不亞于知識(shí)傳授。難點(diǎn)在于：理解授課內(nèi)容與應(yīng)用知識(shí)解答復(fù)雜問(wèn)題之間的素質(zhì)能力差距。培養(yǎng)優(yōu)良的算法設(shè)計(jì)思想、方法技巧與風(fēng)格，進(jìn)行構(gòu)造性思維訓(xùn)練過(guò)程，強(qiáng)化程序抽象能力，培養(yǎng)數(shù)據(jù)抽象能力。從某種意義上說(shuō)，數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的后繼課程。如同學(xué)習(xí)英語(yǔ)一樣，學(xué)習(xí)英語(yǔ)不難，學(xué)好英語(yǔ)不易，要提高程序設(shè)計(jì)水平必須經(jīng)過(guò)艱苦的磨煉。因此，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，僅從書(shū)本上學(xué)習(xí)是不夠的，必須經(jīng)過(guò)大量的實(shí)踐，在實(shí)踐中體會(huì)構(gòu)造性思維方法，掌握數(shù)據(jù)組織與程序設(shè)計(jì)的技術(shù)。

3.關(guān)于本書(shū)內(nèi)容編寫(xiě)說(shuō)明

（1）本書(shū)基本結(jié)構(gòu)

基本結(jié)構(gòu)分為如下四大部分。

第一部分：緒論。

第二部分：基本的數(shù)據(jù)結(jié)構(gòu)。包括：線性結(jié)構(gòu)（第2～4章）——線性表、棧和隊(duì)列、串和數(shù)組；非線性結(jié)構(gòu)（第5、6章）——樹(shù)、圖。

第三部分：基本技術(shù)。包括查找與排序（第7、8章）。

第四部分：實(shí)驗(yàn)實(shí)訓(xùn)。

（2）本書(shū)內(nèi)容編排模式

本書(shū)所列出的程序均在Turbo C 2.0下調(diào)試通過(guò)，所有算法均采用嚴(yán)謹(jǐn)?shù)腃語(yǔ)言進(jìn)行描述，只需加以必要的類型定義與調(diào)用，即可上機(jī)運(yùn)行使用。

每章附有習(xí)題，以便于讀者做配套練習(xí)。