1、第一章 概 論數(shù)據(jù)就是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。數(shù)據(jù)結(jié)構(gòu)的定義：·邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨(dú)立于計(jì)算機(jī)。·線性結(jié)構(gòu)：一對(duì)一關(guān)系。·線性結(jié)構(gòu)：多對(duì)多關(guān)系。·存儲(chǔ)結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。·順序存儲(chǔ)結(jié)構(gòu)：如數(shù)組。·鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：如鏈表。·稠密索引：每個(gè)結(jié)點(diǎn)都有索引項(xiàng)。·稀疏索引：每組結(jié)點(diǎn)都有索引項(xiàng)。·散列存儲(chǔ)結(jié)構(gòu)：如散列表。·對(duì)數(shù)據(jù)的操作：定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一

2、個(gè)運(yùn)算集合。·常用的有：檢索、插入、刪除、更新、排序。·數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。·原子類型：由語(yǔ)言提供。·結(jié)構(gòu)類型：由用戶借助于描述機(jī)制定義，是導(dǎo)出類型。抽象數(shù)據(jù)類型ADT：·是抽象數(shù)據(jù)的組織和與之的操作。相當(dāng)于在概念層上描述問題。·優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)好的算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。算法是一個(gè)良定義的計(jì)算過程，以一個(gè)或多個(gè)值輸入，并以一個(gè)或多個(gè)值輸出。評(píng)價(jià)算法的好壞的因素：·算法是正確的；·執(zhí)行算法的

