數(shù)據(jù)結(jié)構(gòu)考試復習

復習課第一章

基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型是數(shù)據(jù)（集合）中的一個“個體”數(shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位

數(shù)據(jù)類型

是一個值的集合和定義在此集合上的一組操作的總稱。

不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)關系的映象方法：（表示x,y的方法）順序映象以相對的存儲位置表示后繼關系例如:令y的存儲位置和x的存儲位置之間差一個常量C而C是一個隱含值，整個存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息xy鏈式映象以附加信息(指針)表示后繼關系需要用一個和x在一起的附加信息指示y的存儲位置yx

算法是為了解決某類問題而規(guī)定的一個有限長的操作序列。一個算法必須滿足以下五個重要特性：1．有窮性

2．確定性3．可行性4．有輸入5．有輸出算法算法設計的原則設計算法時，通常應考慮達到以下目標：1．正確性2.可讀性3．健壯性4．高效率與低存儲量需求

假如，隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時間復雜度。算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時間

=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時間

算法的執(zhí)行時間

與

原操作執(zhí)行次數(shù)之和

成正比

從算法中選取一種對于所研究的問題來說是基本操作

的原操作，以該基本操作在算法中重復執(zhí)行的次數(shù)作為算法運行時間的衡量準則。例一兩個矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲矩陣元素，c為a和b的乘積

for(i=1;i<=n;++i)

for(j=1;j<=n;++j){c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作時間復雜度:

O(n3)例二選擇排序voidselect_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。

}//select_sort基本操作:

比較(數(shù)據(jù)元素)操作時間復雜度:

O(n2)j=i;//

選擇第i個最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}例三起泡排序voidbubble_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for

(i=n-1,change=TRUE;i>1&&change;--i)}//bubble_sort基本操作:

賦值操作時間復雜度:

O(n2){

change=FALSE;

//change為元素進行交換標志

for(j=0;j<i;++j)

if(a[j]>a[j+1])

{

a[j]←→a[j+1];

change=TRUE;}}//一趟起泡算法的存儲空間需求算法的空間復雜度定義為:

表示隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。S(n)=O(g(n))第二章

線性表一、線性表的類型定義二、線性表類型的實現(xiàn)抽象數(shù)據(jù)類型線性表的定義如下：ADTList{

數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{稱n

為線性表的表長;

稱n=0

時的線性表為空表。}數(shù)據(jù)關系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{設線性表為(a1，a2,...，ai，...，an),

稱i為ai在線性表中的位序。}∈讀作屬于

假設:有兩個集合A和B分別用兩個線性表LA和LB表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員。

現(xiàn)要求一個新的集合

A＝A∪B?！仁锹?lián)集∩是交集例最簡單的一種順序映象方法是：

令y的存儲位置和x的存儲位置相鄰。順序映象——

以x的存儲位置和y的存儲位置之間某種關系表示邏輯關系<x,y>。

用一組地址連續(xù)的存儲單元

依次存放線性表中的數(shù)據(jù)元素

a1a2

…ai-1ai

…an線性表的起始地址稱作線性表的基地址以“存儲位置相鄰”表示有序?qū)?lt;ai-1，ai>

即：LOC(ai)=LOC(ai-1)+C

一個數(shù)據(jù)元素所占存儲量↑所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置

LOC(ai)=

LOC(a1)+(i-1)×C

↑基地址

用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。單鏈表以元素(數(shù)據(jù)元素的映象)

+指針(指示后繼元素存儲位置)=結(jié)點

(表示數(shù)據(jù)元素或數(shù)據(jù)元素的映象)以“結(jié)點的序列”表示線性表

稱作鏈表

以線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地址，稱作線性表的頭指針。頭結(jié)點

a1a2…...an^頭指針頭指針

有時為了操作方便，在第一個結(jié)點之前虛加一個“頭結(jié)點”，以指向頭結(jié)點的指針為鏈表的頭指針。空指針線性表為空表時，頭結(jié)點的指針域為空

在單鏈表中刪除第

i個結(jié)點的基本操作為:找到線性表中第i-1個結(jié)點，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq

1.雙向鏈表其它形式的鏈表typedefstructDuLNode{ElemTypedata;

//數(shù)據(jù)域

structDuLNode*prior;

//指向前驅(qū)的指針域

structDuLNode*next;

//

指向后繼的指針域}

DuLNode,*DuLinkList;

最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表a1a2…...an2.循環(huán)鏈表

和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。雙向循環(huán)鏈表空表非空表a1a2…...an第三章

棧和隊列一、棧的類型定義和實現(xiàn)二、隊列的類型定義和實現(xiàn)通常稱，棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。

