已學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)：線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹(shù)、圖和散列表其中：棧、隊(duì)列和串是特殊的線性表數(shù)組和廣義表是廣義的線性表樹(shù)和圖是非線性的數(shù)據(jù)結(jié)構(gòu)散列表是一種查找數(shù)據(jù)結(jié)構(gòu)還學(xué)習(xí)了在實(shí)際應(yīng)用中應(yīng)用廣泛的查找技術(shù)、排序技術(shù)和索引技術(shù)各章重點(diǎn)：第1章緒論數(shù)據(jù)結(jié)構(gòu)定義：數(shù)據(jù)結(jié)構(gòu)（datastructure）是指相互間存在一定關(guān)系的數(shù)據(jù)元素的集合。或數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)中的基本術(shù)語(yǔ)：數(shù)據(jù)元素--數(shù)據(jù)的基本單位數(shù)據(jù)項(xiàng)--是構(gòu)成數(shù)據(jù)元素的不可再分的最小單位數(shù)據(jù)對(duì)象--是具有相同性質(zhì)的數(shù)據(jù)元素的集合數(shù)據(jù)的邏輯結(jié)構(gòu)--是數(shù)據(jù)元素間邏輯關(guān)系的整體存儲(chǔ)結(jié)構(gòu)--是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的物理表示。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的關(guān)系：1）數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)的機(jī)外表示，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的機(jī)內(nèi)表示。2）一種邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。3）數(shù)據(jù)的基本操作是定義于邏輯結(jié)構(gòu)，實(shí)現(xiàn)于存儲(chǔ)結(jié)構(gòu)。4）采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的方法和效率往往是不同的。訪問(wèn)接口：操作的調(diào)用形式與規(guī)范數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)接口：數(shù)據(jù)結(jié)構(gòu)基本操作接口的全體。數(shù)據(jù)類(lèi)型（datatype）是一組值的集合以及定義于這個(gè)值集上的一組操作的總稱(chēng)抽象數(shù)據(jù)類(lèi)型（AbstractDataType，ADT）:一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱(chēng)。抽象數(shù)據(jù)類(lèi)型的定義形式:ADT=<D,O>算法（algorithm）是對(duì)特定問(wèn)題求解的一種描述，是指令的有限序列。算法的五大特征:⑴輸入⑵輸出⑶有窮性⑷確定性⑸可行性算法的描述:1）自然語(yǔ)言

2）高級(jí)語(yǔ)言

3）偽代碼

4）N-S圖算法分析:“好”的算法至少應(yīng)該滿足以下幾個(gè)條件

1）正確性

2）容錯(cuò)性

3）可讀性

4）分級(jí)性

5）高效性*算法的時(shí)間復(fù)雜度:刻畫(huà)的是算法的運(yùn)行時(shí)間算法的空間復(fù)雜度:主要對(duì)算法的執(zhí)行過(guò)程中需要用到的輔助空間的度量。算法的時(shí)間復(fù)雜度和空間復(fù)雜度都用漸近階來(lái)表示。通常用O來(lái)表示：T(n)=O(f(n))

S(n)=O(f(n))第2章

線性表線性表的定義：線性表（linearlist）也簡(jiǎn)稱(chēng)表。是n(n≥0)個(gè)具有相同數(shù)據(jù)類(lèi)型的數(shù)據(jù)元素的有限序列。L＝（a1,a2,…,ai-1,ai,…,an)線性表的幾個(gè)術(shù)語(yǔ)：表長(zhǎng)：線性表中的元素個(gè)數(shù)；空表：元素個(gè)數(shù)為零的線性表，常表示為L(zhǎng)=（）；前驅(qū)與后繼：a1無(wú)前驅(qū),an無(wú)后繼,其他元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼；性線表特征：順序性、有限性、相同性、抽象性線性表的順序存儲(chǔ)結(jié)構(gòu)---順序表順序表是高級(jí)語(yǔ)言（C++語(yǔ)言)的一維數(shù)組

int

MaxSize;//存儲(chǔ)表的允許長(zhǎng)度

intlength;//存儲(chǔ)表的實(shí)際長(zhǎng)度

T*data;//存儲(chǔ)數(shù)組的初地址主要函數(shù)（操作）說(shuō)明：所有的操作都設(shè)計(jì)為函數(shù)（C++語(yǔ)言），不要求用C++的類(lèi)構(gòu)造順序表:SeqList（a,n,m）--構(gòu)造長(zhǎng)為m，并從數(shù)組a