3、時(shí)間；·執(zhí)行算法的存儲(chǔ)空間(主要是輔助存儲(chǔ)空間)；·算法易于理解、編碼、調(diào)試。時(shí)間復(fù)雜度：是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)。漸近時(shí)間復(fù)雜度：是指當(dāng)問題規(guī)模趨向無窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。評(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度。算法中語(yǔ)句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、k次方階O(nk)、指數(shù)階O(2n)。空間復(fù)雜度：是某個(gè)算法的空間耗費(fèi)，它是該算

4、法所求解問題規(guī)模n的函數(shù)。算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。 第二章 線性表線性表是由n0個(gè)數(shù)據(jù)元素組成的有限序列。n=0是空表;非空表，只能有一個(gè)開始結(jié)點(diǎn)，有且只能有一個(gè)終端結(jié)點(diǎn)。線性表上定義的基本運(yùn)算：·構(gòu)造空表：Initlist(L)·求表長(zhǎng)：Listlength(L)·取結(jié)點(diǎn)：GetNode(L，i)·查找：LocateNode(L，x)·插入：InsertList(L，x，i)·刪除：Delete(L，i)順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲(chǔ)單元中。在存儲(chǔ)單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各

5、結(jié)點(diǎn)相鄰關(guān)系是一致的。地址計(jì)算：LOCa(i)=LOCa(1)+(i-1)*d;(首地址為1)在順序表中實(shí)現(xiàn)的基本運(yùn)算：·插入：平均移動(dòng)結(jié)點(diǎn)次數(shù)為n/2;平均時(shí)間復(fù)雜度均為O(n)。·刪除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為(n-1)/2;平均時(shí)間復(fù)雜度均為O(n)。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同，為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還存儲(chǔ)了其后繼結(jié)點(diǎn)的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。 一個(gè)單鏈表由頭指針的名字來命名。 單鏈表運(yùn)算：·建立單鏈表·頭插法：s->next=head;head=s;

6、生成的順序與輸入順序相反。平均時(shí)間復(fù)雜度均為O(n)。·尾插法：head=rear=null;if(head=null) head=s;else r->next=s;r=s; 平均時(shí)間復(fù)雜度均為O(n)·加頭結(jié)點(diǎn)的算法：對(duì)開始結(jié)點(diǎn)的操作無需特殊處理，統(tǒng)一了空表和非空表。·查找·按序號(hào)：與查找位置有關(guān)，平均時(shí)間復(fù)雜度均為O(n)。·按值：與輸入實(shí)例有關(guān)，平均時(shí)間復(fù)雜度均為O(n)。·插入運(yùn)算：p=GetNode(L，i-1);s->next=p->next;p->next=s;平均時(shí)間復(fù)雜度均為O(n)·

7、;刪除運(yùn)算：p=GetNode(L，i-1);r=p->next;p->next=r->next;free(r);平均時(shí)間復(fù)雜度均為O(n)單循環(huán)鏈表是一種首尾相接的單鏈表，終端結(jié)點(diǎn)的指針域指向開始結(jié)點(diǎn)或頭結(jié)點(diǎn)。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點(diǎn)是查找頭指針和尾指針的時(shí)間都是O(1)，不用遍歷整個(gè)鏈表。雙鏈表就是雙向鏈表，就是在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior，形成兩條不同方向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙(向)循環(huán)鏈表。雙鏈表上的插入和刪除時(shí)間復(fù)雜度均為O

8、(1)。 順序表和鏈表的比較：·基于空間：·順序表的存儲(chǔ)空間是靜態(tài)分配，存儲(chǔ)密度為1；適于線性表事先確定其大小時(shí)采用。·鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配，存儲(chǔ)密度<1；適于線性表長(zhǎng)度變化大時(shí)采用。·基于時(shí)間：·順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時(shí)，宜采用。·以插入和刪除操作為主的線性表宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。·若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。第三章 棧和隊(duì)列棧(Stack)是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無元素時(shí)為空棧。棧

9、的修改是 按后進(jìn)先出的原則進(jìn)行的，我們又稱棧為L(zhǎng)IFO表(Last In First Out)。通常棧有順序棧和鏈棧兩種存儲(chǔ)結(jié)構(gòu)。棧的基本運(yùn)算有六種： ·構(gòu)造空棧：InitStack(S)·判棧空：StackEmpty(S)·判棧滿：StackFull(S)·進(jìn)棧：Push(S，x)·退棧：Pop(S)·取棧頂元素：StackTop(S) 在順序棧中有“上溢”和“下溢”的現(xiàn)象。 ·“上溢”是棧頂指針指出棧的外面是出錯(cuò)狀態(tài)。·“下溢”可以表示棧為空棧，因此用來作為控制轉(zhuǎn)移的條件。順序棧中的基本操作有六種：&

10、#183;構(gòu)造空棧·判棧空·判棧滿·進(jìn)棧·退棧·取棧頂元素鏈棧則沒有上溢的限制，因此進(jìn)棧不要判棧滿。鏈棧不需要在頭部附加頭結(jié)點(diǎn)，只要有鏈表的頭指針就可以了。鏈棧中的基本操作有五種：·構(gòu)造空棧·判棧空·進(jìn)棧·退棧·取棧頂元素 隊(duì)列(Queue)是一種運(yùn)算受限的線性表，插入在表的一端進(jìn)行，而刪除在表的另一端進(jìn)行，允許刪除的一端稱為隊(duì)頭(front)，允許插入的一端 稱為隊(duì)尾(rear) ，隊(duì)列的操作原則是先進(jìn)先出的，又稱作FIFO表(First In First Out) .隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱?/p>

11、儲(chǔ)兩種存儲(chǔ)結(jié)構(gòu)。隊(duì)列的基本運(yùn)算有六種：·置空隊(duì)：InitQueue(Q)·判隊(duì)空：QueueEmpty(Q)·判隊(duì)滿：QueueFull(Q)·入隊(duì)：EnQueue(Q，x)·出隊(duì)：DeQueue(Q)·取隊(duì)頭元素：QueueFront(Q)順序隊(duì)列的“假上溢”現(xiàn)象：由于頭尾指針不斷前移，超出向量空間。這時(shí)整個(gè)向量空間及隊(duì)列是空的卻產(chǎn)生了“上溢”現(xiàn)象。為了克服“假上溢”現(xiàn)象引入循環(huán)向量的概念，是把向量空間形成一個(gè)頭尾相接的環(huán)形，這時(shí)隊(duì)列稱循環(huán)隊(duì)列。判定循環(huán)隊(duì)列是空還是滿，方法有三種： ·一種是另設(shè)一個(gè)布爾變量來判斷

12、；·第二種是少用一個(gè)元素空間，入隊(duì)時(shí)先測(cè)試(rear+1)%m = front)? 滿：空；·第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列，一個(gè)鏈隊(duì)列就是一個(gè)操作受限的單鏈表。為了便于在表尾進(jìn)行插入(入隊(duì))的操作，在表尾增加一個(gè)尾指針，一個(gè)鏈隊(duì) 列就由一個(gè)頭指針和一個(gè)尾指針唯一地確定。鏈隊(duì)列不存在隊(duì)滿和上溢的問題。在鏈隊(duì)列的出隊(duì)算法中，要注意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，出隊(duì)后要同進(jìn)修改頭尾指 針并使隊(duì)列變空。 第四章 串串是零個(gè)或多個(gè)字符組成的有限序列。·空串：是指長(zhǎng)度為零的串，也就是串中不包含任何字符(結(jié)點(diǎn))。·空白串：指串中