線性表棧隊列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和隊列是兩種常用的數(shù)據(jù)類型Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e為新的棧頂元素。

a1a2ane……Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：刪除S的棧頂元素，并用e返回其值。a1a2anan-1

……

棧類型的實現(xiàn)順序棧鏈棧

EnQueue(&Q,e)

初始條件：隊列Q已存在。

操作結(jié)果：插入元素e為Q的新的隊尾元素。a1a2ane……

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。a1a2an……

隊列類型的實現(xiàn)鏈隊列——鏈式映象循環(huán)隊列——順序映象typedefstruct{//鏈隊列類型

QueuePtrfront;//隊頭指針

QueuePtrrear;//隊尾指針}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空隊列#defineMAXQSIZE100//最大隊列長度

typedefstruct{QElemType*base;//動態(tài)分配存儲空間

intfront;//頭指針，若隊列不空，

//指向隊列頭元素

intrear;//尾指針，若隊列不空，指向

//隊列尾元素的下一個位置

}SqQueue;循環(huán)隊列——順序映象第四章

串一、串的數(shù)據(jù)類型定義二、串的表示與實現(xiàn)一、串的定長順序存儲表示二、串的堆分配存儲表示三、串的塊鏈存儲表示串的塊鏈存儲表示也可用鏈表來存儲串值，由于串的數(shù)據(jù)元素是一個字符，它只有8位二進制數(shù)，因此用鏈表存儲時，通常一個結(jié)點中存放的不是一個字符，而是一個子串。存儲密度

=數(shù)據(jù)元素所占存儲位實際分配的存儲位第五章

數(shù)組與廣義表一、數(shù)組的類型定義和實現(xiàn)二、廣義表的類型定義和實現(xiàn)數(shù)組的順序表示和實現(xiàn)

類型特點:1)只有引用型操作，沒有加工型操作；2)數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。

有兩種順序映象的方式:1)以行序為主序(低下標優(yōu)先)；2)以列序為主序(高下標優(yōu)先)。例如：

稱為基地址或基址。以“行序為主序”的存儲映象二維數(shù)組A中任一元素ai,j

的存儲位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲位置的映象關系

稱為n維數(shù)組的映象函數(shù)。數(shù)組元素的存儲位置是其下標的線性函數(shù)。其中cn=L，ci-1=bi×ci,1<in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n假設m行n列的矩陣含t個非零元素，則稱為稀疏因子。通常認為

0.05的矩陣為稀疏矩陣。稀疏矩陣的壓縮存儲何謂稀疏矩陣？十字鏈表30050-100200011314522-1312^^^^^^^廣義表是遞歸定義的線性結(jié)構(gòu)，LS=(1,2,,n)其中：i

或為原子或為廣義表例如:A=()F=(d,(e))D=((a,(b,c)),F)C=(A,D,F)B=(a,B)=(a,(a,(a,,)))廣義表是一個多層次的線性結(jié)構(gòu)例如：D=(E,F)其中:

E=(a,

(b,

c))

F=(d,(e))DEFa()d()bce第六章

樹和二叉樹一、樹和二叉樹的類型定義二、二叉樹的遍歷三、哈夫曼樹與哈夫曼編碼~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點

(無前驅(qū))最后一個數(shù)據(jù)元素

(無后繼)多個葉子結(jié)點

(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)結(jié)點:結(jié)點的度:樹的度:葉子結(jié)點:分支結(jié)點:數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM(從根到結(jié)點的)路徑：孩子結(jié)點、雙親結(jié)點兄弟結(jié)點、堂兄弟祖先結(jié)點、子孫結(jié)點結(jié)點的層次:樹的深度：

由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL假設根結(jié)點的層次為1，第l層的結(jié)點的子樹根結(jié)點的層次為l+1樹中葉子結(jié)點所在的最大層次

二叉樹或為空樹，或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點左子樹右子樹兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應。123456789101112131415abcdefghij

性質(zhì)1：

在二叉樹的第i

層上至多有2i-1個結(jié)點。(i≥1)用歸納法證明：

歸納基：

歸納假設：

歸納證明：i=1

層時，只有一個根結(jié)點：

2i-1=20=1；假設對所有的j，1≤j

i，命題成立；二叉樹上每個結(jié)點至多有兩棵子樹，則第i層的結(jié)點數(shù)=2i-22=2i-1

。性質(zhì)2：

深度為k的二叉樹上至多含2k-1個結(jié)點（k≥1）。證明：

基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點數(shù)至多為

20+21+

+2k-1=2k-1

。

性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子結(jié)點、n2個度為

2

的結(jié)點，則必存在關系式：n0=n2+1。證明：設二叉樹上結(jié)點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。

