1、數(shù)據(jù)結(jié)構(gòu)（C+版）第1章 緒論第2章 線性表第3章 排序第4章 串第5章 棧與隊(duì)列第6章 數(shù)組和廣義表第7章 樹和二叉樹第8章 查找第9章 圖第10章 綜合應(yīng)用設(shè)計(jì)第1章 緒論軟件設(shè)計(jì)是計(jì)算機(jī)學(xué)科各個(gè)領(lǐng)域的核心。軟件設(shè)計(jì)時(shí)要考慮的首要問題是數(shù)據(jù)的表示、組織和處理方法。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和算法設(shè)計(jì)是軟件系統(tǒng)設(shè)計(jì)的核心?！皵?shù)據(jù)結(jié)構(gòu)十算法=程序”。1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念1.2 算法與算法設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念1.1.1 抽象數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)1.1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)1.1.3 數(shù)據(jù)的存儲結(jié)構(gòu)1.1.4 數(shù)據(jù)的操作數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞1.1.1 抽象數(shù)據(jù)類型與數(shù)據(jù)

2、結(jié)構(gòu)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)描述客觀事物的數(shù)字、字符以及所有能輸入到計(jì)算機(jī)中并能為計(jì)算機(jī)接受的各種符號集合統(tǒng)稱為數(shù)據(jù)（data）。數(shù)據(jù)是計(jì)算機(jī)程序的處理對象。表示一個(gè)事物的一組數(shù)據(jù)稱作一個(gè)數(shù)據(jù)元素（data element），數(shù)據(jù)元素是數(shù)據(jù)的基本單位；構(gòu)成數(shù)據(jù)元素的數(shù)據(jù)稱作該數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)（data item），數(shù)據(jù)項(xiàng)是數(shù)據(jù)元素的不可分割的最小單位。數(shù)據(jù)類型類型是一組值的集合。數(shù)據(jù)類型（data type）是指一個(gè)類型和定義在這個(gè)類型上的操作集合。數(shù)據(jù)類型定義了數(shù)據(jù)元素的性質(zhì)、取值范圍以及對數(shù)據(jù)元素所能進(jìn)行的各種操作。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞表1-1 學(xué)生信息表 class Student c

3、har number8; char name20; char boy4; int age;學(xué)號姓名性別年齡20020001王紅男1820020002張明男1920020003吳寧女18數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（Abstract Data Type，縮寫為ADT）是指一個(gè)邏輯概念上的類型和這個(gè)類型上的操作集合。沒有定義具體數(shù)據(jù)類型的數(shù)據(jù)元素稱作抽象數(shù)據(jù)元素。數(shù)據(jù)結(jié)構(gòu)對一個(gè)數(shù)據(jù)元素集合來說，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱為數(shù)據(jù)結(jié)構(gòu)（data structure）。因此，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞1.1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)

4、線性結(jié)構(gòu)：數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素。樹結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素，可有零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。圖結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素可有零個(gè)或若干個(gè)前驅(qū)數(shù)據(jù)元素，零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。圖1-1 三種基本的數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞1.1.3 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)元素在計(jì)算機(jī)中的存儲表示方式稱為數(shù)據(jù)的存儲結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)是把數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存中，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上也相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在數(shù)據(jù)元素的存儲位置關(guān)系上。鏈?zhǔn)酱鎯Y(jié)構(gòu)指針是指向物理存儲單元地址的變量。由數(shù)據(jù)元素域和指針域組成的一個(gè)整體稱為

5、一個(gè)結(jié)點(diǎn)（node）。鏈?zhǔn)酱鎯Y(jié)構(gòu)是使用指針把相互直接關(guān)聯(lián)的結(jié)點(diǎn)（即直接前驅(qū)結(jié)點(diǎn)或直接后繼結(jié)點(diǎn)）鏈接起來，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上（即內(nèi)存存儲位置上）不一定相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在結(jié)點(diǎn)的鏈接關(guān)系上。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞圖1-2 兩種存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞1.1.4 數(shù)據(jù)的操作對一種數(shù)據(jù)類型的數(shù)據(jù)元素進(jìn)行的某種處理稱作數(shù)據(jù)的操作。訪問數(shù)據(jù)元素。統(tǒng)計(jì)數(shù)據(jù)元素個(gè)數(shù)。更新數(shù)據(jù)元素值。插入數(shù)據(jù)元素，在數(shù)據(jù)結(jié)構(gòu)中增加新的結(jié)點(diǎn)。刪除數(shù)據(jù)元素，將指定數(shù)據(jù)元素從數(shù)據(jù)結(jié)構(gòu)中刪除。查找在數(shù)據(jù)結(jié)構(gòu)中查找滿足一定條件的數(shù)據(jù)元素。插入、刪除、更新操作都包括一個(gè)查找操作，以確定需要插入、刪除、

