計算機(jī)科學(xué)是一門研究數(shù)據(jù)表示和數(shù)據(jù)處理的科學(xué)數(shù)據(jù)是

1、第一章 緒論計算機(jī)科學(xué)是一門研究數(shù)據(jù)表示和數(shù)據(jù)處理的科學(xué)。數(shù)據(jù)是計算機(jī)化的信息，它是計算機(jī)可以直接處理的最基本和最重要的對象。無論是進(jìn)行科學(xué)計算或數(shù)據(jù)處理、過程控制以及對文件的存儲和檢索及數(shù)據(jù)庫技術(shù)等計算機(jī)應(yīng)用領(lǐng)域中，都是對數(shù)據(jù)進(jìn)行加工處理的過程。因此，要設(shè)計出一個結(jié)構(gòu)好效率高的程序，必須研究數(shù)據(jù)的特性及數(shù)據(jù)間的相互關(guān)系及其對應(yīng)的存儲表示，并利用這些特性和關(guān)系設(shè)計出相應(yīng)的算法和程序。數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課，是十分重要的核心課程。所有的計算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，要想更好地運(yùn)用計算機(jī)來解決實(shí)際問題，僅掌握幾種計算機(jī)程序設(shè)計語言是難以應(yīng)付眾多復(fù)雜的

2、課題的。要想有效地使用計算機(jī)、充分發(fā)揮計算機(jī)的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識。打好“數(shù)據(jù)結(jié)構(gòu)”這門課程的扎實(shí)基礎(chǔ)，對于學(xué)習(xí)計算機(jī)專業(yè)的其他課程，如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫管理系統(tǒng)、軟件工程、人工智能等都是十分有益的。1.1數(shù)據(jù)結(jié)構(gòu)的定義在計算機(jī)發(fā)展的初期，人們使用計算機(jī)的目的主要是處理數(shù)值計算問題。當(dāng)我們使用計算機(jī)來解決一個具體問題時，一般需要經(jīng)過下列幾個步驟：首先要從該具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計或選擇一個解此數(shù)學(xué)模型的算法，最后編出程序進(jìn)行調(diào)試、測試，直至得到最終的解答。例如，求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學(xué)模型的線性方程組，該方程組可以使用迭代算法來求解。由于當(dāng)時所涉

3、及的運(yùn)算對象是簡單的整型、實(shí)型或布爾類型數(shù)據(jù)，所以程序設(shè)計者的主要精力是集中于程序設(shè)計的技巧上，而無須重視數(shù)據(jù)結(jié)構(gòu)。隨著計算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟、硬件的發(fā)展，非數(shù)值計算問題越來越顯得重要。據(jù)統(tǒng)計，當(dāng)今處理非數(shù)值計算性問題占用了90%以上的機(jī)器時間。這類問題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述。因此，解決這類問題的關(guān)鍵不再是數(shù)學(xué)分析和計算方法，而是要設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問題。下面所列舉的就是屬于這一類的具體問題。例如學(xué)生信息檢索系統(tǒng)。當(dāng)我們需要查找某個學(xué)生的有關(guān)情況的時候；或者想查詢某個專業(yè)或年級的學(xué)生的有關(guān)情況的時候，只要我們建立了相關(guān)的

4、數(shù)據(jù)結(jié)構(gòu)，按照某種算法編寫了相關(guān)程序，就可以實(shí)現(xiàn)計算機(jī)自動檢索。由此，可以在學(xué)生信息檢索系統(tǒng)中建立一張按學(xué)號順序排列的學(xué)生信息表和分別按姓名、專業(yè)、年級順序排列的索引表，如圖1.1所示。由這四張表構(gòu)成的文件便是學(xué)生信息檢索的數(shù)學(xué)模型，計算機(jī)的主要操作便是按照某個特定要求（如給定姓名）對學(xué)生信息文件進(jìn)行查詢。諸如此類的還有電話自動查號系統(tǒng)、考試查分系統(tǒng)、倉庫庫存管理系統(tǒng)等。在這類文檔管理的數(shù)學(xué)模型中，計算機(jī)處理的對象之間通常存在著的是一種簡單的線性關(guān)系，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。例1 學(xué)生信息檢索系統(tǒng)。當(dāng)我們需要查找某個學(xué)生的有關(guān)情況的時候；或者想查詢某個專業(yè)或年級的學(xué)生的有關(guān)情況的時候