13、包含一個(gè)或多個(gè)空格字符的串。·在一個(gè)串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。·子串在主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置。·空串是任意串的子串，任意串是自身的子串。串分為兩種： ·串常量在程序中只能引用不能改變；·串變量的值可以改變。串的基本運(yùn)算有： ·求串長(zhǎng)strlen(char*s)·串復(fù)制strcpy(char*to，char*from)·串聯(lián)接strcat(char*to，char*from)·串比較charcmp(char*s1，char*s2)·

14、字符定位strchr(char*s，charc)。串是特殊的線性表(結(jié)點(diǎn)是字符)，所以串的存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串。 順序串又可按存儲(chǔ)分配的不同分為： ·靜態(tài)存儲(chǔ)分配：直接用定長(zhǎng)的字符數(shù)組來定義。優(yōu)點(diǎn)是涉及串長(zhǎng)的操作速度快，但不適合插入、鏈接操作。·動(dòng)態(tài)存儲(chǔ)分配：是在定義串時(shí)不分配存儲(chǔ)空間，需要使用時(shí)按所需串的長(zhǎng)度分配存儲(chǔ)單元。串的鏈?zhǔn)酱鎯?chǔ)就是用單鏈表的方式存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。為了解決“存儲(chǔ)密度”低的狀況，可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，即結(jié)點(diǎn)的大小。順序串上子串定位的運(yùn)算

15、：又稱串的“模式匹配”或“串匹配”，是在主串中查找出子串出現(xiàn)的位置。在串匹配中，將主串稱為目標(biāo)(串)，子串稱為模 式(串)。這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時(shí)間復(fù)雜度是 O(n-m+1)m)，假如m與n同階的話則它是O(n2)。鏈串上的子串定位運(yùn)算位移是結(jié)點(diǎn)地址而不是整數(shù)第五章 多維數(shù)組和廣義表數(shù)組一般用順序存儲(chǔ)的方式表示。存儲(chǔ)的方式有： ·行優(yōu)先順序，也就是把數(shù)組逐行依次排列。PASCAL、C·列優(yōu)先順序，就是把數(shù)組逐列依次排列。FORTRAN地址的計(jì)算方法： ·按行優(yōu)先順序排列

