基本概念

? 數(shù)據(jù)

數(shù)據(jù)是信息的載體，在計算機科學中是指所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。

? 數(shù)據(jù)元素

數(shù)據(jù)元素也稱為結點，是表示數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。

? 數(shù)據(jù)項

數(shù)據(jù)項是構成數(shù)據(jù)元素的不可分割的最小單位。

? 數(shù)據(jù)對象

數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。

注意：在不產(chǎn)生混淆的情況下，將數(shù)據(jù)對象簡稱為數(shù)據(jù)。

? 數(shù)據(jù)結構

數(shù)據(jù)結構是指相互之間存在一定關系的數(shù)據(jù)元素的集合，即數(shù)據(jù)結構是一個二元組DataStructure = (D, R)，其中D是數(shù)據(jù)元素的集合，R是D上關系的集合。按照視點的不同，數(shù)據(jù)結構分為邏輯結構和存儲結構。

? 數(shù)據(jù)的邏輯結構

數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間邏輯關系的整體。根據(jù)數(shù)據(jù)元素之間邏輯關系的不同，數(shù)據(jù)結構分為四類：

⑴ 集合：數(shù)據(jù)元素之間就是“屬于同一個集合”，除此之外，沒有任何關系；

⑵ 線性結構：數(shù)據(jù)元素之間存在著一對一的線性關系；

⑶ 樹結構：數(shù)據(jù)元素之間存在著一對多的層次關系；

⑷ 圖結構：數(shù)據(jù)元素之間存在著多對多的任意關系。

注意：數(shù)據(jù)結構分為兩類：線性結構和非線性結構。

? 數(shù)據(jù)的存儲結構

數(shù)據(jù)的存儲結構又稱為物理結構，是數(shù)據(jù)及其邏輯結構在計算機中的表示。通常有兩種存儲結構：順序存儲結構和鏈接存儲結構。

順序存儲結構的基本思想是：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關系是由元素的存儲位置來表示的。

鏈接存儲結構的基本思想是：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關系是用指針來表示的。

注意：存儲結構除了存儲數(shù)據(jù)元素之外，必須存儲數(shù)據(jù)元素之間的邏輯關系。

? 抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型是一個數(shù)據(jù)結構以及定義在該結構上的一組操作的總稱。抽象數(shù)據(jù)類型提供了使用和實現(xiàn)兩個不同的視圖，實現(xiàn)了封裝和信息隱藏。

? 算法的定義

通俗地講，算法是解決問題的方法，嚴格地說，算法是對特定問題求解步驟的一種描述，是指令的有限序列。

? 算法的特性

⑴ 輸入：一個算法有零個或多個輸入（即算法可以沒有輸入），這些輸入通常取自于某個特定的對象集合。

⑵ 輸出：一個算法有一個或多個輸出（即算法必須要有輸出），通常輸出與輸入之間有著某種特定的關系。

⑶ 有窮性：一個算法必須總是（對任何合法的輸入）在執(zhí)行有窮步之后結束，且每一步都在有窮時間內(nèi)完成。

⑷ 確定性：算法中的每一條指令必須有確切的含義，不存在二義性。并且，在任何條件下，對于相同的輸入只能得到相同的輸出。

⑸ 可行性：算法描述的操作可以通過已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)。

? 線性表的定義

線性表簡稱表，是零個或多個具有相同類型的數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素的個數(shù)稱為線性表的長度，長度等于零時稱為空表。

? 線性表的邏輯關系

在一個非空表L＝(a1，a2，……，an)中，任意一對相鄰的數(shù)據(jù)元素ai-1和ai之間（1＜i≤n）存在序偶關系（ai-1，ai），且ai-1稱為ai的前驅(qū)，ai稱為ai-1的后繼。在這個序列中，a1無前驅(qū)，an無后繼，其它每個元素有且僅有一個前驅(qū)和一個后繼。

? 順序表的存儲結構定義

用MaxSize表示數(shù)組的長度，順序表的存儲結構定義如下：

#define MaxSize 100

typedef struct

{

ElemType data[MaxSize]; // ElemType表示不確定的數(shù)據(jù)類型

int length; //length表示線性表的長度

} SeqList;

? 順序表是隨機存取結構

設順序表的每個元素占用c個存儲單元，則第i個元素的存儲地址為：

LOC(ai)= LOC(a1)＋(i－1)×c

? 順序表的優(yōu)缺點

順序表利用了數(shù)組元素在物理位置上的鄰接關系來表示線性表中數(shù)據(jù)元素之間的邏輯關系，這使得順序表具有下列優(yōu)點：

⑴ 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間；

⑵ 可以快速地存取表中任一位置的元素（即隨機存?。?/p>

同時，順序表也具有下列缺點：

⑴ 插入和刪除操作需移動大量元素。在順序表上做插入和刪除操作，等概率情況下，平均要移動表中一半的元素。

