1 緒論
數(shù)據(jù)結(jié)構(gòu)主要是研究數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的操作及操作實(shí)現(xiàn)三個(gè)方面的內(nèi)容.
基本概念和常用術(shù)語
數(shù)據(jù)：數(shù)據(jù)是描敘客觀事物的數(shù)值残揉、字符以及能輸入機(jī)器且能被處理的各種字符的集合胧后，
即計(jì)算化的信息。
數(shù)據(jù)元素：數(shù)據(jù)元素也稱為結(jié)點(diǎn)抱环，它是組成數(shù)據(jù)的基本單位壳快，是一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單元。
字段：字段是構(gòu)成數(shù)據(jù)的最小單位镇草。
數(shù)據(jù)對(duì)象：在數(shù)據(jù)結(jié)構(gòu)中眶痰，將性質(zhì)相同的數(shù)據(jù)元素的集合稱為數(shù)據(jù)對(duì)象，它是數(shù)據(jù)的一個(gè)子 集梯啤。
數(shù)據(jù)結(jié)構(gòu)：由某一數(shù)據(jù)元素集合及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成竖伯。具體來說，數(shù)據(jù)結(jié)構(gòu)包含3個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)七婴、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)所施加的操作祟偷。
根據(jù)數(shù)據(jù)結(jié)構(gòu)中元素之間的結(jié)構(gòu)關(guān)系的不同特征，通常將數(shù)據(jù)結(jié)構(gòu)分為如下四種基本結(jié)構(gòu)：
（1）打厘、集合結(jié)構(gòu)(set)::數(shù)據(jù)元素的有限結(jié)合修肠。（2）、線性結(jié)構(gòu)或者稱為序列：：數(shù)據(jù)元素的有序結(jié)合户盯。（3）嵌施、樹形結(jié)構(gòu)(tree)::樹的層次結(jié)構(gòu)，樹中數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系莽鸭。（4）艰管、圖形結(jié)構(gòu)：：：圖中數(shù)據(jù)元素之間的關(guān)系是多對(duì)多。
邏輯結(jié)構(gòu)
《結(jié)點(diǎn)和結(jié)點(diǎn)之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)蒋川∩螅》
(1)、線性結(jié)構(gòu)捺球。元素之間為一對(duì)一的線性關(guān)系缸浦，第一個(gè)元素?zé)o直接前驅(qū)，最后一個(gè)元素?zé)o直接后繼氮兵，其余元素都有一個(gè)直接前驅(qū)和直接后繼裂逐。
（2）、非線性結(jié)構(gòu)泣栈。元素之間為一對(duì)多或多對(duì)多的非線性關(guān)系卜高，元素可有多個(gè)直接前驅(qū)或多個(gè)直接后繼。
（3）南片、集合結(jié)構(gòu)掺涛。元素之間無任何關(guān)系，元素的排序無任何順序疼进。
存儲(chǔ)結(jié)構(gòu)
《數(shù)據(jù)的邏輯結(jié)構(gòu)是獨(dú)立于計(jì)算機(jī)的薪缆，它與數(shù)據(jù)在計(jì)算中的存儲(chǔ)無關(guān)，要對(duì)數(shù)據(jù)進(jìn)行處理伞广，
就必須將數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)中拣帽。數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式稱為 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的
存儲(chǔ)結(jié)構(gòu)主要有4種嚼锄〖跏茫》
樹《一對(duì)多》
《樹形結(jié)構(gòu)是計(jì)算機(jī)算法中最重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用区丑，它可以很好地描述具有分支關(guān)系和層次特性的對(duì)象拧粪，同時(shí)也是具有層次關(guān)系的數(shù)據(jù)在計(jì)算機(jī)中的表示提供了一種自然的表示方法修陡。》
2.1 樹的基本概念
樹(Tree)是由n(n>=0)個(gè)結(jié)點(diǎn)組成的有限集合既们。n=0的樹稱為空樹；n>0的樹即為任意一顆非空樹正什。
2.1.1 樹的邏輯表示方法
(1)啥纸、直接表示法
(2)、嵌套集合表示法
(3)婴氮、凹入表示法<似文檔目錄>
(4)斯棒、廣義表表示法
2.1.2 樹的基本術(shù)語
1)、結(jié)點(diǎn)的度(degree)-----------指結(jié)點(diǎn)中所擁有的子樹的個(gè)數(shù)主经。
(2)荣暮、樹的度--------------是指樹中各結(jié)點(diǎn)的度的最大值≌肿ぃ《結(jié)點(diǎn)的度的最大值》
(3)穗酥、結(jié)點(diǎn)的層次(level)---在樹中根節(jié)點(diǎn)的層次為1,其余任一結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加1.
(4)、樹的深度(depth)------樹中結(jié)點(diǎn)的最大層次稱為樹的深度惠遏，又稱高度砾跃。
2.2 二叉樹的概念和性質(zhì)
2.2.1 定義
二叉樹(binary tree)是指樹的度最大為2的有序樹。它是一種最簡單节吮、最重要的樹抽高，在計(jì)算機(jī)領(lǐng)域有著廣泛的應(yīng)用。
2.2.2 二叉樹的性質(zhì)
性質(zhì)1：在一棵非空的二叉樹的第i層上透绩，最多有2^i-1次方個(gè)結(jié)點(diǎn)(i>=0)翘骂。
性質(zhì)2：一棵深度為K的二叉樹，最多具有2^K-1個(gè)結(jié)點(diǎn)(K>=1)帚豪。
性質(zhì)3：對(duì)任意一棵非空二叉樹碳竟，如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。
滿二叉樹：一棵深度為K且含有2^k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹狸臣。
完全二叉樹：一個(gè)深度為k,有n個(gè)結(jié)點(diǎn)的二叉樹瞭亮，對(duì)樹中的結(jié)點(diǎn)按從上至下、從左到右的順序編號(hào)固棚，如果編號(hào)為i(1<=i<=n)的結(jié)點(diǎn)與滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中位置相同统翩，則稱此二叉樹為完全二叉樹。
性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為|log2N|+1.
性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(其深度為|log2N|+1)的結(jié)點(diǎn)按層次編號(hào)（從第一層到第|log2N|+1層此洲，每層從左到）厂汗，則對(duì)任一結(jié)點(diǎn)i(1<=i<=n),有如下性質(zhì)：
(1)
3 圖《多對(duì)多》
3.1 圖的定義
圖(graph)是由非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間的關(guān)系-----邊(或者弧)的有限集**
合組成的一種數(shù)據(jù)結(jié)構(gòu)。
3.2 圖的相關(guān)術(shù)語
無向圖：沒有方向呜师。
有向圖：有方向娶桦，射線。
無向完全圖：有n(n-1)/2條邊的圖<n為頂點(diǎn)數(shù)>。*
有向完全圖：有n(n-1)條邊的圖<n為頂點(diǎn)數(shù)>衷畦。*
稀疏圖和稠密圖：由頂點(diǎn)引發(fā)邊的多少來判斷栗涂。
頂點(diǎn)的度，《入度祈争，出度相對(duì)于有向圖來說》：無向圖頂點(diǎn)的度----引發(fā)的線段數(shù)
有向圖頂點(diǎn)的度<TD>----=入度<ID>+出度<OD>
權(quán)和網(wǎng)：權(quán)值斤程，邊或者弧帶有權(quán)值的圖形成為網(wǎng)。
**路徑和路徑長度：
路徑
由頂點(diǎn)和相鄰頂點(diǎn)偶對(duì)構(gòu)成的邊所形成的序列 路徑長度------連接頂點(diǎn)的軌跡的權(quán)值相加菩混。
回路：從頂點(diǎn)回到頂點(diǎn)形成的閉合環(huán)形忿墅。
子圖：圖的部分。
連通圖和連通分量：《連通圖》：每頂點(diǎn)都能與其余頂點(diǎn)相連想成強(qiáng)連通圖和強(qiáng)連通分量：《強(qiáng)連通圖》---有向圖沮峡，雙向連接的連通圖 《強(qiáng)連通分量》：把不是強(qiáng)連通圖拆分成多個(gè)子強(qiáng)連通圖疚脐。**
生成樹：它必包含且僅包含G的n-1條邊⌒细恚《多一條：形成了回路棍弄；少一條：非連通》
生成森林。
3.3 圖的存儲(chǔ)結(jié)構(gòu)
3.3.1 鄰接矩陣存儲(chǔ)結(jié)構(gòu)
形式：
A[i][j]=@1: 1------代表兩頂點(diǎn)存在邊
=@2：0----代表兩頂點(diǎn)不存在邊
1：無向連接矩陣圖
特點(diǎn)：對(duì)稱分布
頂點(diǎn)的度：行中非零點(diǎn)的個(gè)數(shù)疟游。
2：有向連接矩陣圖
特點(diǎn)：一般不是對(duì)稱分布照卦，僅當(dāng)它為完全有向圖時(shí)對(duì)稱。非零點(diǎn)的個(gè)數(shù)：行中非零點(diǎn)的個(gè)數(shù)代表出度乡摹。
列中非零點(diǎn)的個(gè)數(shù)代表入度
3：無向連接矩陣網(wǎng)
帶權(quán)圖役耕，矩陣中的1用權(quán)值替換，0用無窮值替換聪廉。
4：有向連接矩陣網(wǎng)
帶權(quán)圖瞬痘，矩陣中的1用權(quán)值替換，0用無窮值替換板熊。
3.3.2 鄰接表存儲(chǔ)結(jié)構(gòu)
相對(duì)于稀疏圖來說框全，是為了節(jié)約存儲(chǔ)空間，引入了指針
1：無向圖鄰接表
將每一頂點(diǎn)連接的線段轉(zhuǎn)換為一個(gè)單鏈表干签。
頂點(diǎn)的度為：分得的段數(shù).<節(jié)點(diǎn)數(shù)>
矩陣大小:n^2
2：有向圖鄰接表
將每一頂點(diǎn)連接的線段轉(zhuǎn)換為一個(gè)單鏈表津辩。
只關(guān)心出度。
如果要關(guān)心入度則引入：有向圖逆鄰接表
3: 延伸
延伸：對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖容劳，若采取鄰接表表示喘沿，則表頭向量的大小為:n, 所有鄰接表中的結(jié)點(diǎn)總數(shù)是:2e
4.4 棧和隊(duì)列
1:棧的定義《先進(jìn)后出》------是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。(棧頂<允許插入和刪除的一端>竭贩，棧底<不允許插入和刪除的一端>).
分為：順序棧和鏈棧蚜印。
2：***順序棧，的定義留量，初始化窄赋，入棧哟冬，出棧，取棧頂元素操作忆绰，判斷空操作,置椇葡浚空操作。
3：多<雙>棧共享(鄰接空間)
4：鏈棧<涉及到指針>:棧也可以采用鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)表示错敢，這種結(jié)構(gòu)的棧簡稱為鏈棧翰灾。
鏈棧的操作:
- 1：分配節(jié)點(diǎn)空間
- 2:數(shù)據(jù)域
- 3:指針域
- 3:頂指針節(jié)點(diǎn)指向》
5:隊(duì)列---《先進(jìn)先出，對(duì)其操作時(shí)：隊(duì)尾插入伐债，對(duì)頭刪除预侯≈驴》:是一種限定性的線性表峰锁，它只允許在表的一端插入元素，而在表的另一端刪除數(shù)據(jù)双戳。
《隊(duì)列分為:順序隊(duì)列和鏈隊(duì)列》
6：順序隊(duì)列：隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列虹蒋，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表，和順序表一樣飒货，順序隊(duì)列也必須用一個(gè)向量空間來存放當(dāng)前隊(duì)列中的元素魄衅。
由于隊(duì)列的對(duì)頭和隊(duì)尾的位置是變化的，因而要設(shè)置兩個(gè)指針front和rear,分別用于指示對(duì)頭元素和隊(duì)尾元素在向量空間的位置塘辅。
(特殊說明：指針front和rear初始化均應(yīng)設(shè)置為0晃虫；在非空隊(duì)列里，頭指針始終指向?qū)︻^元素扣墩，而為指針始終指向隊(duì)尾元素的下一個(gè)位置)
為了防止“假溢出現(xiàn)象”引入-------循環(huán)隊(duì)列哲银。
------循環(huán)隊(duì)列（在front==rear的情況下）是為空還是隊(duì)列已滿：兩種方法--：
《
方法一:犧牲存儲(chǔ)空間。判斷隊(duì)列“滿”的條件為(rear+1)MAXSIZE=front呻惕。
方法二：設(shè)置一個(gè)標(biāo)志變量的方法荆责。（標(biāo)志tag=0表示最后的一次操作是出隊(duì)，tag=1表示最后的一次操作是入隊(duì)）---判斷隊(duì)空的條件為:front==rear && tag==0
判斷隊(duì)滿的條件為:front==rear && tag==1亚脆。
》
7：鏈隊(duì)列--隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈隊(duì)列做院，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾做插入操作濒持，
為此再添加一個(gè)為指針键耕，指向鏈表上的最后一個(gè)節(jié)點(diǎn)。于是柑营，一個(gè)鏈隊(duì)列由一個(gè)頭指針和一個(gè)尾指針唯一確定郁竟。**