5、，只要我們建立了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，按照某種算法編寫了相關(guān)程序，就可以實(shí)現(xiàn)計算機(jī)自動檢索。由此，可以在學(xué)生信息檢索系統(tǒng)中建立一張按學(xué)號順序排列的學(xué)生信息表和分別按姓名、專業(yè)、年級順序排列的索引表，如圖1.1所示。由這四張表構(gòu)成的文件便是學(xué)生信息檢索的數(shù)學(xué)模型，計算機(jī)的主要操作便是按照某個特定要求（如給定姓名）對學(xué)生信息文件進(jìn)行查詢。諸如此類的還有電話自動查號系統(tǒng)、考試查分系統(tǒng)、倉庫庫存管理系統(tǒng)等。在這類文檔管理的數(shù)學(xué)模型中，計算機(jī)處理的對象之間通常存在著的是一種簡單的線性關(guān)系，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)學(xué)號姓名性別專 業(yè)年 級980001吳承志男計算機(jī)科學(xué)與技術(shù)98級980002李淑芳女信息

6、與計算科學(xué)98級990301劉 麗女?dāng)?shù)學(xué)與應(yīng)用數(shù)學(xué)99級990302張會友男信息與計算科學(xué)99級990303石寶國男計算機(jī)科學(xué)與技術(shù)99級000801何文穎女計算機(jī)科學(xué)與技術(shù)2000級000802趙勝利男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2000級000803崔文靖男信息與計算科學(xué)2000級010601劉 麗女計算機(jī)科學(xué)與技術(shù)2001級010602魏永鳴男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2001級崔文靖8何文穎6李淑芳2劉 麗3，9石寶國5魏永鳴10吳承志1趙勝利7張會有4計算機(jī)科學(xué)與技術(shù)1，5，6，9信息與計算科學(xué)2，4，8數(shù)學(xué)與應(yīng)用數(shù)學(xué)3，7，102000級6，7，82001級9，1098級1，2，399級4，5（a）學(xué)生信息

7、表（b）姓名索引表（c）專業(yè)索引表（d）年級索引表圖 1.1 學(xué)生信息查詢系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)例2 八皇后問題。在八皇后問題中，處理過程不是根據(jù)某種確定的計算法則，而是利用試探和回溯的探索技術(shù)求解。為了求得合理布局，在計算機(jī)中要存儲布局的當(dāng)前狀態(tài)。從最初的布局狀態(tài)開始，一步步地進(jìn)行試探，每試探一步形成一個新的狀態(tài)，整個試探過程形成了一棵隱含的狀態(tài)樹。如圖1.2所示（為了描述方便，將八皇后問題簡化為四皇后問題）?；厮莘ㄇ蠼膺^程實(shí)質(zhì)上就是一個遍歷狀態(tài)樹的過程。在這個問題中所出現(xiàn)的樹也是一種數(shù)據(jù)結(jié)構(gòu)，它可以應(yīng)用在許多非數(shù)值計算的問題中。 例3 計劃編排問題。一個教學(xué)計劃包含許多課程，在教學(xué)計劃包含的許多

8、課程之間，有些必須按規(guī)定的先后次序進(jìn)行，有些則沒有次序要求。即有些課程之間有先修和后續(xù)的關(guān)系，有些課程可以任意安排次序。這種各個課程之間的次序關(guān)系可用一個稱作圖的數(shù)據(jù)結(jié)構(gòu)來表示，如圖1.3所示。有向圖中的每個頂點(diǎn)表示一門課程，如果從頂點(diǎn)vi到vj之間存在有向邊，則表示課程i必須先于課程j進(jìn)行。 由以上三個例子可見，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，可以說數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機(jī)操作對象以及它們之間的關(guān)系和操作的學(xué)科。圖1.2 四皇后問題中隱含的狀態(tài)樹課程編號課程名稱先修課程C1計算機(jī)導(dǎo)論無C2數(shù)據(jù)結(jié)構(gòu)C

9、1，C4C3匯編語言C1C4C程序設(shè)計語言C1C5計算機(jī)圖形學(xué)C2，C3，C4C6接口技術(shù)C3C7數(shù)據(jù)庫原理C2，C9C8編譯原理C4C9操作系統(tǒng)C2C1C2C3C6C4C5C9C7C8 12數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)與數(shù)學(xué)、計算機(jī)硬件和軟件有十分密切的關(guān)系。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件之間的一門計算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程，是高級程序設(shè)計語言、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫、人工智能等課程的基礎(chǔ)。同時，數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。 方面 層次數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運(yùn)算實(shí)現(xiàn)存儲結(jié)構(gòu)算法評價不同數(shù)據(jù)結(jié)構(gòu)的比較及算法分析圖1.5

10、數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容體系數(shù)據(jù)結(jié)構(gòu)課程集中討論軟件開發(fā)過程中的設(shè)計階段、同時設(shè)計編碼和分析階段的若干基本問題。此外，為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，還需考慮數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的評價與選擇。因此，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括三個層次的五個“要素”，如圖1.5所示。數(shù)據(jù)結(jié)構(gòu)的核心技術(shù)是分解與抽象。通過分解可以劃分出數(shù)據(jù)的三個層次；再通過抽象，舍棄數(shù)據(jù)元素的具體內(nèi)容，就得到邏輯結(jié)構(gòu)。類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實(shí)現(xiàn)細(xì)節(jié)，就得到運(yùn)算的定義。上述兩個方面的結(jié)合使我們將問題變換為數(shù)據(jù)結(jié)構(gòu)。這是一個從具體（即具體問題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過程。然后，通過增加對實(shí)現(xiàn)細(xì)節(jié)的考慮進(jìn)一步得到存儲結(jié)構(gòu)和實(shí)

