數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)

考點(diǎn)：數(shù)組與矩陣、線性表、廣義表、樹(shù)與二叉樹(shù)、圖、排序與查找、算法基礎(chǔ)與常見(jiàn)的算法

1. 數(shù)組

2. 稀疏矩陣

采用上三角或者下三角的形式存儲(chǔ)矩陣

例題：A、可以使用代入法判斷

3. 數(shù)據(jù)結(jié)構(gòu)的定義

存儲(chǔ)和組織數(shù)據(jù)的方式

線性結(jié)構(gòu)、非線性結(jié)構(gòu)包含樹(shù)(不存在環(huán)路)和圖(存在環(huán)路)；從意義上講圖可以包含樹(shù)，樹(shù)包含線性結(jié)構(gòu)

4. 線性表的定義 - 順序表/鏈表

基本操作
單鏈表刪除：p -> next = q -> next
單鏈表插入：s -> next = p -> next; p -> next = s;

5. 順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)對(duì)比

循環(huán)隊(duì)列問(wèn)題：無(wú)法區(qū)分隊(duì)空和隊(duì)滿(mǎn)的情況
兩種解決方案：1記錄隊(duì)滿(mǎn)隊(duì)空狀態(tài)；2少存一位元素(多數(shù))

例題：

7. 廣義表

例一：3，2
例二：head(head(tail(LS1)))

8. 樹(shù)與二叉樹(shù)

基本概念：

結(jié)點(diǎn)的度是它的孩子字結(jié)點(diǎn)數(shù)，1結(jié)點(diǎn)度2，3結(jié)點(diǎn)度1，7結(jié)點(diǎn)度0

樹(shù)的度是所有結(jié)點(diǎn)度中最高的結(jié)點(diǎn)的度；樹(shù)的度為2

葉子結(jié)點(diǎn)是沒(méi)有子結(jié)點(diǎn)的；4，5，7，8

分支節(jié)點(diǎn)，度不為0的節(jié)點(diǎn)

內(nèi)部節(jié)點(diǎn)，即不是葉子結(jié)點(diǎn)，也不是根結(jié)點(diǎn)；2，3，6

父結(jié)點(diǎn)和子結(jié)點(diǎn)是相對(duì)的概念；2是1的子結(jié)點(diǎn)；4是2的子結(jié)點(diǎn)

兄弟結(jié)點(diǎn)；4和5

層次，4層

9. 滿(mǎn)二叉樹(shù)和完全二叉樹(shù)

滿(mǎn)二叉樹(shù)：可以構(gòu)成一個(gè)完整的三角形

完全二叉樹(shù)：完全二叉樹(shù)的定義是一個(gè)深度為k的有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中的節(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，編號(hào)1≤i≤n的結(jié)點(diǎn)與滿(mǎn)二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置相同。

10. 二叉樹(shù)的特性

二叉樹(shù)的第i層最多有2^(i-1)個(gè)結(jié)點(diǎn)

深度為k的二叉樹(shù)最多有2^k - 1個(gè)結(jié)點(diǎn)

對(duì)任何一顆二叉樹(shù)，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1

如果對(duì)一顆有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層序編號(hào)，對(duì)任意結(jié)點(diǎn)i（1<=i<=n），有：
如果i=1，則結(jié)點(diǎn)無(wú)父結(jié)點(diǎn)，是二叉樹(shù)的根，如果i>i，則它的父結(jié)點(diǎn)是i/2
如果2i>n，則結(jié)點(diǎn)為i為葉子結(jié)點(diǎn)，無(wú)左子結(jié)點(diǎn)；否則，其左子結(jié)點(diǎn)是2i
如果2i+1>n，則結(jié)點(diǎn)i無(wú)右葉子結(jié)點(diǎn)，否則，其右子結(jié)點(diǎn)是2i+1

11. 二叉樹(shù)遍歷

層次遍歷：從根結(jié)點(diǎn)開(kāi)始，每層依次從左至右訪問(wèn)完；12345678

前序遍歷(根左右)是先訪問(wèn)根結(jié)點(diǎn)，再訪問(wèn)左子結(jié)點(diǎn)和右子結(jié)點(diǎn)；12457836

中序遍歷(左根右)是先訪問(wèn)左子結(jié)點(diǎn)，在訪問(wèn)根結(jié)點(diǎn)和右子結(jié)點(diǎn)；42785136

后序遍歷(左右根)是先訪問(wèn)左子結(jié)點(diǎn)，再訪問(wèn)右子結(jié)點(diǎn)和根結(jié)點(diǎn)；48752631

12. 反向構(gòu)造二叉樹(shù)

根據(jù)二叉樹(shù)的遍歷序列，反向構(gòu)造二叉樹(shù)；必須有中序序列和任意前序或后序序列才能實(shí)現(xiàn)

標(biāo)記根結(jié)點(diǎn)，然后推理左右結(jié)點(diǎn)

13. 樹(shù)轉(zhuǎn)二叉樹(shù)

孩子結(jié)點(diǎn) - 左子樹(shù)結(jié)點(diǎn)

兄弟結(jié)點(diǎn) - 右孩子結(jié)點(diǎn)

14. 查找二叉樹(shù)(二叉排序樹(shù))

也稱(chēng)二叉排序樹(shù)；左子結(jié)點(diǎn)小于根；右子結(jié)點(diǎn)大于根；

插入結(jié)點(diǎn)：

若該鍵值結(jié)點(diǎn)已存在，則不再插入，如48
若查找二叉樹(shù)為空樹(shù)，則以新結(jié)點(diǎn)為查找二叉樹(shù)
將要插入結(jié)點(diǎn)鍵值與插入后父結(jié)點(diǎn)鍵值比較，就能確定新結(jié)點(diǎn)是父結(jié)點(diǎn)的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)