⑵ 表的容量難以確定。由于數(shù)組的長度必須事先確定，因此，當線性表的長度變化較大時，難以確定合適的存儲規(guī)模。

⑶ 造成存儲空間的“碎片”。數(shù)組要求占用連續(xù)的存儲空間，即使存儲單元數(shù)超過所需的數(shù)目，如果不連續(xù)也不能使用，造成存儲空間的“碎片”現(xiàn)象。

? 單鏈表的存儲結構定義

單鏈表的存儲結構定義如下：

Struct Node

{ ElemType data; // ElemType表示不確定的數(shù)據(jù)類型

struct Node *next;

} *first; //first為單鏈表的頭指針

? 雙鏈表的存儲結構定義

雙鏈表存儲結構定義如下：

struct DulNode

{

ElemType data; // ElemType表示不確定的數(shù)據(jù)類型

struct DulNode *prior, *next; // prior為前驅(qū)指針域，next為后繼指針域

} *first; //first表示雙鏈表的頭指針

? 棧的定義

棧是限定僅在表尾進行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧。

? 棧的操作特性

棧的操作具有后進先出的特性。

? 隊列的定義

隊列是只允許在一端進行插入操作，而另一端進行刪除操作的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。

? 隊列的操作特性

隊列的操作具有先進先出的特性。

? 循環(huán)隊列中解決隊空隊滿的判斷條件

方法一：附設一個存儲隊列中元素個數(shù)的變量num，當num=0時隊空，當num=QueueSize時為隊滿；

方法二：修改隊滿條件，浪費一個元素空間，隊滿時數(shù)組中只有一個空閑單元；即隊空的條件是front=rear，隊滿的條件是(rear+1) % QueueSize=front，隊列長度為(rear-front+QueueSize) % QueueSize。

方法三：設置標志flag，當front=rear且flag=0時為隊空，當front=rear且flag=1時為隊滿。

? 串的定義

串是零個或多個字符組成的有限序列。

? 空格串和空串的定義

只包含空格的串稱為空格串。串中所包含的字符個數(shù)稱為串的長度，長度為0的串稱空串，記作 " "。

? 串的比較

串的比較是通過組成串的字符之間的比較來進行的。

給定兩個串：

X="x1x2…xn"

Y="y1y2…ym"

則當n=m且x1=y1，…，xn=ym時，稱X=Y；

當下列條件之一成立時，稱X＜Y：

⑴ n＜m，且xi=yi（i=1，2，…，n）；

⑵ 存在某個k≤min(m，n)，使得xi=yi（i=1，2，…，k-1），xk＜yk。

? 改進的模式匹配算法中next[j]的求法

用next[j]表示tj對應的k值（1≤j≤m），其定義如下：

? 數(shù)組的基本操作

數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。因此，在數(shù)組中通常只有兩種操作：

⑴ 讀?。航o定一組下標，讀取相應的數(shù)組元素；

⑵ 修改：給定一組下標，存儲或修改相應的數(shù)組元素。

? 二維數(shù)組的尋址

按行優(yōu)先，設二維數(shù)組的行下標與列下標的范圍分別為［l1，h1］與［l2，h2］，則任一元素aij的存儲地址可由下式確定：