11、現(xiàn)運(yùn)算，從而完成設(shè)計任務(wù)。這是一個從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實(shí)現(xiàn)）的過程。熟練地掌握這兩個過程是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的基本目標(biāo)。數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程在國外是從1968年才開始的，但在此之前其有關(guān)內(nèi)容已散見于編譯原理及操作系統(tǒng)之中。20世紀(jì)60年代中期，美國的一些大學(xué)開始設(shè)立有關(guān)課程，但當(dāng)時的課程名稱并不叫數(shù)據(jù)結(jié)構(gòu)。1968年美國唐.歐.克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的計算機(jī)程序設(shè)計技巧第一卷基本算法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。從20世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對獨(dú)立，結(jié)構(gòu)程序設(shè)計成為程序設(shè)計方法學(xué)的主要

12、內(nèi)容，人們越來越重視數(shù)據(jù)結(jié)構(gòu)。從70年代中期到80年代，各種版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)。目前，數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)，一方面，面向各專門領(lǐng)域中特殊問題的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，如多維圖形數(shù)據(jù)結(jié)構(gòu)等；另一方面，從抽象數(shù)據(jù)類型和面向?qū)ο蟮挠^點(diǎn)來討論數(shù)據(jù)結(jié)構(gòu)已成為一種新的趨勢，越來越被人們所重視。1 3數(shù)據(jù)結(jié)構(gòu)的基本概念1.12基本術(shù)語1.1.1 數(shù)據(jù)（data）數(shù)據(jù)是指能夠輸入到計算機(jī)中，并被計算機(jī)識別和處理的符號的集合。 例如：數(shù)字、字母、漢字、圖形、圖像、聲音都稱為數(shù)據(jù)。 2數(shù)據(jù)元素（data element）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。 數(shù)據(jù)元素是一個數(shù)據(jù)整體中相對獨(dú)立的單位。但它還可以分

13、割成若干個具有不同屬性的項(xiàng)（字段），故不是組成數(shù)據(jù)的最小單位。3 數(shù)據(jù)對象（data object）是性質(zhì)相同的數(shù)據(jù)元素組成的集合，是數(shù)據(jù)的一個子集。例如，整數(shù)數(shù)據(jù)對象的集合可表示為N0，1，2.，字母字符數(shù)據(jù)對象的集合可表示為C=A,B,Z。4數(shù)據(jù)結(jié)構(gòu)（data structures） 數(shù)據(jù)結(jié)構(gòu)定義1：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 形式化定義：數(shù)據(jù)結(jié)構(gòu)是一個二元組 Data_Structure = (D,R)其中，D是數(shù)據(jù)元素的有限集合，R是D上關(guān)系的集合 數(shù)據(jù)結(jié)構(gòu)定義2： 按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計算機(jī)語言并按一定的存儲表示

14、方式把它們存儲在計算機(jī)的存儲器中，并在其上定義了一個運(yùn)算的集合。具體來說，數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存貯結(jié)構(gòu)和對數(shù)據(jù)所施加的運(yùn)算（操作）。 這三個方面的關(guān)系為： （1）數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于計算機(jī)，是數(shù)據(jù)本身所固有的。（2）存貯結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機(jī)存貯器中的映像，必須依賴于計算機(jī)。（3）運(yùn)算是指所施加的一組操作總稱。運(yùn)算的定義直接依賴于邏輯結(jié)構(gòu)，但運(yùn)算的實(shí)現(xiàn)必須依賴于存貯結(jié)構(gòu)。 邏輯結(jié)構(gòu)-劃分方法一、集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。二、線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。三、樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。四、圖狀

