所謂資料存儲結構，就是資料的元素與元素之間在計算機中的一種表示，它的目的是為了解決空間規模問題，或者是通過空間規模問題進而間接地解決時間規模問題。我們知道，随着輸入的資料量越來越大，在有限的記憶體裡，不能把這些資料完全的存下來，這就對資料存儲結構和設計存儲的算法提出了更高的要求。
本文将介紹幾種存儲結構，分别為鍊式結構、樹形結構、圖結構以及矩陣結構。
第一節 鍊式存儲結構
所謂鍊式存儲結構，一般就是用一個頭指針指向連結清單的第一個節點，如果你要增加新的存儲元素時，隻需在已有節點的後面插入新結點即可。
連結清單通常有單連結清單、雙連結清單、循環連結清單。在這，我隻介紹單連結清單，雙連結清單和循環連結清單隻是單連結清單的拓展罷了。下圖就是一個簡單的單連結清單圖示。
單連結清單的類型描述如下代碼：
[cpp]
view
plain
copy print ?- typedef char DataType; /***假設結點的資料域類型為字元***/
- typedef struct node{ /***結點類型定義***/
- DataType data; /***結點的資料域***/
- struct node *next; /***結點的指針域***/
- }ListNode;
- typedef ListNode *LinkList;
- ListNode *p;
- LinkList head;
- 附注：
- ① LinkList和ListNode *是不同名字的同一個指針類型（命名的不同是為了概念上更明确）
- ② LinkList類型的指針變量head表示它是單連結清單的頭指針
- ③ ListNode *類型的指針變量p表示它是指向某一節點的指針
下面我們來看單連結清單的操作：建立節點、增加節點、删除節點、查詢、修改。
1.建立節點：聲明一個節點并為其申請一段記憶體空間，此節點有資料域和指針域。
- node = (struct List *)malloc(sizeof(struct List));
2.增加節點：插入節點，分為頭插入、尾插入和非頭尾插入。
①. 在表頭插入節點，如圖
插入頭節點的代碼如下：
- if(p == head) /***其中p為連結清單中的某一節點***/
- {
- struct list *s = NULL;
- s = (struct list *)malloc(sizeof(struct list)); /***申請空間***/
- s->DataNumber = data; /***為節點s的資料域指派***/
- /***将節點s插入表頭***/
- s->next = p;
- head = s;
- }
②. 在表尾插入節點，如圖
插入尾節點的代碼如下：
- if(p->next == NULL) /***其中p為連結清單中的某一節點***/
- /***将節點s插入表尾***/
- p->next = s;
- s->next = NULL;
③. 在表中插入非頭尾節點，如圖
插入非頭尾節點的代碼如下：
- struct list *s = NULL;
- s = (struct list *)malloc(sizeof(struct list)); /***申請空間***/
- s->DataNumber = data; /***為節點s的資料域指派***/
- /***将節點s插入表中***/
- s->next = p; /***其中p為連結清單中的某一節點***/
- q->next = s; /***其中q為連結清單中p節點的前一個節點***/
3.删除節點：分為删除頭結點，删除尾節點，删除頭尾節點。
①. 删除表頭結點，如圖
删除頭結點的代碼如下：
- if(p == head) /***p指向連結清單中的某一節點***/
- head = p->next;
②. 删除表尾節點，如圖
附注說明：上圖中删完尾節點之後，新連結清單的尾節點下标應為n-1。不過由于作圖時隻做了尾節點，故用圖中的n2節點代替。
删除尾節點的代碼如下：
- if(p->next == NULL) /***p指向連結清單中的某一節點***/
- q->next = NULL; /***q指向連結清單中的p節點的前一節點**/
③. 删除非頭尾節點，如圖
删除非頭尾節點的代碼如下：
- q->next = p->next; /***p指向連結清單中的某一節點，q指向連結清單中的p節點的前一節點***/
4.查詢節點：在連結清單中找到你想要找的那個節點。此操作是根據資料域的内容來完成的。查詢隻能從表頭開始，當要找的節點的資料域内容與目前不相符時，隻需讓目前節點指向下一結點即可，如此這樣，直到找到那個節點。
附注：此操作就不在這用圖和代碼說明了。
5.修改節點：修改某個節點資料域的内容。首先查詢到這個節點，然後對這個節點資料域的内容進行修改。
附注：同上
ok，連結清單的幾種操作介紹完了，接下來我們來總結一下連結清單的幾個特點。
鍊式存儲結構的特點：
1.易插入，易删除。不用移動節點，隻需改變節點中指針的指向。
2.查詢速度慢：每進行一次查詢，都要從表頭開始，速度慢，效率低。
擴充閱讀
連結清單：
http://public.whut.edu.cn/comptsci/web/data/512.htm第二節 樹形存儲結構
所謂樹形存儲結構，就是資料元素與元素之間存在着一對多關系的資料結構。在樹形存儲結構中，樹的根節點沒有前驅結點，其餘的每個節點有且隻有一個前驅結點，除葉子結點沒有後續節點外，其他節點的後續節點可以有一個或者多個。
如下圖就是一棵簡單的樹形結構：
說到樹形結構，我們最先想到的就是二叉樹。我們常常利用二叉樹這種結構來解決一些算法方面的問題，比如堆排序、二分檢索等。是以在樹形結構這節我隻重點詳解二叉樹結構。那麼二叉樹到底是怎樣的呢？如下圖就是一顆簡單的二叉樹：
附注：有關樹的概念以及一些性質在此不做解釋，有意者請到百科一覽。
二叉樹的類型描述如下：
- typedef struct tree
- char data;
- struct tree * lchild, * rchild; /***左右孩子指針***/
- }tree;
二叉樹的操作：建立節二叉樹，建立節點，周遊二叉樹，求二叉樹的深度。
1.建立二叉樹：聲明一棵樹并為其申請存儲空間。
- struct tree * T = NULL;
- T = (struct tree *)malloc(sizeof(struct tree));
2.建立節點：除根節點之外，二叉樹的節點有左右節點之分。
建立節點的代碼如下：
- struct tree * createTree()
- char NodeData;
- scanf(" %c", &NodeData);
- if(NodeData == '#')
- return NULL;
- else
- {
- struct tree * T = NULL;
- T = (struct tree *)malloc(sizeof(struct tree));
- T->data = NodeData;
- T->lchild = createTree();
- T->rchild = createTree();
- return T;
- }
3.周遊二叉樹：分為先序周遊、中序周遊、後續周遊。
①.先序周遊：若二叉樹非空，則依次執行如下操作：
(1) 通路根結點；
(2) 周遊左子樹；
(3) 周遊右子樹。
如圖：
先序周遊的代碼如下：
- void PreTravser(struct tree * T)
- if(T == NULL)
- return;
- printf("%c",T->data);
- PreTravser(T->lchild);
- PreTravser(T->rchild);
②.中序周遊：若二叉樹非空，則依次執行如下操作：
(1)周遊左子樹；
(2)通路根結點；
(3)周遊右子樹。
中序周遊的代碼如下：
- void MidTravser(struct tree * T)
- if(!T)
- MidTravser(T->lchild);
- MidTravser(T->rchild);
③.後續周遊：若二叉樹非空，則依次執行如下操作：
(2)周遊右子樹；
(3)通路根結點。
後續周遊的代碼如下：
- void PostTravser(struct tree * T)
- PostTravser(T->lchild);
- PostTravser(T->rchild);
- printf("%c->",T->data);
4.求二叉樹的深度：樹中所有結點層次的最大值，也稱高度。
二叉樹的深度表示如下圖：
求二叉樹深度的代碼如下：
- int treeDeepth(struct tree * T)
- int i, j;
- return 0;
- if(T->lchild)
- i = treeDeepth(T->lchild);
- else
- i = 0;
- if(T->rchild)
- j = treeDeepth(T->rchild);
- 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.圖的結構有好幾種，在實際應用中需根據具體的情況選擇合适的結點結構和表結構。常用的有數組結構、鄰接表。
①.數組結構
數組結構的類型描述如下：
- 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]。
②.鄰接表
鄰接表的類型描述如下：
- 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];
- 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算法
![swmm與lisflood-fp源碼如何一起編譯 CMake指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)