LOC(aij)＝LOC(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c

? 特殊矩陣的定義

特殊矩陣是指矩陣中有很多值相同的元素并且它們的分布有一定的規(guī)律。

? 矩陣壓縮存儲的基本思想

壓縮存儲的基本思想是：⑴ 為多個值相同的元素只分配一個存儲空間；⑵ 對零元素不分配存儲空間。

? 對稱矩陣的壓縮存儲中：下三角元素aij（i≥j）在一個數(shù)組SA中的下標為：k = i×(i-1)/2 + j-1。上三角中的元素aij（i＜j），則訪問和它對應的下三角中的元素aji即可，即：k = j×(j-1)/2 + i-1。

? 三角矩陣的壓縮存儲中：下三角矩陣中任一元素aij在一個數(shù)組SA中的下標k與i、j的對應關系為：

上三角矩陣元素aij在SA中的下標為：k =(i-1)×(2n-i+2)/2+(j-i)。

? 稀疏矩陣的壓縮存儲方式

三元組順序表和十字鏈表

? 三元組的定義

struct element

{

int row, col;

ElemType item

};

? 廣義表的定義

廣義表是n（n≥0）個數(shù)據(jù)元素的有限序列。

? 表頭

當廣義表LS非空時，稱第一個元素為LS的表頭；

? 表尾

稱廣義表LS中除去表頭后其余元素組成的廣義表為LS的。

? 長度

廣義表LS中的直接元素的個數(shù)稱為LS的長度；

? 深度

廣義表LS中括號的最大嵌套層數(shù)稱為LS的深度。

? 樹的定義

樹是n（n≥0）個結點的有限集合。當n＝0時，稱為空樹；任意一棵非空樹滿足以下條件：

⑴ 有且僅有一個特定的稱為根的結點；

⑵ 當n＞1時，除根結點之外的其余結點被分成m（m>0）個互不相交的有限集合T1，T2，…，Tm，其中每個集合又是一棵樹，并稱為這個根結點的子樹。

? 結點的度、樹的度

某結點所擁有的子樹的個數(shù)稱為該結點的度；樹中各結點度的最大值稱為該樹的度。

? 葉子結點、分支結點

度為0的結點稱為葉子結點，也稱為終端結點；度不為0的結點稱為分支結點，也稱為非終端結點。

? 孩子結點、雙親結點、兄弟結點

某結點的子樹的根結點稱為該結點的孩子結點；反之，該結點稱為其孩子結點的雙親

? 路徑、路徑長度

如果樹的結點序列n1, n2, …, nk滿足如下關系：結點ni是結點ni+1的雙親（1≤i＜k），則把n1, n2, …, nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度。

? 祖先、子孫

如果從結點x到結點y有一條路徑，那么x就稱為y的祖先，而y稱為x的子孫。

注意：某結點子樹中的任一結點都是該結點的子孫。

? 結點的層數(shù)、樹的深度（高度）

規(guī)定根結點的層數(shù)為1，對其余任何結點，若某結點在第k層，則其孩子結點在第k+1層；樹中所有結點的最大層數(shù)稱為樹的深度，也稱為樹的高度。

? 二叉樹的定義

二叉樹是n（n≥0）個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。

? 二叉樹的特點

二叉樹的特點是：⑴ 每個結點最多有兩棵子樹，所以二叉樹中不存在度大于2的結點；⑵ 子樹的次序不能任意顛倒，某結點即使只有一棵子樹也要區(qū)分是左子樹還是右子樹。

注意：二叉樹和樹是兩種樹結構。

? 二叉樹的基本形態(tài)

二叉樹具有五種基本形態(tài)：⑴ 空二叉樹；⑵ 只有一個根結點；⑶ 根結點只有左子樹；⑷ 根結點只有右子樹；⑸ 根結點既有左子樹又有右子樹。

? 斜樹

所有結點都只有左子樹的二叉樹稱為左斜樹；所有結點都只有右子樹的二叉樹稱為右斜樹；左斜樹和右斜樹統(tǒng)稱為斜樹。

斜樹的特點：①每一層只有一個結點，即只有度為1和度為0的結點并且只有一個葉子結點；② 斜樹的結點個數(shù)與其深度相同。

? 滿二叉樹

在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。

滿二叉樹的特點：① 葉子結點都在最下一層；② 只有度為0和度為2的結點。

? 完全二叉樹

對一棵具有n個結點的二叉樹按層序編號，如果編號為i（1≤i≤n）的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中的位置完全相同，則這棵二叉樹稱為完全二叉樹。

完全二叉樹的特點是：① 葉子結點只能出現(xiàn)在最下兩層，且最下層的葉子結點都集中在左面連續(xù)的位置；② 如果有度為1的結點，只可能有一個，且該結點只有左孩子。

? 二叉樹的基本性質(zhì)

性質(zhì)1 二叉樹的第i層上最多有2i-1個結點（i≥1）。

性質(zhì)2 在一棵深度為k的二叉樹中，最多有2k-1個結點，最少有k個結點。

性質(zhì)3 在一棵二叉樹中，如果葉子結點的個數(shù)為n0，度為2的結點個數(shù)為n2，則

n0＝n2＋1。

性質(zhì)4 具有n個結點的完全二叉樹的深度為。

性質(zhì)5 對一棵具有n個結點的完全二叉樹中的結點從1開始按層序編號，則對于任意的編號為i（1≤i≤n）的結點（簡稱為結點i），有：

⑴ 如果i＞1，則結點i的雙親的編號為

；否則結點i是根結點，無雙親；

⑵ 如果2i≤n，則結點i的左孩子的編號為2i；否則結點i無左孩子；

⑶ 如果2i＋1≤n，則結點i的右孩子的編號為2i＋1；否則結點i無右孩子。

? 二叉樹的存儲

包括：二叉樹的順序存儲和二叉樹的鏈式存儲。

二叉鏈表的存儲結構定義如下：

struct BiNode

{

ElemType data;

BiNode *lchild, *rchild;

} *root; //root表示二叉鏈表的頭指針

struct TriNode

{

ElemType data;

TriNode *lchild, *rchild, *parent; // parent指向該結點的雙親

} *root; //三叉鏈表的頭指針

? 遍歷的含義

所謂遍歷就是無重復無遺漏地訪問。二叉樹的遍歷是指從根結點出發(fā)，按照某種次序訪問二叉樹中的所有結點，使得每個結點被訪問一次且僅被訪問一次。

? 二叉樹的遍歷次序定義

前序遍歷（或稱前根遍歷、先序遍歷）

若二叉樹為空，則空操作返回；否則

⑴ 訪問根結點；

⑵ 前序遍歷根結點的左子樹；

⑶ 前序遍歷根結點的右子樹。

中序遍歷（或稱中根遍歷）

若二叉樹為空，則空操作返回；否則

⑴ 中序遍歷根結點的左子樹；

⑵ 訪問根結點；

⑶ 中序遍歷根結點的右子樹。

后序遍歷（或稱后根遍歷）

若二叉樹為空，則空操作返回；否則

⑴ 后序遍歷根結點的左子樹；

⑵ 后序遍歷根結點的右子樹；

⑶ 訪問根結點。

層序遍歷

二叉樹的層序遍歷是從二叉樹的第一層（根結點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y點逐個訪問。

? 線索二叉樹的定義

在一個具有n個結點的二叉鏈表中，利用n+1個空指針域存放指向該結點在某種遍歷序列中的前驅(qū)和后繼結點的指針，這些指向前驅(qū)和后繼結點的指針稱為線索，加上線索的二叉樹稱為線索二叉樹，相應地，加上線索的二叉鏈表稱為線索鏈表。

? 線索二叉樹的存儲結構定義

線索鏈表中的結點定義如下：

enum flag {Child, Thread}; //枚舉類型，枚舉常量Child=0，Thread=1

struct ThrNode

{

ElemType data; // ElemType表示不確定的數(shù)據(jù)類型

ThrNode *lchild, *rchild;

flag ltag, rtag;

}*root; //root表示線索鏈表的頭指針

? 樹的存儲結構

包括：雙親表示法、孩子表示法、孩子兄弟表示法。

雙親表示法的存儲結構定義如下：

#define MaxSize 100; //樹中最大結點個數(shù)

struct PNode //數(shù)組元素的類型

{

ElemType data; //樹中結點的數(shù)據(jù)信息，

int parent; //該結點的雙親在數(shù)組中的下標

};

PNode Tree[MaxSize];

孩子表示法的存儲結構定義如下：

struct CTNode //孩子結點

{

int child;

CTNode *next;

};

struct CBNode //表頭結點

{

ElemType data;

CTNode *firstchild; //指向孩子鏈表的頭指針

};

孩子兄弟表示法又稱為二叉鏈表表示法，存儲結構定義如下：

struct TNode

{

ElemType data; // ElemType表示不確定的數(shù)據(jù)類型

TNode *firstchild; //firstchild指向該結點的第一個孩子

TNode *rightsib; //rightsib指向該結點的右兄弟

};

? 樹轉換為二叉樹

樹轉換為二叉樹的方法是：

⑴ 加線——樹中所有相鄰兄弟結點之間加一條連線；

⑵ 去線——對樹中的每個結點，只保留它與第一個孩子結點之間的連線，刪去它與其它孩子結點之間的連線；

⑶ 層次調(diào)整——以根結點為軸心，將樹順時針轉動一定的角度，使之層次分明。

? 森林轉換為二叉樹

森林轉換為二叉樹的方法如下：

⑴ 將森林中的每棵樹轉換成二叉樹；

⑵ 從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連起來后，所得到的二叉樹就是由森林轉換的二叉樹。

? 二叉樹轉換為樹或森林

樹和森林轉換為二叉樹的過程是可逆的，將一棵二叉樹還原為樹或森林的方法如下：

⑴ 加線——若某結點x是其雙親y的左孩子，則把結點x的右孩子、右孩子的右孩子、……，都與結點y用線連起來；

⑵ 去線——刪去原二叉樹中所有的雙親結點與右孩子結點的連線；

⑶ 層次調(diào)整——整理由⑴、⑵兩步所得到的樹或森林，使之層次分明。

樹的遍歷序列與二叉樹的遍歷序列之間的對應關系

根據(jù)樹與二叉樹的轉換關系以及樹和二叉樹遍歷的操作定義可知，樹的遍歷序列與由樹轉化成的二叉樹的遍歷序列之間具有如下對應關系：樹的前序遍歷序列等于二叉樹的前序遍歷序列，樹的后序遍歷序列等于二叉樹的中序遍歷序列。

? 哈夫曼樹中葉子結點的權值

葉子結點的權值是指對葉子結點賦予的一個有意義的數(shù)值量。

? 二叉樹的帶權路徑長度

設二叉樹具有n個帶權值的葉子結點，從根結點到各個葉子結點的路徑長度與相應葉子結點權值的乘積之和稱做二叉樹的帶權路徑長度，記為：

WPL=

其中，wk為第k個葉子結點的權值；lk為從根結點到第k個葉子結點的路徑長度。

? 哈夫曼樹定義

給定一組具有確定權值的葉子結點，可以構造出不同的二叉樹，將其中帶權路徑長度最小的二叉樹稱為哈夫曼樹，也稱為最優(yōu)二叉樹。

? 哈夫曼算法的基本思想

哈夫曼算法的基本思想是：

⑴ 初始化：由給定的n個權值{w1，w2，…，wn}構造n棵只有一個根結點的二叉樹，從而得到一個二叉樹集合F＝{T1，T2，…，Tn}；

⑵ 選取與合并：在F中選取根結點的權值最小的兩棵二叉樹分別作為左、右子樹構造一棵新的二叉樹，這棵新二叉樹的根結點的權值為其左、右子樹根結點的權值之和；

⑶ 刪除與加入：在F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；

⑷ 重復⑵、⑶兩步，當集合F中只剩下一棵二叉樹時，這棵二叉樹便是哈夫曼樹。

? 圖的定義

圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：

G=(V，E)

其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中頂點之間邊的集合。

? 無向圖與有向圖

若頂點vi和vj之間的邊沒有方向，則稱這條邊為無向邊，用無序偶對(vi，vj)來表示；若從頂點vi到vj的邊有方向，則稱這條邊為有向邊（也稱為弧），用有序偶對<vi, vj>來表示，vi稱為弧尾，vj稱為弧頭。如果圖的任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖，否則稱該圖為有向圖。

? 簡單圖

若不存在頂點到其自身的邊，且同一條邊不重復出現(xiàn)，則稱這樣的圖為簡單圖。

? 鄰接、依附

在無向圖中，對于任意兩個頂點vi和vj，若存在邊(vi，vj)，則稱頂點vi和vj互為鄰接點，同時稱邊(vi，vj)依附于頂點vi和vj。

在有向圖中，對于任意兩個頂點vi和vj，若存在弧<vi，vj>，則稱頂點vj是vi的鄰接點，同時稱弧<vi，vj>依附于頂點vi和vj。

? 無向完全圖、有向完全圖

在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。含有n個頂點的無向完全圖有n×(n-1)/2條邊。

在有向圖中，如果任意兩頂點之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。含有n個頂點的有向完全圖有n×(n-1)條邊。

? 稠密圖、稀疏圖

稱邊數(shù)很少的圖為稀疏圖，反之，稱為稠密圖。

? 頂點的度、入度、出度

在無向圖中，頂點v的度是指依附于該頂點的邊的個數(shù)，記為TD(v)。在具有n個頂點e條邊的無向圖中，有下式成立：

在有向圖中，頂點v的入度是指以該頂點為弧頭的弧的個數(shù)，記為ID(v)；頂點v的出度是指以該頂點為弧尾的弧的個數(shù)，記為OD(v)。在具有n個頂點e條邊的有向圖中，有下式成立：

? 連通圖、連通分量

在無向圖中，若任意頂點vi和vj(i≠j)之間有路徑，則稱該圖是連通圖。非連通圖的極大連通子圖稱為連通分量。

? 強連通圖、強連通分量

在有向圖中，對任意頂點vi和vj (i≠j)，若從頂點vi到vj和從頂點vj到vi均有路徑，則稱該有向圖是強連通圖。非強連通圖的極大強連通子圖稱為強連通分量。

? 鄰接矩陣的存儲結構定義

假設圖G＝(V，E)有n個頂點，則鄰接矩陣是一個n×n的方陣，定義為：

鄰接矩陣的存儲結構定義如下：

#define MaxSize 10

typedef struct

{

ElemType vertex[MaxSize]; //存放圖中頂點的信息，ElemType表示不確定的數(shù)據(jù)類型

int arc[MaxSize][MaxSize]; //存放圖中邊的信息

int vertexNum, arcNum; //圖的頂點數(shù)和邊數(shù)

} MGraph;

? 鄰接表的存儲結構定義

鄰接表是一種順序存儲與鏈接存儲相結合的存儲方法，具體方法為：將頂點vi的所有鄰接點鏈成一個單鏈表，稱為頂點vi的邊表（對于有向圖則稱為出邊表），邊表的頭指針和頂點的數(shù)據(jù)信息采用順序存儲（稱為頂點表）。所以，在鄰接表中存在兩種結點：頂點表結點和邊表結點。

其中，vertex：數(shù)據(jù)域，存放頂點信息；

firstedge：指針域，邊表的頭指針；

adjvex：鄰接點域，存放邊該頂點的鄰接點在頂點表中的下標；

next：指針域，指向邊表中的下一個結點。

鄰接表的存儲結構定義如下：

struct ArcNode //定義邊表結點

{

int adjvex; //鄰接點域

ArcNode *next;

};

struct VertexNode //定義頂點表結點

{

ElemType vertex; // ElemType表示不確定的數(shù)據(jù)類型

ArcNode *firstedge;

};

#define MaxSize 10

typedef struct

{

VertexNode adjlist[MaxSize]; //頂點表

int vertexNum, arcNum; //圖的頂點數(shù)和邊數(shù)

} ALGraph;

? 圖的遍歷次序定義

深度優(yōu)先遍歷

從圖中某頂點v出發(fā)進行深度優(yōu)先遍歷的基本思想是：

① 訪問頂點v；

② 從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進行深度優(yōu)先遍歷；

③ 重復上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。

廣度優(yōu)先遍歷

從圖中某頂點v出發(fā)進行廣度優(yōu)先遍歷的基本思想是：

① 訪問頂點v；

② 依次訪問v的各個未被訪問的鄰接點v1，v2，……，vk；

③ 分別從v1，v2，…，vk出發(fā)依次訪問它們未被訪問的鄰接點，直至圖中所有與頂點v有路徑相通的頂點都被訪問到。

? 最小生成樹的定義

設G=(V，E)是一個無向連通網(wǎng)，生成樹上各邊的權值之和稱為該生成樹的代價，在G的所有生成樹中，代價最小的生成樹稱為最小生成樹。

? 普里姆（Prim）算法的基本思想

設G=(V，E)是一個無向連通網(wǎng)，令T=(U，TE)是G的最小生成樹。T的初始狀態(tài)為U={v0}（v0∈V），TE={ }，然后重復執(zhí)行下述操作：在所有u∈U，v∈V-U的邊中找一條代價最小的邊(u，v)并入邊集TE，同時v并入頂點集U，直至U=V為止。

? 克魯斯卡爾（Kruskal）算法的基本思想

設無向連通網(wǎng)為G＝(V，E)，令G的最小生成樹為T=(U，TE)，其初態(tài)為U＝V，TE={}，然后按照邊的權值由小到大的順序，依次考察邊集E中的各條邊。若被考察邊的兩個頂點屬于T的兩個不同的連通分量，則將此邊加入到TE中，同時把兩個連通分量連接為一個連通分量；若被考察邊的兩個頂點屬于同一個連通分量，則舍去此邊，以免造成回路。如此下去，當T中的連通分量個數(shù)為1時，此連通分量便為G的一棵最小生成樹。

? 迪杰斯特拉（Dijkstra）算法的基本思想

設置集合S存放已經(jīng)找到最短路徑的頂點，S的初始狀態(tài)只包含源點v，對vi∈V-S，假設從源點v到vi的有向邊為最短路徑。以后每求得一條最短路徑v, …, vk，就將vk加入集合S中，并將路徑v, …, vk , vi與原來的假設相比較，取路徑長度較小者為當前最短路徑。重復上述過程，直到集合V中全部頂點加入到集合S中。

? Floyd算法的基本思想

假設從vi到vj的?。ㄈ魪膙i到vj的弧不存在，則將其弧的權值看成∞）是最短路徑，然后進行n次試探。若vi, …, vk和vk, …, vj分別是從vi 到vk和從vk到vj中間頂點的序號不大于k-1的最短路徑，則將vi, …, vk, …, vj和已經(jīng)得到的從vi到vj中間頂點的序號不大于k-1的最短路徑相比較，取長度較短者為從vi到vj中間頂點的序號不大于k的最短路徑。

? AOV網(wǎng)的定義

在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關系，稱這樣的有向圖為頂點表示活動的網(wǎng)，簡稱AOV網(wǎng)。

? 拓撲序列的定義

設G=(V，E)是一個具有n個頂點的有向圖，V中的頂點序列v1, v2, …, vn稱為一個拓撲序列，當且僅當滿足下列條件：若從頂點vi到vj有一條路徑，則在頂點序列中頂點vi必在頂點vj之前。

? 拓撲排序的基本思想

對AOV網(wǎng)進行拓撲排序的基本思想是：

⑴ 從AOV網(wǎng)中選擇一個沒有前驅(qū)的頂點并且輸出它；

⑵ 從AOV網(wǎng)中刪去該頂點，并且刪去所有以該頂點為尾的??；

⑶ 重復上述兩步，直到全部頂點都被輸出，或AOV網(wǎng)中不存在沒有前驅(qū)的頂點。

? 查找算法的時間性能

查找算法用關鍵碼的比較次數(shù)來度量查找算法的時間性能。對于查找成功的情況，將關鍵碼比較次數(shù)的數(shù)學期望值定義為平均查找長度，即：

ASL

其中，n表示問題規(guī)模，即查找集合中的記錄個數(shù)；pi表示查找第i個記錄的概率；ci表示查找第i個記錄所需的關鍵碼的比較次數(shù)。

? 順序查找算法的時間復雜度

對于具有n個記錄的順序表，查找第i個記錄時，需進行n-i+1次關鍵碼的比較。設每個記錄的查找概率相等，查找成功時，順序查找的平均查找長度為：O (n)；查找不成功時，關鍵碼的比較次數(shù)是n+1次，則查找失敗的平均查找長度為O(n)。

? 順序查找的適用情況

順序查找對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可應用；對表中記錄的有序性也沒有要求，無論記錄是否按關鍵碼有序均可應用。

? 折半查找的適用情況

折半查找（也稱對半查找、對分查找、二分查找）要求線性表中的記錄必須按關鍵碼有序，并且必須采用順序存儲。

? 折半查找的基本思想

取有序表的中間記錄作為比較對象，則

（1）若給定值與中間記錄的關鍵碼相等，則查找成功；

（2）若給定值小于中間記錄的關鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；

（3）若給定值大于中間記錄的關鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。

不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。

? 折半查找的時間復雜度

具有n個結點的折半查找判定樹的深度為

。

最好情況：比較1次，即查找的關鍵碼是判定樹的根結點；

最壞情況：比較次數(shù)為

，即查找的關鍵碼是判定樹的最下一層結點；

平均情況：折半查找的平均時間復雜度為O(log2n)。

查找不成功的比較次數(shù)最多不超過樹的深度，最多為

次。

? 二叉排序樹的定義

二叉排序樹或者是一棵空的二叉樹，或者是具有下列性質(zhì)的二叉樹：

⑴ 若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；

⑵ 若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值；

⑶ 它的左右子樹也都是二叉排序樹。

? 二叉排序樹的查找性能

如果二叉排序樹是平衡的，則其查找效率為O(log2n)。如果二叉排序樹為一棵斜樹，則其查找效率為O(n)。因此，二叉排序樹的查找性能在O(log2n)和O(n)之間。

? 平衡二叉樹的定義

平衡二叉樹或者是一棵空的二叉排序樹，或者是具有下列性質(zhì)的二叉排序樹：

⑴ 根結點的左子樹和右子樹的深度最多相差1。

⑵ 根結點的左子樹和右子樹也都是平衡二叉樹。

? 構造平衡二叉樹的基本思想

在構造二叉排序樹的過程中，每當插入一個結點時，首先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。

? 平衡調(diào)整的四種類型

設結點A為最小不平衡子樹的根結點，對該子樹進行平衡化調(diào)整有以下四種情況：

⑴ LL型：結點x插在根結點A的左孩子的左子樹上。

⑵ RR型：結點x插在根結點A的右孩子的右子樹上。

⑶ LR型：結點x插在根結點A的左孩子的右子樹上。

⑷ RL型：結點x插在根結點A的右孩子的左子樹上。

? 散列查找的基本思想

散列查找也稱為哈希查找、Hash查找，其基本思想是：在記錄的存儲位置和它的關鍵碼之間建立一個確定的對應關系H，使得每個關鍵碼key和唯一的一個存儲位置H(key)相對應。在查找時，根據(jù)這個確定的對應關系找到給定值k的映射H(k)，若查找集合中存在這個記錄，則必定在H(k)的位置上。

? 散列查找的基本概念

采用散列技術將記錄存儲在一塊連續(xù)的存儲空間中，這塊連續(xù)的存儲空間稱為散列表，將關鍵碼映射為散列表中適當存儲位置的函數(shù)稱為散列函數(shù)，所得的存儲位置址稱為散列地址。

對于兩個不同的關鍵碼k1≠k2，有H(k1)＝H(k2)，即兩個不同的記錄需要存放在同一個存儲位置，這種現(xiàn)象稱為沖突，k1和k2相對于H稱做同義詞。

? 散列查找的關鍵問題

采用散列技術需要考慮的兩個關鍵問題是：

⑴ 散列函數(shù)的設計。如何設計一個簡單、均勻、存儲利用率高的散列函數(shù)。

⑵ 沖突的處理。如何采取合適的處理沖突方法來解決沖突。

? 處理沖突的方法

開放定址法

用開放定址法處理沖突得到的散列表叫做閉散列表。

所謂開放定址法，就是由關鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。

① 線性探測法

當發(fā)生沖突時，線性探測法從沖突位置的下一個位置起，依次尋找空的散列地址，即對于鍵值key，設H(key)=d，閉散列表的長度為m，則發(fā)生沖突時，尋找下一個散列地址的公式為：

Hi=(H(key)＋di) % m （di=1，2，…，m-1）。

線性探測法會出現(xiàn)非同義詞之間對同一個散列地址爭奪的現(xiàn)象，稱為堆積或聚集。

② 二次探測法

當發(fā)生沖突時，二次探測法尋找下一個散列地址的公式為：

Hi=(H(key)＋di)% m（di=12，－12，22，－22，…，q2，－q2且q≤m/2）

③ 隨機探測法

當發(fā)生沖突時，隨機探測法探測下一個散列地址的位移量是一個隨機數(shù)列，即尋找下一個散列地址的公式為：

Hi=(H(key)+di)% m （di是一個隨機數(shù)列，i=1，2，……，m-1）

拉鏈法（鏈地址法）

用拉鏈法處理沖突構造的散列表叫做開散列表。

拉鏈法的基本思想是：將所有散列地址相同的記錄，即所有關鍵碼為同義詞的記錄存儲在一個單鏈表中——稱為同義詞子表，在散列表中存儲的是所有同義詞子表的頭指針。

? 直接插入排序的基本思想

直接插入排序的基本思想是：依次將待排序序列中的每一個記錄插入到一個已排好序的序列中，直到全部記錄都排好序。

? 直接插入排序算法的性能

·時間性能

最好情況：待排序序列為正序，時間復雜度為O(n)；

最壞情況：待排序序列為逆序，時間復雜度為O(n2)。

平均情況：待排序序列中各種可能排列的概率相同，時間復雜度為O(n2)。

·空間性能

直接插入排序只需要一個記錄的輔助空間。

·穩(wěn)定性

直接插入排序是一種穩(wěn)定的排序方法。

? 希爾排序的基本思想

希爾排序的基本思想是：先將整個待排序記錄序列分割成若干個子序列，在子序列內(nèi)分別進行直接插入排序，待整個序列基本有序時，再對全體記錄進行一次直接插入排序。

? 希爾排序算法的性能

·時間性能

希爾排序算法的時間性能是所取增量的函數(shù)，其時間性能在O(n2)和O(nlog2n)之間，當n在某個特定范圍時，希爾排序的時間性能約為O(n1.3)。

·空間性能

希爾排序只需要一個記錄的輔助空間，用于暫存當前待插入的記錄。

·穩(wěn)定性

希爾排序是一種不穩(wěn)定的排序方法。

? 起泡排序的基本思想

起泡排序的基本思想是：兩兩比較相鄰記錄的關鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。

? 起泡排序算法的性能

·時間性能

最好情況：待排序記錄序列為正序，時間復雜度為O(n)；

最壞情況：待排序記錄序列為反序，時間復雜度為O(n2)；

平均情況：時間復雜度為O(n2)。

·空間性能

起泡排序只需要一個記錄的輔助空間，用來作為記錄交換的暫存單元。

·穩(wěn)定性

起泡排序是一種穩(wěn)定的排序方法。

? 快速排序的基本思想

快速排序又稱為分區(qū)交換排序，其基本思想是：首先選一個軸值（即比較的基準），將待排序記錄分割成獨立的兩部分，左側記錄的關鍵碼均小于或等于軸值，右側記錄的關鍵碼均大于或等于軸值，然后分別對這兩部分重復上述過程，直到整個序列有序。

? 快速排序的性能

·時間性能

最好情況：時間復雜度為O(nlog2n)。

最壞情況：待排序記錄序列為正序或逆序，時間復雜度為O(n2)。

平均情況：時間復雜度為O(nlog2n)。

·空間性能

最好情況下為O(log2n)；最壞情況下，棧的深度為O(n)；平均情況下，棧的深度為O(log2n)。

·穩(wěn)定性

快速排序是一種不穩(wěn)定的排序方法。

? 簡單選擇排序的基本思想

簡單選擇排序的基本思想是：第i趟（1≤i≤n-1）排序通過n-i次關鍵碼的比較，在n-i+1個記錄中選取關鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。

? 簡單選擇排序算法的性能

·時間性能

簡單選擇排序最好、最壞和平均的時間復雜度均為O(n2)。

·空間性能

在簡單選擇排序過程中，只需要一個用來作為記錄交換的暫存單元。

·穩(wěn)定性

簡單選擇排序是一種不穩(wěn)定的排序方法。

? 堆的定義

堆是具有下列性質(zhì)的完全二叉樹：每個結點的值都小于或等于其左右孩子結點的值（稱為小根堆）；或者每個結點的值都大于或等于其左右孩子結點的值（稱為大根堆）。

? 堆排序的基本思想

首先將待排序的記錄序列構造成一個堆（假設利用大根堆），此時，選出了堆中所有記錄的最大者即堆頂記錄，然后將它從堆中移走（通常將堆頂記錄和堆中最后一個記錄交換），并將剩余的記錄再調(diào)整成堆，這樣又找出了次大的記錄，以此類推，直到堆中只有一個記錄為止。

? 堆排序算法的性能

·時間性能

堆排序最好、最壞和平均的時間復雜度為O(nlog2n)。

·空間性能

在堆排序算法中，只需要一個用來交換的暫存單元。

·穩(wěn)定性

堆排序是一種不穩(wěn)定的排序方法。

? 二路歸并排序的基本思想

將若干個有序序列進行兩兩歸并，直至所有待排序記錄都在一個有序序列為止。

? 二路歸并排序算法的性能

·時間性能

歸并排序算法最好、最壞、平均的時間性能的時間代價是O(nlog2n)。

·空間性能

二路歸并排序在歸并過程中需要與原始記錄序列同樣數(shù)量的存儲空間，以便暫存歸并的中間結果，因此其空間復雜度為O(n)。

·穩(wěn)定性

二路歸并排序是一種穩(wěn)定的排序方法。