一：數(shù)據(jù)結(jié)構(gòu)概論

• 在數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)分為兩種關(guān)系，一種時線性誓沸，一種是非線性
• 線性關(guān)系梅桩，比如一張學(xué)生登記表。
• 非線性關(guān)系拜隧，比如文件夾是樹型關(guān)系摘投，比如計算機網(wǎng)絡(luò)是圖關(guān)系。

數(shù)據(jù)結(jié)構(gòu)包括：

• 數(shù)據(jù)的存儲
  • 物理結(jié)構(gòu)：數(shù)據(jù)在計算機內(nèi)的存儲表示
• 數(shù)據(jù)之間的關(guān)系
  • 邏輯結(jié)構(gòu)：數(shù)據(jù)之間的邏輯關(guān)系虹蓄。分為兩種一種是順序存儲結(jié)構(gòu)犀呼，一種是非順序存儲結(jié)構(gòu)。順序結(jié)構(gòu)一般用一維數(shù)組體現(xiàn)數(shù)據(jù)之間的關(guān)系薇组。非順序存儲結(jié)構(gòu)一般采用指針實現(xiàn)數(shù)據(jù)之間的關(guān)系外臂，包括鏈式存儲結(jié)構(gòu)和散列結(jié)構(gòu)，索引存儲結(jié)構(gòu)等律胀。鏈式存儲利用指針直接表示數(shù)據(jù)元素之間的關(guān)系宋光。散列結(jié)構(gòu)是根據(jù)節(jié)點的關(guān)鍵字貌矿，利用散列函數(shù)直接計算出該節(jié)點的存儲地址。索引存儲結(jié)構(gòu)是在存儲節(jié)點信息的同時罪佳，還建立附加的索引表逛漫。索引結(jié)構(gòu)分為稠密索引和稀疏索引。
• 數(shù)據(jù)的操作赘艳。在各種結(jié)構(gòu)上的算法酌毡。

數(shù)據(jù)類型：一個值的集合以及在這些值上定義的一組操作的總稱。

算法特征：

• 正確性
• 確定性
• 有窮性
• 輸入
• 輸出
  效率和低存儲量兩者通常情況下是矛盾的蕾管。

二：線性表

線性表定義：每個數(shù)據(jù)元素最多只有一個直接前趨枷踏，每個數(shù)據(jù)元素最多只有一個直接后繼，只有第一個數(shù)據(jù)元素沒有直接前趨掰曾，最后一個數(shù)據(jù)元素沒有直接后繼旭蠕。

線性表的存儲分為順序存儲和非順序存儲。

• 順序存儲也稱為向量存儲或一維數(shù)組存儲旷坦。特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰掏熬，隨機存取元素簡單，插入刪除會造成大量數(shù)據(jù)移動秒梅。線性表的順序存儲的情況下插入和刪除算法的時間復(fù)雜度為o(n);求表長以及取第i個元素的時間復(fù)雜度為o(1);

• 線性表的鏈式存儲旗芬，不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰。由于不要求物理位置上也相鄰番电，那么每個節(jié)點對象包含兩個元素，一個是當(dāng)前值辆琅，一個是指向下一個節(jié)點的地址漱办。如果插入某個值，那么將插入的值的節(jié)點指向之前的后繼婉烟，之前的指向下一個節(jié)點指向這個插入的節(jié)點即可娩井。

  • 尾插入法。需要一個head指針指向頭部似袁，一個tail指針指向尾部洞辣，其他的地址都保存在前趨的next中。
  • 頭插入法昙衅。不需要tail指針指向尾部扬霜，只是需要不斷修改head頭指針。

鏈式存儲的查找比較麻煩而涉，要按照順序一個一個查著瓶，求表長也如此。單向鏈表啼县，頭節(jié)點至關(guān)重要材原。循環(huán)鏈式存儲沸久，是指最后一個元素的next指向頭部。這樣以來余蟹，就可以查找每個元素的前趨卷胯。

雙向鏈表是在每個節(jié)點的值和next兩個元素的基礎(chǔ)上，再加一個prior威酒，用來保存指向前趨的指針窑睁。當(dāng)然還有雙向循環(huán)鏈表。

三：棧和隊列

兩種特殊的線性表兼搏。

棧：先進后出卵慰。限制只有棧頂才可以操作。每次pop刪除的總是最新元素佛呻，每次push壓入的元素也總是最新元素裳朋。

實現(xiàn)棧的方式：順序棧和鏈式棧

