第六章、數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)
1、數(shù)組與矩陣
1.1、數(shù)組
已知5行5列的二維數(shù)組a中的各元素占兩個(gè)字節(jié)，求元素a[2][3]按行優(yōu)先存儲(chǔ)的存儲(chǔ)地址？
按行存：a+(5*2+3)2=a+26
按列存：a+(53+2)*2=a+34
1.2、稀疏矩陣
在矩陣中，若數(shù)值為0的元素?cái)?shù)目遠(yuǎn)遠(yuǎn)多于非0元素的數(shù)目，并且非0元素分布沒有規(guī)律時(shí)，則稱該矩陣為稀疏矩陣；與之相反，若非0元素?cái)?shù)目占大多數(shù)時(shí)，則稱該矩陣為稠密矩陣。定義非零元素的總數(shù)比上矩陣所有元素的總數(shù)為矩陣的稠密度。
設(shè)有如下所示的下三角矩陣A[0…8,0…8]，將該三角矩陣的非零元素(即行下標(biāo)不小于列下標(biāo)的所有元素）按行優(yōu)先壓縮存儲(chǔ)在數(shù)組M[1…m]中，則元素A[i,j]（0≤i≤8，j≤i）存儲(chǔ)在數(shù)組M的（）中。
因?yàn)锳0,0存儲(chǔ)在M[1]中，所以，將0,0帶入驗(yàn)證
A1,1存儲(chǔ)在M[3]中，將1,1帶入驗(yàn)證
A正確
1.3、數(shù)據(jù)結(jié)構(gòu)的定義
1??數(shù)據(jù)結(jié)構(gòu)的概念
數(shù)據(jù)結(jié)構(gòu)指的是計(jì)算機(jī)中存儲(chǔ)和組織數(shù)據(jù)的方式，包括數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩個(gè)方面
2??數(shù)據(jù)邏輯結(jié)構(gòu)
邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的關(guān)系
-
線性結(jié)構(gòu)（如數(shù)組、鏈表）
-
樹形結(jié)構(gòu)（如二叉樹、堆、AVL樹）
-
圖形結(jié)構(gòu)（如鄰接表、鄰接矩陣）
2、線性表
2.1、順序表和鏈表
線性表的概念
線性表是由同類型數(shù)據(jù)元素構(gòu)成有限序列的數(shù)據(jù)結(jié)構(gòu)，其中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)元素之外，其它每個(gè)數(shù)據(jù)元素都有且只有一個(gè)直接前驅(qū)元素和一個(gè)直接后繼元素
線性表常見的兩種存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)結(jié)構(gòu)是指使用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素
順序表：
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)指針將各個(gè)數(shù)據(jù)元素的存儲(chǔ)單元連接起來(lái)
單鏈表刪除結(jié)點(diǎn)需要先找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后將前驅(qū)結(jié)點(diǎn)的 next 指針指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，然后釋放該結(jié)點(diǎn)的內(nèi)存空間。
p→next=q→next
單鏈表插入結(jié)點(diǎn)
- 創(chuàng)建一個(gè)新的結(jié)點(diǎn)，并給它賦予需要插入的值。
- 找到要插入的位置，即要插入結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。
- 將新結(jié)點(diǎn)的 next 指針指向前驅(qū)結(jié)點(diǎn)的 next 指針指向的結(jié)點(diǎn)。
s→next=p→next - 將前驅(qū)結(jié)點(diǎn)的 next 指針指向新結(jié)點(diǎn)。
p→next=s
2.2、順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)對(duì)比
2.3、 隊(duì)列與棧
循環(huán)隊(duì)列是一種特殊的隊(duì)列數(shù)據(jù)結(jié)構(gòu)，它可以通過(guò)數(shù)組或鏈表實(shí)現(xiàn)。它與普通隊(duì)列最大的不同在于，當(dāng)隊(duì)列滿時(shí)，循環(huán)隊(duì)列可以將新元素插入到隊(duì)列頭部，從而實(shí)現(xiàn)循環(huán)使用存儲(chǔ)空間的目的
習(xí)題：元素按照a、b、c的次序進(jìn)入棧，請(qǐng)嘗試寫出其所有可能的出棧序列。
a b c 、b a c 、 c b a 、 b c a
A ：左進(jìn)1 2 3 4 ，左出4 3 2 1 A正確
B：左進(jìn)1 2 右進(jìn) 3 左進(jìn)4，左出4 2 1 3 B正確
C：左進(jìn) 1 右進(jìn) 2 左進(jìn) 3 4，左出4 3 1 2 C正確
D：no
3、廣義表
廣義表是線性表的推廣，它是由原子和廣義表組成的多層次結(jié)構(gòu)。廣義表中的元素可以是原子，也可以是另一個(gè)廣義表，用逗號(hào)分隔，整個(gè)廣義表用括號(hào)括起來(lái)
通常用遞歸的形式進(jìn)行定義，記做：LS=（ao，a1，…，an)。
注：其中LS是表名，a；是表元素，它可以是表（稱做子表），也可以是數(shù)據(jù)元素（稱為原子）。其中n是廣義表的長(zhǎng)度（也就是最外層包含的元素個(gè)數(shù)），n=0的廣義表為空表；而遞歸定義的重?cái)?shù)就是廣義表的深度，直觀地說(shuō)，就是定義中所含括號(hào)的重?cái)?shù)（原子的深度為0，空表的深度為1）。
基本運(yùn)算：取表頭head(Ls)和取表尾tail(Ls)
若有：LS1=（a，（b,c），（d,e））
head(LS1)=a
tail(LS1)=((b,c),(d,e))
在廣義表中，第一個(gè)元素稱為表頭，它可以是一個(gè)原子或一個(gè)子表，表示廣義表中第一個(gè)元素的值；剩余部分稱為表尾，也是一個(gè)廣義表，由原廣義表中除第一個(gè)元素外的所有元素構(gòu)成。如果廣義表只有一個(gè)元素，那么這個(gè)元素既是表頭，也是表尾。
例1，有廣義表LS1=（a，（b，c)，（d，e)），則其長(zhǎng)度為?深度為?
例2，有廣義表LS1=（a，（b，c），（d，e）），要將其中的b字母取出，操作就為?
長(zhǎng)度為3，深度為2
head(head(tail(LS1)))
4、樹與二叉樹
結(jié)點(diǎn)的度：指結(jié)點(diǎn)擁有的子樹數(shù)目
樹的度：指樹中結(jié)點(diǎn)的最大度數(shù)
葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)
分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)或內(nèi)部結(jié)點(diǎn)
內(nèi)部結(jié)點(diǎn)：除根節(jié)點(diǎn)和葉子結(jié)點(diǎn)外的結(jié)點(diǎn)
父結(jié)點(diǎn)：某個(gè)結(jié)點(diǎn)下面的結(jié)點(diǎn)，該結(jié)點(diǎn)就是它下面的結(jié)點(diǎn)的父結(jié)點(diǎn)
子結(jié)點(diǎn)：某個(gè)結(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)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)為其父結(jié)點(diǎn)的層數(shù)加1
4.1、特殊二叉樹
滿二叉樹是一種特殊的二叉樹，其所有非葉子節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，且所有葉子節(jié)點(diǎn)都在同一層級(jí)上
完全二叉樹是一種特殊的二叉樹，它除了最后一層外，其他所有層都是滿的，而且最后一層上的節(jié)點(diǎn)都靠左排列
非完全二叉樹指的是不符合完全二叉樹定義的二叉樹，即有些層次不滿，且最后一層的葉子節(jié)點(diǎn)不一定靠左對(duì)齊
二叉樹的重要性
1、在二叉樹的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）
2、深度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)（k≥1）
3、對(duì)任何一棵二叉樹，如果其葉子結(jié)點(diǎn)數(shù)為no，度為2的結(jié)點(diǎn)數(shù)為n2，則no=n2+1
4、如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)（從第1層到log2n+1層，每層從左到右），則對(duì)任一結(jié)點(diǎn)i（1≥i≥n），有：
如果i=1，則結(jié)點(diǎn)i無(wú)父結(jié)點(diǎn)，是二叉樹的根；如果i>1，則父結(jié)點(diǎn)是i/2；
如果2i>n，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左子結(jié)點(diǎn)；否則，其左子結(jié)點(diǎn)是結(jié)點(diǎn)2i；
如果2i+1>n，則結(jié)點(diǎn)i無(wú)右子葉點(diǎn)，否則，其右子結(jié)點(diǎn)是結(jié)點(diǎn)2i+1。
4.2、二叉樹遍歷
前序遍歷：先訪問(wèn)根結(jié)點(diǎn)，再依次遞歸訪問(wèn)左子樹和右子樹
中序遍歷：先遞歸訪問(wèn)左子樹，再訪問(wèn)根結(jié)點(diǎn)，最后遞歸訪問(wèn)右子樹
后序遍歷：先遞歸訪問(wèn)左子樹和右子樹，最后訪問(wèn)根結(jié)點(diǎn)
層次遍歷：按照從上到下、從左到右的順序依次訪問(wèn)每個(gè)結(jié)點(diǎn)
圖中前序遍歷結(jié)果是？（根左右）
1 2 4 5 7 8 3 6
圖中中序遍歷結(jié)果是?（左根右）
4 2 7 8 5 1 3 6
圖中后序遍歷結(jié)果是？（左右根）
4 8 7 5 2 6 3 1
圖中層次遍歷結(jié)果是？
1 2 3 4 5 6 7 8
4.3、反向構(gòu)造二叉樹
由前序序列為ABHFDECG；中序序列為HBEDFAGC構(gòu)造二叉樹。
4.4、樹轉(zhuǎn)二叉樹
樹轉(zhuǎn)二叉樹（Tree to Binary Tree）是一種將普通樹轉(zhuǎn)化為二叉樹的過(guò)程。它的主要思想是，對(duì)于樹中的每個(gè)結(jié)點(diǎn)，將它的第一個(gè)孩子作為左孩子，其他孩子都作為該孩子的右孩子。這樣，就可以將普通樹轉(zhuǎn)化為二叉樹
孩子結(jié)點(diǎn)-左子樹結(jié)點(diǎn)
兄弟結(jié)點(diǎn)-右孩子結(jié)點(diǎn)
4.5、查找二叉樹
二叉排序樹
左孩子小于根
右孩子大于根
插入結(jié)點(diǎn)：
①若該鍵值結(jié)點(diǎn)已存在，則不再插入，如：48
②若查找二叉樹為空樹，則以新結(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)，則直接刪除
②若待刪除結(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)，則在其左子樹上，用中序遍歷尋找關(guān)鍵值最大的結(jié)點(diǎn)s，用結(jié)點(diǎn)s的值代替結(jié)點(diǎn)p的值，然后刪除節(jié)點(diǎn)s，節(jié)點(diǎn)s必屬于上述①，②情況之一，如89
4.6、最優(yōu)二叉樹（哈夫曼樹）
需要了解的基本概念：
樹的路徑長(zhǎng)度：指的是從根節(jié)點(diǎn)到任意一個(gè)節(jié)點(diǎn)的邊的條數(shù)之和
權(quán)：是指節(jié)點(diǎn)所帶有的值，比如樹中的權(quán)值可以表示節(jié)點(diǎn)的大小、權(quán)重、出現(xiàn)頻率等
帶權(quán)路徑長(zhǎng)度：指的是樹中每一個(gè)葉子節(jié)點(diǎn)的權(quán)值乘以到根節(jié)點(diǎn)路徑長(zhǎng)度之和。即帶權(quán)路徑長(zhǎng)度 = 葉子節(jié)點(diǎn)權(quán)值 × 路徑長(zhǎng)度
樹的帶權(quán)路徑長(zhǎng)度（樹的代價(jià)）：指的是樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。它可以用來(lái)衡量樹的形態(tài)和節(jié)點(diǎn)權(quán)值的分布情況，是一種評(píng)估樹結(jié)構(gòu)優(yōu)劣的指標(biāo)
例：假設(shè)有一組權(quán)值5,29,7,8,14,23,3,11請(qǐng)嘗試構(gòu)造哈夫曼樹。
4.7、線索二叉樹
為什么要有線索二叉樹
在二叉樹的遍歷過(guò)程中，我們需要用到遞歸或者棧來(lái)實(shí)現(xiàn)，這種方法雖然簡(jiǎn)單易行，但是卻消耗了大量的空間，因?yàn)槊看伪闅v都需要分配新的棧空間。為了避免這種浪費(fèi)，我們可以使用線索二叉樹來(lái)進(jìn)行遍歷，它不僅可以減少空間的浪費(fèi)，還能提高遍歷的效率。
線索二叉樹的概念
線索二叉樹是對(duì)普通二叉樹的一種改進(jìn)，它的每個(gè)結(jié)點(diǎn)除了有左右孩子指針之外，還有指向中序遍歷下的前驅(qū)和后繼的指針，稱之為線索
線索二叉樹的表示
對(duì)于一個(gè)二叉樹結(jié)點(diǎn)來(lái)說(shuō)，如果其左子樹為空，則將左指針指向該結(jié)點(diǎn)的中序遍歷下的前驅(qū)結(jié)點(diǎn)；如果其右子樹為空，則將右指針指向該結(jié)點(diǎn)的中序遍歷下的后繼結(jié)點(diǎn)
如何將二叉樹轉(zhuǎn)化為線索二叉樹
- 對(duì)于任意一個(gè)結(jié)點(diǎn)，如果其左子樹不為空，則將其左孩子結(jié)點(diǎn)的指針指向該結(jié)點(diǎn)的中序遍歷下的前驅(qū)結(jié)點(diǎn)
- 對(duì)于任意一個(gè)結(jié)點(diǎn)，如果其右子樹不為空，則將其右孩子結(jié)點(diǎn)的指針指向該結(jié)點(diǎn)的中序遍歷下的后繼結(jié)點(diǎn)
- 對(duì)于根結(jié)點(diǎn)，其左指針指向其左子樹的中序遍歷下的最后一個(gè)結(jié)點(diǎn)，右指針指向其右子樹的中序遍歷下的第一個(gè)結(jié)點(diǎn)
- 對(duì)于中序遍歷下的最后一個(gè)結(jié)點(diǎn)，其右指針指向中序遍歷的結(jié)束標(biāo)志（如 NULL 或者一個(gè)特殊結(jié)點(diǎn)）
4.8、平衡二叉樹
平衡二叉樹的提出原因
解決二叉查找樹在極端情況下（如插入遞增或遞減的序列）可能退化成鏈表的問(wèn)題，使得查找、插入、刪除的時(shí)間復(fù)雜度保持在O(log n)的級(jí)別
平衡二叉樹的定義
平衡二叉樹是一種二叉查找樹，它的左右子樹的高度差不超過(guò)1，即任意節(jié)點(diǎn)的左右子樹的高度差的絕對(duì)值不超過(guò)1
平衡樹的建立過(guò)程
通常有兩種方法，一種是在空樹中直接插入節(jié)點(diǎn)，每次插入節(jié)點(diǎn)后檢查樹是否失去平衡，如果失去平衡則對(duì)不平衡的節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)操作；另一種是先將所有節(jié)點(diǎn)插入到一個(gè)無(wú)序表中，然后構(gòu)建一棵平衡樹
動(dòng)態(tài)調(diào)平衡問(wèn)題
在向平衡樹中插入或刪除節(jié)點(diǎn)時(shí)，可能會(huì)破壞樹的平衡性，需要通過(guò)旋轉(zhuǎn)操作或其他平衡調(diào)整算法來(lái)恢復(fù)平衡
5、圖
完全圖
在無(wú)向圖中，若每對(duì)頂點(diǎn)之間都有一條邊相連，則稱該圖為完全圖（completegraph)。
在有向圖中，若每對(duì)頂點(diǎn)之間都有二條有向邊相互連接，則稱該圖為完全圖。
5.1、圖的存儲(chǔ) - 鄰接矩陣
用一個(gè)n階方陣R來(lái)存放圖中各結(jié)點(diǎn)的關(guān)聯(lián)信息，其矩陣元素Rij定義為：
5.2、圖的存儲(chǔ) - 鄰接表
首先把每個(gè)頂點(diǎn)的鄰接頂點(diǎn)用鏈表示出來(lái)，然后用一個(gè)一維數(shù)組來(lái)順序存儲(chǔ)上面每個(gè)鏈表的頭指針
5.3、圖的遍歷
5.4、拓?fù)渑判?/h4>
拓?fù)渑判蚴侵笇?duì)有向無(wú)環(huán)圖（DAG）進(jìn)行排序，使得所有的頂點(diǎn)被排序成一個(gè)線性序列，滿足若存在一條從頂點(diǎn) A 到頂點(diǎn) B 的有向路徑，則在序列中頂點(diǎn) A 應(yīng)該出現(xiàn)在頂點(diǎn) B 的前面
我們把用有向邊表示活動(dòng)之間開始的先后關(guān)系。這種有向圖稱為用頂點(diǎn)表示活動(dòng)網(wǎng)絡(luò)，簡(jiǎn)稱AOV網(wǎng)絡(luò)。
上圖的拓樸序列有：02143567，01243657，02143657，01243567。
5.5、圖的最小生成樹–普里姆算法
普里姆算法是一種用于求加權(quán)連通圖的最小生成樹的算法。其基本思想是從圖中任意選一個(gè)頂點(diǎn)開始，不斷尋找與該頂點(diǎn)距離最近的未訪問(wèn)頂點(diǎn)，并將該頂點(diǎn)加入最小生成樹中
5.5、圖的最小生成樹–克魯斯卡爾算法
克魯斯卡爾算法是求解帶權(quán)無(wú)向連通圖的最小生成樹問(wèn)題的一種貪心算法。該算法首先將所有邊按照權(quán)值從小到大排序，然后從小到大依次加入邊，直到生成樹中包含所有頂點(diǎn)為止。在加入一條邊時(shí)，需要判斷該邊的兩個(gè)頂點(diǎn)是否已經(jīng)在生成樹中，如果在，則不能加入這條邊，否則加入這條邊
6、算法基礎(chǔ)
6.1、算法的特性
有窮性：執(zhí)行有窮步之后結(jié)束。
確定性：算法中每一條指令都必須有確切的含義，不能含糊不清。
輸入（>=0）
輸出（>=1）
有效性：算法的每個(gè)步驟都能有效執(zhí)行并能得到確定的結(jié)果。例如a=0，b/a就無(wú)效
6.2、算法的復(fù)雜度
??時(shí)間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需要的時(shí)間。通常分析時(shí)間復(fù)雜度的方法是從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本運(yùn)算的操作，以該操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。一般來(lái)說(shuō)，算法中原操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的某個(gè)函數(shù)T(n)。由于許多情況下要精確計(jì)算T(n)是困難的，因此引入了漸進(jìn)時(shí)間復(fù)雜度在數(shù)量上估計(jì)一個(gè)算法的執(zhí)行時(shí)間。其定義如下：
??如果存在兩個(gè)常數(shù)c和m，對(duì)于所有的n，當(dāng)n≥m時(shí)有f(n)≤cg(n)，則有f(n)=O（g(n))。也就是說(shuō)，隨著n的增大，f(n)漸進(jìn)地不大于g(n)。例如，一個(gè)程序的實(shí)際執(zhí)行時(shí)間為T(n)=3n3+2n2+n，則T(n)=O(n3)。
??常見的對(duì)算法執(zhí)行所需時(shí)間的度量：0(1)<0(log2n)<0(n)<0(nlog2n)<0(n2)<0(n3)<0(2n)
??空間復(fù)雜度是指對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的度量。一個(gè)算法的空間復(fù)雜度只考慮在運(yùn)行過(guò)程中為局部變量分配的存儲(chǔ)空間的大小
7、排序與查找
7.1、順序查找
順序查找的思想：將待查找的關(guān)鍵字為key的元素從頭到尾與表中元素進(jìn)行比較，如果中間存在關(guān)鍵字為key的元素，則返回成功；否則，則查找失敗。
7.2、二分查找
二分法查找的基本思想是：（設(shè)R[low,.….,high]是當(dāng)前的查找區(qū))
（1）確定該區(qū)間的中點(diǎn)位置：mid=[（low+high）/2]；
（2）將待查的k值與R[mid].key比較，若相等，則查找成功并返回此位置，否則需確定新的查找區(qū)間，繼續(xù)二分查找，具體方法如下。
若R[mid].key>k，則由表的有序性可知R[mid…,n].key均大于k，因此若表中存在關(guān)鍵字等于k的結(jié)點(diǎn)，則該結(jié)點(diǎn)必定是在位置mid左邊的子表R[low,.…,mid-1]中。因此，新的查找區(qū)間是左子表R[low,….,high],其中high=mid-1。
若R[mid].key<k，則要查找的k必在mid的右子表R[mid+1,.….,high]中，即新的查找區(qū)間是右子表R[low,.….,high]，其中l(wèi)ow=mid+1?！と鬜[mid].key=k，則查找成功，算法結(jié)束。
（3）下一次查找是針對(duì)新的查找區(qū)間進(jìn)行，重復(fù)步驟（1）和（2）
（4）在查找過(guò)程中，low逐步增加，而high逐步減少。如果high<low，則查找失敗，算法結(jié)束。
折半查找在查找成功時(shí)關(guān)鍵字的比較次數(shù)最多為log2n+1次。
折半查找的時(shí)間復(fù)雜度為O（log2n)。
7.3、散列表
散列表查找的基本思想是：已知關(guān)鍵字集合U，最大關(guān)鍵字為m，設(shè)計(jì)一個(gè)函數(shù)Hash，它以關(guān)鍵字為自變量，關(guān)鍵字的存儲(chǔ)地址為因變量，將關(guān)鍵字映射到一個(gè)有限的、地址連續(xù)的區(qū)間T[0…n-1]（n<<m)中，這個(gè)區(qū)間就稱為散列表，散列查找中使用的轉(zhuǎn)換函數(shù)稱為散列函數(shù)。
例：記錄關(guān)鍵碼為(3，8,12,17,9）,取m=10（存儲(chǔ)空間為10），p=5，散列函數(shù)h=key%p
7.4、排序
排序方法分類
7.4.1、插入排序
1??直接插入排序：即當(dāng)插入第i個(gè)記錄時(shí)，R1，R2，…，Ri-1均已排好序，因此，將第i個(gè)記錄R；依次與Ri-1，…，R2，R1進(jìn)行比較，找到合適的位置插入。它簡(jiǎn)單明了，但速度很慢。
2??希爾（Shell）排序：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為d的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1（dt<dt-1<O<d2<d1），即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。該方法?shí)質(zhì)上是一種分組插入方法。
7.4.2、交換類排序
1??直接選擇排序的過(guò)程是，首先在所有記錄中選出排序碼最小的記錄，把它與第1個(gè)記錄交換，然后在其余的記錄內(nèi)選出排序碼最小的記錄，與第2個(gè)記錄交換…….依次類推，直到所有記錄排完為止。
2??冒泡排序
冒泡排序的基本思想是，通過(guò)相鄰元素之間的比較和交換，將排序碼較小的元素逐漸從底部移向頂部。由于整個(gè)排序的過(guò)程就像水底下的氣泡一樣逐漸向上冒，因此稱為冒泡算法。
3??快速排序
快速排序采用的是分治法，其基本思想是將原問(wèn)題分解成若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。通過(guò)遞歸地解決這些子問(wèn)題，然后再將這些子問(wèn)題的解組合成原問(wèn)題的解。
快速排序通常包括兩個(gè)步驟：
第一步，在待排序的n個(gè)記錄中任取一個(gè)記錄，以該記錄的排序碼為準(zhǔn)，將所有記錄都分成兩組，第1組都小于該數(shù)，第2組都大于該數(shù)，如圖所示。
第二步，采用相同的方法對(duì)左、右兩組分別進(jìn)行排序，直到所有記錄都排到相應(yīng)的位置為止。
7.4.3、選擇類排序
1??簡(jiǎn)單選擇排序
2??堆排序
堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)都有一個(gè)值，并滿足父節(jié)點(diǎn)的值總是大于/小于其子節(jié)點(diǎn)的值。
堆排序的基本思想為：先將序列建立堆，然后輸出堆頂元素，再將剩下的序列建立堆，然后再輸出堆頂元素，依此類推，直到所有元素均輸出為止，此時(shí)元素輸出的序列就是一個(gè)有序序列。堆排序的算法步驟如下（以大頂堆為例）：
（1)初始時(shí)將順序表R[1…n]中元素建立為一個(gè)大頂堆，堆頂位于R[1]待序區(qū)為R[1…n]。
（2）循環(huán)執(zhí)行步驟3～步驟4，共n-1次。
（3)假設(shè)為第/次運(yùn)行，則待序區(qū)為R[1…n-i+1]，將堆頂元素R[1]與待序區(qū)尾元素R[n-i+1]交換，此時(shí)頂點(diǎn)元素被輸出，新的待序區(qū)為R[1…n-i]。
（4）待序區(qū)對(duì)應(yīng)的堆已經(jīng)被破壞，將之重新調(diào)整為大頂堆。
設(shè)有n個(gè)元素的序列{K1，K2，….，Kn}，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆。
(1)ki≤k2i且ki≤k2i+1；
(2)ki≥k2i且ki≥k2i+1；
其中（1）稱為小頂堆，（2）稱為大頂堆
假設(shè)有數(shù)組A={1,3,4,5,7,2,6,8,0},初建堆過(guò)程如下
大頂堆排序
將順序表R{80,60,16,50,45,10,15,30,40,20}進(jìn)行堆排序。 
7.4.4、歸并排序
歸并也稱為合并，是將兩個(gè)或兩個(gè)以上的有序子表合并成一個(gè)新的有序表。若將兩個(gè)有序表合并成一個(gè)有序表，則稱為二路合并。合并的過(guò)程是：比較A[i]和A[j]的排序碼大小，若A[i]的排序碼小于等于A[]]的排序碼，則將第一個(gè)有序表中的元素A[i]復(fù)制到R[k]中，并令i和k分別加1；如此循環(huán)下去，直到其中一個(gè)有序表比較和復(fù)制完，然后再將另一個(gè)有序表的剩余元素復(fù)制到R中。
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-445343.html
7.4.5、基數(shù)排序
基數(shù)排序是一種借助多關(guān)鍵字排序思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法?；鶖?shù)排序不是基于關(guān)鍵字比較的排序方法，它適合于元素很多而關(guān)鍵字較少的序列。基數(shù)的選擇和關(guān)鍵字的分解是根據(jù)關(guān)鍵字的類型來(lái)決定的，例如關(guān)鍵字是十進(jìn)制數(shù)，則按個(gè)位、十位來(lái)分解。
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-445343.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