復(fù)制n個(gè)數(shù)據(jù)的表輸出順序表:PrintList（）順序表插入:voidInsert(int

i,Tx)順序表刪除:TDelete(inti)順序表查找:TGet(inti)int

Locate(Tx)順序表的優(yōu)點(diǎn)：⑴無(wú)需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；⑵隨機(jī)存取：可以快速地存取表中任一位置的元素順序表的缺點(diǎn)：⑴表的容量難以確定，表的容量難以擴(kuò)充；⑵插入和刪除操作需要移動(dòng)大量元素；⑶造成存儲(chǔ)空間的碎片。線性表的鏈接存儲(chǔ)結(jié)構(gòu)—單鏈表

單鏈表是高級(jí)語(yǔ)言（C++語(yǔ)言)的指針單鏈表是使用一組任意的內(nèi)存單元來(lái)存儲(chǔ)線性表的數(shù)據(jù)元素，線性表中的邏輯關(guān)系是通過(guò)指針來(lái)表示的。結(jié)點(diǎn)結(jié)構(gòu):

structNode

{Tdata;

Node<T>*next;

};三種單鏈表：aabbccdd^頭指針////////aabbccdd^first帶頭結(jié)點(diǎn)的單鏈表：循環(huán)單鏈表：////////aabbccddrear一般單鏈表：雙鏈表：template<classT>

struct

DulNode{Tdata;

DulNode<T>*prior;

DulNode<T>*next;}在雙向循環(huán)鏈表中求表長(zhǎng)，按位置查找等操作與單鏈表基本相同，不同的是插入和刪除操作。由于它是對(duì)稱(chēng)結(jié)構(gòu)，使得插入和刪除操作都很容易。也分一般雙鏈表、帶頭結(jié)點(diǎn)的單鏈表、循環(huán)單鏈表要求掌握插入和刪除指定結(jié)點(diǎn)的指針修改的相對(duì)順序主要函數(shù)（操作）說(shuō)明：所有的操作都設(shè)計(jì)為函數(shù)（C＋＋語(yǔ)言），不要求用C++的類(lèi)構(gòu)造單鏈表:LinkList(T

a[],intn)--構(gòu)造長(zhǎng)為n，并從數(shù)組

a復(fù)制n個(gè)數(shù)據(jù)的單鏈表,分頭插法和尾插法輸出單鏈表:PrintList（）單鏈表插入:voidInsert(inti,Tx);//按位置插入（前后）

voidInsert(Ty,Tx);//單鏈表刪除:TDelete(inti);//按位置刪除

TDelete(Tx);//單鏈表查找:TGet(inti)//按位置查找

Node*Locate(Tx);//按值查找并返回指定元素的地址對(duì)線性表，特別是單鏈表要求掌握相關(guān)操作的算法設(shè)計(jì)比如：1、查找指定元素的結(jié)點(diǎn)按要求插入或刪除

2、將單鏈表或循環(huán)單鏈表按要求拆分為兩個(gè)鏈表

3、將兩個(gè)單鏈表或循環(huán)單鏈表按要求合并為一個(gè)鏈表第3章棧、隊(duì)列和串1.棧的定義棧（stack）是限在表尾進(jìn)行插入和刪除操作的線性表。允許進(jìn)行插入和刪除操作的一端叫棧頂，另一端稱(chēng)為棧底。后進(jìn)先出性(lastinfirstout)順序棧和鏈棧主要函數(shù)（操作）：

voidPush(Tx);//入棧TPop();//出棧TGetTop();//取棧頂元素boolEmpty();//判斷棧空否第3章棧、隊(duì)列和串2.隊(duì)列的定義

隊(duì)列（queue）也是特殊的線性表，它的插入和刪除分別在線性表的兩端分別進(jìn)行。允許插入的一端叫隊(duì)尾，刪除的一端則稱(chēng)作隊(duì)首。

循環(huán)順序隊(duì)列和鏈接隊(duì)主要函數(shù)（操作）：

voidEnQueue(Tx);//入隊(duì)

TDeQueue();//出隊(duì)

TGetQueue();//取隊(duì)首頂元素

boolEmpty();//判斷隊(duì)空否第3章棧、隊(duì)隊(duì)列和串棧、隊(duì)列的模塊化引用

stackSqueueQ//定義棧S定義隊(duì)Q

Initstack(S)Initqueue(Q)//初始化棧S和隊(duì)Q