16、的數(shù)組：LOCa(ij)=LOCa(11)+(i-1)*n+(j-1)*d.·按列優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(11)+(j-1)*n+(i-1)*d. 矩陣的壓縮存儲(chǔ)：為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間;對(duì)零元素不分配空間。特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。稀疏矩陣的概念：一個(gè)矩陣中若其非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，則該矩陣稱為稀疏矩陣。特殊矩陣的類型： ·對(duì)稱矩陣：滿足a(ij)=a(ji)。元素總數(shù)n(n+1)/2.I=max(i，j)，J=min(i，j)，LOCa(ij)=LOC(sa0)+(I*(I+

17、1)/2+J)*d.·三角矩陣： ·上三角陣：k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa0)+k*d.·下三角陣：k=i*(i+1)/2+j，LOCa(ij)=LOC(sa0)+k*d.·對(duì)角矩陣：k=2i+j，LOCa(ij)=LOC(sa0)+k*d.稀疏矩陣的壓縮存儲(chǔ)方式用三元組表把非零元素的值和它所在的行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起，用這些結(jié)點(diǎn)組成的一個(gè)線性表來表示。但這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。 廣義表是n(n0)個(gè)元素的有限序列，

18、其中的元素是原子或者是一個(gè)廣義表。廣義表表頭和表尾的概念： ·若廣義表LS非空(n1)，則這個(gè)廣義表的第一個(gè)元素就是表頭。·其余的元素組成的表稱為L(zhǎng)S的表尾，所以表尾必是一個(gè)子表。廣義表有兩種表示法，一種是括號(hào)表示法，一種是圖形表示法。廣義表與樹(形結(jié)構(gòu))相對(duì)應(yīng)，這個(gè)廣義表就是純表。如果一個(gè)廣義表的結(jié)點(diǎn)又可以被其他結(jié)點(diǎn)所共享，則這個(gè)表稱為再入表。允許遞歸的表稱為遞歸表。線性表純表(樹)再入表遞歸表。可見，廣義表是對(duì)線性表和樹的推廣。廣義表有兩個(gè)特殊的基本運(yùn)算： ·取表頭head(LS)：取表中的第一個(gè)數(shù)據(jù)元素，不能對(duì)空表操作。·取表尾tail(LS);取

19、除表頭外，其余數(shù)據(jù)元素構(gòu)成的子表，不能對(duì)空表操作。第六章 樹樹是n個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿足：只有一個(gè)稱為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)形成m個(gè)不相交的子集，并稱根的子樹。根是開始結(jié)點(diǎn)；結(jié)點(diǎn)的子樹數(shù)稱度；度為0的結(jié)點(diǎn)稱葉子(終端結(jié)點(diǎn))；度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn)(非終端結(jié)點(diǎn))；除根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn)；有序樹是子樹有左，右之分的樹；無序樹是子樹沒有左，右之分的樹；森林是m個(gè)互不相交的樹的集合；樹的四種不同表示方法：·樹形表示法；·嵌套集合表示法；·凹入表示法；·廣義表表示法。二叉樹的定義：是n0個(gè)結(jié)點(diǎn)的有限集，它是空集(n=0)或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分

20、別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。二叉樹不是樹的特殊情形，與度數(shù)為2的有序樹不同。二叉樹的4個(gè)重要性質(zhì)： ·二叉樹上第i層上的結(jié)點(diǎn)數(shù)目最多為2(i-1)(i1)；·深度為k的二叉樹至多有(2k)-1個(gè)結(jié)點(diǎn)(k1)；·在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1；·具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int(log2n)+1。滿二叉樹是一棵深度為k，結(jié)點(diǎn)數(shù)為(2k)-1的二叉樹；完全二叉樹是滿二叉樹在最下層自右向左去處部分結(jié)點(diǎn)；二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。(存儲(chǔ)前先

21、將其畫成完全二叉樹)樹的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。BinTNode的結(jié)構(gòu)為lchild|data|rchild，把所有BinTNode類型的結(jié)點(diǎn)，加上一個(gè) 指向根結(jié)點(diǎn)的BinTree型頭指針就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個(gè)指針域，n+1個(gè)空指 針。根據(jù)訪問結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。時(shí)間復(fù)雜度為O(n)。利用二叉鏈表中的n+1個(gè)空指針域來存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查

