第一章：數(shù)據(jù)結(jié)構(gòu)的基本概念

定義

• 在任何問題中，數(shù)據(jù)元素都不是孤立存在的，而是在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)（Structure）。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

• 數(shù)據(jù)結(jié)構(gòu)包括三方面的內(nèi)容：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于所采用的存儲結(jié)構(gòu)。

邏輯結(jié)構(gòu)

• 邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，即從邏輯關(guān)系上描述數(shù)據(jù)。它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的

• 數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)

• 集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個集合”的關(guān)系外，別無其他關(guān)系。 類似于數(shù)學上的集合

• 線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間只存在一對一的關(guān)系。比如排隊

• 樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。比如家族族譜（重要）

• 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。 比如地圖

物理結(jié)構(gòu)

• 存儲結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱映像），也稱物理結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，它依賴于計算機語言。數(shù)據(jù)的存儲結(jié)構(gòu)主要有：順序存儲、鏈式存儲、索引存儲和散列存儲。

• 順序存儲：存儲的物理位置相鄰。（p.s. 物理位置即信息在計算機中的位置。）

• 鏈接存儲：存儲的物理位置未必相鄰，通過記錄相鄰元素的物理位置來找到相鄰元素。

• 索引存儲：類似于目錄。

• 散列存儲：通過關(guān)鍵字直接計算出元素的物理地址。

算法的五個特征

• 1，有窮性：有限步之后結(jié)束

• 2，確定性：不存在二義性，即沒有歧義

• 3，可行性：比如受限于計算機的計算能力，有些算法雖然理論上可行，但實際上無法完成。

• 4，輸入：能被計算機處理的各種類型數(shù)據(jù)，如數(shù)字，音頻，圖像等等。

• 5，輸出：一至多個程序輸出結(jié)果。

※ 算法的復雜度

• 時間復雜度：

• 它用來衡量算法隨著問題規(guī)模增大，算法執(zhí)行時間增長的快慢；

• 問題規(guī)模的函數(shù)：T(n)是時間規(guī)模函數(shù)。時間復雜度主要分析T(n)的數(shù)量級；

• T(n)=O(f(n))，f(n)是算法中基本運算的頻度 一般我們考慮最壞情況下的時間復雜度。

• 空間復雜度：

• 它用來衡量算法隨著問題規(guī)模增大，算法所需空間的快慢；

• 問題規(guī)模的函數(shù)：S(n)=O(g(n)) ，算法所需空間的增長率和g(n)的增長率相同。

概要: 復雜度計算為重點

• 常用的時間復雜度大小關(guān)系：

• 復雜度如何計算

• 兩個運算規(guī)則：乘法規(guī)則，加法規(guī)則。

• 直接關(guān)注循環(huán)體的執(zhí)行次數(shù)，設為k

• 時間復雜度計算（單個循環(huán)體）

• 時間復雜度計算（多個循環(huán)體）

第二章：線性表

線性表的邏輯結(jié)構(gòu)

• 定義：線性表是具有相同數(shù)據(jù)類型的n（n≥0）個數(shù)據(jù)元素的有限序列。其中n為表長。當n=0時 線性表是一個空表

• 特點：線性表中第一個元素稱為表頭元素；最后一個元素稱為表尾元素。除第一個元素外，每個元素有且僅有一個直接前驅(qū)。除最后一個元素外，每個元素有且僅有一個直接后繼。

線性表的順序存儲結(jié)構(gòu)

• 線性表的順序存儲又稱為順序表。它是用一組地址連續(xù)的存儲單元（比如C語言里面的數(shù)組），依次存儲線性表中的數(shù)據(jù)元素，從而使得邏輯上相鄰的兩個元素在物理位置上也相鄰。

• 建立順序表的三個屬性: 1.存儲空間的起始位置（數(shù)組名data）2.順序表最大存儲容量（MaxSize）3.順序表當前的長度（length）

• 其實數(shù)組還可以動態(tài)分配空間，存儲數(shù)組的空間是在程序執(zhí)行過程中通過動態(tài)存儲分配語句分配

• 總結(jié)：

• 1.順序表最主要的特點是隨機訪問（C語言中基于數(shù)組），即通過首地址和元素序號可以在O(1)的時間內(nèi)找到指定的元素。

• 2.順序表的存儲密度高，每個結(jié)點只存儲數(shù)據(jù)元素。無需給表中元素花費空間建立它們之間的邏輯關(guān)系（因為物理位置相鄰特性決定）

• 3.順序表邏輯上相鄰的元素物理上也相鄰，所以插入和刪除操作需要移動大量元素。

順序表的操作

• 1.插入

• 最好情況：在表尾插入（即i=n+1），元素后移語句將不執(zhí)行，時間復雜度為O(1)。