queueempty(Q)//判斷隊(duì)Q是否為空

enqueue(Q,d)//入隊(duì)(在隊(duì)尾插入一個(gè)元素d)

dequeue(Q,d)//出隊(duì)(刪除隊(duì)頭元素給d)

stackempty(S)//判斷棧S是否為空

push(S,d)//入棧（在棧頂插入一個(gè)元素d)

pop(S,d)//出棧(刪除棧頂元素給d)第3章棧、隊(duì)隊(duì)列和串對(duì)棧和隊(duì)要求掌握：

1、模塊化引用

2、操作特性

3、棧頂和棧底、隊(duì)首和隊(duì)尾

4、循環(huán)順序隊(duì)的隊(duì)空和隊(duì)滿的條件

5、順序棧兩棧共享的棧滿和棧空的條件第3章棧、隊(duì)列和串3.串的定義串（string）也是特殊的線性表，它是由字符構(gòu)成的線性表。也就是字符序列，通常記為：S="s1s2s3s4…sn"串的幾個(gè)術(shù)語(yǔ)：空串：不含字符的串""

空格串：僅含空格字符的串""

串長(zhǎng)：串中含有字符的個(gè)數(shù)子串/母串：子串包含在母串中子串在母串的位置：子串在母串的起始位置串的操作：

主要是關(guān)注串的整體性的操作。比如，串的比較，子串的定位，插入，更新等。⑴StrLength(s)：求串s的長(zhǎng)度。⑵StrAssign(s1,s2)：賦值，將s2的值賦值給串s1。⑶StrConcat(s1,s2,s)：連接，將串s2放在串s1的后面連接成一個(gè)新串s。⑷SubStr(s,i,len)：求子串，返回從串s的第i個(gè)字符開(kāi)始取長(zhǎng)為len

的子串。⑸StrCmp(s1,s2)：串比較，若s1=s2，返回0；若s1<s2,返回-1；若s1>s2,返回1模式匹配：在主串中定位子串位置的過(guò)程稱(chēng)為模式匹配（子串也稱(chēng)為模式串）第4章廣義線性表—多維數(shù)組和廣義表1.數(shù)組的定義數(shù)組（array）是由類(lèi)型相同的數(shù)據(jù)元素構(gòu)成的有序集合，每個(gè)數(shù)據(jù)元素稱(chēng)為數(shù)組元素（簡(jiǎn)稱(chēng)元素），每個(gè)元素受n(n≥1)個(gè)線性關(guān)系的約束，每個(gè)元素在n個(gè)線性關(guān)系中的序號(hào)i1,i2,…in稱(chēng)為該元素的下標(biāo)，并稱(chēng)該數(shù)組為n維數(shù)組。數(shù)組采用存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)

用順序存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)多維數(shù)組需要解決多維結(jié)構(gòu)到一維結(jié)構(gòu)的映射問(wèn)題。二維數(shù)組的映射方式：按行優(yōu)先和按列優(yōu)先三維數(shù)組A[n1][n2][n3]按高位優(yōu)先存儲(chǔ)的原則，先存儲(chǔ)第0頁(yè)，再存儲(chǔ)第1頁(yè)，再存儲(chǔ)……，最后存儲(chǔ)第n1-1頁(yè)。第4章廣義線性表—多維數(shù)組和廣義表數(shù)組的尋址方式:一維數(shù)組的存儲(chǔ)方式及尋址方式:

LOC(ai)=LOC(a0)+i*cc為每個(gè)元素占用的內(nèi)存單元數(shù)二維數(shù)組的尋址方式:按行優(yōu)先存儲(chǔ)時(shí)的尋址方式為：

LOC(aij)=LOC(a00)+(i*n+j)*c按列優(yōu)先存儲(chǔ)時(shí)的尋址方式為:

LOC(aij)=LOC(a00)+(j*m+i)*c

第4章廣義線性表—多維數(shù)組和廣義表三維數(shù)組的存儲(chǔ)與尋址方式:

LOC(aijk)=LOC(a000)+(i*n2*n3+j*n3+k)*c對(duì)稱(chēng)矩陣的尋址方式:sak=aiji*(i+1)/2+j當(dāng)i≥j時(shí)j*(j+1)/2+i當(dāng)i<j時(shí)k=下三角矩陣的尋址方式:sak=aiji*(i+1)/2+j當(dāng)i≥j時(shí)n*(n+1)/2當(dāng)i<j時(shí)k=第4章廣義線性表—多維數(shù)組和廣義表上三角矩陣的尋址方式:sak=aijk=三對(duì)角陣An按主對(duì)角線壓縮存儲(chǔ)到一維數(shù)組SA3n中，具體的尋址方式是：