順序棧：入棧是在線性表的頭部插入元素，出棧是在線性表的頭部刪除一個元素吓著。這樣效率不高鲤嫡，時間代價為o(n)。如果是在線性表的尾部作為棧頂绑莺，插入刪除元素暖眼，那么時間代價為o(1)，效率高纺裁。

鏈式棧：單向鏈表存儲棧诫肠。操作一般在頭部。

順序棧和鏈式棧比較：當(dāng)需要堆棧共享時欺缘，順序椂霸ィ可以使用一個數(shù)組存儲兩個棧， 數(shù)組的兩端作為兩個棧各自的棧低谚殊，中間部分為共享區(qū)域丧鸯。這樣的情況適合兩個棧有相反的需求時，此消彼長的情況嫩絮。鏈式棧是每個節(jié)點多了一個指針域的開銷丛肢。

隊列：先進先出。只需要操作線性表的兩端剿干。一端只能進入蜂怎，另一端只能出。隊尾進置尔，隊首出派敷。有順序存儲和鏈式存儲兩種。隊列假溢出是因為隊首指針確定導(dǎo)致的，就是被刪除的元素空間無法被重復(fù)利用篮愉「郑可以讓隊首和隊尾的指針循環(huán)起來就可以，就是將元素存儲在循環(huán)向量中试躏。

基本運算：
判斷隊空

隊列初始化

判斷隊滿

入隊元素

出隊元素

取隊首元素

順序隊列：必須用一個向量空間來存放元素猪勇。設(shè)置front和rear分別來指示隊首和隊尾的位置。

循環(huán)隊列：就是將元素存儲在循環(huán)向量中颠蕴。

鏈式隊列：

四：數(shù)組和廣義表

矩陣存儲分為行優(yōu)先和列優(yōu)先兩種泣刹。

矩陣壓縮存儲，是針對特殊矩陣隊存儲犀被，只存儲其元素一部分椅您，另一部分通過相應(yīng)的算法計算出來。這樣的矩陣包括對稱矩陣寡键，稀疏矩陣和三角矩陣掀泳。

• 稀疏矩陣：矩陣中有多數(shù)為零的值。到底這個數(shù)占了全部數(shù)的多少位稀疏矩陣呢西轩？假設(shè)有m行n列矩陣员舵，有t個非零元素，那么滿足(t+1)*3<=m*n即可

廣義表是線性表的擴展藕畔。元素包括

• 原子元素
• 可以再分的元素

如果所有元素都是原子元素則是線性表马僻。如果有可以再分的元素，也就是子表注服，則是廣義表韭邓。廣義表含有元素的個數(shù)稱為廣義表的長度，廣義表中含有括號對數(shù)稱為廣義表的深度溶弟，也就是層女淑。

五：樹

非線性結(jié)構(gòu)。樹的遞歸定義：樹是由根節(jié)點和若干棵子樹構(gòu)成的可很。

一個節(jié)點的子樹個數(shù)稱為該節(jié)點的度诗力。

度為零的節(jié)點稱為葉子或終端節(jié)點凰浮。不為零的為分支節(jié)點我抠。除根節(jié)點之外的稱為內(nèi)部節(jié)點。

一棵樹中節(jié)點度最大的值稱為該樹的度袜茧。

二叉樹：或者為空菜拓，或者由一個根節(jié)點加上兩棵左右互不交叉的子樹構(gòu)成。

• 滿二叉樹：每個父親都有兩個兒子笛厦。
• 完全二叉樹

二叉樹的順序存儲：只存儲節(jié)點的值纳鼎，不存儲節(jié)點之間的邏輯關(guān)系

二叉樹的鏈接存儲：每個節(jié)點由數(shù)據(jù)域和指針域兩部分組成。指針域有兩個，一個指向父親贱鄙，一個指向兒子劝贸。

二叉樹遍歷，包括前中后三序遍歷逗宁，以及層次遍歷映九。

當(dāng)我們遍歷完二叉樹，就形成一個線性序列瞎颗，于是就有了唯一的前趨和后繼節(jié)點件甥。

線索二叉樹，就是為了解決尋找前趨和后繼的哼拔。每個鏈接節(jié)點有五個變量引有，通常樹都是鏈式存儲。

將一棵樹轉(zhuǎn)為二叉樹的方法：

• 樹中所有相鄰兄弟之間加一條連線倦逐。
• 對樹中每個節(jié)點譬正，只保留它與第一個兒子節(jié)點之間的聯(lián)系，刪除它與其他兒子的連線僻孝。
• 以樹的根節(jié)點為軸旋轉(zhuǎn)导帝。

• 這樣的旋轉(zhuǎn)可以證明是唯一的。而且過程是可逆的穿铆。

  
  

