本博客在在這里重新總結了一下，當前常用的經典資料結構；這里只針對鏈表，順序表，簡單樹和圖進行總結；具體實作請參考：https://github.com/yaowenxu/codes/tree/master/資料結構; 本文章，主要討論資料結構的性質；以及對這些資料結構的性質；主要是用來知識整理與復習；
順序表：順序表是指，將元素順序地存放在一塊連續的記憶體中；元素間的順序關系由他們的存盤順序自然表示；c++宣告一個陣列：int a[10]; 即構建了10個int記憶體大小（40bytes）的順序表；
優點：順序存盤，O(1)的時間進行訪問；
缺點：當容量不夠用時，需要重新構建結構，產生大量記憶體拷貝；洗掉和插入資料時，資料移動開銷較大；
鏈表：鏈表相對于順序表可以充分利用計算機記憶體空間；順序表是記憶體上連續的一塊位置，其在構建時需要預先知道資料大小來申請連續的記憶體空間；而在順序表進行擴充的時候，需要對順序表進行拷貝遷移，并釋放舊空間，產生較多的記憶體拷貝；而鏈表可以在空間不足的時候，可以直接宣告節點并分配記憶體，放到鏈表的末尾；這樣可以方便實作記憶體的靈活管理；(注意：在實作插入和洗掉節點的時候，可以先在本子上把程序畫出來，再來使用代碼實作)
優點：節省記憶體，動態管理記憶體；在洗掉和增加資料的時候為O(1)，沒有順序表的復制和拷貝的開銷；
缺點：只能順序訪問，不能隨機訪問；同時增加了節點指標索引，所以控銷開銷較大；
單向鏈表：node之中只有 next索引; 鏈表中最簡單的一種形式，是一種線性表，不像順序表一樣連續存盤資料，而是每個節點中存放下一個節點的位置資訊，最后一個節點為空指標；
雙向鏈表：每個節點有 next和prev指標，用于指向前一個節點和后一個節點；其中第一個節點prev指標為空，最后一個節點next指標為空；
單向回圈鏈表：單鏈表的一個變形，指鏈表的最后一個節點的next 不再是空，而是指向頭結點；頭結點由head指標進行標識，為單向鏈表的第一個節點；
堆疊：為一種常用的經典資料結構，其只能在一端進行操作push 和 pop, 遵循先入先出規則（LIFO, Last In First Out）；堆疊可以使用順序表和鏈表模擬實作；
佇列：為一種常用的經典資料結構，其允許在一端進行插入，另外一端進行洗掉操作；遵循先進先出策略（First In First Out）；可以使用瞬息表和鏈表模擬實作；
雙端佇列(deque)：全名為double-ended queue, 可以模擬佇列和堆疊的操作；雙端佇列中的元素可以從兩端彈出；插入只可以在兩端插入，雙端佇列可以在佇列的任意一端進行出隊和入隊操作；
佇列變種：優先佇列(priority queue)，佇列中每個元素具有優先級，新的佇列進行入隊時，會根據優先級進行重新排序，重新定位到特定的位置；優先佇列方便使用鏈表進行實作；
樹：樹的經典結構為二叉樹結構；它是又有限節點組成的一個具有層次關系的集合，樹有如下特點：
- 每個節點有零個或者多個子節點；
- 沒有父節點的點為根節點；
- 每一個非根節點有且只有一個父節點；
- 除了根節點以外，每個節點可以分為多個不相交的子樹；
樹的屬性：
- 節點的度：該節點子節點的個數；
- 樹的度：一顆樹中，最大的節點的度，為樹的度；
- 根節點：沒有父節點的節點；
- 葉節點：度為零的節點；
- 兄弟節點：具有相同父節點的節點互稱為兄弟節點；
- 節點層次：從根開始定義起，根為第一層，根的子節點為第二層；以此類推；
- 樹的高度或深度：節點最大層次；
- 堂兄弟節點：父節點在同一層的節點為堂兄弟；
- 節點的祖先：從根到節點所經分支上的所有節點；
- 子孫：以某以節點為根的子樹中任一節點都稱為該節點的子孫；
樹的種類：
- 無序樹：樹中任意節點之間沒有順序關系，這種樹為無序樹，也稱為自由樹；
- 有序樹：樹中任意節點的子節點之間有順序關系為有序樹；
- 二叉樹：每個節點最多含有兩個子樹的樹，稱之為二叉樹（節點度<=2）;
- 完全二叉樹：對于一顆二叉樹，其深度為d(d>1)，除d層以外，其他各層的節點數目均已達到最大值；第d層所有節點從左到右連續地緊密排列，這樣的二叉樹稱為完全二叉樹，其中滿二叉樹的定義是最底層的所有葉節點都在的完全二叉樹；
- 平衡二叉樹：當且僅當任何節點的兩棵子樹的高度差不大于1的二叉樹；
- 排序二叉樹（二叉查找樹，binary searcg tree）：
- 若左子樹不空，則左子樹上所有節點的值都小于它的根節點的值；
- 若右子樹不空，則右子樹上所有節點的值都大于它的根節點的值；
- 左右子樹也分別為二叉排序樹；
- 沒有鍵值相等的節點；
樹的存盤與表示：
- 順序表存盤：完全二叉樹可以用一個陣列來進行表示，對于一個節點索引為i; 其父節點索引為 (n-1)/2; 其左孩子節點為 2i+1; 右孩子節點為2i+2; （堆排序使用此種方法實作；）
- 鏈式存盤：對于一個節點，其包含了兩個指標，left 和 right分別指向左孩子和右孩子；常用此種方法實作樹結構；
樹的遍歷：二叉樹遍歷演算法的實作請參考：https://github.com/yaowenxu/codes/blob/master/資料結構/二叉樹.cc
- 深度優先遍歷(Depth First Search)：沿著樹的深度遍歷樹的節點，盡可能深得搜索樹的分支，根據根節點的訪問次序不同，又細分為三種：
- 先序遍歷：根節點-左子樹-右子樹
- 中序遍歷：左子樹-根節點-右子樹
- 后續遍歷：左子樹-右子樹-根節點
- 先序遍歷，中序遍歷和后序遍歷給兩種遍歷就可以推出樹，但是這兩種遍歷一定要包含中序遍歷；
- 只要給出先序就可以判斷出所有根，通過各段首元素查看根，第一個元素肯定是整棵樹的根，
- 只要給出后序就可以判斷出所有根，通過各段末元素查看根，最后一個元素肯定是整棵樹的根，
- 廣度優先遍歷(Breadth First Search): 從樹的根開始，從上到下，從左到右遍歷整個樹的節點；
- 深度優先遍歷一般用遞回實作，廣度優先一般使用佇列實作；一般情況下能用遞回實作的大部分演算法也能用堆疊來進行實作；
圖結構：圖G由頂點V和邊E構成；邊可以是單向的和雙向的；權重可以加在邊和頂點上；圖有有向圖和無向圖；一個頂點有出度和入度；實際生活中的交通運輸網，社交網路都可以利用圖來進行表示；
無向圖與有向圖：
無向完全圖：每兩個點之間，都存在邊；
有向完全圖：每兩個點之間，都存在相反的兩條邊；
有向無環圖：如果一個有向圖無法從某個頂點出發經過若干條邊回到該點，則這個圖是一個有向無環圖，
無權與有權圖；圖的連通性；
簡單圖：不考慮平行邊和自環邊的圖；
圖的表示：
鄰接矩陣：v表示頂點，表中的陣串列示權重；
鄰接表：在鄰接表中，我們保存所有節點的主串列；每個頂點維護一個鏈接到其他節點的串列和權重；對于 每個頂點維護的串列可以使用map 來進行實作；
至此，經典的資料結構基本概括完畢；后續運用程序中，會繼續進行補充；
保持更新，轉載請注明出處；更多內容請關注cnblogs.com/xuyaowen;
參考博客：注：文中圖片整理自參考博客；
鏈表 順序表 堆疊 佇列 樹結構 圖結構
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69653.html
標籤：其他
上一篇：搜索查找演算法實作合集-經典搜索演算法實作與分析：順序查找，二分查找，分塊查找；廣度優先搜索，深度優先搜索；
下一篇：資料結構（一）：陣列