(2*n-i+1)*i/2+j-i當(dāng)j≥i時(shí)n*(n+1)/2當(dāng)j<i時(shí)sa(j-i+1)*n+i|i-j|<2）時(shí)0|i-j|>1）時(shí)

aij=第4章廣義線性表—多維數(shù)組和廣義表三對(duì)角陣An按按行壓縮存儲(chǔ)到一維數(shù)組SA3n中，具體的尋址方式是：sa2*i+j|i-j|<2）時(shí)0|i-j|>1）時(shí)

aij=稀疏矩陣壓縮存儲(chǔ):三元組表structelement{

introw,col;//行號(hào)，列號(hào)

Titem//非零元素值

};第4章廣義線性表—多維數(shù)組和廣義表廣義表：n（n≥0）個(gè)數(shù)據(jù)元素的有限序列，記作：

LS＝(a1，a2，……，an)其中：LS是廣義表的名稱(chēng)，ai（1≤i≤n）是LS的成員（或直接元素），它可以是單個(gè)的數(shù)據(jù)元素，也可以是一個(gè)廣義表，分別稱(chēng)為L(zhǎng)S的單元素（或原子）和子表。

廣義表的兩個(gè)重要操作：取頭元素和取表尾操作.廣義表的存儲(chǔ)結(jié)構(gòu):tag=0datatag=1hptp子表原子.要求會(huì)畫(huà)出廣義表的存儲(chǔ)結(jié)構(gòu)示意圖:第5章樹(shù)和二叉樹(shù)1、樹(shù)的定義

樹(shù)(tree)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n＝0時(shí)，稱(chēng)為空樹(shù)；任意一棵非空樹(shù)滿足以下條件：⑴當(dāng)n=1時(shí)，有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)；⑵當(dāng)n＞1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的有限集合T1,T2,…,Tm，其中每個(gè)集合又是一棵樹(shù)，并稱(chēng)為這個(gè)根結(jié)點(diǎn)的子樹(shù)。

樹(shù)的定義是遞歸的樹(shù)的基本術(shù)語(yǔ)：結(jié)點(diǎn)的度、葉結(jié)點(diǎn)、分枝結(jié)點(diǎn)、孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)、路徑、路徑長(zhǎng)度、祖先、子孫、結(jié)點(diǎn)的層數(shù)、樹(shù)的高度、層序號(hào)、有序樹(shù)、無(wú)序樹(shù)、森林、同構(gòu)第5章樹(shù)和二叉樹(shù)樹(shù)的遍歷操作：

前序（先根）遍歷

后序（后根）遍歷

層序遍歷樹(shù)的存儲(chǔ)結(jié)構(gòu)：雙親表示法：用靜態(tài)指針來(lái)存儲(chǔ)雙親樹(shù)孩子表示法：多重鏈表表示和孩子鏈表表示雙親孩子表示法：孩子兄弟表示法：firstchilddatarightsib第5章樹(shù)和二叉樹(shù)2、二叉樹(shù)的定義：二叉樹(shù)（binarytree）是度不超過(guò)2的有序樹(shù)。二叉樹(shù)的特點(diǎn)：

1）每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子（度可為0/1/2）；

2）孩子之間有順序（常以左孩子，右孩子來(lái)表示）。幾種特殊的二叉樹(shù)：

1）斜樹(shù)

2）滿二叉樹(shù)

3）完全二叉樹(shù)第5章樹(shù)和二叉樹(shù)二叉樹(shù)的基本性質(zhì)：性質(zhì)5-1：二叉樹(shù)的第i層上最多可有2i-1個(gè)結(jié)點(diǎn)。性質(zhì)5-3：二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù)為n０,度為２的結(jié)點(diǎn)為n２，

則n０=n２+1。性質(zhì)5-2：深度為k二叉樹(shù)中最多可有2k-1個(gè)結(jié)點(diǎn)，最少有

k個(gè)結(jié)點(diǎn)(斜樹(shù))。性質(zhì)5-4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為

「log2n」+1。第5章樹(shù)和二叉樹(shù)二叉樹(shù)的基本性質(zhì)：性質(zhì)5-5：對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)進(jìn)行層序編號(hào)，則編號(hào)為i的結(jié)點(diǎn)滿足：