15、結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。 存儲結(jié)構(gòu)（Storge Structure):數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示(或稱映象）稱為數(shù)據(jù)的存儲結(jié)構(gòu)，又稱為物理結(jié)構(gòu)。四種基本的存儲方法： （1）順序存儲方法（順序存儲結(jié)構(gòu)） （2）鏈接存儲方法（鏈?zhǔn)酱鎯Y(jié)構(gòu)） （3）索引存儲方法 （4）散列存儲方法 同一種邏輯結(jié)構(gòu)可采用不同的存儲方法（以上四種之一或組合），這主要考慮的是運(yùn)算方便及算法的時空要求。順序存儲結(jié)構(gòu):用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯Y(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放地址的指針，用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。索引存儲方法：使用該方法存

16、放元素的同時，還建立附加的索引表，索引表的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是：（關(guān)鍵字，地址），其中的關(guān)鍵字是能惟一標(biāo)識一個結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)。散列存儲方法：通過構(gòu)造散列函數(shù)，用函數(shù)的值來確定元素存放的地址。5數(shù)據(jù)類型是一組性質(zhì)相同的值的集合及定義于這個值集合上的一組操作的總稱。是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念。它最早出現(xiàn)在高級程序設(shè)計語言中，用以刻劃程序中操作對象的特性。在用高級語言編寫的程序中，每個變量、常量或表達(dá)式都有一個它所屬的確定的數(shù)據(jù)類型。類型顯式地或隱含地規(guī)定了在程序執(zhí)行期間變量或表達(dá)式所有可能的取值范圍，以及在這些值上允許進(jìn)行的操作。 C+提供的基本數(shù)據(jù)類型有：整型、實(shí)型、字符型、

17、邏輯型 例如，高級語言中用到的整數(shù)數(shù)據(jù)類型，是指由32768到32767中值構(gòu)成的集合及一組操作（加、減、乘、除、乘方等）的總稱。 注：數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)的區(qū)別，數(shù)據(jù)結(jié)構(gòu)強(qiáng)調(diào)數(shù)據(jù)元素之間的邏輯關(guān)系。6抽象數(shù)據(jù)類型（Abstract data type）抽象數(shù)據(jù)類型（Abstruct Data Type，簡稱ADT）是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個概念。例如，各種計算機(jī)都擁有的整數(shù)類型就是一個抽象數(shù)據(jù)

18、類型，盡管它們在不同處理器上的實(shí)現(xiàn)方法可以不同，但由于其定義的數(shù)學(xué)特性相同，在用戶看來都是相同的。因此，“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。但在另一方面，抽象數(shù)據(jù)類型的范疇更廣，它不再局限于前述各處理器中已定義并實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。為了提高軟件的重用性，在近代程序設(shè)計方法學(xué)中，要求在構(gòu)成軟件系統(tǒng)的每個相對獨(dú)立的模塊上，定義一組數(shù)據(jù)和施于這些數(shù)據(jù)上的一組操作，并在模塊的內(nèi)部給出這些數(shù)據(jù)的表示及其操作的細(xì)節(jié)，而在模塊的外部使用的只是抽象的數(shù)據(jù)及抽象的操作。這也就是面向?qū)ο蟮某绦蛟O(shè)計方法。抽象數(shù)據(jù)類型的定義可以由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作組成，

19、而數(shù)據(jù)結(jié)構(gòu)又包括數(shù)據(jù)元素及元素間的關(guān)系，因此抽象數(shù)據(jù)類型一般可以由元素、關(guān)系及操作三種要素來定義。抽象數(shù)據(jù)類型的特征是使用與實(shí)現(xiàn)相分離，實(shí)行封裝和信息隱蔽。就是說，在抽象數(shù)據(jù)類型設(shè)計時，把類型的定義與其實(shí)現(xiàn)分離開來。格式：ADT is Data: Operation: END 例如:給出自然數(shù)的抽象數(shù)據(jù)類型定義. ADT Natural Number is Data: 一個整數(shù)的有序子集合，它開始于0，終止于機(jī)器能表示的最大整數(shù)（MAXINT）。 Operation: 對于所有x,y Natural Number,定義如下操作： add(x,y) 求x+y sub(x,y) 求x-y mul(

20、x,y) 求x*ydiv(x,y) 求x/yend1.2 算法的描述算法的概念1算法（algorithm） 通俗地講，算法就是一種解題的方法。更嚴(yán)格地說，算法是由若干條指令組成的有窮序列，它必須滿足下述條件（也稱為算法的五大特性）：（1）輸入：具有0個或多個輸入的外界量（算法開始前的初始量）（2）輸出：至少產(chǎn)生一個輸出，它們是算法執(zhí)行完后的結(jié)果。（3有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。（4)確定性：每條指令的含義都必須明確，無二義性。（5）可行性：每條指令的執(zhí)行時間都是有限的。2算法和程序的關(guān)系算法的含義與程序十分相似，但二者是有區(qū)別的。一個程序不一定滿足有窮性（死循環(huán)），另外，程序中的指

21、令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此限制。一個算法若用計算機(jī)語言來書寫，則它就可以是一個程序。算法與數(shù)據(jù)結(jié)構(gòu)是相輔相承的。解決某一特定類型問題的算法可以選定不同的數(shù)據(jù)結(jié)構(gòu)，而且選擇恰當(dāng)與否直接影響算法的效率。反之，一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由各種算法的執(zhí)行來體現(xiàn)。要設(shè)計一個好的算法通常要考慮以下的要求。正確。算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求?？勺x。一個算法應(yīng)當(dāng)思路清晰、層次分明、簡單明了、易讀易懂。健壯。當(dāng)輸入不合法數(shù)據(jù)時，應(yīng)能作適當(dāng)處理，不至引起嚴(yán)重后果。高效。有效使用存儲空間和有較高的時間效率。算法描述 算法可以使用各種不同的方法來描述。最簡單的方法是使用自然語言。用自然語言來