性質(zhì)4：

具有n個結(jié)點的完全二叉樹的深度為

log2n+1。證明：設完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1≤n<2k

即

k-1≤log2n<k

因為k只能是整數(shù)，因此，k=log2n

+1。性質(zhì)5：若對含n個結(jié)點的完全二叉樹從上到下且從左至右進行1

至n

的編號，則對完全二叉樹中任意一個編號為i

的結(jié)點：

(1)若i=1，則該結(jié)點是二叉樹的根，無雙親，否則，編號為i/2的結(jié)點為其雙親結(jié)點；

(2)若2i>n，則該結(jié)點無左孩子，

否則，編號為2i的結(jié)點為其左孩子結(jié)點；

(3)若2i+1>n，則該結(jié)點無右孩子結(jié)點，

否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示例如:ABCDEF

ABDCEF

0123456789101112131401326二、二叉樹的鏈式存儲表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表

“遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，

每個結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法哈夫曼樹與

哈夫曼編碼

最優(yōu)樹的定義

如何構(gòu)造最優(yōu)樹

前綴編碼

最優(yōu)樹的定義樹的路徑長度定義為：

樹中每個結(jié)點的路徑長度之和。

結(jié)點的路徑長度定義為：

從根結(jié)點到該結(jié)點的路徑上分支的數(shù)目。

樹的帶權(quán)路徑長度定義為：

樹中所有葉子結(jié)點的帶權(quán)路徑長度之和

WPL(T)=wklk(對所有葉子結(jié)點)。

在所有含n個葉子結(jié)點、并帶相同權(quán)值的m叉樹中，必存在一棵其帶權(quán)路徑長度取最小值的樹，稱為“最優(yōu)樹”。例如：

指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。前綴編碼

利用赫夫曼樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。第七章

圖一、圖的存儲表示二、圖的遍歷三、最小生成樹與最短路徑頂點的出度:以頂點v為弧尾的弧的數(shù)目；ABECF對有向圖來說，頂點的入度:以頂點v為弧頭的弧的數(shù)目。頂點的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3有向圖的鄰接矩陣為非對稱矩陣ABECF142301201234ABCDE有向圖的鄰接表ABECF可見，在有向圖的鄰接表中不易找到指向該頂點的弧。圖的遍歷

從圖中某個頂點出發(fā)游歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。深度優(yōu)先搜索廣度優(yōu)先搜索最小生成樹

假設要在n個城市之間建立通訊聯(lián)絡網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？問題：

構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）該問題等價于：算法一：（普里姆算法）兩點之間的

最短路徑問題

求從某個源點到其余各點的最短路徑

每一對頂點之間的最短路徑

求從源點到其余各點的最短路徑的算法的基本思想:

依最短路徑的長度遞增的次序求得各條路徑源點v1…其中，從源點到頂點v的最短路徑是所有最短路徑中長度最短者。v2第九章

查找一、靜態(tài)查找表二、動態(tài)查找樹表三、哈希表(n)(1)(n)(1)(nlogn)綜合上一節(jié)討論的幾種查找表的特性：查找插入刪除無序順序表

無序線性鏈表有序順序表

有序線性鏈表

靜態(tài)查找樹表(n)(n)(logn)(n)(logn)(1)(1)(n)(1)(nlogn)（1）若它的左子樹不空，則左子樹上

所有結(jié)點的值均小于根結(jié)點的值；二叉排序樹：

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（3）它的左、右子樹也都分別是二叉排序樹。（2）若它的右子樹不空，則右子樹上

所有結(jié)點的值均大于根結(jié)點的值；

二叉平衡樹是二叉查找樹的另一種形式，其特點為：

樹中每個結(jié)點的左、右子樹深度之差的絕對值不大于1。例如:548254821是平衡樹不是平衡樹查找表的各種結(jié)構(gòu)的共同特點：記錄在表中的位置和它的關鍵字之間不存在一個確定的關系，哈希表是什么？

查找的過程為給定值依次和關鍵字集合中各個關鍵字進行比較，

查找的效率取決于和給定值進行比較的關鍵字個數(shù)。構(gòu)造哈希函數(shù)的方法

對數(shù)字的關鍵字可有下列構(gòu)造方法：

若是非數(shù)字關鍵字，則需先對其進行數(shù)字化處理。1.

直接定址法3.平方取中法5.除留余數(shù)法4.折疊法6.隨機數(shù)法2.數(shù)字分析法處理沖突的方法

“處理沖突”的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。1.開放定址法2.鏈地址法第十章

排序一、排序的定義二、內(nèi)部排序方法的分類一、什么是排序？排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將下列關鍵字序列52,49,80,36,14,58,61,23