1 數(shù)據(jù)結(jié)構(gòu)基本概念
1.1 數(shù)據(jù)結(jié)構(gòu)分類
1. 邏輯結(jié)構(gòu)
集合結(jié)構(gòu) 數(shù)據(jù)元素間的關(guān)系是“屬于同一個集合”。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。
線性結(jié)構(gòu) 數(shù)據(jù)元素之間存在著一對一的對應(yīng)關(guān)系
樹形結(jié)構(gòu) 數(shù)據(jù)元素之間存在著一對多的對應(yīng)關(guān)系
-
網(wǎng)狀結(jié)構(gòu)(圖形結(jié)構(gòu)) 數(shù)據(jù)元素之間存在著多對多的對應(yīng)關(guān)系
一般數(shù)據(jù)結(jié)構(gòu)可以采用一個二元組來表示DataStructure = (D, R) //D 是數(shù)據(jù)元素的有限集，R是D上的關(guān)系有限集。
2. 存儲結(jié)構(gòu)
常見的有順序存儲，鏈式存儲，索引存儲和散列存儲等。
- 順序存儲 把邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，通常借助數(shù)組來實現(xiàn)
- 鏈式存儲 元素間的邏輯關(guān)系通過附設(shè)的指針字段來實現(xiàn)
1.2 算法的衡量標準
兩個衡量算法效率的重要指標。時間復(fù)雜度衡量算法的時間開銷，空間復(fù)雜度衡量算法的空間開銷
1. 時間復(fù)雜度
時間復(fù)雜度就是求基本語句的運行次數(shù)，然后取次數(shù)最高的。
百度百科解釋
2. 空間復(fù)雜度
存儲空間包括兩個不服：
- 固定部分: 程序代碼、常量、簡單變量等結(jié)構(gòu)變量所占的空間。
- 可變部分: 這部分與處理的特定數(shù)據(jù)大小和規(guī)模相關(guān)。
2 線性數(shù)據(jù)結(jié)構(gòu)
2.1線性表
線性表是最簡單、最基本、最常用的一種線形數(shù)據(jù)結(jié)構(gòu)。它有兩種存儲方法：順序存儲和鏈式存儲結(jié)構(gòu)，分別成為順序表和鏈表
- 邏輯結(jié)構(gòu)是線性結(jié)構(gòu)
- 數(shù)據(jù)元素的類型相同
1. 順序表
線性表的順序存儲結(jié)構(gòu)是指在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各個元素。順序表又稱為向量。
只要知道順序表的首地址和每個元素所占地址但愿的個數(shù)就可求出第i個數(shù)據(jù)元素的地址，這也是順序表具有按數(shù)據(jù)元素的序號隨機存取的特點。
在一般的程序設(shè)計語言中，一位數(shù)組在內(nèi)存中占用的存儲空間就是一組連續(xù)的存儲區(qū)域，因此，用一維數(shù)組來表示順序表的數(shù)據(jù)存儲區(qū)域是再合適不過了。
| 按值查找 | 插入操作 | 刪除操作
------------ | ------------- | -----------|------
時間復(fù)雜度 T(n) | O(n) | O(n) | O(n)
2.2 鏈表
根據(jù)需要，鏈表可分為單鏈表、雙向鏈表、循環(huán)鏈表
1. 單鏈表
每個節(jié)點只有一個指向后繼元素的指。
為了避免“第一個節(jié)點”與其它節(jié)點在處理中存在差異，引入了頭節(jié)點的概念。頭節(jié)點的數(shù)據(jù)與無定義，指針域存放的是第一個數(shù)據(jù)節(jié)點的地址，空表時為空。
一個節(jié)點(Node)結(jié)構(gòu)如下所示:
| Data | Next |
|---|---|
| 數(shù)據(jù)域 | 指針域：后繼地址信息 |
- 插入元素：
頭插入：在鏈表的頭部插入節(jié)點建立單鏈表，每次插入修改新插入的元素指向原來頭部指向的節(jié)點，頭部的指針向新插入的元素。這個方法操作簡單，但是插入的順序與邏輯順序相反。
尾插入：設(shè)定一個指針r記錄鏈表最后一個元素位置的地址，如果插入新元素，原來的最后一個元素指向新元素，指針r記錄新元素的地址。
前插入: 在指定元素前插入新元素，時間復(fù)雜度O(n)
后插入: 在指定元素后插入新元素，時間復(fù)雜度O(1)
刪除操作: 前一個元素的指針等于要刪除的元素元素指針，需要查找p的前驅(qū)，所以時間復(fù)雜度O(n)
2. 循環(huán)鏈表
將單鏈表的結(jié)尾Null指針改成變?yōu)轭^指針，其它地方基本沒有變。
這樣的話就可以從鏈表的任何地方開始遍歷，可以提高一定的操作效率。
3. 雙向鏈表
在每一個節(jié)點都設(shè)置一個前向指針，在犧牲存儲空間的條件下達到在每一個節(jié)點都可以任意的訪問前一個節(jié)點。還可以設(shè)置成循環(huán)鏈表。
插入操作時
- p->prior->next = s
- s->prior=p->prior
- p->prior = s
- s->next = p
刪除操作時 - p->next->prior = p->prior
- p->prior->next = p->next
4. 靜態(tài)鏈表
在不支持動態(tài)內(nèi)存的語言里模擬鏈表，可以利用一個規(guī)模較大的數(shù)組。
每個元素的也有Data和Next變量。Next的指針是數(shù)組的序號
數(shù)組下標|0|1|2|3|4|5|6|7|8|9|10
-|-|-|-|-|-|-|-|-|-|-|-|-|-
Data|4|5|7||2|-1|7|1|9||
Next||a4|a2||a1|a5||a3|||
5. 順序表和鏈表的比較
| 順序表 | 鏈表 |
|---|---|
| 實現(xiàn)簡單(一般可用數(shù)組表示) | 實現(xiàn)比較復(fù)雜 |
| 物理結(jié)構(gòu)即為邏輯結(jié)構(gòu) | 額外的鏈指針存儲空間 |
| 可以隨機按序號訪問O(1) | 只能按順序訪問O(n) |
| 插入刪除操作需平均移動一半的元素，大的順序表效率低 | 不需要移動 |
| 需要預(yù)分配大量的空間，可能造成內(nèi)存浪費 | 動態(tài)分配內(nèi)存 |
選擇:
- 長度規(guī)模難以估算的不宜使用順序表
- 經(jīng)常訪問數(shù)據(jù)元素的不宜使用鏈表，經(jīng)常插入刪除時不宜使用順序表d
- 順序表容易實現(xiàn)
2.3 棧
棧是一種特殊的線性表，其數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)定義與線性表完全相同，但是其基本操作定義不同于普通的線性表。棧是限制在表的一端進行插入和刪除的線性表。
允許插入刪除的一端稱為棧頂
另一個固定端稱為棧底
所以棧是一種后進先出(Last In First Out)的線性表，簡稱LIFO表。同理也可稱為FILO。(就像子彈匣)
1. 順序棧
棧的定義類似于表，棧中的數(shù)據(jù)元素用一個預(yù)設(shè)的足夠長度的一位數(shù)組來實現(xiàn),棧底位置可以設(shè)置在數(shù)組的任一個端點，因為棧底是固定的。而棧頂是隨著插入和刪除數(shù)據(jù)而變化的，所以我們用一個始終指向棧頂?shù)南聵酥?code>top作為棧頂指針，指明當(dāng)前棧頂?shù)奈恢?。通常使用下?端設(shè)為棧底，稱為“向上生長”棧?？諚r，棧頂指針top=-1,入棧的時候+1,出棧的時候-1。
數(shù)組出棧操作之后， 可能并沒清空出棧的元素，在內(nèi)存里面，這個值不變，但此時的棧頂指針已經(jīng)移位，來標志已經(jīng)出棧。
對于出棧操作，要首先判斷是否空棧。同樣的，入棧操作要先判斷是否棧滿。
2. 共享棧
為了解決棧溢出的問題，將同一個程序中的兩個棧連接在一起，一個采用“向上生長”，一個采用“向下生長”，將空余的部分連接在一起。以此在一個棧溢出時，占取另一個棧的空余空間來存儲。
3. 鏈棧
用鏈式存儲結(jié)構(gòu)實現(xiàn)的棧稱為鏈棧。鏈棧一般采用單鏈表表示，其節(jié)點結(jié)構(gòu)也與單鏈表相同。
2.4 隊列
隊列是一種“先進先出”的數(shù)據(jù)結(jié)構(gòu)，即插入在表一端進行，而刪除在表另一端進行，這種數(shù)據(jù)結(jié)構(gòu)稱為隊列。允許插入的一端叫做隊頭，允許刪除的一端叫做隊尾。
隊列也是一種操作受限制的線性表，簡稱先進先出表(FIFO)。
1. 順序隊列
隊也有兩種存儲方式，順序存儲和鏈式存儲。順序存儲的隊稱為順序隊。因為隊的隊頭和隊尾都是活動的，因此，除了隊列的數(shù)據(jù)區(qū)外，還有兩個數(shù)組下標，front和rear分別作為隊頭和隊尾的指針。
約定：隊尾指針始終指向隊尾元素，隊頭指針指向隊頭元素的前一個位置。(這只是便于某些操作并不是唯一的方法)。按此約定：
- 空隊時
front = rear - 1 - 在不考慮溢出的情況下，元素入隊時隊尾指針
rear+1指向新元素 - 在不考慮對空的情況下，隊頭元素出隊時隊頭指針
front+1 - 隊中元素的個數(shù)
m = rear - front
當(dāng)刪除操作時，雖然比如有容量為10，滿容量情況下，刪除了一個元素，因為隊頭前面刪除了但卻沒有往前移動，所以隊尾指針仍然處于第10個元素的位置，這種現(xiàn)象稱為假溢出。
2. 循環(huán)隊
循環(huán)隊正是為了解決假溢出現(xiàn)象而產(chǎn)生。
將入隊時隊尾指針操作改成 rear = (rear + 1) % MaxSize這樣隊尾和隊頭就會首尾相連了。
但是這樣子會出現(xiàn)隊空和隊滿無法判斷 (都滿足rear = front)
解決方法之一就是少用一個元素，這種情況下，隊滿的條件是 front = (rear+1)%MaxSize 。 能和隊空條件 front = rear 區(qū)分開來。
另一種解決方法是附設(shè)一個存儲隊中元素個數(shù)的變量如num，當(dāng) num=0時隊空，當(dāng)num = MaxSize 時隊滿。
3. 鏈隊列
鏈式存儲的隊列稱為鏈隊列。用單鏈來表示鏈隊列，根據(jù)隊的FIFO原則，為了操作上的方便，分別需要一個頭指針front和尾指針rear。
2.5 串
串是一種特殊的線性表, 它的數(shù)據(jù)元素僅有一個字符組成。計算機非數(shù)值處理的對象經(jīng)常是字符串?dāng)?shù)組。
1. 串的順序存儲結(jié)構(gòu)
串是字符型的線性表。一般與順序表比較相似，稱為定長順序存儲結(jié)構(gòu)。
三種判定字符床長度的方法
- 類似順序表，用一個last指針來指向最后一個字符，這種存儲伐存儲結(jié)構(gòu)可以直接得到字符串的長度為
last + 1。 - 在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結(jié)符，以此表示串的結(jié)尾。比如在C語言中字符串“\0”結(jié)尾。通過判斷"\0"所在位置來判斷串的長度。
- 用s[0]存放串的實際長度，串值存放在s[1]~s[MaxSize]，字符的序號和存儲位置一致，應(yīng)用更為方便。
2. 串的鏈式存儲結(jié)構(gòu)
鏈式存儲結(jié)構(gòu)比較適合頻繁執(zhí)行插入和刪除操作的程序，但是串中的每個數(shù)據(jù)元素表較小(一般為1個字節(jié))， 鏈串存儲密度會相當(dāng)?shù)?，所以這不是一種理想的存儲結(jié)構(gòu)。
3. 串的堆存儲結(jié)構(gòu)
在程序中，參與操作的字符串變量之間的長度相差較大，并且操作中串值的長度變化也較大，所以為串變量預(yù)先分配固定大小的空間不盡合理。
堆存儲結(jié)構(gòu)的基本思想是：在內(nèi)存中開辟能存儲足夠多的串、抵制連續(xù)的存儲空間作為應(yīng)用程序中所有串的可利用存儲空間，稱為堆空間。根據(jù)每個串的長度，動態(tài)地為每個串在堆空間里申請相應(yīng)大小的存儲區(qū)域，這個串順序存儲在所申請的存儲區(qū)域中，在操作過程中若原空間不夠了，可以根據(jù)串的實際長度重新申請、拷貝原串值后再釋放原空間。
2.6 廣義表
廣義表是線性表的推廣，也稱為列表(Lists)。列表的元素不一定全是同一種類型。
- 性質(zhì)
- 廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)(像多數(shù)組一樣，還可以嵌套數(shù)組使用)。
- 廣義表可以是遞歸的表。廣義表的元素也可以是自身的字表。
- 廣義表可以為其他表所共享(就是多遠數(shù)組一樣，數(shù)組元素還可以是其它數(shù)組)。
