數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)總結(jié)-文庫(kù)吧在線文庫(kù)
【正文】 稱為該串的子串，包含子串的串就稱為主串。它的優(yōu)點(diǎn)是涉及串長(zhǎng)的操作速度快，因?yàn)樗淖畲箝L(zhǎng)度是不變的。第四章棧與隊(duì)列棧的邏輯結(jié)構(gòu)和我們先前學(xué)過的線性表相同，如果它是非空的，則有且只有一個(gè)開始結(jié)點(diǎn)，有且只能有一個(gè)終端結(jié)點(diǎn)，其它的結(jié)點(diǎn)前后所相鄰的也只能是一個(gè)結(jié)點(diǎn)(直接前趨和直接后繼),但是棧的運(yùn)算規(guī)則與線性表相比有更多的限制，棧(Stack)是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除這一端為棧頂，另一端稱為棧底。通常我們應(yīng)用的大都是循環(huán)隊(duì)列。第五章二叉樹與樹樹的邏輯結(jié)構(gòu)特征是：樹中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼(孩子)結(jié)點(diǎn)，但至多只能有一個(gè)直接前趨(雙親)結(jié)點(diǎn)。根據(jù)訪問結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。其原因是查找前序前趨和后序后繼結(jié)點(diǎn)常常要用到給定結(jié)點(diǎn)的雙親結(jié)點(diǎn)才能找到，而線索二叉樹中的結(jié)點(diǎn)沒有指向其雙親結(jié)點(diǎn)的指針，所以線索對(duì)于這兩種序列的結(jié)點(diǎn)查找并非有效。孩子兄弟鏈表表示法（就是在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域）這種存儲(chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是，它和二叉樹的二叉鏈表表示完全一樣，因此可利用二叉樹的算法來實(shí)現(xiàn)對(duì)樹的操作。因此，一般情況需建立一個(gè)函數(shù)關(guān)系，以H(key)作為關(guān)鍵字為key 的錄在表中的位置，通常稱這個(gè)函數(shù)H(key)為哈希函數(shù)。哈希函數(shù)，指的是對(duì)于集合中的任意一個(gè)關(guān)鍵字，經(jīng)哈希函數(shù)撚179。(2) 二叉排序樹的查找算法若二叉排序樹為空，則查找不成功；否則1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找；3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。第八章排序插入排序思想：假設(shè)在排序過程中，記錄序列R[1..n]的狀態(tài)為：則一趟直接插入排序的基本思想為：將記錄R[i]插入到有序子序列R[1..i1]中，使記錄的有序序列從R[1..i1]變?yōu)镽[1..i]。錄的操作，必須改變排序過程中采用的存儲(chǔ)結(jié)構(gòu)?？焖倥判颍?）起泡排序假設(shè)在排序過程中，記錄序列R[1..n]的狀態(tài)為：思想：借助對(duì)無序序列中的記錄進(jìn)行摻187。將堆頂記錄和第n1 個(gè)記錄交換，如此反復(fù)直至排序結(jié)束。完全圖：若無向圖中每?jī)蓚€(gè)頂點(diǎn)之間都存在著一條邊，即有n(n1)/2 條邊，稱完全無向圖；若有向圖中每?jī)蓚€(gè)頂點(diǎn)之間都存在著方向相反的兩條邊，即有n(n1)條邊，稱完全有向圖。如果它多于n1 條邊，則一定有環(huán)。廣度優(yōu)先搜索：從圖中的某個(gè)頂點(diǎn)V0 出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0 的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0 有路徑相通的頂點(diǎn)都被訪問到。主要進(jìn)行拓?fù)渑判蚝完P(guān)鍵路徑的操作。拓?fù)渑判虻乃惴ǎ哼x一個(gè)入度為0 的頂點(diǎn)輸出，并將其所有后繼頂點(diǎn)的入度?1，重復(fù)這兩步直至輸出所有頂點(diǎn)，或找不到入度為0 的頂點(diǎn)為止，為便于查找入度為0 的頂點(diǎn)，算法中利用頂點(diǎn)的入度域建立一個(gè)存放入度為0 的頂點(diǎn)的棧。AOE 網(wǎng)（Activity On Edge Network）：是一個(gè)帶權(quán)的有向無環(huán)圖，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間，可以用來估算工程的完成時(shí)間。（2）Kruskal 算法：Kruskal 算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個(gè)只含n 個(gè)頂點(diǎn)、而邊集為空的子圖，把子圖中各個(gè)頂點(diǎn)看成各棵樹上的根結(jié)點(diǎn)，之后，從網(wǎng)的邊集E 中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹，反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。鄰接表表示法類似于樹的孩子鏈表表示法。連通分量：無向圖的極大連通子圖；任何連通圖的連通分量只有一個(gè)，即其本身；非連通圖有多個(gè)連通分量。歸并排序思想：將兩個(gè)或兩個(gè)以上的有序子序列?歸并?為一個(gè)有序序列，是一種穩(wěn)定的排序方法。選擇排序（1）簡(jiǎn)單選擇排序思想：假設(shè)排序過程中，待排記錄序列的狀態(tài)為：并且有序序列中所有記錄的關(guān)鍵字均小于無序序列中記錄的關(guān)鍵字，則第i 趟簡(jiǎn)單選擇排序是，從無序序列R[i..n]的ni+1 記錄中選出關(guān)鍵字最小的記錄加入有序序列。所謂?宏觀?調(diào)整，指的是?跳躍式數(shù)196。（2）折半插入排序：因?yàn)镽[1..i1]是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)撛218。二叉平衡樹這是另一種形式的二叉查找樹，其特點(diǎn)為左、右子樹深度之差的絕對(duì)值不大于1，稱有這種特性的二叉樹為平衡樹。線性探測(cè)容易產(chǎn)生二次聚集，鏈地址肯定不會(huì)產(chǎn)生二次聚集。因此，在設(shè)計(jì)哈希函數(shù)時(shí)，一方面要考慮選擇一個(gè)摵脭?shù)墓：瘮?shù)。權(quán)就是某結(jié)點(diǎn)被賦予的一個(gè)實(shí)數(shù)（這在實(shí)際應(yīng)用中是有某種意義的，比如使用率，數(shù)值等）。二叉變樹：左孩右右連雙親，去掉原來右孩線。二叉樹線索化的目的及其實(shí)質(zhì)：利用線索化后
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1