1)i=1時(shí)，為根結(jié)點(diǎn)；i>1時(shí)，雙親結(jié)點(diǎn)編號(hào)為i/2；2)若2i≤n，i有左孩子，左孩子編號(hào)為2i；否則，i無(wú)左孩子（必?zé)o右孩子）；3)若2i+1≤n，i有右孩子，右孩子編號(hào)為2i＋1，否則i無(wú)右孩子。第5章樹(shù)和二叉樹(shù)二叉樹(shù)的遍歷操作:先序遍歷，中序遍歷，后序遍歷，層序遍歷由中序和先（后）序遍歷結(jié)果可惟一確定一棵二叉樹(shù)。二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)：

二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)：可采用完全二叉樹(shù)一樣的編號(hào)方法（左子：兩倍，右子：兩倍多1）。12345678910111213ABCDEFG第5章樹(shù)和二叉樹(shù)二叉鏈表存儲(chǔ)結(jié)構(gòu)：lchilddatarchild左孩子指針數(shù)據(jù)域右孩指子針struct

BiNode{Tdata;

BiNode<T>*lchild,*rchild;//存儲(chǔ)左/右孩子指針};lchilddatarchild第5章樹(shù)和二叉樹(shù)二叉鏈表主要函數(shù)（操作）：

BiTree(BiNode<T>*root);//有參構(gòu)造函數(shù)

voidPreOrder(BiNode<T>*root);//前序遍歷二叉樹(shù)

voidInOrder(BiNode<T>*root);//中序遍歷二叉樹(shù)

voidPostOrder(BiNode<T>*root);//后序遍歷二叉樹(shù)

voidLeverOrder(BiNode<T>*root);//層序遍歷二叉樹(shù)構(gòu)造函數(shù)：利用擴(kuò)展二叉樹(shù)的先序遍歷序列建立二叉樹(shù)求二叉樹(shù)t的深度：intDepth(BiNode*r)求二叉樹(shù)t的葉子數(shù)：intLeaf(BiNode*r)交換二叉樹(shù)t的所有左右孩子：voidexchange(BiNode*r)求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)：voidCount(BiNode*r)第5章樹(shù)和二叉樹(shù)要求掌握：

1、二叉樹(shù)的順序存儲(chǔ)表示←→二叉樹(shù)的圖形表示

2、給定樹(shù)和二叉樹(shù)，能寫(xiě)出各種遍歷結(jié)果

3、給定擴(kuò)展二叉樹(shù)的先序遍歷序列→畫(huà)出此二叉樹(shù)的圖形表示給定先序（或后序）和中序遍歷序列→畫(huà)出此二叉樹(shù)的圖形表示

5、樹(shù)和二叉樹(shù)的形態(tài)

4、二叉樹(shù)的基本性質(zhì)

5、樹(shù)和二叉樹(shù)各有幾種存儲(chǔ)結(jié)構(gòu)

6、二叉樹(shù)的先序遍歷和中序遍歷的非遞歸算法

7、利用二叉樹(shù)的先序遍歷和中序遍歷的非遞歸算法求二叉樹(shù)t的深度、求葉子數(shù)、交換所有左右孩子、求結(jié)點(diǎn)個(gè)數(shù)第5章樹(shù)和二叉樹(shù)線索鏈表ltaglchilddatarchildrtag0:lchild指向該結(jié)點(diǎn)的左孩子1:lchild指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)0:rchild指向該結(jié)點(diǎn)的右孩子1:rchild指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)ltag=rtag=以中序遍歷線索二叉樹(shù)能繪出線索鏈表的示意圖第5章樹(shù)和二叉樹(shù)樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)轉(zhuǎn)換為二叉樹(shù)：

1）加線（兄弟間）2）去線（父子間僅保留長(zhǎng)子）3）調(diào)整森林轉(zhuǎn)換為二叉樹(shù)：

1）將森林的每棵樹(shù)轉(zhuǎn)換為二叉樹(shù)2）將后繼樹(shù)作為前趨樹(shù)的右孩子二叉樹(shù)轉(zhuǎn)換為森林（樹(shù)）：

1）加線-----某結(jié)點(diǎn)x是其雙親y的左孩子，則把結(jié)點(diǎn)x的右孩子、右孩子的右孩子、…，都與結(jié)點(diǎn)y用線連起來(lái)；

2）去線-----刪去原二叉樹(shù)中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線；