22、描述算法的優(yōu)點(diǎn)是簡單且便于人們對算法的閱讀。缺點(diǎn)是不夠嚴(yán)謹(jǐn)。可以使用程序流程圖、N-S圖等算法描述工具。其特點(diǎn)是描述過程簡潔、明了。用以上兩種方法描述的算法不能夠直接在計算機(jī)上執(zhí)行，若要將它轉(zhuǎn)換成可執(zhí)行的程序還有一個編程的問題?？梢灾苯邮褂媚撤N程序設(shè)計語言來描述算法，不過直接使用程序設(shè)計語言并不容易，而且不太直觀，常常需要借助于注釋才能使人看明白。 用C+描述算法在本教材中，我們將采用C或類C+來描述算法。并且用C描述算法遵循如下規(guī)則：（1）所有算法的描述都用C中的函數(shù)形式函數(shù)類型 函數(shù)名（形參及類型說明） 函數(shù)語句部分 return(表達(dá)式值)； （2）函數(shù)中的形式參數(shù)有兩種傳值方式若為一般

23、變量名，則為單向傳值，若在變量前面增加“&“符號，則為雙向傳地址。例如有一個函數(shù)為 Void swap(&i, &j,k)則i，j為雙向傳地址參數(shù)，k為單向傳值參數(shù)。（3）函數(shù)的說明部分與函數(shù)的實(shí)現(xiàn)部分分離在C中，用函數(shù)來描述算法時，為使之與面象對象的程序設(shè)計相匹配，一般將函數(shù)的說明部分與函數(shù)的實(shí)現(xiàn)部分分離開來。 （4）輸入函數(shù)C中的輸入函數(shù)調(diào)用為: cin變量名。 （5）輸出函數(shù)C中的輸出函數(shù)調(diào)用為:cout變量名。(6) C+中的類C+對于面向?qū)ο蟪绦蛟O(shè)計的支持,核心部分就是類的定義。類的定義體現(xiàn)了抽象數(shù)據(jù)類型的思想，可以支持說明與實(shí)現(xiàn)的分離，將抽象數(shù)據(jù)類型的實(shí)現(xiàn)封裝在類的內(nèi)部，使之達(dá)到信

24、息隱蔽的目的。1.3 算法分析與度量我們可以從一個算法的時間復(fù)雜度與空間復(fù)雜度來評價算法的優(yōu)劣。當(dāng)我們將一個算法轉(zhuǎn)換成程序并在計算機(jī)上執(zhí)行時，其運(yùn)行所需要的時間取決于下列因素：硬件的速度。例如使用486機(jī)還是使用586機(jī)。書寫程序的語言。實(shí)現(xiàn)語言的級別越高，其執(zhí)行效率就越低。編譯程序所生成目標(biāo)代碼的質(zhì)量。對于代碼優(yōu)化較好的編譯程序其所生成的程序質(zhì)量較高。問題的規(guī)模。例如，求100以內(nèi)的素數(shù)與求1000以內(nèi)的素數(shù)其執(zhí)行時間必然是不同的。顯然，在各種因素都不能確定的情況下，很難比較出算法的執(zhí)行時間。也就是說，使用執(zhí)行算法的絕對時間來衡量算法的效率是不合適的。為此，可以將上述各種與計算機(jī)相關(guān)的軟、硬

25、件因素都確定下來，這樣一個特定算法的運(yùn)行工作量的大小就只依賴于問題的規(guī)模（通常用正整數(shù)n表示），或者說它是問題規(guī)模的函數(shù)。時間復(fù)雜度一個程序的時間復(fù)雜度（Time complexity）是指程序運(yùn)行從開始到結(jié)束所需要的時間。一個算法是由控制結(jié)構(gòu)和原操作構(gòu)成的，其執(zhí)行時間取決于兩者的綜合效果。為了便于比較同一問題的不同的算法，通常的做法是：從算法中選取一種對于所研究的問題來說是基本運(yùn)算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)作為算法的時間度量。一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的某個函數(shù)T(n)。許多時候要精確地計算T(n)是困難的，我們引入漸進(jìn)時間復(fù)雜度在數(shù)量上估計一個算法的執(zhí)行時間，也

