通過一學期對《資料結構與演算法》的學習，大概的了解了基本的資料結構和相應的一些演算法。下面總結一下自己乙個學期學習的收穫和心得。
資料結構是什麼：
資料結構是計算機儲存、組織資料的方式。資料結構是指相互之間存在一種或多種特定關係的資料元素的集合。通常情況下，精心選擇的資料結構可以帶來更高的執行或者儲存效率。
資料結構往往同高效的檢索演算法和索引技術有關。
資料結構重要性：
一般認為，乙個資料結構是由資料元素依據某種邏輯聯絡組織起來的。對資料元素間邏輯關係的描述稱為資料的邏輯結構；資料必須在計算機內儲存，資料的儲存結構是資料結構的實現形式，是其在計算機內的表示；此外討論乙個資料結構必須同時討論在該類資料上執行的運算才有意義。乙個邏輯資料結構可以有多種儲存結構，且各種儲存結構影響資料處理的效率。
在許多態別的程式的設計中，資料結構的選擇是乙個基本的設計考慮因素。許多大型系統的構造經驗表明，系統實現的困難程度和系統構造的質量都嚴重的依賴於是否選擇了最優的資料結構。許多時候，確定了資料結構後，演算法就容易得到了。
有些時候事情也會反過來，我們根據特定演算法來選擇資料結構與之適應。不論哪種情況，選擇合適的資料結構都是非常重要的。選擇了資料結構，演算法也隨之確定，是資料而不是演算法是系統構造的關鍵因素。
這種洞見導致了許多種軟體設計方法和程式語言的出現，物件導向的程式語言就是其中之一。
常見的資料結構：
1. 順序表：
定義：順序表是在計算機記憶體中以陣列的形式儲存的線性表,是指用一組位址連續的儲存單元依次儲存資料元素的線性結構。線性表採用順序儲存的方式儲存就稱之為順序表。
順序表是將表中的結點依次存放在計算機記憶體中一組位址連續的儲存單元中。
基本運算：
置表空：sqlsetnull（l判表滿：sqlempty（l）
求表長：sqllength(l插入：sqlinsert（l,i,x）
按序號取元素：sqlget（l,i） 刪除：sqldelete(l,i)
按值查詢：sqllocate(l,x)
2. 鍊錶
定義：鍊錶是一種物理儲存單元上非連續、非順序的儲存結構，資料元素的邏輯順序是通過鍊錶中的指標鏈結次序實現的。鍊錶由一系列結點（鍊錶中每乙個元素稱為結點）組成，結點可以在執行時動態生成。
每個結點包括兩個部分：乙個是儲存資料元素的資料域，另乙個是儲存下乙個結點位址的指標域。 相比於線性表順序結構，鍊錶比較方便插入和刪除操作。
分類：單鏈表—用一組位址任意的儲存單元存放線性表中的資料元素。
迴圈鍊錶—迴圈鍊錶是另一種形式的鏈式存貯結構。它的特點是表中最後乙個結點的指標域指向頭結點，整個鍊錶形成乙個環。
基本運算：建立鍊錶，插入節點，刪除節點。
3. 堆疊
定義：堆疊都是一種資料項按序排列的資料結構，只能在一端(稱為棧頂(top))對資料項進行插入和刪除。要點：
堆：順序隨意棧：後進先出(last-in/first-out)。
基本演算法：
置空棧：initstack（s判棧空：stackempty（s）
判棧滿：stackfull（s取棧頂元素：gettop（s）
入棧：push（s出棧：pop(s)
4. 佇列
定義：佇列是一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。
佇列中沒有元素時，稱為空佇列。在佇列這種資料結構中，最先插入的元素將是最先被刪除的元素；反之最後插入的元素將最後被刪除的元素，因此佇列又稱為「先進先出」（fifo—first in first out）的線性表。
分類：順序佇列；鏈隊；
基本運算：初始化佇列 qini (q) 入隊 qadd(q,x)
出隊 qdel(q,x判斷佇列是否為qempty(q)
判斷佇列是否為滿qfull(q)
5. 特殊矩陣
分類：對陣矩陣；三角矩陣；稀疏矩陣；
6. 二叉樹
定義：二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。
二叉樹的每個結點至多只有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結點；深度為k的二叉樹至多有2^(k) -1個結點；對任何一棵二叉樹t，如果其終端結點數(即葉子結點數)為n0，度為2的結點數為n2，則n0 = n2 + 1。
(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層有葉子節點，並且葉子節點都是從左到右依次排布，這就是完全二叉樹。
(2)滿二叉樹——除了葉結點外每乙個結點都有左右子葉且葉結點都處在最底層的二叉樹,。
(3)深度——二叉樹的層數，就是高度。
性質：(1) 在二叉樹中，第i層的結點總數不超過2^(i-1)；
(2) 深度為h的二叉樹最多有2^h-1個結點(h>=1)，最少有h個結點；
(3) 對於任意一棵二叉樹，如果其葉結點數為n0，而度數為2的結點總數為n2，則n0=n2+1；
(4) 具有n個結點的完全二叉樹的深度為int（log2n）+1
(5)有n個結點的完全二叉樹各結點如果用順序方式儲存，則結點之間有如下關係： 若i為結點編號則如果i<>1，則其父結點的編號為i/2；如果2*i<=n，則其左兒子（即左子樹的根結點）的編號為2*i；若2*i>n，則無左兒子；如果2*i+1<=n，則其右兒子的結點編號為2*i+1；若2*i+1>n，則無右兒子。
(6)給定n個節點，能構成h(n)種不同的二叉樹。h(n)為卡特蘭數的第n項。h(n)=c(n,2*n)/(n+1)。
（7）設有i個枝點，i為所有枝點的道路長度總和，j為葉的道路長度總和j=i+2i。
二叉樹遍歷：
遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每乙個結點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為乙個線性序列來表示。
設l、d、r分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：dlr（稱為先根次序遍歷），ldr（稱為中根次序遍歷），lrd （稱為後根次序遍歷）。
(1)前序遍歷訪問根；按前序遍歷左子樹；按前序遍歷右子樹
(2)中序遍歷按中序遍歷左子樹；訪問根；按中序遍歷右子樹
(3)後序遍歷按後序遍歷左子樹；按後序遍歷右子樹；訪問根
（4）層次遍歷即按照層次訪問，通常用佇列來做。訪問根，訪問子女，再訪問子女的子女（越往後的層次越低）（兩個子女的級別相同）。
7. 雜湊
定義：若結構中存在和關鍵字k相等的記錄，則必定在f(k)的儲存位置上。由此，不需比較便可直接取得所查記錄。
稱這個對應關係f為雜湊函式(hash function)，按這個思想建立的表為雜湊表。
雜湊函式：直接定址法；除留餘數法；數字分析法；平方取中法；摺疊法。
衝突處理方法：開放位址法（線性探測再雜湊，二次探測再雜湊，偽隨機探測再雜湊） 鏈位址法。
8. 圖
定義：一種較線性表和樹更為複雜的資料結構。
儲存結構：鄰接矩陣；鄰接表；逆鄰接表；十字鍊錶；鄰接多重表。
圖的遍歷：
深度優先遍歷：深度優先遍歷的思想類似於樹的先序遍歷。其遍歷過程可以描述為：
從圖中某個頂點v出發，訪問該頂點，然後依次從v的未被訪問的鄰接點出發繼續深度優先遍歷圖中的其餘頂點，直至圖中所有與v有路徑相通的頂點都被訪問完為止。
廣度優先遍歷：對圖的廣度優先遍歷方法描述為：從圖中某個頂點v出發，在訪問該頂點v之後，依次訪問v的所有未被訪問過的鄰接點，然後再訪問每個鄰接點的鄰接點，且訪問順序應保持先被訪問的頂點其鄰接點也優先被訪問，直到圖中的所有頂點都被訪問為止。
下面是對乙個無向圖進行廣度優先遍歷的過程。
查詢演算法
1. 順序查詢：在乙個已知無(或有序）序佇列中找出與給定關鍵字相同的數的具體位置。原理是讓關鍵字與佇列中的數從第乙個開始逐個比較，直到找出與給定關鍵字相同的數為止。
2. 折半查詢：首先，假設表中元素是按公升序排列，將表中間位置記錄的關鍵字與查詢關鍵字比較，如果兩者相等，則查詢成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查詢關鍵字，則進一步查詢前一子表，否則進一步查詢後一子表。
重複以上過程，直到找到滿足條件的記錄，使查詢成功，或直到子表不存在為止，此時查詢不成功。
3. 分塊查詢：先選取各塊中的最大關鍵字構成乙個索引表；查詢分兩個部分：先對索引表進行二分查詢或順序查詢，以確定待查記錄在哪一塊中； 然後，在已確定的塊中用順序法進行查詢。
4. 二叉排序樹：
定義：二叉排序樹（binary sort tree）又稱二叉查詢樹。 它或者是一棵空樹；或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；（3）左、右子樹也分別為二叉排序樹；
查詢：若根結點的關鍵字值等於查詢的關鍵字，成功。否則，若小於根結點的關鍵字值，遞迴查左子樹。若大於根結點的關鍵字值，遞迴查右子樹。若子樹為空，查詢不成功。
排序演算法：
1. 直接插入排序：插入排序的基本操作就是將乙個資料插入到已經排好序的有序資料中,從而得到乙個新的、個數加一的有序資料，演算法適用於少量資料的排序，時間複雜度為o(n^2)。
是穩定的排序方法。插入演算法把要排序的陣列分成兩部分：第一部分包含了這個陣列的所有元素，但將最後乙個元素除外，而第二部分就只包含這乙個元素。
在第一部分排序後，再把這個最後元素插入到此刻已是有序的第一部分裡的位置。
2. 希爾排序：先取乙個小於n的整數d1作為第乙個增量，把檔案的全部記錄分成d1個組。
所有距離為d1的倍數的記錄放在同乙個組中。先在各組內進行直接插入排序；然後，取第二個增量d23. 氣泡排序：
依次比較相鄰的兩個數，將小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放後。
然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。至此第一趟結束，將最大的數放到了最後。在第二趟：
仍從第一對數開始比較（因為可能由於第2個數和第3個數的交換，使得第1個數不再小於第2個數），將小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到乙個新的最大數（其實在整個數列中是第二大的數）。如此下去，重複以上過程，直至最終完成排序。
資料結構學習總結
經過一學期的學習，我對資料結構有了我自己的認識。一開始，我以為它和c語言和c 一樣，都是講一門語言。但學習之後，發現事實並不是這樣，在資料結構的學習中，有線性表，有隊，有棧，有樹，有圖等等。這些看起來沒有關係，其實之間有著千絲萬縷的聯絡。線性表是其中最簡單的，所以在前幾章學習，後面依次逐章變難，學起...
資料結構學習方法
學習方法二先邏輯結構後儲存結構的學習方法 資料結構的一項重要任務就是把實際應用中的實際問題抽象成數學模型 邏輯結構 然後再根據不同計算機語言的特點，安排儲存結構，為進一步的操作和計算服務，我們在學習資料結構時，如果遵循這個原則來學習。不但可以加強我們的記憶，而且可以加深我們對所學知識的理解，同時也能...
資料結構學習試題及答案
3 1 線性鍊錶 單鏈表 每個資料元素有兩部分 乙個資料域 儲存資料元素資訊 乙個指標域 後繼儲存位置 最都乙個元素的指標為空 3.2 迴圈鍊錶最後乙個結點的指標域指向頭結點 3.3雙向鍊錶每個結點有兩個指標域，乙個指向前域，乙個是後域 4 靜態鍊錶 用陣列描述鍊錶。指標指向下乙個元素位址 第三章棧...