VisuAlgo!
一，Date Structure的核心技術(shù)是分解和抽象
二，基本概念和常用術(shù)語
①Date是對信息的一種符號表示，包括數(shù)字，文檔，記錄，數(shù)組，句子，單詞，算式都成為數(shù)據(jù)。在計(jì)算機(jī)中，任何能輸入到計(jì)算機(jī)中的信息都叫做數(shù)據(jù)。
——Date Object是眾多具有相同性質(zhì)的Date Element的集合
②Date Element是Data的基本單位，在計(jì)算機(jī)科學(xué)中作為整體進(jìn)行考慮和處理。
③Date Item是Date Element的最小不可分割單位。
④Date Structure是具有一種或多種關(guān)系的數(shù)據(jù)元素的集合，按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按照一定的存儲方式存儲在計(jì)算機(jī)存儲器中，在其之上定義一種運(yùn)算的集合，就成為一個Date Structure，計(jì)算機(jī)在存儲數(shù)據(jù)時(shí)，不僅要存儲數(shù)據(jù)本身，還要存儲數(shù)據(jù)之間相互的邏輯結(jié)構(gòu)。存儲方式成為物理結(jié)構(gòu)或存儲結(jié)構(gòu)，在邏輯結(jié)構(gòu)上存儲“做什么”，在存儲結(jié)構(gòu)上規(guī)定數(shù)據(jù)“如何做”。
三，邏輯結(jié)構(gòu)
1，邏輯結(jié)構(gòu)通常分為四大類：
集合（無關(guān)系）
線性結(jié)構(gòu)（唯一前驅(qū)和后繼）
非線性結(jié)構(gòu)：樹形結(jié)構(gòu)（唯一前驅(qū)，多后繼），圖形結(jié)構(gòu)（多前驅(qū)多后繼）
例如
D={1,2,3,4,5,6} //數(shù)據(jù)元素的集合
R={r} //對應(yīng)關(guān)系的集合
r={（1,2），（2,3），（3,4），（4,5），（5,6）} //序偶的集合
——關(guān)系r是序偶的集合，如名字，有順序的兩個結(jié)點(diǎn)，稱為序偶：
①數(shù)據(jù)元素的集合+數(shù)據(jù)關(guān)系的集合
②每個數(shù)據(jù)元素成為一個結(jié)點(diǎn)
③前一結(jié)點(diǎn)稱為后一結(jié)點(diǎn)的前驅(qū)，反之，則稱為后繼
四，存儲結(jié)構(gòu)
1，計(jì)算機(jī)的存儲結(jié)構(gòu)是由有限個存儲單元組成，每個單元有唯一的地址，地址連續(xù)編碼，多個則稱為存儲區(qū)域
2，4種基本存儲方法
①順序存儲：把邏輯上相鄰的元素存儲在物理位置相鄰的位置，邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。
②鏈?zhǔn)酱鎯Γ簩⑦壿嬒噜彽脑夭淮鎯υ谖锢砦恢孟噜彽奈恢茫前阉加玫拇鎯卧譃閮刹糠郑徊糠执鎯?shù)據(jù)元素本身，另一部分存儲結(jié)點(diǎn)后繼元素的地址。
③索引存儲：存儲節(jié)點(diǎn)信息的同時(shí)，建立索引表，索引表的每一項(xiàng)包含關(guān)鍵字和地址，關(guān)鍵字能唯一識別數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)，針對數(shù)據(jù)內(nèi)容的存儲公式
④散列存儲：以數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵字為自變量，通過散列函數(shù)來定向計(jì)算該元素的存儲位置，針對數(shù)據(jù)內(nèi)容的存儲方式
五，運(yùn)算集合
1，每種邏輯結(jié)構(gòu)都有一種運(yùn)算的集合
①引用型運(yùn)算:不改變原有element的狀態(tài)，只進(jìn)行讀取
②加工型運(yùn)算:改變原有element的狀態(tài)，如內(nèi)容，個數(shù)等。
六，抽象數(shù)據(jù)類型
1，數(shù)據(jù)類型
①類型顯示或隱式的規(guī)定了在程序執(zhí)行期間變量的一切可能取值和一切在這些值上可能進(jìn)行的操作，數(shù)據(jù)類型就是一組值的集合加上在這些值上進(jìn)行的操作的集合之和。
②數(shù)據(jù)結(jié)構(gòu)分兩類，一類是基本類型，是給定的，值不可分解，如int，double;一類是結(jié)構(gòu)類型，其可分解，其值也可分解，如結(jié)構(gòu)體，數(shù)組etc.
③一般數(shù)據(jù)類型又稱為預(yù)定義數(shù)據(jù)類型
2，抽象數(shù)據(jù)類型
①是一個數(shù)學(xué)模型以及在它上面定義的一組操作(數(shù)據(jù)的邏輯結(jié)構(gòu)和其上定義的操作)
②通常由用戶自定義其邏輯結(jié)構(gòu)與操作說明，不考慮結(jié)構(gòu)和操作的具體實(shí)現(xiàn)
③特點(diǎn):使用和實(shí)現(xiàn)分離開(類型的定義和其實(shí)現(xiàn)分離開)
七，線性表
1，邏輯結(jié)構(gòu)
①L = （a1,a2,a3……an-1,an）
a.數(shù)據(jù)元素個數(shù)n稱為表的長度，n=0時(shí)稱為空表
b.非空線性表中，存在唯一一個只有后繼沒前驅(qū)的表頭元素，同理，職業(yè)前驅(qū)沒有后繼的稱為表尾元素
c.除表頭元素有且僅有一個前驅(qū)，除表尾元素有且僅有一個后繼
d.表中元素?cái)?shù)據(jù)類型相同，n的取值個數(shù)有限
②操作
a.初始化，構(gòu)造一個新表
b.求線性表的長度
c.按序號取元素
d.按值查找元素，返回第一個結(jié)點(diǎn)的位置，若沒找到，返回一個值代表沒有找到
e.插入
f.刪除
g.清空
2，存儲結(jié)構(gòu)
①順序存儲結(jié)構(gòu)
//簡單直接，所占空間連續(xù)，隨機(jī)存取任一結(jié)點(diǎn)按物理位置相鄰來實(shí)現(xiàn)其邏輯結(jié)構(gòu)，叫做順序表
a.定義，在一個結(jié)構(gòu)體中定義一個數(shù)組存貯數(shù)據(jù)元素，用一個length存儲表長
// #define MaxLen 100;
typedef int DataType;
typedef struct
{ DataType data[MaxLen];
int length;
}SeqList;
b.初始化，令L->length = 0；即可
c.求表長，return L->length；即可
d.按位置取結(jié)點(diǎn)值，若查找位置小于1或者大于MaxLen返回錯誤，若范圍正確return data[i - 1]；即可
e.按值取結(jié)點(diǎn)位置，用一個i=0來初始化，用一組循環(huán)來比較第data[i]個元素的值是否為所需值，若不是i++若是return i；即是所求值結(jié)點(diǎn)所在位置。
f.插入，將每個數(shù)據(jù)元素依次后移，然后插入新節(jié)點(diǎn)，將表長+1
//void InsertList(SsqList * L, DataType e,int i)
{//錯誤檢測
for(int j = L -> length - 1; j >= i - 1;j --)
L- > data[j+1] = L -> data[j];
L -> data[i-1] = e;
L -> length ++;
}
//注意當(dāng)空間已滿，或插入位置非法時(shí)，不可進(jìn)行插入操作
g.刪除,先去除欲刪除節(jié)點(diǎn)，再將i+1……n的元素依次移動到i……n-1
②鏈?zhǔn)酱鎯Y(jié)構(gòu)
散亂，結(jié)點(diǎn)次序與物理順序不一定一致，由于第一個結(jié)點(diǎn)沒有前驅(qū)，要用一個head來存儲頭結(jié)點(diǎn)的地址
L=（head，a1,a2,....an）
——應(yīng)用malloc申請結(jié)點(diǎn)變量地址，用free函數(shù)來釋放一個結(jié)點(diǎn)變量地址
a.單鏈表：
(1).建立set，一個結(jié)構(gòu)體內(nèi)放一個存放數(shù)據(jù)內(nèi)容的變量和一個存放下一個結(jié)構(gòu)體的指針。
——頭插法：在head與a1間插入新結(jié)點(diǎn)
——尾插法：在an后插入新結(jié)點(diǎn)
(2).查找Locate，單鏈表中不會像順序表中那樣直接按序號找元素，只能從頭指針開始，逐一循環(huán)。
——按序查：……
——按值查：……
(3).插入Inser，插入到第i個結(jié)點(diǎn)的位置，步驟
one.找到第ai-1個結(jié)點(diǎn)的位置
two.創(chuàng)建一個新結(jié)點(diǎn) s
three.新結(jié)點(diǎn)指針指向ai
four.令q指向新結(jié)點(diǎn)。
——例如：
ListNode *p, q,s;
int j = 1; p = head;
if(i<1||i>GetLength(head)+1)exit(1);
s=(ListNode )malloc(sizeof(ListNode));
s->data = x;
while(j <= i)
{ q=p;p=p->next;
j++; }
s->next = q->next;
q->next = s;
(4)刪除delete，要刪除結(jié)點(diǎn)i，首先找到i-1個結(jié)點(diǎn)，用一個指針指向i，然后把i-1個結(jié)點(diǎn)的指針指向i+1，最后free指向i的指針
b.循環(huán)鏈表，將表中終端結(jié)點(diǎn)的指針域指向表頭
(1)沒有NULL指針，終止條件不是p或者p->next是否為空，而是判斷他們是否等于某一特定指針
(2)從任意一結(jié)點(diǎn)開始，不止能訪問其后繼結(jié)點(diǎn)，能訪問所有結(jié)點(diǎn)。
c.雙鏈表，結(jié)點(diǎn)結(jié)構(gòu)體中，增加一項(xiàng)指針域prior，用于存儲上一結(jié)點(diǎn)的位置，插入和刪除必須同時(shí)修改兩個方向上的指針。
d.靜態(tài)鏈表……
e.應(yīng)用,一元多項(xiàng)式的加法
3線性表總結(jié)
①順序表與鏈表，若較為穩(wěn)定則使用順序表，若需要頻繁的插入或刪除操作，則用鏈表
②線性表初期建表容易，無額外開銷，可以隨機(jī)訪問任一結(jié)點(diǎn)，缺點(diǎn)是建表初期需要預(yù)估大小，插入刪除操作相應(yīng)繁瑣，需要頻繁的移動數(shù)組元素。
③鏈表建表相應(yīng)復(fù)雜，額外開銷未知，不能隨機(jī)訪問任一結(jié)點(diǎn)，但內(nèi)存管理完美，執(zhí)行刪除插入操作復(fù)雜度小。
④由于高級語言中沒有指針類型，可以定義一個結(jié)構(gòu)體數(shù)組，為數(shù)組的每個元素附加一個鏈接指針，從而形成靜態(tài)鏈表。
八，堆棧
1.定義
①限定僅在表的一端進(jìn)行插入刪除的線性表，通常稱插入刪除的一端稱為棧頂，另一端稱為棧底，特點(diǎn)：先進(jìn)后出，后進(jìn)先出，故也稱為后進(jìn)先出表。
2.基本運(yùn)算
①初始化
②壓棧
③出棧
④判斷空棧
⑤取棧頂元素
3.順序存儲結(jié)構(gòu)(順序棧)
#define Maxsize <存儲數(shù)據(jù)元素的最大個數(shù)>
typedef <棧中元素實(shí)際數(shù)據(jù)類型> SElemType;
typedef struct {
Selemtype data[Maxsize];
int top;
}STACK;
STACK *s；
——習(xí)慣上將top = -1表示?？?，top = Maxsize - 1表示棧滿，常稱此處的top為“棧頂指針”，但其實(shí)并不是指針類型變量。
①初始化，top=-1.
②壓棧，首先判斷是否棧滿，再通過s->top+1后s->data[s->top]來完成壓棧
③出棧，判斷是否為空棧，再先把s->data[s->top]賦值給指針變量后，后s->top-1
④判斷空棧，判斷s->top是否為-1
⑤取棧頂元素，判斷是否為空棧，再先s->data[s->top]賦值給數(shù)據(jù)類型變量，后s->top-1
4.鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈棧）
typedef <棧中元素實(shí)際數(shù)據(jù)類型> SElemType;
typedef struct Snode{
SElemtype data；
struct Snode next；
}LinkSTACK；
LinkSTACK top；
①初始化，malloc函數(shù)為top分配內(nèi)存，再做內(nèi)存分配成功判斷，若成功top->next=NULL；
②壓棧，為一個s分配內(nèi)存空間，判斷是否成功，若成功，頭插法插入鏈表結(jié)點(diǎn)
③出棧，判斷是否為空棧，若不是，用一個s存儲棧頂元素內(nèi)容，隨后刪除鏈表結(jié)點(diǎn)，釋放s的內(nèi)存地址。
④判斷空棧，判斷s->next是否為NULL
⑤取棧頂元素，判斷是否為空棧，再先s->data[s->top]賦值給數(shù)據(jù)類型變量，后s->top-1
5.遞歸
①使用遞歸的三種情況
（1）.很多函數(shù)是遞歸定義的
（2）.有些數(shù)據(jù)結(jié)構(gòu)本身固有遞歸特定，可以利用遞歸來定義
（3）.使用遞歸化解更簡單
②兩個限制條件
（1）.規(guī)模較大的原問題能分解成一個或多個規(guī)模較小但具有類似于原問題特性的問題。
（2）.存在一個或多個無需分解即可直接求解的最小子問題，經(jīng)過有限次遞歸后，子問題的規(guī)模減至最小。
九，隊(duì)列
1，定義
僅限在隊(duì)尾進(jìn)行插入操作，在對頭進(jìn)行刪除操作的“先進(jìn)先出”表。
①初始化
②入隊(duì)
③出隊(duì)
④判斷空隊(duì)
⑤取棧頂元素
2，順序存儲結(jié)構(gòu)
typedef 實(shí)際元素?cái)?shù)據(jù)類型 QElemtype;
typedef struct{
QElemType data[Maxsize];
int front,rear;
}QUEUE;
——順序隊(duì)結(jié)構(gòu)體中數(shù)組低下標(biāo)一端為隊(duì)頭，高下標(biāo)一端為隊(duì)尾
——fornt總是指向?qū)︻^元素的前一位置，rear總是指向隊(duì)尾元素
——假溢出現(xiàn)象用循環(huán)隊(duì)列來處理
①初始化 ： Q->front = Q->rear = 0;
②入隊(duì)：先判斷是否空隊(duì)，然后Q->rear = （Q->rear+1）%Maxsize； 對rear指針指向地方賦值即可
③出隊(duì)：先判斷是否空隊(duì)，然后Q->rear = （Q->rear+1）%Maxsize； 用指針指向front指針指向地方，然后釋放即可。
④判斷空隊(duì) ：判斷是否Q->front = Q->rear;
⑤取隊(duì)頭元素：*x = (Q -> data[Q->front+1]) % Maxsize
⑥計(jì)算隊(duì)列成員個數(shù)：(rear - front +Maxsize)%Maxsize
3，鏈?zhǔn)酱鎯Y(jié)構(gòu)
typedef 實(shí)際元素?cái)?shù)據(jù)類型 QElemType；
typedef struct qnode{
QElemType data；
struct qnode *next；
}QTYPE；
typedef struct {
QTYPE * front， *rear；
}LinkQUEUE；
LinkQUEUE LQ；
——同時(shí)帶有頭指針和尾指針的單鏈表
①初始化：新建結(jié)點(diǎn)p，申請空間，判斷內(nèi)存，p->next = NULL; LQ->front = LQ ->rear = p;
②入隊(duì):新建結(jié)點(diǎn)s，申請空間，判斷內(nèi)存,s->data = x; s->next = NULL; LQ->rear->next = s; LQ ->rear = s;
③出隊(duì):
void OutQueue(LinkQUEUE * LQ, QElemType *x)
{
QTYPE *p;
if(EmptyQueue(LQ))
{printf("cuowu");
return 0;}
p = LQ->front->next;
*x = p->data;
LQ->front->next = p->next;
if(LQ->front->next == NULL)
LQ->rear = LQ->front;
free(p);
}
④判斷空隊(duì):LQ->front == LQ ->rear?1:0;
⑤取隊(duì)頭元素:*x = LQ->front->next->data;
九，串
1，定義
又稱作字符串，形如S = “a1a2a3a4an-1”
①所含字符個數(shù)稱為串的長度，主串中任意連續(xù)字符組成的子序列稱為串的子串
②字符串以'\0'結(jié)束，所以串的實(shí)際長度要多1個。串中每個字符占1個字節(jié)
2，順序存儲結(jié)構(gòu)
#define MaxLen <最大串長>
typedef struct string{
char str[MaxLen];
int curlen;
};
①判斷Equal，先比較長度是否一樣，再比較每一個字符是否一樣
②鏈接concat,先計(jì)算兩個字符串的長度和，將t復(fù)制到s后面。
3，鏈?zhǔn)酱鎯Y(jié)構(gòu)
typedef struct Lstring{
char data；
struct Lstring * next；
}Lstring；
①判斷Equal，無視長度，同上
②鏈接concat，無視長度，同上
④求子串Lsubstr,先進(jìn)行錯誤判斷，找到指定的i位置，開始向后賦值n位給一個新的指針，返回
4，優(yōu)缺點(diǎn)，即鏈?zhǔn)酱鎯晚樞虼鎯Φ睦厦 ?br>
5，應(yīng)用，
1，文本編輯器
2，KMP判子串算法
十，數(shù)組
1，定義
①數(shù)據(jù)元素固定，不可后添加刪除。
②元素?cái)?shù)據(jù)類型相同
③每個數(shù)據(jù)元素值有唯一下標(biāo)對應(yīng)
④隨機(jī)存儲結(jié)構(gòu)，隨機(jī)存取任意元素
⑤數(shù)據(jù)元素是一個數(shù)據(jù)結(jié)構(gòu)，可以是線性表中的一個元素，也可以是一個線性表
——下標(biāo)個數(shù)又稱為數(shù)組的維度
2，順序存儲結(jié)構(gòu)
①一維數(shù)組按下標(biāo)順序分配即可
②多維數(shù)組：
（1）：行優(yōu)先，a00，a01，a02，a10，a11……
（2）：列優(yōu)先，a10，a20，a30，a11，a21……
3，應(yīng)用：
①矩陣的壓縮存儲
——若aij==aji，則稱Anxn為矩陣
（1）對稱矩陣
——關(guān)于對角線對稱，這樣我們就只需要存儲上半角或者下半角的元素，就節(jié)約了一半
（2）三角矩陣
——下三角或者上三角全部為c（常數(shù)）或者0，c或0只用一個數(shù)組元素來存儲
（3）對角矩陣
——對角線附近有元素，其余元素全是0
（4）稀疏矩陣（非零元素遠(yuǎn)大于0元素個數(shù)）
——使用三元組（橫坐標(biāo)，縱坐標(biāo)，值），運(yùn)用數(shù)組行優(yōu)先順序來保存為線性表
——三元組結(jié)構(gòu)體：
typedef struct {
int row；
int col；
elementtype val；
}Triple；
——三元組順序表：
typedef struct {
int m；
int n；
int len；//非零元素總數(shù)
Triple data[Maxsize]；
}TMatrix M；
①初始化
M->m = 0;M->n = 0;M->len = 0;
②創(chuàng)建一個稀疏矩陣
傳入稀疏矩陣的行，列值。賦值M->mM->n，輸入行列值，傳入M->data[k].row/col/val，每一次增加k的值，最后傳入M->k.
③輸出稀硫矩陣
……
④求轉(zhuǎn)置矩陣
先將M中的m，n，len賦值給t，再將每一個m里面的row col val賦值給t
⑤矩陣相加
先判斷行數(shù)，優(yōu)先加行數(shù)小的，再判斷列數(shù)，優(yōu)先加列數(shù)小的，若行列數(shù)都相等，則直接賦值data的三維坐標(biāo)，val為n+m的val值總和。最后將mn的剩余數(shù)據(jù)按序賦值到t。
例如：void MatrixAdd（TMatrix* M , TMatrix* N, TMatrix* T)
{int i = 0,j = 0, k = 0;
elementtype v;
if(M->m!=N->m||M->n!=N->n)
{printf("矩陣不匹配");
exit（1）}；
T->m = M->m;T->n = M->n;
while(ilen&&jlen)
{
if(M->data[i].rowdata[j].row)
{
T->data[k].row=M->data[i].row;
T->data[k].col=M->data[i].col;
T->data[k].val=M->data[i].val;
k++;
i++;
}
else if(M->data[i].row > N->data[j].row)
{
T->data[k].row=N->data[i].row;
T->data[k].col=N->data[i].col;
T->data[k].val=N->data[i].val;
k++;
j++;
}
else//行相等
{
if(M->data[i].col < N->data[j].col)
{
T->data[k].row=M->data[i].row;
T->data[k].col=M->data[i].col;
T->data[k].val=M->data[i].val;
k++;
i++;
}
else if(M->data[i].row > N->data[j].row)
{
T->data[k].row=N->data[i].row;
T->data[k].col=N->data[i].col;
T->data[k].val=N->data[i].val;
k++;
j++;
}
else//行列都相等
{
v = M->data[i].val + N->data[j].val;
T->data[k].row=M->data[i].row;
T->data[k].col=M->data[i].col;
T->data[k].val = v;
}
i++;
j++;
}
}
for(;ilen;i++)
{
T->data[k].row = M->data[i].row;
T->data[k].col = M->data[i].col;
T->data[k].val = M->data[i].val;
k++;
}
for(;ilen;i++)
{
T->data[k].row = M->data[j].row;
T->data[k].col = M->data[j].col;
T->data[k].val = M->data[j].val;
k++;
}
T->len = k;
}
——————難點(diǎn)是行號的匹配問題，要進(jìn)行行號的匹配
十，樹
1，基本術(shù)語
重要的概念：
①度，擁有的子樹個數(shù)
②葉子結(jié)點(diǎn)（分支結(jié)點(diǎn)）：（非）終端節(jié)點(diǎn)的意思
③森林：互不相交的樹的集合
④深度：層次數(shù)
表示方法：樹形圖，文氏圖，廣義表，凹入表示法
2，二叉樹
——每個節(jié)點(diǎn)只有兩個子樹左子樹，右子樹，而且有序！左右子樹互換位置是兩種二叉樹
性質(zhì)①二叉樹的第i層上有2^（i - 1）
性質(zhì)②深度為k的二叉樹有2^k-1個結(jié)點(diǎn)
性質(zhì)③葉子結(jié)點(diǎn)=結(jié)點(diǎn)數(shù)+1
兩種形態(tài)：
①滿二叉樹，即所有結(jié)點(diǎn)都有左子樹和右子樹
②完全二叉樹，左子樹有，右子樹不一定有，左子樹沒有，右子樹一定沒有。
（1）有n個結(jié)點(diǎn)的完全二叉樹深度為【log2n】+1
（2）
順序存儲結(jié)構(gòu)
typedef int TElemType；
typedef TElemType SqBiTree【最大容納數(shù)】
SqBiTree bt；
按從左到右從上到下給完全二叉樹編號存入數(shù)組，沒有子樹的地方用0來表示。
鏈?zhǔn)酱鎯Y(jié)構(gòu)
typedef int TElemType；
typedef struct node {
TElemType data；
struct node * lchild， rchild；
}BiTnode， BiTree；
（1）二叉鏈表存儲結(jié)構(gòu) lchild data rchild 三個結(jié)點(diǎn)域
（2）三叉鏈表存儲結(jié)構(gòu) lchild data parent rchild 四個結(jié)點(diǎn)域
（3）線索鏈表
遍歷
（1）先序遍歷（DLR）
1,遞歸實(shí)現(xiàn)
void x（BiTree bt） {
if（bt） {
visit（bt->data）；
x（bt->lchild）;
x（bt->rchild）;
}
}
2,非遞歸實(shí)現(xiàn)
void x（BiTree bt）{
Bitree stack【Maxsize】；//定義順序棧
int top = -1；
BiTree p = bt;
while(p||top!=-1) {
while(p) {
visit(p->data);//訪問結(jié)點(diǎn)數(shù)據(jù)
if(棧沒滿) {
top++； stack【top】 = p }
p = p->lchild;
}
if(top!=-1){p=stack[top]; top--; p = p->rchild;}
}
（2）中序遍歷（LDR）,改變visit函數(shù)的位置
（3）后序遍歷（LRD）,改變xisit函數(shù)的位置
——便利操作是非線性結(jié)構(gòu)線性化
——訪問根結(jié)點(diǎn)和遍歷其左右子樹的順序不同，每一次遍歷每個結(jié)點(diǎn)需要經(jīng)過三次，“先后序”遍歷只是在這三次的那一次訪問結(jié)點(diǎn)元素的區(qū)別
（4）層次遍歷
利用順序隊(duì)列數(shù)據(jù)結(jié)構(gòu)
二，二叉樹的線索化。
三，樹和森林
1，雙親表示法， typedef char TElemType；
typedef struct PTnode {
TElemType data；
int parent；
}PTNode；
typedef struct {
PTNode node【】；
int r，n；
}
2，孩子表示法，typedef struct CTNode {
int child；
struct CTNode * next；
} * ChildPtr；
typedef struct CTNode {
TElemType data；
ChildPtr FirstChild；
}CTBox；
typedef struct {
CTBox nodes【】；
int r， n；
}CTree；
3，也可以綜合以上兩種制造雙親孩子鏈表，不做解釋
4，兄弟孩子表示法
（與二叉樹的表示方法差不多，顧已成為二叉樹表示法）
typedef char TElemType；
typedef struct CSNode {
TElemType data；
struct CSNode *firstchild * nextsibling；
}CSNode， * CSTree；
三，
1，樹與二叉樹的轉(zhuǎn)換
1，因?yàn)闃涞男值芎⒆颖硎痉ǎ櫧o定一棵樹，可以找到唯一的一顆二叉樹與之對應(yīng)
1，樹轉(zhuǎn)換為二叉樹
①凡是下一個兄弟，用線連起來（加線）；
②去掉每個結(jié)點(diǎn)除第一個孩子之外與孩子的連線（抹線）
③排列（調(diào)整）
2，二叉樹轉(zhuǎn)化為樹
①若結(jié)點(diǎn)是雙親的左孩子，則把該結(jié)點(diǎn)的右結(jié)點(diǎn)，右結(jié)點(diǎn)的右結(jié)…都與雙親連起來（加線）
②抹去所有雙親結(jié)點(diǎn)與右孩子的連線（抹線）
③排列（調(diào)整）
——這樣轉(zhuǎn)換得到二叉樹和普通樹唯一對應(yīng)
2，森林與二叉樹的轉(zhuǎn)換
1，森林轉(zhuǎn)換為二叉樹
將森林中的每一棵樹轉(zhuǎn)為二叉樹（轉(zhuǎn)換），將每一個二叉樹的根節(jié)點(diǎn)連線（加線），然后調(diào)整
2，二叉樹轉(zhuǎn)換為森林
抹去二叉樹根節(jié)點(diǎn)右鏈與其所有右鏈上的右結(jié)點(diǎn)連線（抹線），將二叉樹轉(zhuǎn)換為樹（轉(zhuǎn)換），調(diào)整
3，樹和森林的遍歷
四，二叉樹的應(yīng)用
最后，圖
一 重要定義。
1.弧或邊帶權(quán)的圖稱為有向網(wǎng)或無向網(wǎng)
2.如果無向圖中任意一對頂點(diǎn)都是連通的，就成為連通圖
3.如果有向圖中，對于每一對頂點(diǎn)vi和vj都存再一條vi到vj的路徑以及vj到vi的路徑，就成為強(qiáng)連通圖
4.度表示和頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目，有向圖存在出度和入度，顧名思義
5.路徑上經(jīng)過邊的數(shù)目稱為路徑長度，除頂點(diǎn)和終點(diǎn)可以相同外，其余各點(diǎn)不同稱為簡單路徑，若起點(diǎn)和終點(diǎn)相同稱為環(huán)或回路。
二 存儲結(jié)構(gòu)。
1.鄰接矩陣
（1）無向圖的鄰接矩陣通常是對稱的，有向則不是，因?yàn)椋╲i，vj）與（vj，vi）的不同
（2）便于查找任意邊或邊上的權(quán)
——查找圖中是否有邊（vi，vj）查找第i行第j列上的元素是否為有效數(shù)
（3）便于查找任一頂點(diǎn)的度
——對無向圖，vi的度是第i行或第i列上的有效元素個數(shù)
——對有向圖，vi的出度就是第i行的有效元素的個數(shù)，入度就是第i列上的有效元素個數(shù)
typedef int V；
typedef struct {
int A【】【】//鄰接矩陣存儲頂點(diǎn)間的鄰接關(guān)系
V v【】//存儲頂點(diǎn)的表
int vex，arc//圖的頂點(diǎn)數(shù)和弧數(shù)
}MGraph；
（4）缺點(diǎn)?。。捍鎯臻g的浪費(fèi)，無論有多少條邊總是需要開銷nXn空間
2.鄰接表
（1）保存有向圖中，把保存出邊的叫鄰接表，保存入邊的叫逆鄰接表，需要占用
n+e個存儲空間
（2）找一個頂點(diǎn)的邊或者鄰接點(diǎn)，從頂點(diǎn)表中取出對應(yīng)的表頭指針，從表頭指針開始查找即可
typedef int V；
typedef struct ArcNode{//定義邊表結(jié)點(diǎn)
int adjvex；//該弧指向頂點(diǎn)的位置
struct ArcNode * nextarc；//指向下一條弧的指針
int info；//該弧上的權(quán)值
}ArcNode；
typedef struct VNode {
Vertex data；
ArcNode *firstarc； //指向邊表
}VNode；
typedef struct {
VNode adjlist【】；
int vexnum， arcnum//頂點(diǎn)數(shù)，弧數(shù)
}
3.鄰接多重表
頂點(diǎn)表還是由data值域存放的頂點(diǎn)加上firstedge指針域存放的
4.十字鏈表
三 圖的遍歷
1.深度優(yōu)先搜索
從一個頂點(diǎn)開始，先訪問一個頂點(diǎn)的鄰接頂點(diǎn)，依次下去，直到?jīng)]有沒訪問的鄰接頂點(diǎn)的鄰接頂點(diǎn)，就倒回去，直到有沒被訪問的鄰接頂點(diǎn)的那個節(jié)點(diǎn)再訪問其沒被訪問的鄰接頂點(diǎn)
（1）采用visited數(shù)組表示頂點(diǎn)是否已經(jīng)被訪問
（2）采用鄰接表的存儲方式表示圖，整個算法分DFS和DFST
2.廣度優(yōu)先搜索
從一個頂點(diǎn)開始先訪問一個頂點(diǎn)所有的鄰接頂點(diǎn)，然后按照順序依次訪問剛訪問那一組鄰接頂點(diǎn)的鄰接頂點(diǎn)，就像一個樹一樣
（1）也需要一個訪問標(biāo)志visited數(shù)組
（2）需要設(shè)置一個隊(duì)列Queue來記錄已被訪問的頂點(diǎn)順序
（3）采用鄰接表的存儲方式表示圖，整個算法分BFS和BFST
四 最小生成樹
對于網(wǎng)絡(luò)來說，弧一般都是帶權(quán)的，，對于一個連通圖G，其最小生成樹指的是包括其所有頂點(diǎn)，以及部分邊，滿足邊權(quán)總和最小，圖是連通的這樣一個。
1.普里姆算法
2.克魯斯卡爾算法
五 DAG有向無環(huán)圖
1.拓?fù)渑判?br>
通常把用頂點(diǎn)表示活動，弧表示活動間先后順序的有向圖稱為頂點(diǎn)的網(wǎng)——AOV網(wǎng)
在AOV網(wǎng)中，若不存在回路，則所有頂點(diǎn)都可以排成一個序列，所有前驅(qū)活動都排在后驅(qū)活動的前面，這叫拓?fù)湫蛄?，由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程叫做拓?fù)渑判?br>
方法：（1）在AOV網(wǎng)中選擇一個入度為0的點(diǎn)把它寫入拓?fù)湫蛄兄?br>
（2）在AOV網(wǎng)中刪除該點(diǎn)以及其所有的出邊
結(jié)果：（1）網(wǎng)中全部頂點(diǎn)被輸出，說明網(wǎng)中不存在回路（2）頂點(diǎn)未被全部輸出，且網(wǎng)中不存在入度為0的頂點(diǎn)，說明有回路
采用鄰接表作為有向圖的存儲結(jié)構(gòu)，需要設(shè)置一個一維整型數(shù)組，用來保存圖中每個頂點(diǎn)的入度值
算法：（1）將入度為0的頂點(diǎn)入棧
（2）從堆棧中彈出棧頂元素：
①輸出棧頂元素
②把該頂點(diǎn)發(fā)出的所有有向邊刪去，即將所有后繼頂點(diǎn)的入度減1，若減1后該頂點(diǎn)入度為0，則該頂點(diǎn)入棧
③重復(fù)②直到?jīng)]有入度為0的頂點(diǎn)
實(shí)現(xiàn)：
2.關(guān)鍵路徑
六 最短路徑
1,.某一源頭到各定點(diǎn)
2.每一對頂點(diǎn)之間