26、能夠達(dá)到分析算法的目的。定義（大記號）：如果存在兩個正常數(shù)c和n0，使得對所有的n，nn0，有：f(n) cg(n)則有：f(n) (g(n)例如，一個程序的實(shí)際執(zhí)行時間為T(n)2.7n3+3.8n2+5.3。則T(n)(n3)。使用大記號表示的算法的時間復(fù)雜度，稱為算法的漸進(jìn)時間復(fù)雜度（Asymptotic Complexity）。通常用(1)表示常數(shù)計算時間。常見的漸進(jìn)時間復(fù)雜度有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個常數(shù)，則時間復(fù)雜度為O(1),另外，在時間頻度不相同時，時間復(fù)雜度有可能相同，如T(n)=n2+3

27、n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復(fù)雜度相同，都為O(n2)。例分析以下程序段的時間復(fù)雜度for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+)x+; 常見函數(shù)的時間復(fù)雜度按數(shù)量遞增排列及增長率。 常數(shù)階O(1) 對數(shù)階O(log2n) 線性階O(n) 線性對數(shù)階O(nlog2n) 平方階O(n2) 立方階O(n3) k次方階O(nk) 指數(shù)階O(2n)空間復(fù)雜度與時間復(fù)雜度類似，空間復(fù)雜度是指一程序運(yùn)行從開始到結(jié)束所需的存儲量。即算法在計算機(jī)內(nèi)執(zhí)行時所需存儲空間的度量。記作: S(n)=O(f(n) 我們一般所討論的是除正常占用內(nèi)存開

28、銷外的輔助存儲單元規(guī)模。討論方法與時間復(fù)雜度類似，不再贅述。本章小結(jié) 數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)等基本概念 數(shù)據(jù)結(jié)構(gòu)的三個方面的內(nèi)容 抽象數(shù)據(jù)類型的概念 線性和非線性結(jié)構(gòu)的邏輯特征 數(shù)據(jù)存儲的四種基本方法 算法、算法的時間復(fù)雜度第一章 概論 自測題 一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的 以及它們之間的 和運(yùn)算等的學(xué)科。2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 的有限集合，R是D上的 有限集合。3. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 、數(shù)據(jù)的 和數(shù)據(jù)的 這三個方面的內(nèi)容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 和 。5. 線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹形結(jié)構(gòu)中元素之間

29、存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。6 在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn) 前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 1個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn) 后續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有1個后續(xù)結(jié)點(diǎn)。7. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 個前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以 。8. 在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 。9數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是 。10. 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是 。11. 一個算法的效率可分為 效率和 效率。二、單項(xiàng)選擇題（ ）1. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對多關(guān)系 B）多對多關(guān)

30、系 C）多對一關(guān)系 D）一對一關(guān)系（ ）2. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲（ ）3. 算法分析的目的是：A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進(jìn) D) 分析算法的易懂性和文檔性（ ）4. 算法分析的兩個主要方面是：A) 空間復(fù)雜性和時間復(fù)雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（ ）5. 計算機(jī)算法指的是：A) 計算方法 B) 排序方法 C) 解決問題的有限運(yùn)算序列 D) 調(diào)度方法（ ）6. 計算機(jī)算法必須具備輸入、輸出和 等5個特性。

31、A) 可行性、可移植性和可擴(kuò)充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性三、簡答題1.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎？ 2. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。四、分析下面各程序段的時間復(fù)雜度2. s=0; for (i=0; in; i+)for(j=0; jn; j+) s+=Bij;sum=s; 1. for (i=0; in; i+)for (j=0; jm; j+)Aij=0; 3. x=0;for(i=1; in; i+) for (j=1; j=n-i; j+)x+; 4. i=1; while(i=n) i=i*3; 五、

32、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=（D,R），試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系R，哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？ 1. D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 2。D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 3。D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)第2章

33、線性表 線性表是我們要介紹的數(shù)據(jù)結(jié)構(gòu)中的第一種數(shù)據(jù)結(jié)構(gòu)，也是比較簡單的數(shù)據(jù)結(jié)構(gòu)，對于線性表的操作是動態(tài)的還是靜態(tài)的在后續(xù)的章節(jié)里要用到，是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。首先看一下什么是線性表。21 線性表的定義及其運(yùn)算 線性表的定義1 線性表的定義線性表（linear_list）是具有相同屬性的數(shù)據(jù)元素的一個有限序列。用二元組表示為： linear_list=(A,R)其中 A=ai 1in,n0,aielemtype R= 1in-1A表示屬性相同的數(shù)據(jù)元素，R代表關(guān)系，ai,ai+1表示有序，也叫有序偶。有了這種關(guān)系就表示線性表的數(shù)據(jù)元素之間是一個有限序列。Elemtype表示一種具體的已知數(shù)據(jù)類型

