這幾天開始了對數據結構的學習，內容較多較雜，理解起來也頗爲困難,故記錄下學習中的筆記
數據結構是一門研究數據之間關係和操作 的學科，而非計算方法
數據結構的基本概念
數據結構的三個方面
邏輯結構和儲存結構
集合:數據元素同屬於一個集體，但元素之間沒有任何關係
線性結構:數據元素之間存在一對一關係
樹形結構:數據元素之間存在一對多關係(倒懸樹)
圖型結構:數據元素之間存在多對多關係(地鐵圖)
數據的物理結構
順序結構:數據元素儲存在連續的記憶體中,用數據元素的相對位置來表示關係
優點:能夠隨機存取(想存取那個就存取那個) 存取效率極高(速度快)
缺點:空間利用率低，對記憶體要求比較高,插入、刪除不方便
鏈式結構:數據元素儲存在彼此獨立的記憶體空間中,每個獨立的元素也叫節點,每個數據元素中增加一個數據項用於儲存其他元素的地址,用來表示元素之間的關係
優點:插入刪除非常方便,空間利用率高
缺點:不能隨機存取(只能由前到後逐個存取)
邏輯結構和物理結構的對應關係
表 順序 鏈式
樹 鏈式 順序
圖 順序+鏈式
每種邏輯結構採用什麼物理結構儲存並沒有明確的規定，通常根據實際的難易程度以及空間、時間方面的要求，來選擇最合適的物理儲存結構,也有可能採用多種物理結構複合儲存
數據結構的和運算
1 建立數據結構 create
2 銷燬數據結構 destory
3 清空數據結構 clean
4 數據結構排序 sort
5 刪除元素 delete
6 插入元素 insert
7 存取元素 access
8 修改元素 modify
9 查詢元素 query
10遍歷數據結構 ergodic (show printf)
順序表和鏈式表的實現
順序表:
數據項
1儲存的記憶體首地址
2表的容量
3元素的數量
運算:
建立 銷燬 清空 插入 刪除 存取 修改 查詢 排序 遍歷
注意
1 越界問題(不要越界)
2 要保持元素的連續性
優點:支援隨機存取,修改 查詢 排序 效率高,大塊連續的記憶體不易產生記憶體碎片
缺點:對記憶體的要求比較高(記憶體連續、大塊記憶體) 插入刪除元素時不方便 且效率低
鏈式表:
元素的數據項:
數據域:可以是各種型別的若幹個數據項
指針域:指向下一個元素
由若幹個元素通過指針域鏈接在一起形成鏈式表
不帶頭節點:第一個元素儲存的數據域就是有效的數據
新增刪除是可以修改頭節點指針，參數需要使用二級指針
同時需要獲取到上一個節點的指針,而頭節點沒有上一個節點
帶頭節點:第一個元素只代表頭 不使用
進行插入、刪除操作時會比不帶頭節點的鏈表方便
注意:其他操作時要從第二個節點開始
對錶的結構加以限制，形成特殊的表結構
四種順序棧
top 初值 0 入棧 top++ 空增棧
top 初值 -1 top++ 入棧 滿增棧
top 初值max-1 入棧 top-- 空減棧
top 初值max top-- 入棧 滿減棧
先進後出
順序棧:
數據域:
儲存元素的記憶體首地址
棧的容量
棧頂位置
運算:
建立、入棧、出棧、棧滿、棧空、棧頂、銷燬
鏈式棧:
數據域
棧頂
節點數量
運算
建立、銷燬
棧的應用:
1 函數的呼叫(棧記憶體)
2 生產者與消費者模型(棧當做倉庫)
3 表達式解析(中綴表達式後綴表達式)
常見筆試面試題
某序列爲棧的入棧順序,某序列是否是出棧順序(邊入邊出)
1 2 3 4 5
3 1 2 4 5假！
實現一個函數，判斷序列b是否是a的出棧順序
bool is_popstack(int* a,int* b,size_t len);
{
// 建立一個棧
// 按a的順序入棧
// 按b的順序出棧
// 最後判斷如果棧爲空，則b是a的出棧順序
}
bool is_popstack(int* a,int* b,size_t len)
{
// 建立一個棧
ArrayStack* stack = create_array_stack(len);
// 按a的順序入棧
for(int i=0,j=0; i<len; i++)
{
push_array_stack(stack,a[i]);
// 按b的順序出棧
int val = 0;
while(top_array_stack(stack,&val) && val==b[j])
{
pop_array_stack(stack);
j++;
}
}
// 最後判斷如果棧爲空，則b是a的出棧順序
bool flag = empty_array_stack(stack);
destory_array_stack(stack);
return flag;
}
順序佇列:
由一維陣列+隊頭位置+隊尾位置rear 組成,入隊時rear+1，出隊時front+1 爲了讓佇列反覆 反復使用要把一維陣列想象成環形.爲了讓rear和front加1後要用鏈表的容量求餘
rear = rear+1 % cal
front = front+1 % cal
如何判斷佇列爲空: front == rear
如何判斷佇列爲滿: front == rear+1
代價就是要空一個位置不能用,或者再新增一個數據項用來標記是否是空還是滿
如何計算元素的數量:
(rear-front+cal)%cal
數據項:
儲存元素的記憶體首地址
隊頭指針
隊尾 即將入隊的位置
容量
運算:建立、銷燬、入棧、出棧、隊空、隊滿、隊頭、隊尾、元素數量
鏈式佇列
由若幹個節點組成的佇列
數據項:
隊頭指針
隊尾指針
節點數量
運算:建立、銷燬、隊空、(鏈式一般不滿) 、入隊、出隊、隊頭、隊尾、數量
佇列應用:
1 訊息排隊
2 樹的層序遍歷
3 圖的廣度優先遍歷
4 封裝執行緒池、數據池
常見的筆試面試題:
使用兩個棧來模擬一個佇列的功能
從棧1到棧2一個不留
如棧2不空則棧1不到棧2
尾新增效率低，非法下標的判斷效率也非常低
數據項:
頭指針
尾指針
節點數量
節點:
數據域
遊標
靜態鏈表的節點儲存在連續的記憶體，通過遊標來存取下一個節點
這種鏈表在插入刪除時只需要修改遊標的值，而不用申請、釋放記憶體達到一種鏈式結構
但是也犧牲了隨機存取的功能,是給沒有指針的程式語言實現的一種單鏈表
節點:
前驅指針
數據域
後驅指針
數據項:
頭節點
節點數量
// 逆序輸出
void anti_show_list(Node* head)
{
Node* n1 = head;
Node* n2 = head->next;
for(Node* n3=NULL;NULL == n2;n2=n2->next)
{
n1->next = n3;
n3=n1;
n1=n2;
}
}
陣列：儲存空間鏈接的表結構
矩陣：帶二維資訊的數據,一般使用二維數據來儲存矩陣
特殊矩陣
上三角形矩陣:
[1][2][3][4]
[ ][5][6][7]
[ ][ ][8][9]
[ ][ ][ ][x]
壓縮方法:用一維陣列進行儲存 (1 25 368 479x)
陣列長度 (n+1)*n/2
對應關係 (j+1)×j/2+i
i和j要滿足 i<=j
下三角形矩陣:
[x][ ][ ][ ]
[x][x][ ][ ]
[x][x][x][ ]
[x][x][x][x]
陣列長度 (n+1)*n/2
對應關係 (i+1)*i/2+j
i和j要滿足 j<=i
對稱矩陣:沿着(0,0) (1,1) (2,2)...對稱
壓縮方法:用一維矩陣儲存把他當做上三角或下三角
對角矩陣:(帶狀矩陣)沿着(0,0) (1,1) (2,2)...對角線兩邊有數據
用一維陣列儲存
陣列長度 3*n-2
對應關係 2*i+j
i和j要滿足 abs(i-j) <= 1
稀疏矩陣:有效資訊不多,絕大多數都是無效資訊,不需要儲存,這種二維陣列,沒有特定的標準，全憑感覺
壓縮方式:
三元組
有三個數據項 行 列 值 構成一個整體儲存在一維陣列中
//十字鏈表
這些矩陣如果使用二維陣列來儲存的話，會非常浪費儲存空間,爲了節約空間，我們可以對這些矩陣進行壓縮