常用數(shù)據(jù)結構及其存儲

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

定義：是對特定問題求解步驟的一種描述。或者說，是為求解某問題的方法和步驟。

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

算法的效率：指的是時間復雜度（TimeComplexity）

存儲需求：指的是空間復雜度（SpaceComplexity）

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

數(shù)據(jù):

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

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

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

數(shù)據(jù)項:

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

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

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

數(shù)據(jù)結構:互相之間存在著一種或多種關系的數(shù)據(jù)元素的集合。

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

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

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

檢索：在數(shù)據(jù)結構里查找滿足一定條件的結點

插入：往數(shù)據(jù)結構里增加新的結點

刪除：把指定的結點從數(shù)據(jù)結構里去掉

更新：修改指定結點的一個或多個域的值

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

（a1，a2，…，an）

順序表：指用順序存儲結構存儲的線性表。

鏈表：用鏈式存儲結構存儲的線性表。

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

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

插入一個結點平均需要移動之結點個數(shù)為

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

刪除一個結點平均需移動結點個數(shù)為

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

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

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

棧的物理存儲可以用順序存儲結構或鏈式存儲結構;

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

a1a2a3…an

入隊列

隊頭

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

樹形結構是一類重要的非線性結構，樹和二叉樹是最常見的樹形結構。

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

第十九頁，共二十七頁，2022年，8月28日樹形結構的常用術語

結點的度（Degree）：一個結點的子樹的個數(shù)。

樹的度：樹中各結點的度的最大值。

樹葉（Leaf）：度為0的結點。

分支結點：度不為0的結點。

雙親（Parent）、子女（Child）：結點的各子樹的根稱作該結點的子女；相應的該結點稱作其子女的雙親。

兄弟（Sibling）：具有相同雙親的結點互為兄弟。

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

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

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

二叉樹的性質：

1、在二叉樹的i層上，最多有2i-1個結點（i≥1）

2、深度為k的二叉樹最多有2k-1個結點(k≥1)

3、對于任意一棵二叉樹，如果度為0的結點個數(shù)為n0，度為2的結點個數(shù)為n2，則n0=n2+1。

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

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

一棵深度為k且具有2k-1個結點的二叉樹稱為滿二叉樹（FullBinaryTree）。深度為k，有n個結點的二叉樹，當且僅當其妹一個結點都與深度為k的滿二叉樹中編號從1到n的結點一一對應時，稱為完全二叉樹。第二十三頁，共二十七頁，2022年，8月28日二叉樹的存儲

二叉樹的存儲通常采用：鏈接方式。每個結點除存儲結點自身的信息外再設置兩個指針域Ichild和rchild，分別指向結點的左子女和右子女，當結點的某個指針為空時，則相應的指針值為空（NIL或∧

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

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