34、。為線性表中的數(shù)據(jù)元素所有可能的數(shù)據(jù)類型的一個抽象名稱。例如：L1=（A，R） =5，38，12，49，63，200，470=某校1971至1977年擁有的計算機(jī)的數(shù)量L1=(5，38，12，49，63，200，470) L2=（A，R）=“王一”，“王蘭”，“王心”，“王小白”，“王小紅”R父子關(guān)系 新生報到入學(xué)，一個班級有個學(xué)生，這個學(xué)生只能形成一個集合，如果加上一個關(guān)系，把學(xué)生按學(xué)號來編，這個集合由于有了學(xué)號這樣的一個關(guān)系就成為了一個線性表。所以線性表的關(guān)鍵在于關(guān)系。 2 線性結(jié)構(gòu)的基本特性：一對一的關(guān)系。 必有唯一一個元素?zé)o前驅(qū)，必有唯一一個元素元后繼，除此之外任何元素都有唯一的前驅(qū)和

35、唯一的后繼。 有了這種一對一的關(guān)系，就稱為線性結(jié)構(gòu)或線性表。由以上知道了什么樣的關(guān)系是線性表，但是我們考慮的不是判斷什么樣的關(guān)系是線性表，什么樣的關(guān)系不是線性表，而是前提已知一個線性表，那么怎樣在計算機(jī)里如何存儲，如何處理是要研究的問題。下面要介紹幾個概念。1。如果已經(jīng)是一個線性表，用園括可如下來表示。線性表的一般形式：L=（a1,ai-1,ai,an） n是線性表的元素的個數(shù)即線性表的長度,n=0是空表。這個圖表示在邏輯關(guān)系上每個元素的前驅(qū)和后繼的關(guān)系。以上是線性表的邏輯結(jié)構(gòu)。2。物理存儲線性表的物理存儲也就是物理結(jié)構(gòu)的表示，線性表已經(jīng)存在，對這個線性表進(jìn)行如下的一些操作，用什么方法，在計算

36、機(jī)里如何存儲，它的操作怎樣來實(shí)現(xiàn)。例如，有一種結(jié)構(gòu)整型可以進(jìn)行四則、求余、求模、運(yùn)算等。這些運(yùn)算就是整型可以實(shí)現(xiàn)的操作。對于線性表也是一種數(shù)據(jù)類型，這種結(jié)構(gòu)也可以實(shí)現(xiàn)很多操作。線性表作為抽象數(shù)據(jù)類型可能實(shí)現(xiàn)的基本操作： 線性表的運(yùn)算 常見線性表的運(yùn)算有：1置空表 SETNULL（&L）將線性表L置成空表2 求長度 LENGTH（L） 求給定線性表L的長度3 取元素 GET（L，i） 若1ilength(L),則取第i個位置上的元素，否則取得的 元素為NULL。 4求直接前趨 PRI0R（L，X）求線性表L中元素值為X的直接前趨，若X為第一個元素，前驅(qū)為NULL5求直接后繼 NEXT（L，X）

37、求線性表L中元素值為X直接后繼，若X為最后一個元素，后繼為NULL。6定位函數(shù) LOCATE（L，X） 在線性表L中查找值為X的元素位置，若有多個值為X，則以第一個為準(zhǔn)，若沒有，位置為0。7插入 INSERT（&L，X，i） 在線性表L中第i個位置上插入值為X的元素。8刪除 DELETE（&L，i） 刪除線性表L中第i個位置上的元素。注意：初始條件、返回值、操作功能是編寫一個函數(shù)的依據(jù)。 引用類型&：給變量起別名。x=y 程序?qū)進(jìn)行的任何操作，同時對y也進(jìn)行操作，反之亦然。因?yàn)閤,y指向同一存儲單元即兩個變量使用同一個存儲單元?？梢杂闷渲械娜魏我粋€名字對存儲單元進(jìn)行操作。形參中用&將的值帶回

38、到主要函數(shù)。例：假設(shè)線性表L=(23,56,89,76,18),i=3,x=56,y=88,則對L的一組操作及結(jié)果如下：Length(L); /所得結(jié)果為5Get(L,i) /所得結(jié)果為89Prior(L,x) /所得結(jié)果為23Next(L,x) /所得結(jié)果為89Locate(L,x) /所得結(jié)果為2Insert(&L,y,i) /所得結(jié)果為(23,56,88,89,76,18)Delete(&L,i+1) /所得結(jié)果為(23,56,88,76,18)以上了解了線性表、線性表的關(guān)系以及基本操作。這些基本操作的實(shí)現(xiàn)是要有存儲作為前提的，線性表在里存儲為什么樣子，是動態(tài)的還是靜態(tài)的，只有確定了這些

