附注說明：上圖中刪完尾節(jié)點之后，新鏈表的尾節(jié)點下標(biāo)應(yīng)為n-1。不過由于作圖時只做了尾節(jié)點，故用圖中的n2節(jié)點代替。

刪除尾節(jié)點的代碼如下：

刪除非頭尾節(jié)點的代碼如下：

附注：此操作就不在這用圖和代碼說明了。

5.修改節(jié)點：修改某個節(jié)點數(shù)據(jù)域的內(nèi)容。首先查詢到這個節(jié)點，然后對這個節(jié)點數(shù)據(jù)域的內(nèi)容進(jìn)行修改。
附注：同上

       ok，鏈表的幾種操作介紹完了，接下來我們來總結(jié)一下鏈表的幾個特點。

       鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點：
              1.易插入，易刪除。不用移動節(jié)點，只需改變節(jié)點中指針的指向。
              2.查詢速度慢：每進(jìn)行一次查詢，都要從表頭開始，速度慢，效率低。

擴(kuò)展閱讀
鏈表：http://public.whut.edu.cn/comptsci/web/data/512.htm

第二節(jié) 樹形存儲結(jié)構(gòu)

       所謂樹形存儲結(jié)構(gòu)，就是數(shù)據(jù)元素與元素之間存在著一對多關(guān)系的數(shù)據(jù)結(jié)構(gòu)。在樹形存儲結(jié)構(gòu)中，樹的根節(jié)點沒有前驅(qū)結(jié)點，其余的每個節(jié)點有且只有一個前驅(qū)結(jié)點，除葉子結(jié)點沒有后續(xù)節(jié)點外，其他節(jié)點的后續(xù)節(jié)點可以有一個或者多個。

如下圖就是一棵簡單的樹形結(jié)構(gòu)：

       說到樹形結(jié)構(gòu)，我們最先想到的就是二叉樹。我們常常利用二叉樹這種結(jié)構(gòu)來解決一些算法方面的問題，比如堆排序、二分檢索等。所以在樹形結(jié)構(gòu)這節(jié)我只重點詳解二叉樹結(jié)構(gòu)。那么二叉樹到底是怎樣的呢？如下圖就是一顆簡單的二叉樹：

附注：有關(guān)樹的概念以及一些性質(zhì)在此不做解釋，有意者請到百科一覽。

二叉樹的類型描述如下：

1.創(chuàng)建二叉樹：聲明一棵樹并為其申請存儲空間。

創(chuàng)建節(jié)點的代碼如下：

    ①.先序遍歷：若二叉樹非空，則依次執(zhí)行如下操作：
                    (1) 訪問根結(jié)點；
                    (2) 遍歷左子樹；
                    (3) 遍歷右子樹。

如圖：

先序遍歷的代碼如下：

中序遍歷的代碼如下：

后續(xù)遍歷的代碼如下：

[cpp] view plaincopyprint?

1. void PostTravser(struct tree * T)  
2. {  
3.     if(!T)  
4.         return;  
5.     else  
6.     {  
7.         PostTravser(T->lchild);  
8.         PostTravser(T->rchild);  
9.         printf("%c->",T->data);  
10.     }  
11. }  

void PostTravser(struct tree * T) { if(!T) return; else { PostTravser(T->lchild); PostTravser(T->rchild); printf("%c->",T->data); } }
4.求二叉樹的深度：樹中所有結(jié)點層次的最大值，也稱高度。
二叉樹的深度表示如下圖：

求二叉樹深度的代碼如下：

[cpp] view plaincopyprint?

1. int treeDeepth(struct tree * T)  
2. {  
3.     int i, j;  
4.     if(!T)  
5.         return 0;  
6.     else  
7.     {  
8.         if(T->lchild)  
9.             i = treeDeepth(T->lchild);  
10.         else  
11.             i = 0;  
12.           
13.         if(T->rchild)  
14.             j = treeDeepth(T->rchild);  
15.         else  
16.             j = 0;  
17.     }  
18.     return i > j? i+1:j+1;   
19. }  

int treeDeepth(struct tree * T) { int i, j; if(!T) return 0; else { if(T->lchild) i = treeDeepth(T->lchild); else i = 0; if(T->rchild) j = treeDeepth(T->rchild); else j = 0; } return i > j? i+1:j+1; }
好了，二叉樹的幾種操作介紹完了。

拓展閱讀
二叉樹：http://student.zjzk.cn/course_ware/data_structure/web/DOWNLOAD/%CA%FD%BE%DD%BD%E1%B9%B9%D3%EB%CB%E3%B7%A82.htm
赫夫曼編碼：http://blog.csdn.net/fengchaokobe/article/details/6969217

第三節(jié) 圖型存儲結(jié)構(gòu)
       所謂圖形結(jié)構(gòu)，就是數(shù)據(jù)元素與元素之間的關(guān)系是任意的，任意兩個元素之間均可相關(guān)，即每個節(jié)點可能有多個前驅(qū)結(jié)點和多個后繼結(jié)點，因此圖形結(jié)構(gòu)的存儲一般是采用鏈接的方式。圖分為有向圖和無向圖兩種結(jié)構(gòu)，如下圖

       通過圖，我們可以判斷兩個點之間是不是具有連通性；通過圖，我們還可以計算兩個點之間的最小距離是多少；通過圖，我們還可以根據(jù)不同的要求，尋找不同的合適路徑。