22、找中序前趨和中序后繼變得簡(jiǎn)單有效，但對(duì)于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并沒有什么作用。樹和森林及二叉樹的轉(zhuǎn)換是唯一對(duì)應(yīng)的。轉(zhuǎn)換方法： ·樹變二叉樹：兄弟相連，保留長(zhǎng)子的連線。·二叉樹變樹：結(jié)點(diǎn)的右孩子與其雙親連。·森林變二叉樹：樹變二叉樹，各個(gè)樹的根相連。樹的存儲(chǔ)結(jié)構(gòu)：·有雙親鏈表表示法：結(jié)點(diǎn)data | parent，對(duì)于求指定結(jié)點(diǎn)的雙親或祖先十分方便，但不適于求指定結(jié)點(diǎn)的孩子及后代。·孩子鏈表表示法：為樹中每個(gè)結(jié)點(diǎn)data | next設(shè)置一個(gè)孩子鏈表firstchild，并將data | firstchild存放在一個(gè)向量中。·

23、;雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。·孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域。樹的前序遍歷與相對(duì)應(yīng)的二叉樹的前序遍歷一致;樹的后序遍歷與相對(duì)應(yīng)的二叉樹的中序遍歷一致。樹的帶權(quán)路徑長(zhǎng)度是樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。樹的帶權(quán)路徑長(zhǎng)度最小的二叉樹就稱為最優(yōu)二叉樹(即哈夫曼樹)。在葉子的權(quán)值相同的二叉樹中，完全二叉樹的路徑長(zhǎng)度最短。哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，共有2n-1個(gè)結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn)，這類樹又稱為嚴(yán)格二叉樹。變長(zhǎng)編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編

24、碼長(zhǎng)，但是變長(zhǎng)編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個(gè)碼無法在解碼時(shí)確定是哪一個(gè)，所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼(其實(shí)是非前綴碼)。哈夫曼樹的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構(gòu)造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼0，右路徑上寫代碼1，然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。第七章 圖圖的邏輯結(jié)構(gòu)特征就是其結(jié)點(diǎn)(頂點(diǎn))的前趨和后繼的個(gè)數(shù)都是沒有限制的，即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。圖GraphG=(V，E)，V是頂點(diǎn)的有窮非空

25、集合，E是頂點(diǎn)偶對(duì)的有窮集。有向圖Digraph：每條邊有方向；無向圖Undigraph：每條邊沒有方向；有向完全圖：具有n*(n-1)條邊的有向圖；無向完全圖：具有n*(n-1)/2條邊的無向圖；有根圖：有一個(gè)頂點(diǎn)有路徑到達(dá)其它頂點(diǎn)的有向圖；簡(jiǎn)單路徑：是經(jīng)過頂點(diǎn)不同的路徑；簡(jiǎn)單回路：是開始和終端重合的簡(jiǎn)單路徑；網(wǎng)絡(luò)：是帶權(quán)的圖。圖的存儲(chǔ)結(jié)構(gòu)：·鄰接矩陣表示法：用一個(gè)n階方陣來表示圖的結(jié)構(gòu)是唯一的，適合稠密圖。·無向圖：鄰接矩陣是對(duì)稱的。·有向圖：行是出度，列是入度。建立鄰接矩陣算法的時(shí)間是O(n+n2+e)，其時(shí)間復(fù)雜度為O(n2)·鄰接表表示法：用頂

26、點(diǎn)表和鄰接表構(gòu)成不是唯一的，適合稀疏圖。·頂點(diǎn)表結(jié)構(gòu) vertex | firstedge，指針域存放鄰接表頭指針。·鄰接表：用頭指針確定。 ·無向圖稱邊表；·有向圖又分出邊表和逆鄰接表；·鄰接表結(jié)點(diǎn)結(jié)構(gòu)為 adjvex | next，時(shí)間復(fù)雜度為O(n+e)，空間復(fù)雜度為O(n+e)。圖的遍歷： ·深度優(yōu)先遍歷：借助于鄰接矩陣的列。使用棧保存已訪問結(jié)點(diǎn)。·廣度優(yōu)先遍歷：借助于鄰接矩陣的行。使用隊(duì)列保存已訪問結(jié)點(diǎn)。生成樹的定義：若從圖的某個(gè)頂點(diǎn)出發(fā)，可以系統(tǒng)地訪問到圖中所有頂點(diǎn)，則遍歷時(shí)經(jīng)過的邊和圖的所有頂點(diǎn)所構(gòu)成的子圖稱作

