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

刪除尾節點的代碼如下：

刪除非頭尾節點的代碼如下：

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

5.修改節點：修改某個節點數據域的內容。首先查詢到這個節點，然后對這個節點數據域的內容進行修改。
附注：同上

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

       鏈式存儲結構的特點：
              1.易插入，易刪除。不用移動節點，只需改變節點中指針的指向。
              2.查詢速度慢：每進行一次查詢，都要從表頭開始，速度慢，效率低。

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

第二節 樹形存儲結構

       所謂樹形存儲結構，就是數據元素與元素之間存在著一對多關系的數據結構。在樹形存儲結構中，樹的根節點沒有前驅結點，其余的每個節點有且只有一個前驅結點，除葉子結點沒有后續節點外，其他節點的后續節點可以有一個或者多個。

如下圖就是一棵簡單的樹形結構：

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

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

二叉樹的類型描述如下：

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

創建節點的代碼如下：

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

如圖：

先序遍歷的代碼如下：

中序遍歷的代碼如下：

后續遍歷的代碼如下：

[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.求二叉樹的深度：樹中所有結點層次的最大值，也稱高度。
二叉樹的深度表示如下圖：

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

[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

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

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

1.圖的結構有好幾種，在實際應用中需根據具體的情況選擇合適的結點結構和表結構。常用的有數組結構、鄰接表。
   ①.數組結構
   數組結構的類型描述如下：

[cpp] view plaincopyprint?

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

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

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

[cpp] view plaincopyprint?

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

typedef char VertexType; // 頂點類型 typedef int EdgeType; //邊權值類型 typedef struct EdgeNode //邊表節點 { int adjvex; //鄰接點域，存儲該頂點對應的下標 EdgeType weight; //用于存儲權值 struct EdgeNode *next; //鏈域,指向下一個鄰接點 }EdgeNode; typedef struct VertexNode //頂點表節點 { VertexType data; //頂點域，存儲頂點信息 EdgeNode * firstedge; //邊表頭指針 }VertexNode,AdjList[MAXVEX]; typedef struct { AdjList adjList; int numVertexes,numEdges; //圖當前頂點數和邊數 }GraphAdjList;
2.圖的遍歷：從圖中的某一節點出發訪問圖中的其余節點，且使每一節點僅被訪問一次。圖的遍歷算法是求解圖的連通性問題、拓撲排序和求路徑等算法的基礎。圖的遍歷分為深度優先遍歷和廣度優先遍歷，且它們對無向圖和有向圖均適用。

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

深度遍歷過程如下圖：

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

廣度遍歷過程如下圖：

擴展閱讀
最小生成樹：Prim算法，Kruskal算法
最短路徑：Dijkstra算法，Floyd算法

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