常用數(shù)據(jù)結(jié)構(gòu)及其存儲(chǔ)

常用數(shù)據(jù)結(jié)構(gòu)及其存儲(chǔ)第一頁，共二十七頁，2022年，8月28日[主要內(nèi)容]21.1算法21.2數(shù)據(jù)結(jié)構(gòu)的基本概念21.3線性表21.4棧與隊(duì)列21.5樹與二叉樹第二頁，共二十七頁，2022年，8月28日21.1算法

定義：是對(duì)特定問題求解步驟的一種描述?；蛘哒f，是為求解某問題的方法和步驟。

特征：有窮性確定性有效性零個(gè)或多個(gè)輸入一個(gè)或多個(gè)輸出第三頁，共二十七頁，2022年，8月28日例如：一元二次方程求根算法。鍵盤輸入系數(shù)送到a,b,c中start計(jì)算出兩個(gè)根放在x1、x2中顯示x1、x2中存放的數(shù)據(jù)end第四頁，共二十七頁，2022年，8月28日算法復(fù)雜度評(píng)價(jià)一個(gè)算法優(yōu)劣的主要標(biāo)準(zhǔn)是：算法的執(zhí)行效率與存儲(chǔ)需求

算法的效率：指的是時(shí)間復(fù)雜度（TimeComplexity）

存儲(chǔ)需求：指的是空間復(fù)雜度（SpaceComplexity）

一般情況下，算法中的基本操作重復(fù)操作執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間復(fù)雜度記做：T(n)=O(f(n))第五頁，共二十七頁，2022年，8月28日21.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù):

是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序加工處理的符號(hào)的集合。

數(shù)據(jù)元素:

是數(shù)據(jù)的基本元素，即數(shù)據(jù)集合中的個(gè)體。

數(shù)據(jù)項(xiàng):

具有獨(dú)立意義的最小數(shù)據(jù)單位。

數(shù)據(jù)對(duì)象:

具有相同特性的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。

數(shù)據(jù)結(jié)構(gòu):互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。

第六頁，共二十七頁，2022年，8月28日數(shù)據(jù)的邏輯結(jié)構(gòu)

集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀或網(wǎng)狀結(jié)構(gòu)第七頁，共二十七頁，2022年，8月28日數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)主要特點(diǎn)：所有元素所占的存儲(chǔ)空間是連續(xù)的；各個(gè)元素在存儲(chǔ)空間中是按邏輯順序依次存放的；元素可隨機(jī)存取，但插入、刪除運(yùn)算不便，會(huì)引起大量結(jié)點(diǎn)的移動(dòng)。第八頁，共二十七頁，2022年，8月28日二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)主要特點(diǎn)：存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)；各結(jié)點(diǎn)的存儲(chǔ)順序與元素之間的邏輯關(guān)系可以不一致，元素之間的邏輯關(guān)系由指針域來確定；插入、刪除操作靈活方便，不必移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中的指針值即可。

第九頁，共二十七頁，2022年，8月28日數(shù)據(jù)的運(yùn)算

檢索：在數(shù)據(jù)結(jié)構(gòu)里查找滿足一定條件的結(jié)點(diǎn)

插入：往數(shù)據(jù)結(jié)構(gòu)里增加新的結(jié)點(diǎn)

刪除：把指定的結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)里去掉

更新：修改指定結(jié)點(diǎn)的一個(gè)或多個(gè)域的值

排序：保持線性結(jié)構(gòu)的結(jié)點(diǎn)序列里結(jié)點(diǎn)數(shù)不變，將結(jié)點(diǎn)按某種指定的順序重新排列第十頁，共二十七頁，2022年，8月28日21.3線性表線性表是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有限序列。

（a1，a2，…，an）

順序表：指用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。

鏈表：用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。

棧和隊(duì)列：是對(duì)線性表的插入、刪除運(yùn)算可以發(fā)生的位置加以限制的兩種特殊的線性表。第十一頁，共二十七頁，2022年，8月28日順序表

各種高級(jí)語言里的一維數(shù)組就是用順序方式存儲(chǔ)的線性表，因此常用一維數(shù)組稱呼順序表。若順序表中結(jié)點(diǎn)個(gè)數(shù)為n，則：

插入一個(gè)結(jié)點(diǎn)平均需要移動(dòng)之結(jié)點(diǎn)個(gè)數(shù)為

n/2，算法的時(shí)間復(fù)雜度是O(n)；

刪除一個(gè)結(jié)點(diǎn)平均需移動(dòng)結(jié)點(diǎn)個(gè)數(shù)為

（n-1）/2，算法的時(shí)間復(fù)雜度是O(n)。第十二頁，共二十七頁，2022年，8月28日鏈表

線性鏈表（單鏈表）：刪除算法的時(shí)間復(fù)雜度為O(n)，其主要執(zhí)行時(shí)間是搜索刪除位置。