將二叉樹還原為普通樹的方法：

樹的遍歷分為先根遍歷和后根遍歷您单。

森林的遍歷分為前序遍歷和中序遍歷。

哈夫曼樹荞雏，也是二叉樹虐秦。這種二叉樹的帶權(quán)路徑長度最小。并且每個權(quán)值都是葉子節(jié)點凤优。
帶權(quán)路徑長度為根節(jié)點到該節(jié)點之間的路徑長度與該節(jié)點的值的乘積悦陋。該節(jié)點的值，是我們?nèi)藶橹付ǖ摹?br> 路徑長度是層數(shù)減1.根節(jié)點為第一層筑辨。

六：圖

圖是非線性結(jié)構(gòu)俺驶。圖中任何兩個頂點都可能有關(guān)聯(lián)，頂點間的關(guān)系是多對多點關(guān)系棍辕。圖的每個節(jié)點有任意多個前趨和后繼暮现。圖分為有向圖和無向圖。帶權(quán)的圖稱為網(wǎng)楚昭。網(wǎng)分為有向網(wǎng)和無向網(wǎng)栖袋。

1:圖的存儲結(jié)構(gòu)

圖的鄰接矩陣表示法和鄰接表表示法。
鄰接矩陣抚太，行與列分別表示各個頂點塘幅。1表示有邊昔案，0表示沒有邊。比如第一行第二列是1电媳，則表示頂點1到頂點2有邊踏揣。第三行第四列是1，則表示頂點3到頂點4有邊匾乓。這是有向圖呼伸。如果是無向圖的話，那么矩陣是對稱的钝尸，就是說如果第三行第四列是1括享，那么第四列第三行也是1，因為頂點3和頂點4的邊沒有方向珍促。

鄰接表：是圖的一種鏈式存儲結(jié)構(gòu)铃辖。先建立一個鏈表存儲每個頂點。每個頂點有兩個域猪叙，鄰接點域和指針域娇斩。鄰接點域存序號，指針域指向邊的表節(jié)點穴翩。邊表是存儲頂點與鄰接點具有邊關(guān)系的表犬第，每個節(jié)點也有兩個域，指針域指向下一個與鄰接表節(jié)點具有邊關(guān)系的頂點芒帕。比如頂點1與頂點2歉嗓，3都有邊。那么頂點1在鄰接表中的指針域指向邊表的頂點2的位置背蟆。邊表中頂點2的指針域指向與頂點1有邊的頂點3的位置鉴分。

2:圖的遍歷

圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷

• 深度優(yōu)先遍歷：遞歸訪問頂點，直到某個頂點沒有未被訪問的頂點為止带膀，開始訪問它的前趨志珍。如果前趨是最開始訪問的那個頂點，就結(jié)束遍歷垛叨。

• 廣度優(yōu)先遍歷：從最開始的訪問點出發(fā)伦糯，訪問與它鄰接的所有點，再從這些鄰接點出發(fā)訪問它們的鄰接點嗽元。直到所有頂點均被訪問為止敛纲。

3：最小生成樹

克魯斯卡爾算法。普里姆算法

4：最短路徑和拓撲排序

最短路徑：迪卡斯特拉算法

拓撲排序：從網(wǎng)中旋轉(zhuǎn)一個入度為0的頂點并輸出还棱。也就是沒有其它頂點指向這個頂點载慈，只有這個頂點指向其它頂點惭等。從網(wǎng)中刪除此頂點及其所有出邊珍手。如此循環(huán)。拓撲排序解決的是各個頂點的依賴關(guān)系的有序數(shù)列。

七：排序

排序的穩(wěn)定性是根據(jù)需要排序的元素中的關(guān)鍵字如果有相等的情況琳要，那么這些相等關(guān)鍵字的元素如果排序前后的相對位置不變就是穩(wěn)定的寡具，如果這些相等關(guān)鍵字的元素相對位置發(fā)生了改變，就是不穩(wěn)定的稚补。
排序過程中是否涉及數(shù)據(jù)的內(nèi)外存交換可以將排序分為：

