數(shù)據(jù)結(jié)構(gòu)概念匯總
傳送門：
數(shù)據(jù)
·是計(jì)算機(jī)加工處理的對(duì)象
·分為數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)
·非數(shù)值數(shù)據(jù)
·數(shù)值數(shù)據(jù)包含整數(shù)、實(shí)數(shù)、復(fù)數(shù)
·非數(shù)值類型包括字符
數(shù)據(jù)元素
·是數(shù)據(jù)的基本單位
數(shù)據(jù)項(xiàng)
·是數(shù)據(jù)的最小單位
邏輯結(jié)構(gòu)
·線性結(jié)構(gòu)、集合結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)
存儲(chǔ)結(jié)構(gòu)
·線性存儲(chǔ)、鏈接存儲(chǔ)、索引存儲(chǔ)、散列存儲(chǔ)
·數(shù)據(jù)結(jié)構(gòu)涉及到數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及數(shù)據(jù)的運(yùn)算
·數(shù)據(jù)結(jié)構(gòu)的規(guī)范：是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算的定義
·數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)：是數(shù)據(jù)的存儲(chǔ)表示和數(shù)據(jù)的運(yùn)算的描述
數(shù)據(jù)類型
·數(shù)據(jù)類型是定義了一個(gè)值的集合以及作用在集合上的運(yùn)算
數(shù)據(jù)抽象
·數(shù)據(jù)抽象是只關(guān)注數(shù)據(jù)的邏輯結(jié)構(gòu)(錯(cuò)了)
過(guò)程抽象
·過(guò)程抽象是只關(guān)注數(shù)據(jù)的運(yùn)算的定義
抽象數(shù)據(jù)類型
·抽象數(shù)據(jù)類型就是過(guò)程抽象和數(shù)據(jù)抽象的聯(lián)合
·使用和實(shí)現(xiàn)的分離
·為什么是使用和實(shí)現(xiàn)的分離而不是規(guī)范和實(shí)現(xiàn)的分離，這里是使用的定義,而數(shù)據(jù)結(jié)構(gòu)式要定義規(guī)范和實(shí)現(xiàn)，沒(méi)有使用
·對(duì)象和運(yùn)算的規(guī)范與對(duì)象的表示和運(yùn)算的實(shí)現(xiàn)分離
數(shù)據(jù)結(jié)構(gòu)的規(guī)范
·是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)運(yùn)算的定義
數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)
·是數(shù)據(jù)的存儲(chǔ)表示和運(yùn)算的的實(shí)現(xiàn)
算法描述
·算法有五個(gè)特點(diǎn) 至少有輸出 可以沒(méi)有輸入 無(wú)二義性 有窮的 可運(yùn)行
·算法是一系列有窮的指令序例，用于解決某一特定問(wèn)題的一系列運(yùn)算
算法分析
·一個(gè)好的算法要有的條件：
簡(jiǎn)明、健壯、正確、效率
·算法分析目的：
分析算法的效率以求改進(jìn)算法
算法的時(shí)間復(fù)雜度
·目的：分析算法的時(shí)間復(fù)雜度和問(wèn)題規(guī)模的關(guān)系
·有最好、最壞、平均
算法的空間復(fù)雜度
·目的(不知道)：分析算法的空間復(fù)雜度與問(wèn)題規(guī)模的關(guān)系
·通?？紤]最壞情況
線性表
·是n個(gè)元素的線性序列
順序表
·就是按順序存儲(chǔ)的線性表
順序表長(zhǎng)度
·順序表的長(zhǎng)度是n也是線性表的長(zhǎng)度
順序表在程序中的表示
·即相關(guān)程序
順序表插入算法
·插入就是直接增加元素，后移后面的元素
順序表刪除算法
·刪除就是直接減少元素，前移元素
單向鏈表
·帶表頭結(jié)點(diǎn)和不帶的，都有first指針
雙向鏈表
·兩個(gè)域，一個(gè)字段，對(duì)應(yīng)llink和rlink
表頭指針
·first指針，指向第一個(gè)或者表頭結(jié)點(diǎn)
表尾指針
·最后一個(gè)結(jié)點(diǎn)的next稱為表尾指針，單向鏈表就是null
表頭結(jié)點(diǎn)
·方便運(yùn)算加的一個(gè)結(jié)點(diǎn)
循環(huán)單向鏈表
·即表尾指針指向一個(gè)第一個(gè)結(jié)點(diǎn)的元素
循環(huán)雙向鏈表
·最后一個(gè)的右指向第一個(gè)元素的左
單向鏈表定位算法
·順著指針往后面找
單向鏈表插入算法
·改變鏈接的位置
單向鏈表刪除算法
·同
雙向鏈表插入操作步驟
·
雙向鏈表刪除操作步驟
·
棧
·棧是一種數(shù)據(jù)結(jié)構(gòu)
·是線性表，限制訪問(wèn)的
·限定線性表的插入和刪除操作在同端進(jìn)行
隊(duì)列
·一種數(shù)據(jù)結(jié)構(gòu)
·是線性表，限制訪問(wèn)的
·限定線性表的插入和刪除操作在不同端進(jìn)行
棧頂
·進(jìn)行操作的一端
棧底
·不進(jìn)行操作的一端
隊(duì)首
·進(jìn)數(shù)據(jù)的一端
隊(duì)尾
·出數(shù)據(jù)的一端
順序棧
·棧的順序存儲(chǔ)結(jié)構(gòu)是順序棧
鏈接棧
·棧的鏈接存儲(chǔ)結(jié)構(gòu)是鏈接棧
棧頂指針
·用來(lái)專門指出棧頂元素所在的位置，即Top
順序棧在程序中的表示
·即代碼表示
鏈接棧在程序中的表示
·即代碼表示
順序隊(duì)列
·隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
鏈接隊(duì)列
·隊(duì)列的鏈接存儲(chǔ)
隊(duì)首指針
·就是在隊(duì)列的插入輸出的時(shí)候，那個(gè)往中間移動(dòng)的，為于隊(duì)首元素的前一個(gè)，即往右移動(dòng)就是出隊(duì)
隊(duì)尾指針
·指向隊(duì)尾元素，向右就是進(jìn)隊(duì)，剛開始的時(shí)候在2個(gè)指針都在一個(gè)位置，就是空隊(duì)，然后是先進(jìn)隊(duì)，就是隊(duì)尾指針移動(dòng)
順序隊(duì)列在程序中的表示
·記住是限定插入和刪除的線性表的順序存儲(chǔ)
鏈接隊(duì)列在程序中的表示
·同理，限定插入和刪除的線性表的鏈接存儲(chǔ)
順序棧插入刪除算法
·自己構(gòu)造了一個(gè)數(shù)組，通過(guò)Top指針來(lái)插入和刪除這個(gè)數(shù)組內(nèi)的元素
順序隊(duì)列插入刪除算法
·這個(gè)的就是2個(gè)指針的移動(dòng)，實(shí)現(xiàn)自己的那個(gè)數(shù)組的元素插入和刪除
鏈接棧插入刪除算法(自己的擴(kuò)充)
·我覺(jué)得應(yīng)該Top指針和first指針一樣，并在基礎(chǔ)上改變相當(dāng)于單向鏈表的在一開始插入和刪除，可實(shí)現(xiàn)要求
鏈接隊(duì)列插入刪除算法(自己的擴(kuò)充)
·同上，一個(gè)放在鏈表最后，一個(gè)放在最前面，進(jìn)來(lái)在前面插入，出去在后面刪除
樹
·有根樹的簡(jiǎn)稱，必須含有根，不能為空
樹根
·有根樹的一個(gè)定義，就是不存在另外一個(gè)到這個(gè)點(diǎn)的邊的存在，其中關(guān)于其余的點(diǎn)，只存在一個(gè)點(diǎn)也就是雙親可以存在到該點(diǎn)的邊
子樹
·有根樹的另外一個(gè)定義，分成了很多個(gè)除根結(jié)點(diǎn)外的互不相交的集合，這些集合也就是子樹
二叉樹
·二叉樹是另外一種樹形結(jié)構(gòu)，可以為空，由一個(gè)根和互不相交的2顆二叉樹構(gòu)成(遞歸定義)
左子樹
·靠左的那顆二叉樹
右子樹
·靠右的那顆二叉樹
雙親結(jié)點(diǎn)
·A點(diǎn)的雙親結(jié)點(diǎn)是樹中唯一存在
孩子結(jié)點(diǎn)
·b點(diǎn)的A
兄弟結(jié)點(diǎn)
·有同一個(gè)b點(diǎn)的點(diǎn)
分支結(jié)點(diǎn)
·度不是0
終端結(jié)點(diǎn)
·度為0
樹葉
·度為0
結(jié)點(diǎn)的度
·兒子的數(shù)量
樹的度
·結(jié)點(diǎn)中最大的那個(gè)度
結(jié)點(diǎn)的層
·即深度
森林
· 由若干顆樹組成的集合
森林與二叉樹的轉(zhuǎn)換
·左邊是兒子，右邊是兄弟，森林到二叉樹，第一顆樹的根是根，第二顆樹的根相當(dāng)于它的兄弟
樹的高度
·就是最后那一層的結(jié)點(diǎn)的層吧??
樹的雙親數(shù)組存儲(chǔ)表示
·這種方法方便尋找子結(jié)點(diǎn)的雙親結(jié)點(diǎn)
·就是地址值，雙親的地址值，元素值
樹的二叉鏈表存儲(chǔ)表示
·左孩子，右兄弟，中間元素值
滿二叉樹
·滿二叉樹2的n次方-1個(gè)結(jié)點(diǎn)
完全二叉樹
·從0開始存儲(chǔ)結(jié)點(diǎn)，結(jié)點(diǎn)為i的二叉樹的左子樹是2i + 1
·因此要求最小一層靠左，中間不能斷，即一直滿足上面的條件
二叉樹的順序存儲(chǔ)表示
·順序，按照邏輯位置來(lái)，就比如層次遍歷，形成一個(gè)數(shù)組
二叉樹的二叉鏈表存儲(chǔ)表示
·左子樹 元素值 右子樹 2個(gè)域指向不同的字段，一個(gè)字段
樹的前序遍歷規(guī)則
·先訪問(wèn)根，在訪問(wèn)根的子樹
樹的后序遍歷規(guī)則
·訪問(wèn)子樹后，再訪問(wèn)根
樹和二叉樹的層次遍歷規(guī)則
·以隊(duì)列來(lái)理解，當(dāng)爸爸出隊(duì)的時(shí)候，兒子們就可以進(jìn)來(lái)了，這樣就會(huì)是層次的
二叉樹的前序遍歷規(guī)則
·根 左 右
二叉樹的中序遍歷規(guī)則
·左 根 右
二叉樹的后序遍歷規(guī)則
·左 右 根
二叉樹結(jié)點(diǎn)的前序序列
·前序遍歷得到的
二叉樹結(jié)點(diǎn)的中序序列
·中序遍歷得到的
二叉樹結(jié)點(diǎn)的后序序列
·后序遍歷得到的
二叉樹的遞歸遍歷算法
·采用2個(gè)函數(shù)，第一個(gè)函數(shù)通過(guò)樹開始訪問(wèn)根結(jié)點(diǎn)，并且開始遍歷的操作左右子樹，就像實(shí)際遍歷的過(guò)程中的思路上是一樣的。
二叉樹的帶權(quán)路徑長(zhǎng)度
·葉子的值為權(quán)，所有葉子的權(quán)和邊數(shù)目的積的和就是二叉樹的帶權(quán)路徑長(zhǎng)度
最優(yōu)二叉樹
·對(duì)于相同的權(quán)值葉子結(jié)點(diǎn)，得到最小的帶權(quán)路徑長(zhǎng)度
哈夫曼樹
·哈夫曼算法構(gòu)造而成的二叉樹
哈夫曼樹的構(gòu)造過(guò)程
·依次在葉子的權(quán)值中取2個(gè)最小的權(quán)值相加(形成樹)，代回，接著操作
哈夫曼編碼
·經(jīng)過(guò)的雙親到左子樹的邊為0，到右子樹的邊為1，這樣每個(gè)葉子就有一系列的編碼
有向圖
·邊是不是有方向的
無(wú)向圖
·邊是沒(méi)方向的
完全圖
·每2個(gè)不同的點(diǎn)都有路徑存在
頂點(diǎn)
·就是點(diǎn)
相鄰頂點(diǎn)
·有存在邊的，有向圖只有一條路徑也算是相鄰頂點(diǎn)
與頂點(diǎn)相關(guān)聯(lián)的邊
·相鄰頂點(diǎn)的那一條邊
頂點(diǎn)的度
·相關(guān)聯(lián)邊的數(shù)目
頂點(diǎn)的出度
·有向圖的特有，即以該點(diǎn)為出發(fā)點(diǎn)的邊數(shù)目
頂點(diǎn)的入度
·有向圖的特有，即以該點(diǎn)為終點(diǎn)的邊數(shù)目
子圖
·點(diǎn)和邊都是圖的集合中的一部分
路徑
·2個(gè)點(diǎn)的路徑是經(jīng)歷的邊
路徑長(zhǎng)度
·經(jīng)過(guò)邊的數(shù)目
回路
·初始點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑
簡(jiǎn)單回路
·個(gè)人認(rèn)為和回來(lái)概念沖突
簡(jiǎn)單路徑
·路徑只有初始點(diǎn)和終點(diǎn)可以相同的路徑
連通圖
·無(wú)向圖每2個(gè)點(diǎn)之間都有路徑可以到達(dá)
連通分量
·無(wú)向圖含有的點(diǎn)的集合中部分點(diǎn)，這些點(diǎn)可以通過(guò)邊的集合的邊構(gòu)成連通圖，這個(gè)連通圖就是連通分量
強(qiáng)連通圖
·有向圖每2個(gè)點(diǎn)之間都有路徑可以到達(dá)
強(qiáng)連通分量
·有向圖含有的點(diǎn)的集合中部分點(diǎn)，這些點(diǎn)可以通過(guò)邊的集合的邊構(gòu)成強(qiáng)連通圖，這個(gè)連通圖就是強(qiáng)連通分量
有向圖的根(重要)
·到每一個(gè)點(diǎn)都有路徑可以到達(dá)
網(wǎng)絡(luò)
·無(wú)向圖的邊用權(quán)值表示，有向圖邊沒(méi)有權(quán)值
鄰接矩陣
·沒(méi)權(quán)值時(shí)，無(wú)向圖一條邊相當(dāng)于有向圖的一來(lái)一往的兩條邊
·有權(quán)值時(shí)，矩陣中是用0，∞，權(quán)值表示 僅僅包括無(wú)向圖
鄰接表(只保存出邊的鄰接表)
·第一排時(shí)放出發(fā)點(diǎn)的
·從第二排開始，一個(gè)字段，一個(gè)域，字段時(shí)終點(diǎn)的值，域指向這一排的下一個(gè)結(jié)點(diǎn)
圖的深度遍歷規(guī)則
·隨機(jī)開始一個(gè)鄰接結(jié)點(diǎn)進(jìn)行訪問(wèn)
圖的廣度遍歷規(guī)則
·相當(dāng)于層次遍歷，先把開始訪問(wèn)的鄰接結(jié)點(diǎn)都訪問(wèn)完畢
圖的深度遍歷算法
·一個(gè)判斷數(shù)組，來(lái)判斷這個(gè)元素是否已經(jīng)訪問(wèn)，用鄰接表的表示來(lái)尋找下個(gè)點(diǎn)，見(jiàn)其方法，這個(gè)是直接下一個(gè)沒(méi)有訪問(wèn)過(guò)的鄰接點(diǎn)就可以
圖的廣度遍歷算法
·一個(gè)判斷數(shù)組，來(lái)判斷這個(gè)元素是否已經(jīng)訪問(wèn)，用鄰接表的表示來(lái)尋找下個(gè)點(diǎn)，見(jiàn)其方法，這個(gè)還要判斷是不是當(dāng)前這個(gè)結(jié)點(diǎn)的都訪問(wèn)完畢，就需要加上一個(gè)while循環(huán)，相當(dāng)于形成了遞歸
生成樹
·一個(gè)連通圖的極小連通子圖
生成樹林
·非連通圖生成的連通變量生成的
深度優(yōu)先生成樹
·使用深度遍歷算法的圖的生成樹
廣度優(yōu)先生成樹
·使用廣度遍歷算法圖生成的生成樹
最小生成樹
·權(quán)值最小的極小連通子圖
普里姆方法
·每一次沒(méi)有連通的結(jié)點(diǎn)的，找最小的權(quán)值的邊
迪杰斯特拉方法
·單源最短路徑的方法
·確定每一個(gè)最短路徑
·先找到了一個(gè)最短路徑，看通過(guò)這個(gè)路徑，可不可以讓其他路徑變短，然后修改，確定一個(gè)最短路徑
·再找到另外一個(gè)最短路徑，除開始的那個(gè)最短路徑，找有沒(méi)有到其他路的最短路徑
拓?fù)渑判?
·先把入度為0的結(jié)點(diǎn)排出，然后刪除結(jié)點(diǎn)，在排出入度為0的結(jié)點(diǎn)
拓?fù)湫蛄?
·如上
拓?fù)渑判蚍椒?
·如上
拓?fù)渑判蛩惴?
·這里是用的鄰接表，可以根據(jù)判斷這個(gè)頂點(diǎn)的入度(通過(guò)鄰接表遍歷每一個(gè)結(jié)點(diǎn)，看有沒(méi)有以這個(gè)點(diǎn)結(jié)尾的結(jié)點(diǎn)，有一個(gè)入度加一)，放入數(shù)組(數(shù)組是自己定義的)中，讓出入度是0的，輸出這個(gè)結(jié)點(diǎn)，通過(guò)鄰接表把這個(gè)點(diǎn)的鄰接點(diǎn)的入度減一，這樣就達(dá)到刪除的結(jié)點(diǎn)的目的
AOV網(wǎng)
·用頂點(diǎn)代表事件
關(guān)鍵路徑
·在AOE網(wǎng)中開始點(diǎn)的最終點(diǎn)的的最長(zhǎng)路徑
關(guān)鍵活動(dòng)
·關(guān)鍵活動(dòng)是在關(guān)鍵路徑上，延期就會(huì)對(duì)整個(gè)工程有影響，所以應(yīng)該是關(guān)鍵路徑上的
AOE網(wǎng)
·用邊表示事件，邊的權(quán)值就是事件完成要的時(shí)間
求關(guān)鍵路徑的方法
·求最早開始時(shí)間和最晚開始時(shí)間
·最早開始時(shí)間和最晚開始時(shí)間
·相同的就是關(guān)鍵活動(dòng)
·關(guān)鍵活動(dòng)組成了關(guān)鍵路徑
·最早開始時(shí)間，求最長(zhǎng)的路徑，因?yàn)楸仨殱M足拓?fù)湫蛄兄械纳弦粋€(gè)相鄰接的事件完成才可以開始當(dāng)前事件，因而是最長(zhǎng)的路徑
·最晚開始時(shí)間就是在已經(jīng)知道最早開始時(shí)間的基礎(chǔ)上，通過(guò)去減去到終點(diǎn)的路徑中最小的那一條。這就是最晚可以開始的時(shí)間，再晚就要延期了
關(guān)鍵字
·可以用來(lái)判斷數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)
主關(guān)鍵字
·可唯一判斷
次關(guān)鍵字
·不可唯一判斷
平均查找長(zhǎng)度
·即進(jìn)行一次查找平均要用的查找次數(shù)
順序查找算法
·就是從0到n-1查找
·因此可以是順序存儲(chǔ)和鏈接存儲(chǔ)都可以訪問(wèn)到
·而其中的有序和無(wú)序則要涉及到要不要加上哨兵元素
順序查找的平均查找長(zhǎng)度
· (n+1)/2 吧
折半查找方法
·找中間的元素，再去訪問(wèn)左還是右
·因此，這個(gè)是要有序的，對(duì)于鏈接存儲(chǔ)，因?yàn)殒溄右箜樞虼鎯?chǔ)的，因此無(wú)法找到中間開始
折半查找算法
·因?yàn)橹荒茉陧樞虼鎯?chǔ)的有序表，設(shè)置3個(gè)整數(shù)值 a是第一個(gè)元素的數(shù)組地址 b是最后一個(gè)元素的地址
c = (a+b)/2也就是開始折半的那個(gè)元素
·在判斷小于R【c】的時(shí)候，b = c -1
·大于的時(shí)候，a = c + 1
·再進(jìn)行折半，以此類推
折半查找的平均查找長(zhǎng)度
·具體的問(wèn)題的時(shí)候 m個(gè)元素，求每個(gè)要的次數(shù)，相加的和除以m是平均長(zhǎng)度
·當(dāng)一般化的時(shí)候，O(log2`n) 失敗是log2`n向上取整或者再加一(會(huì)因?yàn)閚的奇偶)
·搜索成功不超過(guò)搜索失敗的次數(shù)，一般化只有O(log2`n)這個(gè)數(shù)量級(jí)
二叉排序樹
·在用折半搜索的方法得時(shí)候，相類似的那一棵樹，就是中序是一個(gè)遞增的
二叉排序樹查找方法
·先比較根結(jié)點(diǎn)來(lái)判斷要進(jìn)入左子樹還是右子樹(較大和較小的進(jìn)入右和左，等于則成功)
·進(jìn)入子樹后循環(huán)這個(gè)概念
二叉排序樹插入方法
·相類似的，先查找一波，沒(méi)有再插入
·插入的時(shí)候，根據(jù)值的大小，先選擇進(jìn)入左子樹還是右子樹
·一直到某一次的左子樹或者右子樹出現(xiàn)了null，表述就可以插入那個(gè)點(diǎn)
二叉排序樹刪除方法
·沒(méi)有兒子的時(shí)候，直接殺了
·有一個(gè)兒子，殺了，讓兒子代替
·有2個(gè)孩子，殺了，中序遍歷后一個(gè)的那個(gè)點(diǎn)代替，那個(gè)點(diǎn)相當(dāng)于被殺了，開始看它有沒(méi)有孩子，再依次執(zhí)行這些操作
二叉排序樹查找算法
·算法嚴(yán)格意義上按照遞歸的方法，遍歷每一個(gè)結(jié)點(diǎn)
二叉排序樹插入算法
·先查找
·查找后，實(shí)現(xiàn)方法的遞歸的操作
二叉排序樹刪除算法
·如上方法
平衡二叉排序樹
·平衡因子絕對(duì)值不能大于二的二叉搜索樹
平衡因子
·左子樹的深度減去右子樹的深度
平衡二叉排序樹插入方法
·插入，和二叉搜索樹一樣
·重組，插入的時(shí)候發(fā)現(xiàn)平衡因子的絕對(duì)值大于二要進(jìn)行重組，防止大于2
·重組的方法，=。 =
樹型查找的平均查找長(zhǎng)度
·和折半方法的一樣
散列表
·是一個(gè)通過(guò)關(guān)鍵字
·用一個(gè)數(shù)組ht[m]來(lái)存儲(chǔ)散列函數(shù)得到的地址，m為散列表的長(zhǎng)度
·因此這種存儲(chǔ)也叫散列存儲(chǔ)
散列函數(shù)
·散列函數(shù)是值域0到m-1，自變量是關(guān)鍵字的函數(shù)
散列沖突
·一個(gè)地址有2個(gè)關(guān)鍵字可以得到，這就是產(chǎn)生了沖突
散列地址
·關(guān)鍵字為k的元素的散列地址是ht[k]
處理沖突的線性探測(cè)法
·雙散列函數(shù)的次散列函數(shù)為1的情況
雙散列函數(shù)法
·定義了2個(gè)散列函數(shù)，主散列函數(shù)是對(duì)的，而次散列函數(shù)相當(dāng)于發(fā)生沖突的時(shí)候，邁過(guò)的步子大小，這樣可以減少線性探測(cè)法連續(xù)一片需要花費(fèi)太多的時(shí)間的問(wèn)題
拉鏈法
·每一個(gè)ht數(shù)組的元素都還有一個(gè)數(shù)組，里面存放著地址相同的散列表的元素
散列表的插入方法
·先查找
·對(duì)于查找，這個(gè)時(shí)候就要用考慮到散列沖突
·尋找過(guò)程中(見(jiàn)下)，會(huì)通過(guò)解決散列沖突的方法，已經(jīng)把pos(第一個(gè)空的位置)的值改變了，因此插入只要ht[pos] = x就可以實(shí)現(xiàn)了插入，至于表滿的情況和已經(jīng)找到的情況可以通過(guò)ResultCode的返回值發(fā)現(xiàn)
散列表的查找方法
·噗，查找過(guò)程中，先來(lái)判斷是不是已經(jīng)以及存在，存在就反悔成功，不存在則進(jìn)去，開始找空的位置，如果應(yīng)該放的位置被占了，這個(gè)時(shí)候就開始散列沖突解決，這樣將找到的第一個(gè)空的地址，然后標(biāo)記(就是給pos賦值)，如果pos為-1，就表示表滿了，返回Overflow，否則返回Notpresent
散列查找
·O(1)
散列表的負(fù)載因子
·就是裝載密度，實(shí)際存儲(chǔ)結(jié)點(diǎn)數(shù)/空間數(shù)
排序碼
·通常是次關(guān)鍵字
·用于排序
直接插入排序方法
·開始第一個(gè)元素一個(gè)組，后來(lái)慢慢一個(gè)一個(gè)地加，加的過(guò)程排序，比較，較小則往前比較，較大則就不動(dòng)了，停下來(lái)。
·最怕的是反順序，這樣就要一直移動(dòng)
簡(jiǎn)單選擇排序算法
·不管怎么樣，都有O(n`2)的比較
·開始的所有元素一個(gè)組，然后從里面剔除最小的元素出來(lái)，是一個(gè)從n到1的過(guò)程，上面是從1到n
·好像沒(méi)什么影響，但是不管怎么樣，都有比較
堆的定義
·一種優(yōu)先權(quán)隊(duì)列，堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu),每個(gè)結(jié)點(diǎn)都有一個(gè)值.通常我們所說(shuō)的堆的數(shù)據(jù)結(jié)構(gòu),是指二叉堆.堆的特點(diǎn)是根結(jié)點(diǎn)的值最小(或最大),且根結(jié)點(diǎn)的兩個(gè)子樹也是一個(gè)堆.
快速排序算法
·最壞的時(shí)候就會(huì)變成冒泡排序
·先挑一個(gè)元素出來(lái)，大于它的放右邊，小于它的放左邊
·這樣先固定好一個(gè)位置，接著拿元素出來(lái)進(jìn)行這個(gè)操作
·它是速度最快的，但是存儲(chǔ)空間是O(lon2`n)，遞歸用的
·最壞的就是有順序，順序和逆順序都不好
排序的穩(wěn)定性
·就是排序碼相同的元素相同的，排序以后，相對(duì)位置不變的排序
·判斷的方法，是不是針對(duì)整個(gè)數(shù)組進(jìn)行操作了
·這里是冒泡排序、歸并排序、直接插入排序是穩(wěn)定的
內(nèi)排序
·是在內(nèi)存中進(jìn)行的排序，這里的六個(gè)都是內(nèi)排序
冒泡排序
·不停的比較2個(gè)元素，大的向后移動(dòng)，小的向前移動(dòng)，一直到?jīng)]有元素的移動(dòng)才算結(jié)束
·注意：排序碼較大的也可能往前移動(dòng)，因?yàn)榕龅搅烁蟮?
·最好是順序，最壞是逆順序
堆排序
·堆排序是每次構(gòu)造最大堆，然后把最大的，也就是堆頂?shù)姆诺阶詈?，其余的重新?gòu)造最大堆，再進(jìn)行交換，再構(gòu)造，這樣就可以得到一個(gè)序列
·最好堆序列，可以少一點(diǎn)移動(dòng)元素
·
歸并排序
·先是每一個(gè)元素一個(gè)小組，然后一個(gè)一個(gè)地合并，在合并的過(guò)程中，自己構(gòu)造一個(gè)數(shù)組，在構(gòu)造過(guò)程中，就比較，用自己的數(shù)組幫忙排好序，然后再?gòu)倪@里面放回原來(lái)的數(shù)組中，完成了合并后排序
·因此最好是順序，這樣可以少一點(diǎn)比較，但是移動(dòng)都是要的，影響不大
·要O(n)的存儲(chǔ)空間，就是自己的輔助數(shù)組
算法
·冒泡排序
·說(shuō)一個(gè)實(shí)現(xiàn)的方法：自己定義一個(gè)元素n，初始值為0，用來(lái)記錄元素移動(dòng)的次數(shù)，每一次比較開始(比較整個(gè)序列每?jī)蓚€(gè)相鄰的元素的值)，賦值n為0，然后一次比較完成后，看n的值，如果什么時(shí)候n為0，表面了冒泡排序完成
·堆排序
·主要是構(gòu)造堆的那個(gè)算法，每一次交換最大值和最后一個(gè)元素交換后，都重新構(gòu)造最大堆，通過(guò)n(序列的元
素個(gè)數(shù))—的方法，剔除已經(jīng)選出來(lái)的最大值，這樣，就可以一直進(jìn)行下去直到n為1
下載文檔