3）調(diào)整-----整理由1）和2)所得到的樹(shù)或森林。第5章樹(shù)和二叉樹(shù)二叉樹(shù)應(yīng)用—哈夫曼樹(shù)及哈夫曼編碼幾個(gè)概念：葉結(jié)點(diǎn)的權(quán)值帶權(quán)二叉樹(shù)葉結(jié)點(diǎn)的路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度

WPL=哈夫曼樹(shù)（Hhffmantree）--帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，也稱(chēng)為最優(yōu)二叉樹(shù)。要求：給定一組權(quán)值能構(gòu)建出哈夫曼樹(shù)可求出每一個(gè)權(quán)值所對(duì)應(yīng)的哈夫曼編碼能計(jì)算該哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度。第6章圖1.圖的定義圖（graph）是由有窮非空的頂點(diǎn)集和連接這些頂點(diǎn)的邊集構(gòu)成的整體，通常表示為：

G=〈V,E〉其中，G表示一個(gè)圖，V是圖G的頂點(diǎn)集，E是圖G的集。圖的基本術(shù)語(yǔ)：

無(wú)向邊、有向邊、無(wú)向圖、有向圖、簡(jiǎn)單圖、鄰接、依附、完全圖、稠密/稀疏圖、無(wú)向圖的度、有向圖的入/出度、權(quán)、網(wǎng)圖、路徑、路徑長(zhǎng)度、回路、簡(jiǎn)單路徑、簡(jiǎn)單回路、子圖、連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量、生成樹(shù)、生成森林n個(gè)頂點(diǎn)的無(wú)向完全圖中，有n*(n-1)/2條邊n個(gè)頂點(diǎn)的有向完全圖中，有n*(n-1)條邊第6章圖圖的遍歷：

深度優(yōu)先遍歷

DFSTraverse()廣度優(yōu)先遍歷BFSTraverse()圖的存儲(chǔ)結(jié)構(gòu)：

鄰接矩陣和鄰接表圖的操作（算法）：

MGraph(Ta[],intn,inte)

//構(gòu)造函數(shù)n個(gè)頂點(diǎn)e條邊

DFSTraverse(intv)//深度優(yōu)先遍歷

BFSTraverse(intv)//廣度優(yōu)先遍歷不同的存儲(chǔ)結(jié)構(gòu)（鄰接矩陣和鄰接表）的算法

鄰接矩陣中（無(wú)向圖、有向圖、網(wǎng)圖）

鄰接表中（無(wú)向圖、有向圖、網(wǎng)圖）及逆鄰接表第6章圖給定一個(gè)圖的鄰接矩陣或鄰接表（無(wú)向圖、有向圖、網(wǎng)圖）能畫(huà)出相應(yīng)的圖能寫(xiě)出從給定結(jié)點(diǎn)出發(fā)進(jìn)行廣度、深度優(yōu)先遍歷的結(jié)點(diǎn)序列

能分別按Prim和Kruskal算法構(gòu)造該圖的最小生成樹(shù)，寫(xiě)出構(gòu)造過(guò)程。

n個(gè)頂點(diǎn)的連通圖其生成樹(shù)有且僅有n-1條邊無(wú)向圖的連通性和有向圖的連通性最小生成樹(shù)：

Prim(普里姆）算法

Kruskal（克魯斯卡爾）算法要求掌握基本思想和構(gòu)造過(guò)程第6章圖最短路徑：?jiǎn)卧醋疃搪窂降腄ijkstra（狄杰斯特拉）算法每一對(duì)頂點(diǎn)間的最短路徑的Folyd(弗洛伊德）算法要求掌握基本思想和各頂點(diǎn)的最小路徑長(zhǎng)度及具體路徑AOV網(wǎng)與拓樸排序：頂點(diǎn)表示活動(dòng)的網(wǎng)要求掌握定義及基本方法求得拓樸排序序列AOE網(wǎng)與關(guān)鍵路徑：頂點(diǎn)表示事件，邊表示活動(dòng)的網(wǎng)要求掌握定義及基本方法求得關(guān)鍵路徑事件的最早發(fā)生時(shí)間ve[k]、最遲發(fā)生時(shí)間vl[k]、活動(dòng)的最早開(kāi)始時(shí)間e[i]、活動(dòng)的最晚開(kāi)始時(shí)間l[i]及活動(dòng)的緩沖時(shí)間t[k]關(guān)鍵路徑(criticalpath)：始點(diǎn)到終點(diǎn)最大長(zhǎng)度的路徑第7章查找技術(shù)查找的基本概念:查找（search）是數(shù)據(jù)處理中使用最頻繁的一種操作。是在具有相同類(lèi)型的記錄構(gòu)成的集合中找出滿足條件的記錄。關(guān)鍵碼(Key)---能夠惟一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)。