刪除結(jié)點(diǎn)：

若刪除結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則直接刪除
若待刪除結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)，則將這個(gè)子結(jié)點(diǎn)與待刪除結(jié)點(diǎn)的父結(jié)點(diǎn)直接連接，如56
若待刪除的結(jié)點(diǎn)p右兩個(gè)子結(jié)點(diǎn)，則在其左子樹(shù)上，用中序遍歷尋找關(guān)鍵值最大的結(jié)點(diǎn)S，用結(jié)點(diǎn)s的值代替結(jié)點(diǎn)p的值，然后刪除結(jié)點(diǎn)s，結(jié)點(diǎn)s必屬于上述兩種情況之一，如89

15. 最優(yōu)二叉樹(shù)(哈夫曼樹(shù))

樹(shù)的路徑長(zhǎng)度：樹(shù)的路徑累加長(zhǎng)度
權(quán)：某個(gè)葉子結(jié)點(diǎn)的鍵值，即某個(gè)字符出現(xiàn)的頻度
帶權(quán)路徑長(zhǎng)度：路徑長(zhǎng)度 * 權(quán)值；例如2結(jié)點(diǎn)，2*2=4；4結(jié)點(diǎn)3*4=12
樹(shù)的帶權(quán)路徑長(zhǎng)度（樹(shù)的代價(jià)）：所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和

構(gòu)造哈夫曼樹(shù)是嘗試讓樹(shù)的帶權(quán)路徑長(zhǎng)度最?。蝗缦碌谝环N樹(shù)的帶權(quán)路徑長(zhǎng)度是41，第二種是25

例題：

1、從序列中選出2個(gè)權(quán)值最小的數(shù) 3，5構(gòu)成一顆小樹(shù)，小樹(shù)的權(quán)是8，將8添加到序列

2、再?gòu)男蛄兄羞x2個(gè)權(quán)值最小的7，8構(gòu)成一顆樹(shù)，得到權(quán)值15的樹(shù)加到序列

3、依此類(lèi)推不斷構(gòu)成樹(shù)

4、求樹(shù)的葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度只和得到樹(shù)的帶權(quán)路徑長(zhǎng)度

通過(guò)構(gòu)造發(fā)現(xiàn)我們最開(kāi)始的序列都是葉子結(jié)點(diǎn)，所以回頭看定義樹(shù)的帶權(quán)路徑長(zhǎng)度也就是所以葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度只和

16. 線索二叉樹(shù)

如圖在二叉樹(shù)的基礎(chǔ)上有虛線建線把結(jié)點(diǎn)連接起來(lái)；

因?yàn)樵诙鏄?shù)中許多結(jié)點(diǎn)是空閑狀態(tài)，一些結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的指針是空的

