數(shù)據(jù)結(jié)構(gòu)知識點全面總結(jié)—精華版
第1章 緒論
內(nèi)容提要：
◆ 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。
針對非數(shù)值計算的程序設(shè)計問題，研究計算機(jī)的操作對象以及它們之間的關(guān)系和操作。
數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容：
◆ 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型。
數(shù)據(jù)——所有能被計算機(jī)識別、存儲和處理的符號的集合。
數(shù)據(jù)元素——是數(shù)據(jù)的基本單位，具有完整確定的實際意義。
數(shù)據(jù)對象——具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。
數(shù)據(jù)結(jié)構(gòu)——是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：
Data_Structure=（D, R）
數(shù)據(jù)類型——是一個值的集合和定義在該值上的一組操作的總稱。
抽象數(shù)據(jù)類型——由用戶定義的一個數(shù)學(xué)模型與定義在該模型上的一組操作，
它由基本的數(shù)據(jù)類型構(gòu)成。
◆ 算法的定義及五個特征。
算法——是對特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉(zhuǎn)換為輸出的計算步驟。
算法的基本特性：輸入、輸出、有窮性、確定性、可行性
◆ 算法設(shè)計要求。
①正確性、②可讀性、③健壯性、④效率與低存儲量需求
◆ 算法分析。
時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性
學(xué)習(xí)重點：
◆ 數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu)、物理（存儲）結(jié)構(gòu)及在這種結(jié)構(gòu)上所定義的操作（運算） 。
◆ 用計算語句頻度來估算算法的時間復(fù)雜度。
第二章 線性表
內(nèi)容提要：
◆ 線性表的邏輯結(jié)構(gòu)定義，對線性表定義的操作。
線性表的定義：用數(shù)據(jù)元素的有限序列表示
◆ 線性表的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。
順序存儲定義：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。
鏈?zhǔn)酱鎯Y(jié)構(gòu): 其結(jié)點在存儲器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。通過指針來實現(xiàn)！
◆ 線性表的操作在兩種存儲結(jié)構(gòu)中的實現(xiàn)。
數(shù)據(jù)結(jié)構(gòu)的基本運算：修改、插入、刪除、查找、排序
1) 修改——通過數(shù)組的下標(biāo)便可訪問某個特定元素并修改之。
核心語句: V[i]=x;
順序表修改操作的時間效率是 O(1)
2) 插入——在線性表的第i個位置前插入一個元素
實現(xiàn)步驟：
①將第n至第i 位的元素向后移動一個位置；
②將要插入的元素寫到第i個位置；
③表長加1。
注意：事先應(yīng)判斷: 插入位置i 是否合法?表是否已滿?
應(yīng)當(dāng)符合條件： 1≤i≤n+1 或 i=[1, n+1]
核心語句：
for (j=n; j>=i; j--)
a[j+1]=a[ j ];
a[ i ]=x;
n++;
插入時的平均移動次數(shù)為：n(n+1)/2÷（n+1）＝n/2≈O(n)
3) 刪除——刪除線性表的第i個位置上的元素
實現(xiàn)步驟：
①將第i+1 至第n 位的元素向前移動一個位置；
②表長減1。
注意：事先需要判斷，刪除位置i 是否合法?
應(yīng)當(dāng)符合條件：1≤i≤n 或 i=[1, n]
核心語句：
for ( j=i+1; j<=n; j++ )
a[j-1]=a[j];
n--;
順序表刪除一元素的時間效率為:T（n)=(n-1)/2 ≈O(n)
順序表插入、刪除算法的平均空間復(fù)雜度為O(1)
單鏈表：
（1）
用單鏈表結(jié)構(gòu)來存放26個英文字母組成的線性表（a，b，c，…，z）,請寫出C語言程序。
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
char data;
struct node *next;
}node;
node *p,*q,*head; //一般需要3個指針變量
int n ; // 數(shù)據(jù)元素的個數(shù)
int m=sizeof(node); /*結(jié)構(gòu)類型定義好之后，每個node類型的長度就固定了，
m求一次即可*/
void build( ) //字母鏈表的生成。要一個個慢慢鏈入
{
int i;
head=(node*)malloc(m); //m=sizeof(node) 前面已求出
p=head;
for( i=1; i<26; i++) //因尾結(jié)點要特殊處理，故i≠26
{
p->data=i+‘a(chǎn)’-1; // 第一個結(jié)點值為字符a
p->next=(node*)malloc(m); //為后繼結(jié)點“挖坑”！
p=p->next；} //讓指針變量P指向后一個結(jié)點
p->data=i+‘a(chǎn)’-1; //最后一個元素要單獨處理
p->next=NULL ; //單鏈表尾結(jié)點的指針域要置空！
}
}
void display() //字母鏈表的輸出
{
p=head;
while (p) //當(dāng)指針不空時循環(huán)（僅限于無頭結(jié)點的情況）
{
printf("%c",p->data);
p=p->next; //讓指針不斷“順藤摸瓜”
}
}
（2）單鏈表的修改(或讀取）
思路：要修改第i個數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點的指針p，
然后才能：p>data=new_value
讀取第i個數(shù)據(jù)元素的核心語句是：
Linklist *find(Linklist *head ,int i)
{
int j=1;
Linklist *p;
P=head->next;
While((p!=NULL)&&(j<i))
{
p=p->next;
j++;
}
return p;
}
3.
單鏈表的插入
鏈表插入的核心語句：
Step 1：s->next=p->next;
Step 2：p->next=s ；
6.單鏈表的刪除
刪除動作的核心語句（要借助輔助指針變量q）：
q = p->next; //首先保存b的指針，靠它才能找到c；
p->next=q->next; //將a、c兩結(jié)點相連，淘汰b結(jié)點；
free(q) ； //徹底釋放b結(jié)點空間
7.雙向鏈表的插入操作：
設(shè)p已指向第 i 元素，請在第 i 元素前插入元素 x：
① ai-1的后繼從 ai ( 指針是p)變?yōu)?x（指針是s) :
s->next = p ; p->prior->next = s ;
② ai 的前驅(qū)從 ai-1 ( 指針是p->prior)變?yōu)?x ( 指針是s);
s->prior = p ->prior ; p->prior = s ;
8.雙向鏈表的刪除操作：
設(shè)p指向第 i 個元素，刪除第 i 個 元素
后繼方向：ai-1的后繼由 ai ( 指針p)變?yōu)?ai+1(指針 p ->next );
p ->prior->next = p->next ;
前驅(qū)方向：ai+1的前驅(qū)由 ai ( 指針p)變?yōu)閍i-1 (指針 p -> prior );
p->next->prior = p ->prior ;
◆ 數(shù)組的邏輯結(jié)構(gòu)定義及存儲
數(shù)組： 由一組名字相同、下標(biāo)不同的變量構(gòu)成
N維數(shù)組的特點：n個下標(biāo)，每個元素受到n個關(guān)系約束
一個n維數(shù)組可以看成是由若干個n－1維數(shù)組組成的線性表。
存儲：事先約定按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存入存儲器中。
在二維數(shù)組中，我們既可以規(guī)定按行存儲，也 可以規(guī)定按列存儲。
設(shè)一般的二維數(shù)組是A[c1..d1, c2..d2]，
則行優(yōu)先存儲時的地址公式為：
二維數(shù)組列優(yōu)先存儲的通式為：
◆ 稀疏矩陣（含特殊矩陣）的存儲及運算。
稀疏矩陣：矩陣中非零元素的個數(shù)較少（一般小于5%）
學(xué)習(xí)重點：
◆ 線性表的邏輯結(jié)構(gòu)，指線性表的數(shù)據(jù)元素間存在著線性關(guān)系。在順序存儲結(jié)構(gòu)中，元素存儲的先后位置反映出這種線性關(guān)系，而在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，是靠指針來反映這種關(guān)系的。
◆ 順序存儲結(jié)構(gòu)用一維數(shù)組表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于隨機(jī)存取的存儲結(jié)構(gòu)。
◆ 鏈表操作中應(yīng)注意不要使鏈意外“斷開”。因此，若在某結(jié)點前插入一個元素，或刪除某元素，必須知道該元素的前驅(qū)結(jié)點的指針。
◆ 掌握通過畫出結(jié)點圖來進(jìn)行鏈表（單鏈表、循環(huán)鏈表等）的生成、插入、刪除、遍歷等操作。
◆ 數(shù)組（主要是二維）在以行序/列序為主的存儲中的地址計算方法。
◆ 稀疏矩陣的三元組表存儲結(jié)構(gòu)。
◆ 稀疏矩陣的十字鏈表存儲方法。
補(bǔ)充重點：
1.每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和指針域(鏈域)
2.在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由 其直接前驅(qū)結(jié)點的鏈域的值 指示。
3.在鏈表中設(shè)置頭結(jié)點有什么好處？
頭結(jié)點即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的數(shù)據(jù)域可以為空，也可存放表長度等附加信息，其作用是為了對鏈表進(jìn)行操作時，可以對空表、非空表的情況以及對首元結(jié)點進(jìn)行統(tǒng)一處理，編程更方便。
4.如何表示空表？
（1）無頭結(jié)點時，當(dāng)頭指針的值為空時表示空表；
（2）有頭結(jié)點時，當(dāng)頭結(jié)點的指針域為空時表示空表。
5.鏈表的數(shù)據(jù)元素有兩個域，不再是簡單數(shù)據(jù)類型，編程時該如何表示？
因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。
6.sizeof(x)—— 計算變量x的長度（字節(jié)數(shù)）；
malloc(m) — 開辟m字節(jié)長度的地址空間，并返回這段空間的首地址；
free(p) —— 釋放指針p所指變量的存儲空間，即徹底刪除一個變量。
7.鏈表的運算效率分析：
（1）查找
因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為 O(n)。
（2） 插入和刪除
因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復(fù)雜度為 O(1)。
但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因為要從頭查找前驅(qū)結(jié)點，所耗時間復(fù)雜度將是 O(n)。
例：在n個結(jié)點的單鏈表中要刪除已知結(jié)點*P，需找到它的前驅(qū)結(jié)點的地址，其時間復(fù)雜度為 O（n）
8. 順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別和優(yōu)缺點？
順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。
鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。鏈?zhǔn)酱鎯Φ膬?yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。
◆ 順序表適宜于做查找這樣的靜態(tài)操作；
◆ 鏈表宜于做插入、刪除這樣的動態(tài)操作。
◆ 若線性表的長度變化不大，且其主要操作是查找，則采用順序表；
◆ 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。
9. 判斷：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單”，對嗎？
答：對的。因為——
① 數(shù)組中各元素具有統(tǒng)一的類型；
② 數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。
③數(shù)組的基本操作比較簡單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。
10.三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的 行下標(biāo) 、列下標(biāo) 和 元素值 。
11.寫出右圖所示稀疏矩陣的壓縮存儲形式。
解：介紹3種存儲形式。
法1：用線性表表示：
（( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)，
(4,3,24)， (5,2,18) ，(6,1,15)， (6,4,-7)）
法2：用十字鏈表表示
用途：方便稀疏矩陣的加減運算
方法：每個非0元素占用5個域
法3：用三元組矩陣表示：
稀疏矩陣壓縮存儲的缺點：將失去隨機(jī)存取功能
代碼：
1.用數(shù)組V來存放26個英文字母組成的線性表（a，b，c，…，z），寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。
char V[30];
void build() //字母線性表的生成，即建表操作
{
int i;
V[0]='a';
for( i=1; i<=n-1; i++ )
V[i]=V[i-1]+1;
}
void display( ) //字母線性表的顯示，即讀表操作
{
int i;
for( i=0; i<=n-1; i++ )
printf( "%c", v[i] );
printf( "\n " );
}
void main(void) //主函數(shù)，字母線性表的生成和輸出
{
n=26; // n是表長，是數(shù)據(jù)元素的個數(shù)，而不是V的實際下標(biāo)
build( );
display( );
}
第三章 棧和隊列
內(nèi)容提要：
◆ 從數(shù)據(jù)結(jié)構(gòu)角度來講，棧和隊列也是線性表，其操作是線性表操作的子集，屬操作受限的線性表。但從數(shù)據(jù)類型的角度看，它們是和線性表大不相同的重要抽象數(shù)據(jù)類型。
◆ 棧的定義及操作。棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，該端稱為棧的頂端。
插入元素到棧頂?shù)牟僮?，稱為入棧。
從棧頂刪除最后一個元素的操作，稱為出棧。
對于向上生成的堆棧:
入棧口訣：堆棧指針top “先壓后加” : S[top++]=an+1
出?？谠E：堆棧指針top “先減后彈” : e=S[--top]
◆ 棧的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)，及在這兩種結(jié)構(gòu)下實現(xiàn)棧的操作。
順序棧入棧函數(shù)PUSH（）
status Push(ElemType e)
{ if(top>M){上溢}
else s[top++]=e;
}
順序棧出棧函數(shù)POP()
status Pop( )
{ if(top=L) { 下溢 }
else { e=s[--top]; return(e);}
}
◆ 隊列的定義及操作，隊列的刪除在一端（隊尾），而插入則在隊列的另一端（隊頭）。因此在兩種存儲結(jié)構(gòu)中，都需要隊頭和隊尾兩個指針。
隊列：只能在表的一端進(jìn)行插入運算，在表的另一端進(jìn)行刪除運算的線性表。
鏈隊列
結(jié)點類型定義：
typedef Struct QNode{
QElemType data; //元素
Struct QNode *next; //指向下一結(jié)點的指針
}Qnode , * QueuePtr ;
鏈隊列類型定義：
typedef struct {
QueuePtr front ; //隊首指針
QueuePtr rear ; //隊尾指針
} LinkQueue;
鏈隊示意圖：
① 空鏈隊的特征：front=rear
② 鏈隊會滿嗎？一般不會，因為刪除時有free動作。除非內(nèi)存不足！
③ 入隊（尾部插入）：rear->next=S; rear=S;
出隊（頭部刪除）：front->next=p->next;
2.順序隊
順序隊類型定義：
#define QUEUE-MAXSIZE 100 //最大隊列長度
typedef struct {
QElemType *base; //隊列的基址
int front; //隊首指針
int rear; //隊尾指針
}SqQueue
建隊核心語句：
q . base=(QElemType *)malloc(sizeof (QElemType ）
* QUEUE_MAXSIZE; //分配空間
順序隊示意圖：
循環(huán)隊列：
隊空條件 : front = rear (初始化時：front = rear )
隊滿條件： front = (rear+1) % N (N=maxsize)
隊列長度（即數(shù)據(jù)元素個數(shù)）：L=（N＋rear－front）% N
1）初始化一個空隊列
Status InitQueue ( SqQueue &q ) //初始化空循環(huán)隊列 q
{
q . base=(QElemType *)malloc(sizeof(QElemType）
* QUEUE_MAXSIZE); //分配空間
if (!q.base) exit(OVERFLOW);//內(nèi)存分配失敗，退出程序
q.front =q.rear=0; //置空隊列
return OK;
} //InitQueue;
2）入隊操作
Status EnQueue(SqQueue &q, QElemType e)
{//向循環(huán)隊列 q 的隊尾加入一個元素 e
if ( (q.rear+1) % QUEUE_MAXSIZE = = q.front )
return ERROR ; //隊滿則上溢，無法再入隊
q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE;
q.base [ q.rear ] = e; //新元素e入隊
return OK;
}// EnQueue;
3）出隊操作
Status DeQueue ( SqQueue &q, QElemType &e)
{//若隊列不空，刪除循環(huán)隊列q的隊頭元素，
//由 e 返回其值，并返回OK
if ( q.front = = q.rear ) return ERROR;//隊列空
q.front=(q.front+1) % QUEUE_MAXSIZE ;
e = q.base [ q.front ] ;
return OK;
}// DeQueue
◆ 鏈隊列空的條件是首尾指針相等，而循環(huán)隊列滿的條件的判定，則有隊尾加1等于隊頭和設(shè)標(biāo)記兩種方法。
補(bǔ)充重點：
1.為什么要設(shè)計堆棧？它有什么獨特用途？
① 調(diào)用函數(shù)或子程序非它莫屬；
② 遞歸運算的有力工具；
③ 用于保護(hù)現(xiàn)場和恢復(fù)現(xiàn)場；
④ 簡化了程序設(shè)計的問題。
2.為什么要設(shè)計隊列？它有什么獨特用途？
① 離散事件的模擬（模擬事件發(fā)生的先后順序,例如 CPU芯片中的指令譯碼隊列）；
② 操作系統(tǒng)中的作業(yè)調(diào)度（一個CPU執(zhí)行多個作業(yè)）；
③ 簡化程序設(shè)計。
3.什么叫“假溢出” ？如何解決？
答：在順序隊中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。解決假溢出的途徑———采用循環(huán)隊列。
4.在一個循環(huán)隊列中，若約定隊首指針指向隊首元素的前一個位置。那么，從循環(huán)隊列中刪除一個元素時，其操作是先 移動隊首位置 ，后 取出元素。
5.線性表、棧、隊的異同點：
相同點：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表（只是對插入、刪除運算加以限制）。
不同點：① 運算規(guī)則不同：
線性表為隨機(jī)存取；
而棧是只允許在一端進(jìn)行插入和刪除運算，因而是后進(jìn)先出表LIFO；
隊列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運算，因而是先進(jìn)先出表FIFO。
② 用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡化設(shè)計等；隊列用于離散事件模擬、OS作業(yè)調(diào)度和簡化設(shè)計等。
第四章 串
內(nèi)容提要 ：
◆ 串是數(shù)據(jù)元素為字符的線性表，串的定義及操作。
串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。
串比較：int strcmp(char *s1,char *s2);
求串長：int strlen(char *s);
串連接：char strcat(char *to,char *from)
子串T定位：char strchr(char *s,char *c);
◆ 串的存儲結(jié)構(gòu)，因串是數(shù)據(jù)元素為字符的線性表，所以存在“結(jié)點大小”的問題。
模式匹配算法 。
串有三種機(jī)內(nèi)表示方法：
模式匹配算法 ：
算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）
定位問題稱為串的模式匹配，典型函數(shù)為Index(S,T,pos)
BF算法的實現(xiàn)—即編寫Index(S, T, pos)函數(shù)
BF算法設(shè)計思想：
將主串S的第pos個字符和模式T的第1個字符比較，
若相等，繼續(xù)逐個比較后續(xù)字符；
若不等，從主串S的下一字符（pos+1）起，重新與T第一個字符比較。
直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。
否則，匹配失敗，返回值 0。
Int Index_BP(SString S, SString T, int pos)
{ //返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數(shù)值為0.
// 其中，T非空，1≤pos≤StrLength(S)
i=pos; j=1;
while ( i<=S[0] && j<=T[0] ) //如果i,j二指針在正常長度范圍，
{
if (S[i] = = T[j] ) {++i, ++j; } //則繼續(xù)比較后續(xù)字符
else {i=i-j+2; j=1;} //若不相等，指針后退重新開始匹配
}
if(j>T[0]) return i-T[0]; //T子串指針j正常到尾，說明匹配成功， else return 0; //否則屬于i>S[0]情況，i先到尾就不正常
} //Index_BP
補(bǔ)充重點：
1.空串和空白串有無區(qū)別？
答：有區(qū)別。
空串(Null String)是指長度為零的串；
而空白串(Blank String),是指包含一個或多個空白字符‘ ’(空格鍵)的字符串.
2.“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串?！?/strong>
第六章 樹和二叉樹
內(nèi)容提要：
◆ 樹是復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二叉樹的遞歸定義，基本概念，術(shù)語。
樹：由一個或多個(n≥0)結(jié)點組成的有限集合T，有且僅有一個結(jié)點稱為根（root），當(dāng)n>1時，其余的結(jié)點分為m(m≥0)個互不相交的有限集合T1,T2，…，Tm。每個集合本身又是棵樹，被稱作這個根的子樹 。
二叉樹：是n（n≥0）個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。
術(shù)語：P88
◆ 二叉樹的性質(zhì)，存儲結(jié)構(gòu)。
性質(zhì)1: 在二叉樹的第i層上至多有2i-1個結(jié)點（i>0）。
性質(zhì)2: 深度為k的二叉樹至多有2k-1個結(jié)點（k>0）。
性質(zhì)3: 對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)（n0）必定為n2＋1
性質(zhì)4: 具有n個結(jié)點的完全二叉樹的深度必為 ?
性質(zhì)5: 對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結(jié)點，其左孩子編號必為2i，其右孩子編號為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）。
二叉樹的存儲結(jié)構(gòu)：
一、順序存儲結(jié)構(gòu)
按二叉樹的結(jié)點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。
若是完全/滿二叉樹則可以做到唯一復(fù)原。
不是完全二叉樹：一律轉(zhuǎn)為完全二叉樹！
方法很簡單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點”，其內(nèi)容為空。
缺點：①浪費空間；②插入、刪除不便
二、鏈?zhǔn)酱鎯Y(jié)構(gòu)
用二叉鏈表即可方便表示。一般從根結(jié)點開始存儲。
優(yōu)點：①不浪費空間；②插入、刪除方便
◆ 二叉樹的遍歷。
指按照某種次序訪問二叉樹的所有結(jié)點，并且每個結(jié)點僅訪問一次，得到一個線性序列。
遍歷規(guī)則———
二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、 L、R
若限定先左后右，則有三種實現(xiàn)方案：
DLR LDR LRD
先序遍歷 中序遍歷 后序遍歷
◆ 樹的存儲結(jié)構(gòu)，樹、森林的遍歷及和二叉樹的相互轉(zhuǎn)換。
回顧2：二叉樹怎樣還原為樹？
要點：逆操作，把所有右孩子變?yōu)樾值埽?/p>
討論1：森林如何轉(zhuǎn)為二叉樹？
法一：① 各森林先各自轉(zhuǎn)為二叉樹；② 依次連到前一個二叉樹的右子樹上。
法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹
討論2：二叉樹如何還原為森林？
要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?/p>
樹和森林的存儲方式：
樹有三種常用存儲方式：
①雙親表示法 ②孩子表示法 ③孩子—兄弟表示法
問：樹→二叉樹的“連線—抹線—旋轉(zhuǎn)” 如何由計算機(jī)自動實現(xiàn)？
答：用“左孩子右兄弟”表示法來存儲即可。
存儲的過程就是樹轉(zhuǎn)換為二叉樹的過程！
樹、森林的遍歷：
① 先根遍歷：訪問根結(jié)點；依次先根遍歷根結(jié)點的每棵子樹。
② 后根遍歷：依次后根遍歷根結(jié)點的每棵子樹；訪問根結(jié)點。
討論：樹若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？
1. 樹的先根遍歷與二叉樹的先序遍歷相同；
2. 樹的后根遍歷相當(dāng)于二叉樹的中序遍歷；
3. 樹沒有中序遍歷，因為子樹無左右之分。
① 先序遍歷
若森林為空，返回；
訪問森林中第一棵樹的根結(jié)點；
先根遍歷第一棵樹的根結(jié)點的子樹森林；
先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。
② 中序遍歷
若森林為空，返回；
中根遍歷森林中第一棵樹的根結(jié)點的子樹森林；
訪問第一棵樹的根結(jié)點；
中根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。
◆ 二叉樹的應(yīng)用：哈夫曼樹和哈夫曼編碼。
Huffman樹：最優(yōu)二叉樹（帶權(quán)路徑長度最短的樹）
Huffman編碼：不等長編碼。
樹的帶權(quán)路徑長度：（樹中所有葉子結(jié)點的帶權(quán)路徑長度之和）
構(gòu)造Huffman樹的基本思想：權(quán)值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑。
構(gòu)造Huffman樹的步驟（即Huffman算法）：
(1) 由給定的 n 個權(quán)值{ w1, w2, …, wn }構(gòu)成n棵二叉樹的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉樹 Ti 中只有一個帶權(quán)為 wi 的根結(jié)點，其左右子樹均空。
(2) 在F 中選取兩棵根結(jié)點權(quán)值最小的樹 做為左右子樹構(gòu)造一棵新的二叉樹，且讓新二叉樹根結(jié)點的權(quán)值等于其左右子樹的根結(jié)點權(quán)值之和。
(3) 在F 中刪去這兩棵樹，同時將新得到的二叉樹加入 F中。
(4) 重復(fù)(2) 和(3) , 直到 F 只含一棵樹為止。這棵樹便是Huffman樹。
具體操作步驟：
學(xué)習(xí)重點：（本章內(nèi)容是本課程的重點）
◆ 二叉樹性質(zhì)及證明方法，并能把這種方法推廣到K叉樹。
◆ 二叉樹遍歷，遍歷是基礎(chǔ)，由此導(dǎo)出許多實用的算法，如求二叉樹的高度、各結(jié)點的層次數(shù)、度為0、1、2的結(jié)點數(shù)。
◆ 由二叉樹遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹。由前序和后序序列不能唯一確定一棵二叉樹。
◆ 完全二叉樹的性質(zhì)。
◆ 樹、森林和二叉樹間的相互轉(zhuǎn)換。
◆ 哈夫曼樹的定義、構(gòu)造及求哈夫曼編碼。
補(bǔ)充：
1.滿二叉樹和完全二叉樹有什么區(qū)別？
答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前k-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點。滿二叉樹是完全二叉樹的一個特例。
2.Huffman樹有什么用？
最小冗余編碼、信息高效傳輸
第七章 圖
內(nèi)容提要：
◆ 圖的定義，概念、術(shù)語及基本操作。
圖：記為 G＝( V, E )
其中：V 是G 的頂點集合，是有窮非空集；
E 是G 的邊集合，是有窮集。
術(shù)語：見課件
◆ 圖的存儲結(jié)構(gòu)。
1.鄰接矩陣(數(shù)組)表示法
① 建立一個頂點表和一個鄰接矩陣
② 設(shè)圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是一個二維數(shù)組 A.Edge[n][n]。
注：在有向圖的鄰接矩陣中，
第i行含義：以結(jié)點vi為尾的弧(即出度邊）；
第i列含義：以結(jié)點vi為頭的弧(即入度邊）。
鄰接矩陣法優(yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。?、找頂點的鄰接點等等。
鄰接矩陣法缺點：n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。
2.鄰接表(鏈?zhǔn)?表示法
① 對每個頂點vi 建立一個單鏈表，把與vi有關(guān)聯(lián)的邊的信息（即度或出度邊）鏈接起來，表中每個結(jié)點都設(shè)為3個域:
② 每個單鏈表還應(yīng)當(dāng)附設(shè)一個頭結(jié)點（設(shè)為2個域），存vi信息；
③ 每個單鏈表的頭結(jié)點另外用順序存儲結(jié)構(gòu)存儲。
鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點；
鄰接表的缺點：判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。
◆ 圖的遍歷。
遍歷定義：從已給的連通圖中某一頂點出發(fā)，沿著一些邊，訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。
圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索
深度優(yōu)先搜索（遍歷）步驟：
① 訪問起始點 v;
② 若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點；
③ 若當(dāng)前鄰接點已訪問過，再找v的第2個鄰接點重新遍歷。
基本思想：——仿樹的先序遍歷過程。
廣度優(yōu)先搜索（遍歷）步驟：
① 在訪問了起始點v之后，依次訪問 v的鄰接點；
② 然后再依次（順序）訪問這些點（下一層）中未被訪問過的鄰接點；
③ 直到所有頂點都被訪問過為止。
◆ 圖的應(yīng)用（最小生成樹，最短路經(jīng)）
最小生成樹（MST）的性質(zhì)如下：若U集是V的一個非空子集，若(u0, v0)是一條最小權(quán)值的邊，其中u0?U，v0?V-U；則：(u0, v0)必在最小生成樹上。
求MST最常用的是以下兩種：Kruskal（克魯斯卡爾）算法、Prim（普里姆）算法
Kruskal算法特點：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。
Prime算法特點: 將頂點歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)。
在帶權(quán)有向圖中A點（源點）到達(dá)B點（終點）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。
兩種常見的最短路徑問題：
一、 單源最短路徑—用Dijkstra（迪杰斯特拉）算法
二、所有頂點間的最短路徑—用Floyd（弗洛伊德）算法
一、單源最短路徑 (Dijkstra算法)一頂點到其余各頂點（v0→j）
目的： 設(shè)一有向圖G=（V, E），已知各邊的權(quán)值，以某指定點v0為源點，求從v0到圖的其余各點的最短路徑。限定各邊上的權(quán)值大于或等于0。
二、所有頂點之間的最短路徑
可以通過調(diào)用n次Dijkstra算法來完成，還有更簡單的一個算法：Floyd算法（自學(xué)）。
學(xué)習(xí)重點： 圖是應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，本章也是這門課程的重點。
◆ 基本概念中，連通分量，生成樹，鄰接點是重點。
① 連通圖：在無向圖中, 若從頂點v1到頂點v2有路徑, 則稱頂點v1與v2是連通的。
如果圖中任意一對頂點都是連通的, 則稱此圖是連通圖。
非連通圖的極大連通子圖叫做連通分量。
② 生成樹：是一個極小連通子圖，它含有圖中全部n個頂點，但只有n-1條邊。
③ 鄰接點：若 (u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接頂點。
◆ 圖是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，也有順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)：數(shù)組表示法（重點是鄰接距陣）和鄰接表。這兩種存儲結(jié)構(gòu)對有向圖和無向圖均適用
◆ 圖的遍歷是圖的各種算法的基礎(chǔ)，應(yīng)熟練掌握圖的深度、廣度優(yōu)先遍歷。
◆ 連通圖的最小生成樹不是唯一的，但最小生成樹邊上的權(quán)值之和是唯一的。 應(yīng)熟練掌握prim和kruscal算法，特別是手工分步模擬生成樹的生成過程。
◆ 從單源點到其他頂點，以及各個頂點間的最短路徑問題，掌握熟練手工模擬。
補(bǔ)充：
1.問：當(dāng)有向圖中僅1個頂點的入度為0,其余頂點的入度均為1，此時是何形狀？
答：是樹！而且是一棵有向樹！
2.討論：鄰接表與鄰接矩陣有什么異同之處？
1. 聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，
鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。
2. 區(qū)別：
對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），
但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。
3. 用途：
鄰接矩陣多用于稠密圖的存儲
而鄰接表多用于稀疏圖的存儲
3.若對連通圖進(jìn)行遍歷，得到的是生成樹
若對非連通圖進(jìn)行遍歷，得到的是生成森林。
第八章 查找
內(nèi)容提要：
◆ 查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。是元素間約束力最差的數(shù)據(jù)結(jié)構(gòu)：元素間的關(guān)系是元素僅共在同一個集合中。（同一類型的數(shù)據(jù)元素構(gòu)成的集合）
◆ 查找表的操作：查找，插入，刪除。
◆ 靜態(tài)查找表：順序表，有序表等。
針對靜態(tài)查找表的查找算法主要有:順序查找、折半查找、分塊查找
一、順序查找（線性查找）
技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。
int Search_Seq( SSTable ST , KeyType key ){
ST.elem[0].key =key;
for( i=ST.length; ST.elem[ i ].key!=key; - - i );
return i;
} // Search_Seq
//ASL＝（1＋n）/2，時間效率為 O(n)，這是查找成功的情況:
順序查找的特點：
優(yōu)點：算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。
缺點： ASL 太大，時間效率太低。
二、折半查找（二分或?qū)Ψ植檎遥?/p>
若關(guān)鍵字不在表中，怎樣得知并及時停止查找？
典型標(biāo)志是：當(dāng)查找范圍的上界≤下界時停止查找。
ASL的含義是“平均每個數(shù)據(jù)的查找時間”，而前式是n個數(shù)據(jù)查找時間的總和，所以：
三、分塊查找（索引順序查找）
思路：先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個子表中的數(shù)據(jù)元素值都比后一塊中的數(shù)值?。ǖ颖韮?nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個索引表，表中還要包含每個子表的起始地址（即頭指針）。
特點：塊間有序，塊內(nèi)無序。
查找：塊間折半，塊內(nèi)線性
查找步驟分兩步進(jìn)行：
① 對索引表使用折半查找法（因為索引表是有序表）；
② 確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因為各子表內(nèi)部是無序表）；
查找效率ASL分析：
◆ 動態(tài)查找表：二叉排序樹，平衡二叉樹。
特點：表結(jié)構(gòu)在查找過程中動態(tài)生成。
要求：對于給定值key, 若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key 的記錄。
① 二叉排序樹的定義
----或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：
（1）左子樹的所有結(jié)點均小于根的值；
（2）右子樹的所有結(jié)點均大于根的值；
（3）它的左右子樹也分別為二叉排序樹。
② 二叉排序樹的插入與刪除
思路：查找不成功，生成一個新結(jié)點s，插入到二叉排序樹中；查找成功則返回。
SearchBST (K, &t) { //K為待查關(guān)鍵字，t為根結(jié)點指針
p=t; //p為查找過程中進(jìn)行掃描的指針
while（p!=NULL）{
case {
K= p->data: {查找成功，return }
K< p->data : {q=p；p=p->L_child } //繼續(xù)向左搜索
K> p->data : {q=p；p=p->R_child } //繼續(xù)向右搜索
}
} //查找不成功則插入到二叉排序樹中
s =(BiTree)malloc(sizeof(BiTNode));
s->data=K; s ->L_child=NULL; s ->R_child=NULL;
//查找不成功，生成一個新結(jié)點s，插入到二叉排序樹葉子處
case {
t=NULL： t=s; //若t為空，則插入的結(jié)點s作為根結(jié)點
K < q->data: q->L_child=s; //若K比葉子小，掛左邊
K > q->data: q->R_child=s; //若K比葉子大，掛右邊
}
return OK
}
③ 二叉排序樹的刪除操作如何實現(xiàn)？
如何刪除一個結(jié)點？
假設(shè)：*p表示被刪結(jié)點的指針； PL和PR 分別表示*P的左、右孩子指針；
*f表示*p的雙親結(jié)點指針；并假定*p是*f的左孩子；則可能有三種情況：
*p有兩棵子樹時，如何進(jìn)行刪除操作？
設(shè)刪除前的中序遍歷序列為：…. PL s p PR f
//顯然p的直接前驅(qū)是s ，s是*p左子樹最右下方的結(jié)點
希望刪除p后，其它元素的相對位置不變。有兩種解決方法：
法1：令*p的左子樹為 *f的左子樹，*p的右子樹接為*s的右子樹； //即 fL=PL ; SR=PR ;
法2：直接令*s代替*p // *s為*p左子樹最右下方的結(jié)點
二叉排序樹的
④ 平衡二叉樹的定義：又稱AVL樹，即它或者是一顆空樹，或者是它的左子樹和右子樹都是平衡二叉樹，且左子樹與右子樹的深度之差的絕對值不超過1。
平衡因子：——該結(jié)點的左子樹的深度減去它的右子樹的深度。
平衡二叉樹的特點：任一結(jié)點的平衡因子只能取：-1、0 或 1。
如果在一棵AVL樹中插入一個新結(jié)點，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)。
平衡旋轉(zhuǎn)可以歸納為四類：
學(xué)習(xí)重點：
◆ 查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。因元素間關(guān)系非常松散，其操作需借助其它數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。本章列舉了三種方法（靜態(tài)查找表，動態(tài)查找表）實現(xiàn)查找表的運算。
◆ 順序表因設(shè)置了監(jiān)視哨使查找效率大大提高。有序表的平均查找長度不超過樹的深度。
◆ 查找的ASL
◆ 二叉排序樹的形態(tài)取決于元素的輸入順序。按中序遍歷可得到結(jié)點的有序序列，應(yīng)熟練掌握其建立、查找，插入和刪除算法。
◆ 平衡二叉樹的概念，應(yīng)熟練掌握手工繪制平衡二叉樹。
補(bǔ)充：
1.查找的過程是怎樣的？
給定一個值K，在含有n個記錄的文件中進(jìn)行搜索，尋找一個關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。
2.對查找表常用的操作有哪些？
查詢某個“特定的”數(shù)據(jù)元素是否在表中；
查詢某個“特定的”數(shù)據(jù)元素的各種屬性；
在查找表中插入一元素；
從查找表中刪除一元素。
3.哪些查找方法？
查找方法取決于表中數(shù)據(jù)的排列方式;
4.如何評估查找方法的優(yōu)劣？
用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為平均查找長度ASL。
ASL=∑ Pi. Ci
5.使用折半查找算法時，要求被查文件：采用順序存貯結(jié)構(gòu)、記錄按關(guān)鍵字遞增有序
6.將線性表構(gòu)造成二叉排序樹的優(yōu)點：
① 查找過程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高；
② 中序遍歷此二叉樹，將會得到一個關(guān)鍵字的有序序列（即實現(xiàn)了排序運算）；
③ 如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點上，而且插入或刪除時只需修改指針而不需移動元素。
第九章 內(nèi)部排序
內(nèi)容提要：
◆ 排序的定義，排序可以看作是線性表的一種操作
排序:將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。
◆ 排序的分類，穩(wěn)定排序與不穩(wěn)定排序的定義。
穩(wěn)定性——若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。
◆ 插入排序（直接插入、折半插入，索引表插入、希爾插入排序）。
插入排序的基本思想是：
每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。
簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。
1) 直接插入排序
在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。
時間效率： 因為在最壞情況下，所有元素的比較次數(shù)總和為（0＋1＋…＋n-1)→O(n2)。
其他情況下也要考慮移動元素的次數(shù)。 故時間復(fù)雜度為O(n2)
空間效率：僅占用1個緩沖單元——O（1）
算法的穩(wěn)定性：因為25*排序后仍然在25的后面——穩(wěn)定
直接插入排序算法的實現(xiàn)：
void InsertSort ( SqList &L ) { //對順序表L作直接插入排序
for ( i = 2; i <=L.length; i++) //假定第一個記錄有序
{ L.r[0]= L.r[i];
j=i-1 ; //先將待插入的元素放入“哨兵”位置
while（L[0] .key<L[j].key)
{ L.r[j+1]= L.r[j];
j-- ; } //只要子表元素比哨兵大就不斷后移
L.r[j+1]= L.r[0]; //直到子表元素小于哨兵，將哨兵值送入
//當(dāng)前要插入的位置（包括插入到表首）
}
}
2） 折半插入排序
既然子表有序且為順序存儲結(jié)構(gòu)，則插入時采用折半查找定可加速。
優(yōu)點：比較次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。
時間效率：雖然比較次數(shù)大大減少，可惜移動次數(shù)并未減少， 所以排序效率仍為O(n2) 。
空間效率：仍為 O（1）
穩(wěn) 定 性： 穩(wěn)定
若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？
答：行，而且無需移動元素，時間效率更高！
但請注意：單鏈表結(jié)構(gòu)無法實現(xiàn)“折半查找”
3） 表插入排序
基本思想：在順序存儲結(jié)構(gòu)中，給每個記錄增開一個指針分量，在排序過程中將指針內(nèi)容逐個修改為已經(jīng)整理（排序）過的后繼記錄地址。
優(yōu)點：在排序過程中不移動元素，只修改指針。
此方法具有鏈表排序和地址排序的特點
表插入排序算法分析：
① 無需移動記錄，只需修改指針值。但由于比較次數(shù)沒有減少，故時間效率仍為O(n2) 。
② 空間效率肯定低，因為增開了指針分量（但在運算過程中沒有用到更多的輔助單元）。
③ 穩(wěn)定性：25和25*排序前后次序未變，穩(wěn)定。
注：此算法得到的只是一個有序鏈表，查找記錄時只能滿足順序查找方式。
5）希爾（shell）排序
基本思想：先將整個待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行一次直接插入排序。
優(yōu)點：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。
◆ 交換排序（冒泡排序、快速排序）。
交換排序的基本思想是：兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。
1) 冒泡排序
基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。
優(yōu)點：每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。
前提：順序存儲結(jié)構(gòu)
冒泡排序的算法分析：
時間效率：O（n2) —因為要考慮最壞情況
空間效率：O（1） —只在交換時用到一個緩沖單元
穩(wěn) 定 性： 穩(wěn)定 —25和25*在排序前后的次序未改變
冒泡排序的優(yōu)點：每一趟整理元素時，不僅可以完全確定一個元素的位置（擠出一個泡到表尾），還可以對前面的元素作一些整理，所以比一般的排序要快。
2） 快速排序
基本思想：從待排序列中任取一個元素 (例如取第一個) 作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個子表的元素只剩一個。此時便為有序序列了。
優(yōu)點：因為每趟可以確定不止一個元素的位置，而且呈指數(shù)增加，所以特別快！
前提：順序存儲結(jié)構(gòu)
時間效率：O(nlog2n) —因為每趟確定的元素呈指數(shù)增加
空間效率：O（log2n）—因為遞歸要用棧(存每層low，high和pivot)
穩(wěn) 定 性： 不 穩(wěn) 定 —因為有跳躍式交換。
◆ 選擇排序（簡單選擇排序、樹形選擇排序、堆排序）。
選擇排序的基本思想是：每一趟在后面n-i 個待排記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i 個記錄。
1）簡單選擇排序
思路異常簡單：每經(jīng)過一趟比較就找出一個最小值，與待排序列最前面的位置互換即可。
——首先，在n個記錄中選擇最小者放到r[1]位置；然后，從剩余的n-1個記錄中選擇最小者放到r[2]位置；…如此進(jìn)行下去，直到全部有序為止。
優(yōu)點：實現(xiàn)簡單
缺點：每趟只能確定一個元素，表長為n時需要n-1趟
前提：順序存儲結(jié)構(gòu)
Void SelectSort(SqList &L ) {
for (i=1; i<L.length; ++i){
j = SelectMinKey(L,i);
if( i!=j ) r[i] ?r[j];
} //for
} //SelectSort
2）錦標(biāo)賽排序 (又稱樹形選擇排序)
基本思想：與體育比賽時的淘汰賽類似。
首先對 n 個記錄的關(guān)鍵字進(jìn)行兩兩比較，得到 én/2ù 個優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來。然后在這 én/2ù 個較小者之間再進(jìn)行兩兩比較，…，如此重復(fù)，直到選出最小關(guān)鍵字的記錄為止。
優(yōu)點：減少比較次數(shù)，加快排序速度
缺點：空間效率低
3）堆排序
1.堆的定義：設(shè)有n個元素的序列 k1，k2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為堆。
解釋：如果讓滿足以上條件的元素序列 （k1，k2，…，kn）順次排成一棵完全二叉樹，則此樹的特點是：樹中所有結(jié)點的值均大于（或小于）其左右孩子，此樹的根結(jié)點（即堆頂）必最大（或最?。?。
2. 怎樣建堆？
步驟：從最后一個非終端結(jié)點開始往前逐步調(diào)整，讓每個雙親大于（或小于）子女，直到根結(jié)點為止。
堆排序算法分析：
時間效率： O(nlog2n)。因為整個排序過程中需要調(diào)用n-1次HeapAdjust( )算法，而算法本身耗時為log2n；
空間效率：O(1)。僅在第二個for循環(huán)中交換記錄時用到一個臨時變量temp。
穩(wěn)定性： 不穩(wěn)定。
優(yōu)點：對小文件效果不明顯，但對大文件有效。
學(xué)習(xí)要點：
◆ 各種排序所基于的基本思想。
◆ 在“最好”和“最差”情況下，排序性能的分析，是否是穩(wěn)定排序的結(jié)論，時間效率和空間效率。
◆ 對每種排序方法的學(xué)習(xí)，應(yīng)掌握其本質(zhì)（排序所基于的思想），熟練掌握手工模擬各種排序的過程。
補(bǔ)充：
1.排序算法的好壞如何衡量？
時間效率——排序速度（即排序所花費的全部比較次數(shù)）
空間效率——占內(nèi)存輔助空間的大小
穩(wěn)定性——若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。
2.“快速排序”是否真的比任何排序算法都快？
——基本上是，因為每趟可以確定的數(shù)據(jù)元素是呈指數(shù)增加的。