循環(huán)鏈表：指鏈表的最后一個(gè)結(jié)點(diǎn)的指針值指向第一個(gè)結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)（如下圖）。…結(jié)點(diǎn)1結(jié)點(diǎn)2結(jié)點(diǎn)n第十三頁，共二十七頁，2022年，8月28日21.4棧和隊(duì)列棧：是一種特殊的線性表，是限定僅在表尾進(jìn)行插入和刪除運(yùn)算的線性表，表尾稱為棧頂（top），表頭稱為棧底（bottom）。表中無元素即空棧。棧中有元素a1,a2,…,an，如下頁圖所示，稱a1為棧底元素。新元素進(jìn)棧要置于an之上，刪除或退棧先對(duì)an進(jìn)行，即“后進(jìn)先出”（LIFO）的操作原則;

棧的物理存儲(chǔ)可以用順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu);

棧的運(yùn)算還有取棧頂元素，檢查棧是否為空，清除等。第十四頁，共二十七頁，2022年，8月28日棧的插入和刪除ABACBABAFEBAATOPTOPTOPTOPTOPTOPan…a2a1進(jìn)棧出棧棧底棧結(jié)構(gòu)(3)(1)(2)(5)(4)(6)棧頂?shù)谑屙?，共二十七頁?022年，8月28日隊(duì)列隊(duì)列：是限定所有的插入都在表的一端進(jìn)行，所有的刪除都在表的另一端進(jìn)行的線性表。進(jìn)行刪除的一端叫隊(duì)頭，進(jìn)行插入的一端叫隊(duì)尾，如下頁圖所示。在隊(duì)列中，新元素總是加入到隊(duì)尾，每次刪除的總是對(duì)頭元素，即當(dāng)前“最老的”元素，這就是“先進(jìn)先出”（FIFO）的操作原則。隊(duì)列的物理存儲(chǔ)可以用：順序存儲(chǔ)結(jié)構(gòu)，也可用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。第十六頁，共二十七頁，2022年，8月28日隊(duì)列的示意圖出隊(duì)列

a1a2a3…an

入隊(duì)列

隊(duì)頭

隊(duì)尾第十七頁，共二十七頁，2022年，8月28日隊(duì)列的插入和刪除示例第十八頁，共二十七頁，2022年，8月28日21.5樹與二叉樹

樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)，樹和二叉樹是最常見的樹形結(jié)構(gòu)。

樹（Tree）:是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。若n=0，則稱為空樹；否則，有且僅有一個(gè)特定的結(jié)點(diǎn)被稱為根，當(dāng)n>1時(shí)，其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的子集T1，T2，…，Tm，每個(gè)子集又是一棵樹，稱作這個(gè)根的子樹（subtree）。

第十九頁，共二十七頁，2022年，8月28日樹形結(jié)構(gòu)的常用術(shù)語

結(jié)點(diǎn)的度（Degree）：一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)。

樹的度：樹中各結(jié)點(diǎn)的度的最大值。

樹葉（Leaf）：度為0的結(jié)點(diǎn)。

分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。

雙親（Parent）、子女（Child）：結(jié)點(diǎn)的各子樹的根稱作該結(jié)點(diǎn)的子女；相應(yīng)的該結(jié)點(diǎn)稱作其子女的雙親。

兄弟（Sibling）：具有相同雙親的結(jié)點(diǎn)互為兄弟。

結(jié)點(diǎn)的層數(shù)（Level）；樹的深度（Depth）森林（Forest）第二十頁，共二十七頁，2022年，8月28日二叉樹

二叉樹（BinaryTree）:是n（n≥0)個(gè)結(jié)點(diǎn)的有限集合，這個(gè)集合或者為空集（n=0），或者由一個(gè)根結(jié)點(diǎn)及兩棵不相交的、分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。二叉樹是樹的特殊情形。

二者的區(qū)別是：二叉樹為有序樹。第二十一頁，共二十七頁，2022年，8月28日

二叉樹的性質(zhì)：

1、在二叉樹的i層上，最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）

2、深度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)(k≥1)

3、對(duì)于任意一棵二叉樹，如果度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=n2+1。

4、具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。其中，[log2n]是不大于log2n的最大整數(shù)。

第二十二頁，共二十七頁，2022年，8月28日滿二叉樹和完全二叉樹

一棵深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹（FullBinaryTree）。深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其妹一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。第二十三頁，共二十七頁，2022年，8月28日二叉樹的存儲(chǔ)

二叉樹的存儲(chǔ)通常采用：鏈接方式。每個(gè)結(jié)點(diǎn)除存儲(chǔ)結(jié)點(diǎn)自身的信息外再設(shè)置兩個(gè)指針域Ichild和rchild，分別指向結(jié)點(diǎn)的左子女和右子女，當(dāng)結(jié)點(diǎn)的某個(gè)指針為空時(shí)，則相應(yīng)的指針值為空（NIL或∧

）。結(jié)點(diǎn)的形式為：lchilddatarchild第二十四頁，共二十七頁，2022年，8月28日二叉樹的遍歷

遍歷一個(gè)樹形結(jié)構(gòu)是指：按一定次序系統(tǒng)的訪問該結(jié)構(gòu)中的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被訪問一次。前序遍歷法（NLR次序）訪問根，按前序遍歷左子樹，按前序遍歷右子樹。后序遍歷法（LRN次序）按后序遍歷左子樹，按后序遍歷右子樹，訪問根。