• 內(nèi)部排序

  • 插入排序童叠。將待排序的數(shù)組中元素，一個一個地插入到有序數(shù)組當(dāng)中课幕。
    • 直接插入排序厦坛。穩(wěn)定。正序是o(n)乍惊，反序和隨機是o(n*n);
    • 希爾排序杜秸。不穩(wěn)定。在直接插入排序的基礎(chǔ)上進行分組插入润绎。
  • 選擇排序撬碟。每一趟從待排序的記錄中選擇關(guān)鍵字最小的紀錄順序放在排好序的子文件最后。
    • 直接選擇排序莉撇。不穩(wěn)定呢蛤。o(n*n)
    • 堆排序。
  • 交換排序棍郎。兩兩比較待排序記錄的關(guān)鍵字其障，發(fā)現(xiàn)兩個紀錄的次序相反時就進行交換。
    • 冒泡排序涂佃。正序是o(n)静秆。最壞是o(n*n)。穩(wěn)定巡李。排序過程中交替改變掃描方向抚笔，改進不對稱性。
    • 快速排序侨拦。不穩(wěn)定殊橙。平均時間復(fù)雜度o(nlgn)
  • 歸并排序
  • 分配排序

• 外部排序

  • 合并排序
  • 直接合并排序法

八：查找

1：順序查找。適用于線性表的順序結(jié)構(gòu)狱从，也適用于線性表的鏈式存儲結(jié)構(gòu)膨蛮。但是鏈式存儲結(jié)構(gòu)需要從第一個節(jié)點開始掃描季研。

2：二分查找与涡。屬于靜態(tài)查找，因為如果該表要是還需要修改氨肌，那么就很費時。要求線性表是有序的卿叽，并且要用向量作為表的存儲結(jié)構(gòu)考婴。二分查找不會超過樹的深度催烘，但是由于需要有序颗圣，因此也費時在岂。二分查找只能用于順序結(jié)構(gòu)。鏈式結(jié)構(gòu)需要用順序查找易茬。因為二分查找需要線性表可以隨機存取抽莱。因為二分查找需要隨機讀取一半的位置食铐，一半的一半的位置僧鲁。寞秃。春寿。

3：分塊查找。比如給一個學(xué)號要在一個學(xué)校中查找谢床。我們需要維護一個數(shù)組用來存放有序的的班級信息。通過二分查找找到班級所在的塊之后，再通過順序查找來查找班級中的學(xué)號覆履。分塊查找是順序查找和二分查找的結(jié)合费薄。需要多維護一個有序索引數(shù)組楞抡。

4：二叉排序樹簿寂。動態(tài)查找表效率高比藻。每個節(jié)點的左邊子元素的值小于該節(jié)點棠隐，右子元素的值大于該節(jié)點暂幼。二叉排序樹最壞的情況是形成一個單支樹，最好的情況是勻稱败潦。

5：B樹劫扒，用來對磁盤等外部存儲進行查找。B樹幾乎替代了除散列方法意外的所有大型文件查找疮胖。

6：散列表澎灸。建立關(guān)鍵字與地址之間的關(guān)系遮晚，通過對元素直接尋址來查找县遣。兩個不同的關(guān)鍵字汹族，由于散列函數(shù)值不同顶瞒，而被映射到同一個低智商榴徐，稱為沖突坑资。

九：動態(tài)存儲管理

動態(tài)內(nèi)存分區(qū)常用算法：

最先適配法(nrst-fit)：按分區(qū)在內(nèi)存的先后次序從頭查找袱贮，找到符合要求的第一個分區(qū)進行分配攒巍。該算法的分配和釋放的時間性能較好窑业，較大的空閑分區(qū)可以被保留在內(nèi)存高端常柄。但隨著低端分區(qū)不斷劃分會產(chǎn)生較多小分區(qū)西潘，每次分配時查找時間開銷便會增大喷市。

下次適配法(循環(huán)首次適應(yīng)算法 next fit)：按分區(qū)在內(nèi)存的先后次序品姓，從上次分配的分區(qū)起查找(到最后{區(qū)時再從頭開始}腹备，找到符合要求的第一個分區(qū)進行分配植酥。該算法的分配和釋放的時間性能較好，使空閑分區(qū)分布得更均勻漂羊，但較大空閑分區(qū)不易保留。

最佳適配法(best-fit)：按分區(qū)在內(nèi)存的先后次序從頭查找耻瑟，找到其大小與要求相差最小的空閑分區(qū)進行分配。從個別來看淤毛，外碎片較小瞬项；但從整體來看囱淋，會形成較多外碎片優(yōu)點是較大的空閑分區(qū)可以被保留妥衣。

最壞適配法(worst- fit)：按分區(qū)在內(nèi)存的先后次序從頭查找税手，找到最大的空閑分區(qū)進行分配芦倒”铮基本不留下小空閑分區(qū)器钟，不易形成外碎片俱箱。但由于較大的空閑分區(qū)不被保留狞谱，當(dāng)對內(nèi)存需求較大的進程需要運行時跟衅，其要求不易被滿足掰读。