Chapter 1 線性表
線性表的邏輯結構
邏輯結構
邏輯定義
線性表（Linear List）是由n（n≥0）個數據元素（結點）a1，a2，…，an組成的有限序列。
① 數據元素的個數n定義為表的長度（n=0時稱為空表）。
② 將非空的線性表（n＞0）記作：（a1，a2，…，an）
③ 數據元素ai（1≤i≤n）只是個抽象符號，其具體含義在不同情況下可以不同。
邏輯結構特征
對于非空的線性表:
① 有且僅有一個開始結點a1，沒有直接前趨，有且僅有一個直接后繼a2；
② 有且僅有一個終結結點an，沒有直接后繼，有且僅有一個直接前趨an-1；
③ 其余的內部結點ai（2≤i≤n-1）都有且僅有一個直接前趨ai-1和一個ai+1。
順序存儲結構
順序表
順序表的定義
(1) 順序存儲方法
即把線性表的結點按邏輯次序依次存放在一組地址連續的存儲單元里的方法。
(2) 順序表（Sequential List）
用順序存儲方法存儲的線性表簡稱為順序表（Sequential List）。
結點ai 的存儲地址：LOC（ai）= LOC（a1）+（i-1）*c 1≤i≤n （每個結點所占用存儲空間大小亦相同，占用c個存儲單元）
順序表上的基本運算
鏈式存儲結構
單鏈表
鏈接方式存儲的線性表簡稱為鏈表（Linked List）。
鏈表的具體存儲表示為：
① 用一組任意的存儲單元來存放線性表的結點（這組存儲單元既可以是連續的，也可以是不連續的）
② 鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其后繼結點的地址（或位置）信息（稱為指針（pointer）或鏈(link)）
單鏈表的運算
1、建立單鏈表：（1） 頭插法建表（2） 尾插法建表（3）尾插法建帶頭結點的單鏈表
2、單鏈表的查找運算：（1）按序號查找（2） 按值查找
3、插入運算 4、刪除運算
循環鏈表 循環鏈表是一種首尾相接的鏈表。
1、循環鏈表
（1）單循環鏈表——在單鏈表中，將終端結點的指針域NULL改為指向表頭結點或開始結點即可。
（2）多重鏈的循環鏈表——將表中結點鏈在多個環上。
2、帶頭結點的單循環鏈表
3、僅設尾指針的單循環鏈表
用尾指針rear表示的單循環鏈表對開始結點a1和終端結點an
雙鏈表
雙向鏈表（Double Linked List）
雙（向）鏈表中有兩條方向不同的鏈，即每個結點中除next域存放后繼結點地址外，還增加一個指向其直接前趨的指針域prior。
順序表和鏈表的比較
分配方式：
前者：靜態分配；后者：動態分配
存取方式：
前者：隨機存取；后者：順序存取（掃描）
插入或刪除操作：
前者：需要移動近一半的節點；后者：只需要修改指針
Chapter 2棧與隊列
棧和隊列是兩種特殊的線性表，它們的邏輯結構和線性表相同，只是其運算規則較線性表有更多的限制，故又稱它們為運算受限的線性表
棧
棧的定義及基本運算
1、棧的定義
棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。
(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。
(2)當表中沒有元素時稱為空棧。
(3)棧為后進先出（Last In First Out）的線性表，簡稱為LIFO表。
2、棧的基本運算
（1）InitStack（S）
構造一個空棧S。
（2）StackEmpty（S）
判棧空。若S為空棧，則返回TRUE，否則返回FALSE。
（3）StackFull（S）
判棧滿。若S為滿棧，則返回TRUE，否則返回FALSE。
注意：
該運算只適用于棧的順序存儲結構。
（4）Push（S，x）
進棧。若棧S不滿，則將元素x插入S的棧頂。
（5）Pop（S）
退棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。
（6）StackTop（S）
取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態。
順序棧 棧的順序存儲結構簡稱為順序棧,它是運算受限的順序表。
1、 順序棧的類型定義
#define StackSize 100 //假定預分配的棧空間最多為100個元素
typedef char DataType;//假定棧元素的數據類型為字符
typedef struct{
DataType data[StackSize];
int top;
}SeqStack;
注意：
①順序棧中元素用向量存放
②棧底位置是固定不變的，可設置在向量兩端的任意一個端點
③棧頂位置是隨著進棧和退棧操作而變化的，用一個整型量top（通常稱top為棧頂指針）來指示當前棧頂位置
2、 順序棧的基本操作
前提條件：
設S是SeqStack類型的指針變量。若棧底位置在向量的低端，即S-＞data[0]是棧底元素。
（1） 進棧操作
進棧時，需要將S-＞top加1
注意：
①S-＞top==StackSize-1表示棧滿
②"上溢"現象--當棧滿時，再做進棧運算產生空間溢出的現象。
上溢是一種出錯狀態，應設法避免。
（2） 退棧操作
退棧時，需將S-＞top減1
注意：
①S-＞top<0表示空棧
②"下溢"現象——當棧空時，做退棧運算產生的溢出現象。
下溢是正常現象，常用作程序控制轉移的條件。
順序棧在進棧和退棧操作時的具體變化情況【參見動畫演示】
3、順序棧的基本運算
（1） 置棧空
void InitStack（SeqStack *S）
{//將順序棧置空
S->top=-1;
}
（2） 判棧空
int StackEmpty（SeqStack *S）
{
return S->top==-1;
}
（3） 判棧滿
int StackFull（SeqStack *SS）
{
return S->top==StackSize-1;
}
（4） 進棧
void Push（S，x）
{
if (StackFull(S))
Error("Stack overflow"); //上溢，退出運行
S->data[++S->top]=x;//棧頂指針加1后將x入棧
}
（5） 退棧
DataType Pop（S）
{
if(StackEmpty(S))
Error("Stack underflow"); //下溢，退出運行
return S->data[S->top--];//棧頂元素返回后將棧頂指針減1
}
（6） 取棧頂元素
DataType StackTop（S）
{
if(StackEmpty(S))
Error("Stack is empty");
return S->data[S->top];
}
鏈棧 棧的鏈式存儲結構稱為鏈棧。
2、鏈棧的基本運算
（1） 置棧空
Void InitStack(LinkStack *S)
{
S->top=NULL;
}
（2） 判棧空
int StackEmpty(LinkStack *S)
{
return S->top==NULL;
}
（3） 進棧
void Push(LinkStack *S,DataType x)
{//將元素x插入鏈棧頭部
StackNode *p=(StackNode *)malloc(sizeof(StackNode));
p->data=x;
p->next=S->top;//將新結點*p插入鏈棧頭部
S->top=p;
}
（4） 退棧
DataType Pop(LinkStack *S)
{
DataType x;
StackNode *p=S->top;//保存棧頂指針
if(StackEmpty(S))
Error("Stack underflow."); //下溢
x=p->data; //保存棧頂結點數據
S->top=p->next; //將棧頂結點從鏈上摘下
free(p);
return x;
}
（5） 取棧頂元素
DataType StackTop(LinkStack *S)
{
if(StackEmpty(S))
Error("Stack is empty.")
return S->top->data;
}
隊列
隊列的定義及基本運算
1、定義
隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表
（1）允許刪除的一端稱為隊頭（Front）。
（2）允許插入的一端稱為隊尾（Rear）。
（3）當隊列中沒有元素時稱為空隊列。
（4）隊列亦稱作先進先出（First In First Out）的線性表，簡稱為FIFO表。
順序隊列
（1）順序隊列的定義
隊列的順序存儲結構稱為順序隊列，順序隊列實際上是運算受限的順序表。
（2） 順序隊列的表示
①和順序表一樣，順序隊列用一個向量空間來存放當前隊列中的元素。
②由于隊列的隊頭和隊尾的位置是變化的，設置兩個指針front和rear分別指示隊頭元素和隊尾元素在向量空間中的位置，它們的初值在隊列初始化時均應置為0。
（3） 順序隊列的基本操作
①入隊時：將新元素插入rear所指的位置，然后將rear加1。
②出隊時：刪去front所指的元素，然后將front加1并返回被刪元素。
2、循環隊列
為充分利用向量空間，克服"假上溢"現象的方法是：將向量空間想象為一個首尾相接的圓環，并稱這種向量為循環向量。存儲在其中的隊列稱為循環隊列（Circular Queue）。
鏈隊列
1、 鏈隊列的定義
隊列的鏈式存儲結構簡稱為鏈隊列。它是限制僅在表頭刪除和表尾插入的單鏈表。
2、 鏈隊列的基本運算
棧和隊列的應用實例
棧的應用實例
隊列的應用實例
Chapter 3 串
串及其運算
串的基本概念：串（又稱字符串）是一種特殊的線性表，它的每個結點僅由一個字符組成。
串的基本運算
1、求串長
int strlen(char *s);//求串s的長度
【例】printf("%d",strlen(s1)); //輸出s1的串長12
2、串復制
char *strcpy(char *to,*from)；//將from串復制到to串中，并返回to開始處指針
【例】strcpy(s3,s1); //s3="dir/bin/appl",s1串不變
3、聯接
char *strcat(char *to,char *from);//將from串復制到to串的末尾，
//并返回to串開始處的指針
【例】strcat(s3,"/"); //s3="dir/bin/appl/"
strcat(s3,s2); //s3="dir/bin/appl/file.asm"
4、串比較
int strcmp(char *s1,char *s2);//比較s1和s2的大小，
//當s1<s2、s1>s2和s1=s2時，分別返回小于0、大于0和等于0的值
【例】result=strcmp("baker","Baker"); //result>0
result=strcmp("12","12"); //result=0
result=strcmp("Joe","joseph") //result<0
5、字符定位
char *strchr(char *s,char c);//找c在字符串s中第一次出現的位置，
//若找到，則返回該位置，否則返回NULL
【例】p=strchr(s2,'.'); //p指向"file"之后的位置
if(p) strcpy(p,".cpp"); //s2="file.cpp"
串的存儲結構
串的順序存儲：串的順序存儲結構簡稱為順序串。靜態存儲分配和動態存儲分配
串的鏈式存儲：用單鏈表方式存儲串值，串的這種鏈式存儲結構簡稱為鏈串。
串運算的實現
Chapter 4 多維數組
多維數組和廣義表是一種復雜的非線性結構，它們的邏輯特征是：一個數據元素可能有多個直接前驅和多個直接后繼。
多維數組
多維數組
多維數組
1、數組（向量）——常用數據類型
一維數組（向量）是存儲于計算機的連續存儲空間中的多個具有統一類型的數據元素。
同一數組的不同元素通過不同的下標標識。（a1,a2,…,an)
2、二維數組
二維數組Amn可視為由m個行向量組成的向量，或由n個列向量組成的向量。
矩陣的壓縮存儲
矩陣的存儲
1、矩陣的二維數組描述
矩陣用二維數組描述時，存儲的密度為1。可以對其元素進行隨機存取，各種矩陣運算也非常簡單。
2、矩陣的壓縮存儲
矩陣中非零元素呈某種規律分布或者矩陣中出現大量的零元素的情況下，為了節省存儲空間，我們可以對這類矩陣進行壓縮存儲：即為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。
特殊矩陣
1．對稱矩陣
（1）對稱矩陣
在一個n階方陣A中，若元素滿足下述性質： aij=aji 0≤i，j≤n-1則稱A為對稱矩陣
（2）三角矩陣的劃分
以主對角線劃分，三角矩陣有上三角矩陣和下三角矩陣兩種。
①上三角矩陣 如下圖(a)所示，它的下三角(不包括主角線)中的元素均為常數c。
②下三角矩陣 與上三角矩陣相反，它的主對角線上方均為常數c，如下圖(b)所示。
（3）對角矩陣
所有的非零元素集中在以主對角線為中心的帶狀區域中，即除了主對角線和主對角線相鄰兩側的若干條對角線上的元素之外，其余元素皆為零的矩陣為對角矩陣。
稀疏矩陣 設矩陣Amn中有s個非零元素，若s遠遠小于矩陣元素的總數(即s<<m×n)，則稱A為稀疏矩陣。
其中每一個非零元素所在的行號、列號和值組成一個三元組(i，j，aij)，并由此三元組惟一確定。
稀疏矩陣進行壓縮存儲通常有兩類方法：順序存儲和鏈式存儲
Chapter 5 廣義表
廣義表
廣義表的概念：廣義表(Lists，又稱列表)是線性表的推廣。即廣義表中放松對表元素的原子限制，容許它們具有其自身結構。
廣義表是n(n≥0)個元素a1，a2，…，ai，…，an的有限序列。
其中：
①ai--或者是原子或者是一個廣義表。②廣義表通常記作：Ls=( a1，a2，…，ai，…，an)。③Ls是廣義表的名字，n為它的長度。④若ai是廣義表，則稱它為Ls的子表。
Chapter 6 樹
樹的概念
概念 樹的遞歸定義：
樹(Tree)是n(n≥0)個結點的有限集T，T為空時稱為空樹，否則它滿足如下兩個條件：
(1)有且僅有一個特定的稱為根(Root)的結點；
(2)其余的結點可分為m(m≥0)個互不相交的子集Tl，T2，…，Tm，其中每個子集本身又是一棵樹，并稱其為根的子樹(Subree)。
1、樹的表示：
（1）樹形圖表示（2）嵌套集合表示法（3）凹入表表示法（4）廣義表表示法
2、樹結構的基本術語：
（1）結點的度(Degree) 樹中的一個結點擁有的子樹數稱為該結點的度(Degree)。一棵樹的度是指該樹中結點的最大度數。度為零的結點稱為葉子(Leaf)或終端結點。度不為零的結點稱分支結點或非終端結點。除根結點之外的分支結點統稱為內部結點。根結點又稱為開始結點。
（2）孩子(Child)和雙親(Parents) 樹中某個結點的子樹之根稱為該結點的孩子(Child)或兒子，相應地，該結點稱為孩子的雙親(Parents)或父親。同一個雙親的孩子稱為兄弟(Sibling)。
（3）路徑（path） 若樹中存在一個結點序列k1，k2，…，ki，使得ki是ki+1的雙親(1≤i<j)，則稱該結點序列是從kl到kj的一條路徑(Path)或道路。路徑的長度指路徑所經過的邊(即連接兩個結點的線段)的數目，等于j-1。
（4）祖先(Ancestor)和子孫(Descendant) 若樹中結點k到ks存在一條路徑，則稱k是ks的祖先(Ancestor)，ks是k的子孫(Descendant)。
（5）結點的層數(Level)和樹的高度（Height）根的層數為1， 其余結點的層數等于其雙親結點的層數加1。雙親在同一層的結點互為堂兄弟。樹中結點的最大層數稱為樹的高度(Height)或深度(Depth)。
（6）有序樹(OrderedTree)和無序樹(UnoderedTree) 若將樹中每個結點的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有序樹；否則稱為無序樹。
（7）森林(Forest) 森林(Forest)是m(m≥0)棵互不相交的樹的集合。
二叉樹
二叉樹的定義
1.二叉樹的遞歸定義
二叉樹(BinaryTree)是n(n≥0)個結點的有限集，它或者是空集(n=0)，或者由一個根結點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。
二叉樹的性質
性質1 二叉樹第i層上的結點數目最多為2i-1(i≥1)。
性質2 深度為k的二叉樹至多有2k-1個結點(k≥1)。
性質3 在任意-棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則no=n2+1。
滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形。
滿二叉樹(FullBinaryTree) 一棵深度為k且有2k-1個結點的二又樹稱為滿二叉樹。
完全二叉樹(Complete BinaryTree) 若一棵二叉樹至多只有最下面的兩層上結點的度數可以小于2，并且最下一層上的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。
性質4 具有n個結點的完全二叉樹的深度為
二叉樹的存儲結構
順序存儲結構 該方法是把二叉樹的所有結點按照一定的線性次序存儲到一片連續的存儲單元中。結點在這個序列中的相互位置還能反映出結點之間的邏輯關系。
鏈式存儲結構 二叉樹的每個結點最多有兩個孩子。用鏈接方式存儲二叉樹時，每個結點除了存儲結點本身的數據外，還應設置兩個指針域lchild和rchild，分別指向該結點的左孩子和右孩子。
二叉樹的遍歷
二叉樹的遍歷 遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。
一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
（1）訪問結點本身(N)，（2）遍歷該結點的左子樹(L)，（3）遍歷該結點的右子樹(R)。
三種遍歷的命名
根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))——訪問結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal) ——訪問結點的操作發生在遍歷其左右子樹之中(間)。
③ LRN：后序遍歷(PostorderTraversal)——訪問結點的操作發生在遍歷其左右子樹之后
遍歷序列：1．遍歷二叉樹的執行蹤跡 三種遞歸遍歷算法的搜索路線相同（如下圖虛線所示）。
二叉鏈表的構造
線索二叉樹
線索二叉樹
n個結點的二叉鏈表中含有n+1個空指針域。利用二叉鏈表中的空指針域，存放指向結點在某種遍歷次序下的前趨和后繼結點的指針（這種附加的指針稱為"線索"）。
ltag和rtag是增加的兩個標志域，用來區分結點的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。
線索二叉樹中，一個結點是葉結點的充要條件為：左、右標志均是1。
線索化：按某種次序將二叉樹線索化的實質是：按該次序遍歷二叉樹，在遍歷過程中用線索取代空指針。
線索二叉樹的運算：
1． 查找某結點*p在指定次序下的前趨和后繼結點
2．遍歷線索二叉樹
樹和森林
樹、森林和二叉樹的轉換
（1）將樹轉換為二叉樹
樹中每個結點最多只有一個最左邊的孩子(長子)和一個右鄰的兄弟。按照這種關系很自然地就能將樹轉換成相應的二叉樹：
①在所有兄弟結點之間加一連線；
②對每個結點，除了保留與其長子的連線外，去掉該結點與其它孩子的連線。
（2）將一個森林轉換為二叉樹
具體方法是：
① 將森林中的每棵樹變為二叉樹
② 因為轉換所得的二叉樹的根結點的右子樹均為空，故可將各二叉樹的根結點視為兄弟從左至右連在一起，就形成了一棵二叉樹。
（3）把二叉樹轉換到樹和森林
方式是：若結點x是雙親y的左孩子，則把x的右孩子，右孩子的右孩子，…，都與y用連線連起來，最后去掉所有雙親到右孩子的連線。
樹的存儲結構
1、 雙親鏈表表示法：在存儲結點信息的同時，為每個結點附設一個指向其雙親的指針parent，惟一地表示任何-棵樹。
2、 孩子鏈表表示法：孩子鏈表表示法是為樹中每個結點設置一個孩子鏈表，并將這些結點及相應的孩子鏈表的頭指針存放在一個向量中。
3、 孩子兄弟鏈表表示法 : 在存儲結點信息的同時，附加兩個分別指向該結點最左孩子和右鄰兄弟的指針域leftmostchild和rightsibling，即可得樹的孩子兄弟鏈表表示。
樹和森林的遍歷
樹的遍歷
1．樹T的前序遍歷定義：若樹T非空，則：①訪問根結點R；②依次前序遍歷根R的各子樹T1，T2，…，Tk。
2．樹T的后序遍歷定義：若樹T非空，則：①依次后序遍歷根T的各子樹Tl，T2，…，Tk；②訪問根結點R。
森林的兩種遍歷方法
1．前序遍歷森林
若森林非空，則：①訪問森林中第一棵樹的根結點；②前序遍歷第一棵樹中根結點的各子樹所構成的森林③前序遍歷除第一棵樹外其它樹構成的森林。
2．后序遍歷森林
若森林非空，則:①后序遍歷森林中第一棵樹的根結點的各子樹所構成的森林；②訪問第一棵樹的根結點；③后序遍歷除第一棵樹外其它樹構成的森林。
哈夫曼樹及其應用
最優二叉樹
哈夫曼編碼