27、該圖的生成樹。最小生成樹：圖的生成樹不唯一，從不同的頂點(diǎn)出發(fā)可得到不同的生成樹，把權(quán)值最小的生成樹稱為最小生成樹(MST)。構(gòu)造最小生成樹的算法： ·Prim算法的時(shí)間復(fù)雜度為O(n2)與邊數(shù)無關(guān)適于稠密圖。·Kruskal算法的時(shí)間復(fù)雜度為O(lge)，主要取決于邊數(shù)，較適合于稀疏圖。最短路徑的算法：·Dijkstra算法，時(shí)間復(fù)雜度為O(n2)。·類似于prim算法。拓?fù)渑判颍菏菍⒂邢驘o環(huán)圖G中所有頂點(diǎn)排成一個(gè)線性序列，若E(G)，則在線性序列u在v之前，這種線性序列稱為拓?fù)湫蛄小Ｍ負(fù)渑判蛞灿袃煞N方法：·無前趨的頂點(diǎn)優(yōu)先：每次輸出一個(gè)無前趨

28、的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其出邊，最后得到的序列即拓?fù)湫蛄小?#183;無后繼的結(jié)點(diǎn)優(yōu)先：每次輸出一個(gè)無后繼的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其入邊，最后得到的序列是逆拓?fù)湫蛄小５诎苏?排序記錄中可用某一項(xiàng)來標(biāo)識(shí)一個(gè)記錄，則稱為關(guān)鍵字項(xiàng)，該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字。排序是使文件中的記錄按關(guān)鍵字遞增(或遞減)次序排列起來。·基本操作：比較關(guān)鍵字大小；改變指向記錄的指針或移動(dòng)記錄。·存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變，則稱這種排序方法是穩(wěn)定的，否則排序算法是不穩(wěn)定的。排序過程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱之為“內(nèi)部排序”(內(nèi)排序)，反之，若

29、存在數(shù)據(jù)的內(nèi)外存交換，則稱之為外排序。內(nèi)部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條：執(zhí)行時(shí)間和所需的輔助空間，另外算法的復(fù)雜程序也是要考慮的一個(gè)因素。插入排序：·直接插入排序；·逐個(gè)向前插入到合適位置；·哨兵(監(jiān)視哨)有兩個(gè)作用； ·作為臨變量存放Ri；·是在查找循環(huán)中用來監(jiān)視下標(biāo)變量j是否越界；·直接插入排序是就地的穩(wěn)定排序。時(shí)間復(fù)雜度為O(n2)，比較次數(shù)為(n+2)(n-1)/2;移動(dòng)次數(shù)為(n+4)(n-1)/2。希爾排序： ·等間隔的數(shù)據(jù)比較并按要求順序排

30、列，最后間隔為1；·希爾排序是就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為O(n1.25)，比較次數(shù)為(n1.25)；移動(dòng)次數(shù)為(1.6n1.25)；交換排序：冒泡排序：·自下向上確定最輕的一個(gè)。·自上向下確定最重的一個(gè)。·自下向上確定最輕的一個(gè)，后自上向下確定最重的一個(gè)。·冒泡排序是就地的穩(wěn)定排序。時(shí)間復(fù)雜度為O(n2)，比較次數(shù)為n(n-1)/2;移動(dòng)次數(shù)為3n(n-1)/2；快速排序：·以第一個(gè)元素為參考基準(zhǔn)，設(shè)定、動(dòng)兩個(gè)指針，發(fā)生交換后指針交換位置，直到指針重合。重復(fù)直到排序完成。·快速排序是非就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為O(n

31、log2n)，比較次數(shù)為n(n-1)/2。選擇排序：·直接選擇排序；·選擇最小的放在比較區(qū)前；·直接選擇排序就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為O(n2)。比較次數(shù)為n(n-1)/2。堆排序 ·建堆：按層次將數(shù)據(jù)填入完全二叉樹，從int(n/2)處向前逐個(gè)調(diào)整位置。·然后將樹根與最后一個(gè)葉子交換值并斷開與樹的連接并重建堆，直到全斷開。·堆排序是就地不穩(wěn)定的排序，時(shí)間復(fù)雜度為O(nlog2n)，不適宜于記錄數(shù)較少的文件。歸并排序： ·先兩個(gè)一組排序，形成(n+1)/2組，再將兩組并一組，直到剩下一組為止。·歸并排序是非就地