關(guān)鍵碼在數(shù)據(jù)集合中最多只會(huì)出現(xiàn)一次。靜態(tài)查找：

不涉及記錄插入和刪除操作的查找。靜態(tài)查找不會(huì)影響數(shù)據(jù)源，僅返回待查記錄的地址信息。動(dòng)態(tài)查找：

涉及記錄插入和刪除操作的查找。動(dòng)態(tài)查找會(huì)影響數(shù)據(jù)源，會(huì)將待查記錄插入到數(shù)據(jù)源集合中或從數(shù)據(jù)源中刪除。第7章查找技術(shù)查找的存儲(chǔ)結(jié)構(gòu):邏輯上講，查找基于的數(shù)據(jù)結(jié)構(gòu)是記錄集合，說(shuō)明我們只關(guān)注記錄本身的地址，不關(guān)心記錄間的其它關(guān)系。

在某些應(yīng)用中，查找操作是主要的操作，為了提高；查找效率，需要專(zhuān)門(mén)為查找操作設(shè)置數(shù)據(jù)結(jié)構(gòu)，這種面向查找操作的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為查找結(jié)構(gòu)。查找算法的性能:

平均查找長(zhǎng)度(averagesearchlength)是指所有關(guān)鍵碼查找的次數(shù)的平均值。第7章查找技術(shù)查找方法:

1、順序表的順序查找（哨兵）單鏈表的順序查找

2、折半查找（二分查找）

3、斐波那契查找

4、插值查找

5、二叉排序樹(shù)的查找

6、散列表的查找技術(shù)第7章查找技術(shù)平衡二叉樹(shù)：

最小不平衡子樹(shù)是指距離插入點(diǎn)（葉結(jié)點(diǎn)）最近的且平衡因子的絕對(duì)值大于1的結(jié)點(diǎn)為根的子樹(shù)。平衡二叉樹(shù)的調(diào)整方法：①LL型順時(shí)針旋轉(zhuǎn)，結(jié)點(diǎn)A為結(jié)點(diǎn)B的右孩子，結(jié)點(diǎn)B的右孩子為A的左孩子

②RR型逆時(shí)針旋轉(zhuǎn)，結(jié)點(diǎn)A為結(jié)點(diǎn)B的左孩子，結(jié)點(diǎn)B的左孩子為A的右孩子

③LR型ⅰ.B為支撐點(diǎn)逆時(shí)針旋轉(zhuǎn)，同RR型

ⅱ.A為支撐點(diǎn)順時(shí)針旋轉(zhuǎn)，同LL型

④RL型ⅰ.B為支撐點(diǎn)順時(shí)針旋轉(zhuǎn)，同LL型

ⅱ.A為支撐點(diǎn)逆時(shí)針旋轉(zhuǎn)，同RR型第7章查找技術(shù)散列表的查找技術(shù)：相關(guān)術(shù)語(yǔ)：

散列函數(shù)(hashfunction)：由關(guān)鍵字計(jì)算存儲(chǔ)位置的函數(shù)，也稱(chēng)為哈希函數(shù)。

散列地址(hashaddress)：由散列函數(shù)計(jì)算出的存儲(chǔ)地址（相對(duì)地址）。

散列表(hashtable)：通過(guò)散列地址來(lái)存儲(chǔ)數(shù)據(jù)的一片連續(xù)存儲(chǔ)空間（數(shù)組）。

散列技術(shù)：將數(shù)據(jù)通過(guò)特定的散列地址存儲(chǔ)在指定的散列表中，查找時(shí)，通過(guò)散列函數(shù)計(jì)算出其散列地址來(lái)直接查找的技術(shù)。第7章查找技術(shù)散列函數(shù)的設(shè)計(jì)：直接定址法：H(key)=a*key+b(a、b為常數(shù))除留余數(shù)法（模除法）：H(key)=key%p數(shù)字分析法：當(dāng)關(guān)鍵字的位數(shù)較長(zhǎng)時(shí)，可以通過(guò)對(duì)各個(gè)位的數(shù)字的分析，選擇合適的若干位來(lái)進(jìn)行散列平方取中法：平方取中法就是對(duì)關(guān)鍵碼平方后取其中間的若干位作為散列地址。折疊法：折疊法就是將關(guān)鍵碼分割成與散列地址相對(duì)應(yīng)的幾個(gè)部分，疊加后取最后的和作為散列地址第7章查找技術(shù)沖突處理方法：鏈地址法（開(kāi)散列表）：鏈地址法就是將所有散列地址相同的記錄存儲(chǔ)在一個(gè)單鏈表中，將這個(gè)單鏈表的頭指針存儲(chǔ)在散列表中的方法。公共溢出區(qū)法：公共溢出區(qū)法的散列表包括基本表和溢出表兩個(gè)部分，其思想是將發(fā)生沖突的記錄順序存儲(chǔ)在溢出表中。開(kāi)放定址法（閉散列表）：

