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