按照前序遍歷、中序遍歷、后序遍歷序列的順序連接指針，就構(gòu)成了相對(duì)應(yīng)種類(lèi)的線索二叉樹(shù)

17. 平衡二叉樹(shù)

結(jié)點(diǎn)平衡度 = 左子樹(shù)深度 - 右子樹(shù)深度

18. 圖 - 基本概念

鄰接矩陣

無(wú)向圖的鄰接矩陣全對(duì)角線為0(自己連接自己的點(diǎn))，沿對(duì)角線對(duì)稱(chēng)，所以存儲(chǔ)時(shí)可以只存上三角或下三角

鄰接表

圖的遍歷

19. 圖 - 拓?fù)渑判?/h3>

20. 圖的最小生成樹(shù)

保留最小權(quán)值的邊并能使圖連貫；

樹(shù)和圖的區(qū)別，樹(shù)沒(méi)有環(huán)路；設(shè)樹(shù)的結(jié)點(diǎn)n，邊則n-1；

普里姆算法

例題：從一個(gè)任意結(jié)點(diǎn)出發(fā)，將這個(gè)結(jié)點(diǎn)定義為紅點(diǎn)集，其他結(jié)點(diǎn)為藍(lán)點(diǎn)集；找出從紅點(diǎn)集中到藍(lán)點(diǎn)集中最小的權(quán)

比如選A，找到權(quán)值最小的A -> B，連接后將B加入紅點(diǎn)集

再次判斷的時(shí)候就需要把紅點(diǎn)集的A，B找到藍(lán)點(diǎn)集中到最小權(quán)；依此類(lèi)推

克魯斯卡爾算法

設(shè)頂點(diǎn)樹(shù)為n，依次選擇出圖中最短的n-1條邊，且每次選擇下一條邊時(shí)要保證不形成環(huán)路

21. 算法的特性

有窮性：執(zhí)行有窮步數(shù)之后結(jié)束

確定性：算法中每一條指令都必須有確切的含義，不能含糊不清

輸入數(shù)量（>=0）

輸出數(shù)量（>=1）

有效性：算法的每個(gè)步驟都能有效執(zhí)行并能得到確定的結(jié)果。例如a=0，b/a就無(wú)效。

22. 算法的復(fù)雜度

時(shí)間復(fù)雜度（重點(diǎn)，下午設(shè)計(jì)題出現(xiàn)問(wèn)程序的時(shí)間復(fù)雜度計(jì)算）、空間復(fù)雜度

23. 順序查找

時(shí)間復(fù)雜度O(n)

24. 二分查找

時(shí)間復(fù)雜度(log以2為底n的對(duì)數(shù))

25. 散列表

在數(shù)據(jù)存儲(chǔ)時(shí)遵循一定的規(guī)則。

26. 排序算法總結(jié)**

（有時(shí)只在上午考，有時(shí)上下午都考）

排序的概念

穩(wěn)定與不穩(wěn)定排序(排序前后原有的相等兩個(gè)數(shù)字的順序是否改變，比如分?jǐn)?shù)的排名先來(lái)后到等)、內(nèi)排序(在內(nèi)存進(jìn)行)與外排序(涉及到外部存儲(chǔ)空間)

27. 冒泡排序

https://www.runoob.com/w3cnote/bubble-sort.html

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

28. 直接選擇排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。

重復(fù)第二步，直到所有元素均排序完畢。

29. 直接插入排序

將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。

從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。）

30. 希爾排序(Shell)

希爾排序，也稱(chēng)遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

• 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率；
• 但插入排序一般來(lái)說(shuō)是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位；

希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄"基本有序"時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

算法步驟：

選擇一個(gè)增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；

每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

31. 歸并排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。對(duì)有多個(gè)有序序列進(jìn)行排序，為了方便一般每次操作兩個(gè)序列。

1. 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列；
2. 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；
3. 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；
4. 重復(fù)步驟 3 直到某一指針達(dá)到序列尾；
5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

31. 快速排序

快速排序是一種常用的排序算法，也是一種基于交換排序的算法。它的基本思想是通過(guò)一趟排序?qū)⒋判蛐蛄蟹指畛瑟?dú)立的兩部分，其中一部分的所有元素都比另一部分小，然后再按此方法對(duì)這兩部分分別進(jìn)行快速排序，遞歸地進(jìn)行，以達(dá)到整個(gè)序列有序的目的。