• 最壞情況：在表頭插入（即i=1），元素后移語句將執(zhí)行n次，時間復雜度為O(n)。

• 平均情況：假設pi（pi=1/(n+1) ）是在第i個位置上插入一個結(jié)點的概率，則在長度為n的線性表中插入一個結(jié)點時所需移動結(jié)點的平均次數(shù)為 n/2

• 2.刪除

• 最好情況：刪除表尾元素（即i=n），無須移動元素，時間復雜度為O(1)。

• 最壞情況：刪除表頭元素（即i=1），需要移動除第一個元素外的所有元素，時間復雜度為O(n)。

• 平均情況：假設pi(pi=1/n)是刪除第i個位置上結(jié)點的概率，則在長度為n的線性表中刪除一個結(jié)點時所需移動結(jié)點的平均次數(shù)為 (n-1)/2

線性表的鏈式存儲結(jié)構(gòu)

• 線性表的鏈式存儲是指通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素。

• 頭結(jié)點和頭指針的區(qū)別？

• 不管帶不帶頭結(jié)點，頭指針始終指向鏈表的第一個結(jié)點，而頭結(jié)點是帶頭結(jié)點鏈表中的第一個結(jié)點，結(jié)點內(nèi)通常不存儲信息

• 為什么要設置頭結(jié)點？

• 1.處理操作起來方便 例如：對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點起操作與其它結(jié)點的操作就統(tǒng)一了

• 2.無論鏈表是否為空，其頭指針是指向頭結(jié)點的非空指針，因此空表和非空表的處理也就統(tǒng)一了。

單鏈表的操作

• 1.頭插法建立單鏈表：建立新的結(jié)點分配內(nèi)存空間，將新結(jié)點插入到當前鏈表的表頭

• 2.尾插法建立單鏈表：建立新的結(jié)點分配內(nèi)存空間，將新結(jié)點插入到當前鏈表的表尾

• 3.按序號查找結(jié)點：在單鏈表中從第一個結(jié)點出發(fā)，順指針next域逐個往下搜索，直到找到第i個結(jié)點為止,否則返回最后一個結(jié)點指針域NULL。

• 4.按值查找結(jié)點：從單鏈表第一個結(jié)點開始，由前往后依次比較表中各結(jié)點數(shù)據(jù)域的值，若某結(jié)點數(shù)據(jù)域的值等于給定值e，則返回該結(jié)點的指針；若整個單鏈表中沒有這樣的結(jié)點，則返回NULL。

• 5．插入：插入操作是將值為x的新結(jié)點插入到單鏈表的第i個位置上。先檢查插入位置的合法性，然后找到待插入位置的前驅(qū)結(jié)點，即第i?1個結(jié)點，再在其后插入新結(jié)點。

• 算法思路：1.取指向插入位置的前驅(qū)結(jié)點的指針① p=GetElem(L,i-1);2.令新結(jié)點s的指針域指向p的后繼結(jié)點② s->next=p->next;3.令結(jié)點p的指針域指向新插入的結(jié)點s③ p->next=s;

• 6．刪除：刪除操作是將單鏈表的第i個結(jié)點刪除。先檢查刪除位置的合法性，然后查找表中第i?1個結(jié)點，即被刪結(jié)點的前驅(qū)結(jié)點，再將其刪除。

• 算法思路：1.取指向刪除位置的前驅(qū)結(jié)點的指針 p=GetElem(L,i-1);2.取指向刪除位置的指針 q=p->next;3.p指向結(jié)點的后繼指向被刪除結(jié)點的后繼 p->next=q->next4.釋放刪除結(jié)點 free(q);

雙鏈表

• 定義

• 1.插入：(方法不唯一)① s->next=p->next;② p->next->prior=s;③ s->prior=p;④ p->next=s;

• 2.刪除：① p->next=q->next;② q->next->prior=p;③ free(q);

循環(huán)鏈表&&靜態(tài)鏈表

• 循環(huán)單鏈表：循環(huán)單鏈表和單鏈表的區(qū)別在于，表中最后一個結(jié)點的指針不是NULL，而改為指向頭結(jié)點，從而整個鏈表形成一個環(huán)。

• 循環(huán)雙鏈表：類比循環(huán)單鏈表，循環(huán)雙鏈表鏈表區(qū)別于雙鏈表就是首尾結(jié)點構(gòu)成環(huán)。

• 當循環(huán)雙鏈表為空表時，其頭結(jié)點的prior域和next域都等于Head。

• 靜態(tài)鏈表：靜態(tài)鏈表是用數(shù)組來描述線性表的鏈式存儲結(jié)構(gòu)。

• 數(shù)組第一個元素不存儲數(shù)據(jù)，它的指針域存儲第一個元素所在的數(shù)組下標。鏈表最后一個元素的指針域值為-1。