6、更新數(shù)據(jù)元素的確切位置。排序在線性結(jié)構(gòu)中數(shù)據(jù)元素?cái)?shù)目不變的情況下，將數(shù)據(jù)元素按某種指定的順序重新排列。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞1.2 算法與算法設(shè)計(jì) 1.2.1 算法1.2.2 算法設(shè)計(jì)1.2.3 算法分析數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞1.2.1 算法算法定義有窮性算法必須在執(zhí)行有窮步之后結(jié)束。確定性算法的每一個(gè)步驟必須是確切地定義的。輸入算法有零個(gè)或多個(gè)輸入。輸出算法有一個(gè)或多個(gè)輸出，即與輸入有某種特定關(guān)系的量?？尚行运惴ㄖ杏写龍?zhí)行的操作和操作必須是相當(dāng)基本的，即是說，它們原則上都是能夠精確地進(jìn)行的，而且用筆和紙做有窮次就可以完成。算法的描述算法可用文字、高級程序設(shè)計(jì)語言或類同于高級程序設(shè)計(jì)語言的

7、偽碼描述。此時(shí)算法是由語義明確的操作步驟組成的有限序列，它精確地指出怎樣從給定的輸入信息得到要求的輸出信息。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例1-3 學(xué)生信息表的順序查找算法圖1-5 學(xué)生信息表的順序查找過程數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞算法與數(shù)據(jù)結(jié)構(gòu) 算法是建立在數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)上的。對于同樣的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，根據(jù)問題的不同要求，采用不同的算法。同樣的數(shù)據(jù)結(jié)構(gòu)，不同的存儲結(jié)構(gòu)，則采用的算法必然不同。例如，存儲結(jié)構(gòu)不同的線性表其排序算法必然不同。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例1-4 字典的分塊查找算法。圖1-6 字典與其索引表示意圖數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞算法與程序算法用抽象的語言描述解決特定問題的

8、每一步的操作。程序是計(jì)算機(jī)能理解和執(zhí)行的指令序列。一個(gè)程序?qū)崿F(xiàn)一個(gè)算法。算法和程序的區(qū)別是算法的執(zhí)行是有窮的，而程序的執(zhí)行可以是無限的。例如操作系統(tǒng)程序，只要系統(tǒng)不受破壞，操作系統(tǒng)的運(yùn)行將不會停止。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞1.2.2 算法設(shè)計(jì)算法設(shè)計(jì)目標(biāo)正確性可讀性健壯性高時(shí)間效率高空間效率算法設(shè)計(jì)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例1-5 求最大值算法的設(shè)計(jì)與調(diào)用從兩個(gè)整數(shù)類型數(shù)據(jù)中得到較大數(shù)值的算法設(shè)計(jì)如下：int Max(int a,int b) return (a=b)?a:b;主函數(shù)中，調(diào)用Max(Max(a,b),c)將從三個(gè)整數(shù)中返回最大值，例如，coutmax=Max(Max(1,2

9、),3)endl;數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例1-6 求兩個(gè)整數(shù)的最大公因數(shù)的算法實(shí)現(xiàn)。 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞1.2.3 算法分析算法的時(shí)間復(fù)雜度算法的執(zhí)行時(shí)間等于所有語句執(zhí)行時(shí)間的總和，是算法所處理的數(shù)據(jù)個(gè)數(shù)n的函數(shù)，表示為O(f(n)，O(f(n)稱為該算法的時(shí)間復(fù)雜度。O(1)表示時(shí)間是一個(gè)常數(shù)，不依賴于n；O(n)表示時(shí)間與n成正比，是線性關(guān)系，O(n2)、O(n3)、O(2n)分別稱為平方階、立方階和指數(shù)階；O(log2n)為對數(shù)階。算法的空間復(fù)雜度 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例1-7 算法時(shí)間復(fù)雜度的分析。 一個(gè)簡單語句的時(shí)間復(fù)雜度為O(1)。int count=0; 時(shí)間復(fù)雜度為

10、O(n)的循環(huán)語句。 int n=8,count=0,i;for(i=1;i=n;i+) count+;時(shí)間復(fù)雜度為O(log2n)的循環(huán)語句。 int n=8,count=0,i;for(i=1;i=n;i*=2) count+;時(shí)間復(fù)雜度為O(n2)的二重循環(huán)。 count=0;for(i=1;i=n;i+) for(j=1;j=n;j+) count+;數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞時(shí)間復(fù)雜度為O(nlog2n)的二重循環(huán)。count=0;for(i=1;i=n;i*=2) for(j=1;j=n;j+) count+; 時(shí)間復(fù)雜度為O(n)的二重循環(huán)。count=0;for(i=1;i=n;i*=2) for(j=1;j=i;j+) count+;數(shù)