數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)整理

1、數(shù)據(jù)數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)（數(shù)值、字符等）的集合。數(shù)據(jù)元素（數(shù)據(jù)成員）數(shù)據(jù)元素（數(shù)據(jù)成員）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象具有相同性質(zhì)的數(shù)據(jù)元素（數(shù)據(jù)成員）的集合數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為Data_Structure=DR其中，D是某一數(shù)據(jù)對(duì)象，R是該對(duì)象中所

2、有數(shù)據(jù)成員之間的關(guān)系的有限集合。數(shù)據(jù)類型數(shù)據(jù)類型是指一種類型，以及定義在這個(gè)值集合上的一組操作的總稱。判斷一個(gè)算法的優(yōu)劣主要標(biāo)準(zhǔn)判斷一個(gè)算法的優(yōu)劣主要標(biāo)準(zhǔn)：正確性、可使用性、可讀性、效率、健壯性、簡(jiǎn)單性。算法效率的衡量方法算法效率的衡量方法：后期測(cè)試，事前估計(jì)算法分析算法分析是算法的漸進(jìn)分析簡(jiǎn)稱數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個(gè)方面(層次):邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)成員之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)成員的集合和定義在此集

3、合上的若干關(guān)系來表示物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱“存儲(chǔ)結(jié)構(gòu)”線性表的定義線性表的定義：n（?0）個(gè)表項(xiàng)的有限序列L=（a1a2…an）ai是表項(xiàng)，n是表長(zhǎng)度。第一個(gè)表項(xiàng)是表頭，最后一個(gè)是表尾。線性表的特點(diǎn)線性表的特點(diǎn)：表中元素的數(shù)據(jù)類型相同；線性表中，結(jié)點(diǎn)和結(jié)點(diǎn)間的關(guān)系是一對(duì)一的，有序表和無(wú)序表線性表的存儲(chǔ)方式。一，順序存儲(chǔ)方式，二，鏈表存儲(chǔ)方式。順序表的存儲(chǔ)表示有順序表的存儲(chǔ)表示有2種方式種方式：靜態(tài)方式和動(dòng)態(tài)方式

4、。順序表的定義是順序表的定義是：把線性表中的所有表項(xiàng)按照其邏輯順序依次存儲(chǔ)到從計(jì)算機(jī)存儲(chǔ)中指定存儲(chǔ)位置開始的一塊連續(xù)的存儲(chǔ)空間中。順序表的特點(diǎn)順序表的特點(diǎn)：用地址連續(xù)的一塊存儲(chǔ)空間順序存放各表項(xiàng)，各表項(xiàng)的邏輯順序與物理順序一致，對(duì)各個(gè)表項(xiàng)可以順序訪問，也可以隨機(jī)訪問。單鏈表單鏈表是一種最簡(jiǎn)單的鏈表表示，也叫線性鏈表線性鏈表，用她來表示線性表時(shí)，用指針表示結(jié)點(diǎn)間的邏輯關(guān)系。特點(diǎn)：是長(zhǎng)度可以很方便地進(jìn)行擴(kuò)充。連續(xù)存儲(chǔ)方式（順序表）特點(diǎn)連續(xù)存

5、儲(chǔ)方式（順序表）特點(diǎn)：存儲(chǔ)利用率高，存取速度快缺點(diǎn)：插入、刪除等操作時(shí)需要移動(dòng)大量數(shù)據(jù)：鏈?zhǔn)酱鎯?chǔ)方式（鏈表）鏈?zhǔn)酱鎯?chǔ)方式（鏈表）特點(diǎn)特點(diǎn)：適應(yīng)表的動(dòng)態(tài)增長(zhǎng)和刪除。缺點(diǎn)：需要額外的指針存儲(chǔ)空間單鏈表的類定義單鏈表的類定義：多個(gè)類表達(dá)一個(gè)概念(單鏈表)。分為：鏈表結(jié)點(diǎn)(ListNode)類，鏈表(List)類。循環(huán)鏈表的概念循環(huán)鏈表的概念：是另一種形式的表示線性表的鏈表，它的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表相同，與單鏈表不同的是鏈表中表尾結(jié)點(diǎn)的LINK域中

6、不是NULL，而是存放了一個(gè)指向鏈表開始結(jié)點(diǎn)的指針，這樣，只要知道表中任何一個(gè)結(jié)點(diǎn)的地址，就能遍歷表中其他任何一結(jié)點(diǎn)。雙向鏈表的概念雙向鏈表的概念：在雙向鏈表的沒餓結(jié)點(diǎn)中應(yīng)有兩個(gè)鏈接指針作為它的數(shù)據(jù)成員：1LINK指示它的前驅(qū)結(jié)點(diǎn)，RLINK指示它的后繼結(jié)點(diǎn)，因此，雙向鏈表的每個(gè)結(jié)點(diǎn)至少有3個(gè)域：1LINK(前驅(qū)指針)DADA（數(shù)據(jù)）RLINK（后繼指針）。棧：定義為只允許在表的末端進(jìn)行插入和刪除的線性表。特點(diǎn)是：后進(jìn)先出。遞歸的定義遞