開(kāi)放定址法的基本思想是，當(dāng)產(chǎn)生沖突時(shí)，只要散列表未滿，用某種方法尋找一個(gè)空單元來(lái)存儲(chǔ)記錄。第7章查找技術(shù)開(kāi)放定址法中，尋找下一個(gè)空單元的方法是

Hi=(H(key)+di)%m(i=1,2,3,m-1)。三種常見(jiàn)的偏移方法：⑴線性探測(cè)法

線性探測(cè)法即偏移數(shù)組d[]取{1,2,3,4,5,..m-1}⑵二次探測(cè)法

二次探測(cè)法的偏移數(shù)組d[]取{12,-12,22,-22.……}⑶隨機(jī)探測(cè)法

H=(H(key)+rand())%m第7章查找技術(shù)要求掌握：

1、順序查找、折半查找和二叉排序樹(shù)查找的算法

2、二叉排序樹(shù)的構(gòu)造（保序插入）方法

3、二叉排序樹(shù)的刪除方法：葉結(jié)點(diǎn)的刪除單子樹(shù)的結(jié)點(diǎn)的刪除有兩個(gè)子樹(shù)的根結(jié)點(diǎn)的刪除

4、平衡二叉樹(shù)的調(diào)整方法

5、散列函數(shù)：除留余數(shù)法（模除法）

H(key)=key%p第7章查找技術(shù)

6、沖突處理方法：線性探測(cè)法和鏈地址法

會(huì)求查找成功與不成功的的平均查找長(zhǎng)度

7、時(shí)間復(fù)雜性：順序查找O(n)

折半查找和斐波那契查找O(log2n)

二叉排序樹(shù)查找O(log2n)

散列查找O(1)第8章排序技術(shù)排序的定義：排序（sort）是將任意的記錄序列重新排列成一個(gè)按某關(guān)鍵字有序的序列排序的相關(guān)術(shù)語(yǔ)：正序(exactorder)：處理的記錄的排列順序與要求關(guān)鍵字的排列順序正好相同。反序(antiorder)：處理的記錄排列順序與排序關(guān)鍵字要求順序下好相反。趟(pass)：對(duì)待排序記錄進(jìn)行的一遍掃描排序算法的穩(wěn)定性(stable)：待排序關(guān)鍵字中相同的多個(gè)記錄相對(duì)位置不發(fā)生變化的排序，否則就是不穩(wěn)定的第8章排序技術(shù)排序的性能：時(shí)間性能：基于比較的內(nèi)部排序的操作主要有兩類(lèi)：比較：指關(guān)鍵字的比較移動(dòng)：指記錄的移動(dòng)高效的排序算法應(yīng)該有比較少的比較次數(shù)和移動(dòng)次數(shù)空間性能：指的是排序需要的附加空間。第8章排序技術(shù)排序方法：1、插入排序直接插入排序希爾排序2、交換排序冒泡排序快速排序3、選擇排序簡(jiǎn)單選擇排序堆排序4、歸并排序第8章排序技術(shù)各種排序算法的比較：1、時(shí)間復(fù)雜性排序方法平均情況最好情況最壞情況直接插入排序O(n2)O(n)O(n2)希爾排序O(nlog2n)O(n1.3)O(n2)起泡排序O(n2)O(n)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)簡(jiǎn)單選擇排序O(n2)O(n2)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)第8章排序技術(shù)各種排序算法的比較：2、空間復(fù)雜性排序方法輔助空間直接插入排序O(1)希爾排序O(1)起泡排序O(1)快速排序O(log2n)~O(n)簡(jiǎn)單選擇排序O(1)堆排序O(1)歸并排序O(n)第8章排序技術(shù)各種排序算法的比較：3