39、才能實(shí)現(xiàn)操作，也就是說存儲是實(shí)現(xiàn)操作的依據(jù)。下面介紹兩種存儲方法。2.2線性表的順序存儲結(jié)構(gòu)一、順序表結(jié)構(gòu)順序存儲的特點(diǎn)：邏輯關(guān)系相鄰（ai和ai+1是相鄰的）物理位置也相鄰存完ai一定要存ai+1線性表的順序存儲指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。這種存儲結(jié)構(gòu)的線性表也稱為順序表。它的特點(diǎn)為表中相鄰的元素賦以相鄰的存儲位置。換句話說，以元素在計算機(jī)內(nèi)“物理位置相鄰”來表示線性表數(shù)據(jù)元素之間的邏輯關(guān)系。假設(shè)線性表中元素為（a1，a2，.,an），設(shè)第一個元素a1的內(nèi)存地址為LOC(a1)（基地址），而每個元素在計算機(jī)內(nèi)占d個存貯單元,則第i個元素ai的地址為 LOC(ai)

40、=LOC(a1)+(i-1)d (其中1in)由于高級語言中的數(shù)組類型具有如下的特點(diǎn)：數(shù)組中的元素間的地址是連續(xù)的，數(shù)組中所有元素的數(shù)據(jù)類型是相同的。而這與線性表的存儲空間結(jié)構(gòu)是類似的。因此，通常都用數(shù)組來描述數(shù)據(jù)結(jié)構(gòu)中的順序存儲結(jié)構(gòu)。 存儲的時候即要存儲數(shù)據(jù)元素又要存儲數(shù)據(jù)關(guān)系，那么數(shù)組把數(shù)據(jù)元素存儲在list,也就存儲了關(guān)系。用數(shù)組存放以后，線性表的長度是數(shù)組空間中變化的，用len來表示線性表的長度，并事先預(yù)計分配一個足夠大的空間maxsize，用一個宏來定義.const int maxsize=maxlen； /maxlen表示線性表允許的最大長度struct sequenlist el

41、emtype amaxsize; /表示線性表（a1，a2，.,an） int len; /len表示當(dāng)前線性表的實(shí)際長度 （可以變化） ；如何來使用？使用方法：首先定義sequenlist L; int n=7;結(jié)構(gòu)體有兩個域：L.a1=a1; L.a2=a2; . L.len;注：結(jié)構(gòu)體類型定義的是一種樣子，沒有實(shí)際的內(nèi)容。結(jié)構(gòu)體變量是系統(tǒng)實(shí)際分配一個空間。變量定義之后，才用實(shí)際的空間可以使用。才可以對其兩個域進(jìn)行訪問、進(jìn)行操作。二、順序表操作的實(shí)現(xiàn)1求順序表的長度length(L)int length(sequenlist L) return L.len;2置空表setnull(&L)

42、void setnull(sequenlist &L) L.len=0;3.遍歷線性表：traverlist(&L) 依次訪問（輸出）表中的元素，且只訪問一次。void traverllist(&L)for(i=1; i=L.len;i+) coutL.ai ;coutendl;4刪除運(yùn)算Delete(&L,i)void Delete(sequenlist &L,int i) int j; if(iL.len) cout” position is not correct!”endl; else for(j=i+1;j=maxsize-1) cout”overflow”endl;else if

43、(iL.len+1) cout”position is not correct!”=i;j-)L.aj+1=L.aj; /元素后移L.ai=x; /插入元素L.len+; /表長度增加1注意邏輯關(guān)系的變化 5 定位算法（查找）Locate(L,x)int Locate(sequenlist L, elemtype x) int j=1; while(j=L.len)&(L.aj!=x) j+; if(j=L.len) return j; else return 0; 6 取元素Get(L,i) elemtype Get(sequenlist L,int i) if(iL.len) return

44、 NULL; else return L.ai; . 線性表的鏈?zhǔn)酱尜A結(jié)構(gòu)靜態(tài)存儲的特點(diǎn)是用數(shù)組的方法來處理，事先定義一個足夠大的空間，插入和刪除的操作需要不斷地移動。效率比較低。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)是用一組地址任意的存儲單元（可以是連續(xù)的，也可以是不連續(xù)的）存儲線性表的數(shù)據(jù)元素。因此，為了表示每個數(shù)據(jù)元素與其直接后繼之間的邏輯關(guān)系的有序性，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即存儲位置）。這兩部分信息組成數(shù)據(jù)元素的存儲映象，稱為結(jié)點(diǎn)。數(shù)據(jù)元素 + 指針（指示后繼元素存儲位置） =結(jié)點(diǎn) 以“結(jié)點(diǎn)的序列”表示線性表-鏈表。 就是將數(shù)據(jù)元素存放在結(jié)點(diǎn)中，按照前驅(qū)和后繼的關(guān)系用鏈子將其串起來。在定義的鏈表中，若只含有一個指針域來存放下一個元素地址，稱這樣的鏈表為單鏈表或線性鏈表。線性鏈表中的結(jié)點(diǎn)結(jié)構(gòu)可描述為:其中data 域用來存放結(jié)點(diǎn)本身信息，next域用來存放下一個元素地址。單鏈表可用+描述為:struct link elemtype