7、歸的定義：若一個(gè)對(duì)象部分地包含它自己，或用它自己給自己定義則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過程直接地或間接地調(diào)用自己則稱這個(gè)過程是遞歸的過程。以下三種情況常常用到遞歸方法一。定義是遞歸的二。數(shù)據(jù)結(jié)構(gòu)是遞歸的三問題的解法是遞歸的。隊(duì)列隊(duì)列：隊(duì)列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊(duì)頭，允許插入的一端叫做隊(duì)尾。特性：先進(jìn)先出。優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列：是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素。

8、多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組的特點(diǎn)是每一個(gè)數(shù)據(jù)元素可以有多個(gè)直接前驅(qū)和多個(gè)直接后繼。數(shù)組元素的下標(biāo)一般具有固定的下界和上界，因此它比其他復(fù)雜的非線性結(jié)構(gòu)簡(jiǎn)單。字符串字符串是n(?0)個(gè)字符的有限序列，記作S:“c1c2c3…cn”其中，S是串名字c1c2c3…cn”是串值ci是串中字符n是串的長(zhǎng)度，n=0稱為空串。廣義表廣義表是n(≥0)個(gè)表元素組成的有限序列，記作LS(a1a2a3…an)，LS

9、是表名，ai是表元素，可以是表（稱為子表），可以是數(shù)據(jù)元素（稱為原子）。n為表的長(zhǎng)度。n=0的廣義表為空表。n0時(shí)，表的第一個(gè)表元素稱為廣義表的表頭（head），除此之外，其它表元素組成的表稱為廣義表的表尾（tail有根樹有根樹：一棵有根樹T，簡(jiǎn)稱為樹，它是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，T稱為空樹；否則，T是非空樹，記作T=空集n=0上所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。4左子樹和右子樹也是二叉搜索樹。二叉搜索樹為二叉排序

10、樹二叉搜索樹為二叉排序樹如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹在二叉搜索樹上進(jìn)行搜索在二叉搜索樹上進(jìn)行搜索，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為x的元素，搜索過程從根結(jié)點(diǎn)開始。如果根指針為NULL，則搜索不成功；否則用給定值x與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：若給定值等于根結(jié)點(diǎn)關(guān)鍵碼，則搜索成

11、功，返回搜索成功信息并報(bào)告搜索到結(jié)點(diǎn)地址。若給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹；否則。遞歸搜索根結(jié)點(diǎn)的右子二叉搜索樹的插入算法：二叉搜索樹的插入算法：為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如果搜索成功，說明樹中已經(jīng)有這個(gè)元素，不再插入；如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。圖定

12、義圖定義：圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph＝(VE)其中V=x|x?某個(gè)數(shù)據(jù)對(duì)象是頂點(diǎn)的有窮非空集合；E=(xy)|xy?V或E=|xy?V&&Path(xy)，是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。Path(xy)表示從x到y(tǒng)的一條單向通路它是有方向的。有向圖與無(wú)向圖有向圖與無(wú)向圖：在有向圖中，頂點(diǎn)對(duì)是有序的。在無(wú)向圖中，頂點(diǎn)對(duì)(xy)是無(wú)序的。完全圖完全圖：若有n個(gè)頂點(diǎn)的無(wú)

13、向圖有n(n1)2條邊則此圖為完全無(wú)向圖。有n個(gè)頂點(diǎn)的有向圖有n(n1)條邊則此圖為完全有向圖在圖的鄰接矩陣鄰接矩陣表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。鄰接表鄰接表是鄰接矩陣的改進(jìn)形式。為此需要把鄰接矩陣的各行分別組織為一個(gè)單鏈表。在鄰接表中，同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊（邊結(jié)點(diǎn)），結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo)dest和指針link。對(duì)于帶權(quán)圖，邊結(jié)點(diǎn)中還要保存該邊

14、的權(quán)值cost。頂點(diǎn)表的第i個(gè)頂點(diǎn)中保存該頂點(diǎn)的數(shù)據(jù)，以及它對(duì)應(yīng)邊鏈表的頭指針adj最短路徑問題最短路徑問題：如果從圖中某一頂點(diǎn)（稱為源點(diǎn)）另一頂點(diǎn)（稱為終點(diǎn)）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。排序排序：將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來。數(shù)據(jù)表數(shù)據(jù)表(datalist):它是待排序數(shù)據(jù)元素的有限集合。排序碼排序碼(key):通常數(shù)據(jù)元素有多個(gè)屬性域即多個(gè)數(shù)據(jù)成員組成其中有一個(gè)屬性域可