1.圖的結(jié)構(gòu)有好幾種，在實際應(yīng)用中需根據(jù)具體的情況選擇合適的結(jié)點結(jié)構(gòu)和表結(jié)構(gòu)。常用的有數(shù)組結(jié)構(gòu)、鄰接表。
   ①.數(shù)組結(jié)構(gòu)
   數(shù)組結(jié)構(gòu)的類型描述如下：

[cpp] view plaincopyprint?

1. typedef char VertexType;    /***頂點類型***/  
2. typedef int EdgeType;   /***邊權(quán)值類型***/  
3. #define maxvex 100  /***頂點的最大個數(shù)***/   
4.   
5. typedef struct  
6. {  
7.     VertexType vexs[maxvex];    /***頂點個數(shù)***/  
8.     EdgeType arc[maxvex][maxvex];   /***兩頂點構(gòu)成邊的權(quán)值***/  
9. }Mgraph;  

typedef char VertexType; /***頂點類型***/ typedef int EdgeType; /***邊權(quán)值類型***/ #define maxvex 100 /***頂點的最大個數(shù)***/ typedef struct { VertexType vexs[maxvex]; /***頂點個數(shù)***/ EdgeType arc[maxvex][maxvex]; /***兩頂點構(gòu)成邊的權(quán)值***/ }Mgraph;附注：當(dāng)前圖為無向圖時，圖中某兩個頂點VA和VB構(gòu)成一條邊時，其權(quán)值可表示為EdgeType arc[VA][VB]；當(dāng)前圖為有向圖時，圖中某兩個頂點VA和VB構(gòu)成一條邊時，并且是由VA指向VB，其權(quán)值可表示為EdgeType arc[VA][VB]，如果是由VB指向VA，其權(quán)值可表示為EdgeType arc[VB][VA]。

   ②.鄰接表
   鄰接表的類型描述如下：

[cpp] view plaincopyprint?

1. typedef char VertexType;   // 頂點類型   
2. typedef int EdgeType;     //邊權(quán)值類型   
3.   
4. typedef struct EdgeNode  //邊表節(jié)點   
5. {  
6.    int adjvex;              //鄰接點域，存儲該頂點對應(yīng)的下標(biāo)   
7.    EdgeType weight;         //用于存儲權(quán)值   
8.    struct EdgeNode *next;   //鏈域,指向下一個鄰接點   
9. }EdgeNode;  
10.   
11. typedef struct VertexNode   //頂點表節(jié)點   
12. {  
13.    VertexType data;       //頂點域，存儲頂點信息   
14.    EdgeNode * firstedge;  //邊表頭指針   
15. }VertexNode,AdjList[MAXVEX];  
16.   
17. typedef struct  
18. {  
19.     AdjList adjList;  
20.     int numVertexes,numEdges;   //圖當(dāng)前頂點數(shù)和邊數(shù)   
21. }GraphAdjList;  

typedef char VertexType; // 頂點類型 typedef int EdgeType; //邊權(quán)值類型 typedef struct EdgeNode //邊表節(jié)點 { int adjvex; //鄰接點域，存儲該頂點對應(yīng)的下標(biāo) EdgeType weight; //用于存儲權(quán)值 struct EdgeNode *next; //鏈域,指向下一個鄰接點 }EdgeNode; typedef struct VertexNode //頂點表節(jié)點 { VertexType data; //頂點域，存儲頂點信息 EdgeNode * firstedge; //邊表頭指針 }VertexNode,AdjList[MAXVEX]; typedef struct { AdjList adjList; int numVertexes,numEdges; //圖當(dāng)前頂點數(shù)和邊數(shù) }GraphAdjList;
2.圖的遍歷：從圖中的某一節(jié)點出發(fā)訪問圖中的其余節(jié)點，且使每一節(jié)點僅被訪問一次。圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓舐窂降人惴ǖ幕A(chǔ)。圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷，且它們對無向圖和有向圖均適用。

   ①. 深度優(yōu)先遍歷
   定義說明：假設(shè)給定圖G的初態(tài)是所有頂點均未曾訪問過。在G中任選一頂點V為初始出發(fā)點，則深度優(yōu)先遍歷可定義如下：首先訪問出發(fā)點V，并將其標(biāo)記為已訪問過；然后依次從V出發(fā)搜索v的每個鄰接點W。若W未曾訪問過，則以W為新的出發(fā)點繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點V有路徑相通的頂點(亦稱為從源點可達(dá)的頂點)均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復(fù)上述過程，直至圖中所有頂點均已被訪問為止。

深度遍歷過程如下圖：

②. 廣度優(yōu)先遍歷
   定義說明：假設(shè)從圖中某頂點V出發(fā)，在訪問了V之后一次訪問V的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中還有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。換句話說，廣度優(yōu)先遍歷圖的過程是以V為起點，由近至遠(yuǎn)，依次訪問和V有路徑相同且路徑長度為1,2，...的頂點。

廣度遍歷過程如下圖：

擴(kuò)展閱讀
最小生成樹：Prim算法，Kruskal算法
最短路徑：Dijkstra算法，F(xiàn)loyd算法

第四節(jié) 結(jié)束語
       想想，寫寫，畫畫......
原文地址：http://blog.csdn.net/fengchaokobe/article/details/7416547