32、穩(wěn)定排序，時(shí)間復(fù)雜度是O(nlog2n)，分配排序：箱排序： ·按關(guān)鍵字的取值范圍確定箱子數(shù)，按關(guān)鍵字投入箱子，鏈接所有非空箱。·箱排序的平均時(shí)間復(fù)雜度是線性的O(n)。基數(shù)排序：·從低位到高位依次對(duì)關(guān)鍵字進(jìn)行箱排序。·基數(shù)排序是非就穩(wěn)定的排序，時(shí)間復(fù)雜度是O(d*n+d*rd)。各種排序方法的比較和選擇： ·待排序的記錄數(shù)目n；n較大的要用時(shí)間復(fù)雜度為O(nlog2n)的排序方法；·記錄的大小(規(guī)模)；記錄大最好用鏈表作為存儲(chǔ)結(jié)構(gòu)，而快速排序和堆排序在鏈表上難于實(shí)現(xiàn)；·關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；·對(duì)穩(wěn)定性的要求；

33、·語(yǔ)言工具的條件；·存儲(chǔ)結(jié)構(gòu)；·時(shí)間和輔助空間復(fù)雜度。第九章 查找查找的同時(shí)對(duì)表做修改操作(如插入或刪除)則相應(yīng)的表稱之為動(dòng)態(tài)查找表，否則稱之為靜態(tài)查找表。衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(即平均查找長(zhǎng)度ASL)。線性表查找的方法： ·順序查找：逐個(gè)查找，ASL=(n+1)/2；·二分查找：取中點(diǎn)int(n/2)比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹表示。ASL=(每層結(jié)點(diǎn)數(shù)*層數(shù))/N；·分塊查找：要求“分塊有序”，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中的最大關(guān)鍵字及其位置建立有序

34、索引表。二叉排序樹(BST)定義是二叉排序樹是空樹或者滿足如下性質(zhì)的二叉樹： ·若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；·若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；·左、右子樹本身又是一棵二叉排序樹。二叉排序樹的插入、建立、刪除的算法平均時(shí)間性能是O(nlog2n)。二叉排序樹的刪除操作可分三種情況進(jìn)行處理： ·*P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可。·*P只有一個(gè)孩子*child，此時(shí)只需將*child和*p的雙親直接連接就可刪去*p。·*p有兩

35、個(gè)孩子，則先將*p結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)的數(shù)據(jù)到*p，刪除中序后繼結(jié)點(diǎn)。關(guān)于B-樹(多路平衡查找樹)。它適合在磁盤等直接存取設(shè)備上組織動(dòng)態(tài)的查找表，是一種外查找算法。建立的方式是從下向上拱起。散列技術(shù)：將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表的過程稱為散列。散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡(jiǎn)單和均勻。常見的散列函數(shù)構(gòu)的造方法：·平方取中法：hash=int(x2)%100)·除余法：表長(zhǎng)為m，hash=x%m·相乘取整法：hash=int(m*(x*A-int(x*A);A=0.618·隨機(jī)數(shù)法：hash=random(x)。處理沖突的方法：開放定址法： 一般形式為hi=(h(key)+di)%m1im-1，開放定址法要求散列表的裝填因子1。·開放定址法類型： ·線性探查法：address=(ha