具體實(shí)現(xiàn)過(guò)程如下：

1. 選定一個(gè)樞紐元素（pivot），一般可以選擇待排序數(shù)組的第一個(gè)元素，也可以隨機(jī)選擇。這個(gè)樞紐元素可以將數(shù)組分為兩部分，一部分的元素都小于等于樞紐元素，另一部分的元素都大于樞紐元素。
2. 然后將小于等于樞紐元素的元素放到樞紐元素的左邊，大于樞紐元素的元素放到樞紐元素的右邊。這一步稱(chēng)為分區(qū)（partitioning）。
3. 遞歸地對(duì)樞紐元素左右兩部分分別進(jìn)行上述步驟，直到所有子問(wèn)題的規(guī)模都變得足夠小，可以直接采用插入排序等其他算法進(jìn)行排序。
4. 合并所有已排序的子序列，得到最終的排序結(jié)果。

快速排序的時(shí)間復(fù)雜度為O(nlogn)，其中n為待排序序列的長(zhǎng)度。它是原地排序算法，因此不需要額外的空間，但是快速排序的實(shí)現(xiàn)依賴(lài)于遞歸，因此遞歸過(guò)程中需要使用?？臻g。同時(shí)，由于快速排序是一種不穩(wěn)定的排序算法，因此在需要保持排序前后元素相對(duì)位置關(guān)系的情況下需要進(jìn)行特殊處理。

public class QuickSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left + 1, j = right;
        while (i <= j) {
            while (i <= j && arr[i] < pivot) {
                i++;
            }
            while (i <= j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                swap(arr, i, j);
            }
        }
        swap(arr, left, j);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

小于基準(zhǔn)的放左邊，大于基準(zhǔn)的放右邊；通過(guò)外層while里的兩個(gè)while判斷左右兩邊數(shù)是否需要交換；遞歸對(duì)分好的左右兩邊序列做相同操作

32. 堆排序

初建大頂堆：

從最后一個(gè)非葉子結(jié)點(diǎn)開(kāi)始調(diào)整，依次倒出第2個(gè)，3個(gè)…

5和它的兩個(gè)子結(jié)8,0點(diǎn)比較，將最大值調(diào)整為根；

4和2，6比較后調(diào)整

3個(gè)8，7比較后調(diào)整；注意跟包含子結(jié)點(diǎn)的8交換后還有進(jìn)一步調(diào)整，3，和5，0調(diào)整

最后調(diào)整到根結(jié)點(diǎn)1和8，6調(diào)整，1，8交換后繼續(xù)對(duì)當(dāng)前包含子結(jié)點(diǎn)的1和5，7調(diào)整，把7換上來(lái)后7剛剛不包含子結(jié)點(diǎn)，所以交換結(jié)束

建立堆后的排序：

取走堆頂，將二叉樹(shù)的最后一個(gè)結(jié)點(diǎn)放到堆頂

然后對(duì)堆進(jìn)行調(diào)整，同上面的初建堆方法把20根兩個(gè)子結(jié)點(diǎn)比對(duì)…

public class HeapSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 對(duì) arr 進(jìn)行拷貝，不改變參數(shù)內(nèi)容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int len = arr.length;

        buildMaxHeap(arr, len);

        for (int i = len - 1; i > 0; i--) {
          	// 將堆頂(最大值)與最后一個(gè)結(jié)點(diǎn)交換，然后長(zhǎng)度減一從前面的結(jié)點(diǎn)開(kāi)始再構(gòu)建大頂堆
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    private void buildMaxHeap(int[] arr, int len) {
        // len長(zhǎng)度的線性表，最后一個(gè)元素的父結(jié)點(diǎn)序號(hào)為n/2，因此第一個(gè)大頂堆的子根在這里誕生
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        // 從0開(kāi)始，平衡二叉樹(shù)中當(dāng)前的左、右子結(jié)點(diǎn)
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

33. 基數(shù)排序

(考察的比較少)

基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。

先排個(gè)位，再排十位，再排百位…

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-410829.html

到了這里，關(guān)于【軟件設(shè)計(jì)師06】數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！