1. 線性表 線性表的定義 特點： 存在唯一一個被稱為第一個的數據元素 存在唯一一個被稱為最後一個的數據元素 除了第一個元素之外，其他的數據元素都有唯一一個直接前驅 除了最後一個元素之外，其他的數據元素都有唯一一個直接後驅 定義：是由 $n(n\ge 0)$ 個相同的數據元素組成的有限序列 邏輯特征 ...
1. 線性表
- 線性表的定義
- 特點：
- 存在唯一一個被稱為第一個的數據元素
- 存在唯一一個被稱為最後一個的數據元素
- 除了第一個元素之外，其他的數據元素都有唯一一個直接前驅
- 除了最後一個元素之外，其他的數據元素都有唯一一個直接後驅
- 定義：是由 \(n(n\ge 0)\) 個相同的數據元素組成的有限序列
- 邏輯特征
- 有限性：數據元素的個數是有限的
- 相同性：數據元素的元素類型是相同的
- 相繼性（線性性）：\(a_1\) 為表中的第一個元素，無前驅元素，\(a_n\) 為表中最後一個元素，無後驅元素；對於 \(1<i<n\) ， \(a_{i-1}\) 為 \(a_{i}\) 的直接前驅， \(a_{i+1}\) 為 \(a_{i}\) 的直接後驅
- 基本操作 \(Operations\)
- 求線性表的長度
Lenlist(L) - 獲取線性表中的元素
GetElem(L , i) - 通過值來查找線性表當中的元素
SearchElem(L , Val) - 插入元素
InsertElem(L , i , Elem) - 刪除元素
DeleteElem(L , i)
- 求線性表的長度
- 特點：
- 線性表的存儲結構設計
-
連續存儲結構(數組)
- 存儲方式：依次將元素存放進連續的存儲空間中
- 順序表示： \(loc(a_i) = loc(a_1)+(i-1)*c\)
- 存儲特點：邏輯上相鄰的元素，物理結構上也相鄰
- \(Operations\)
// 1. 插入元素 O(n) int insertElem(list *L , Datatype x , int i){ if((*L).last >= maxsize - 1){ //overflow printf("Overflow\n"); return -1; } else if(i < 1 || i > (*L).last + 1){ //wrong location printf("Error\n"); return -1; } else{ for(int j = (*L).last ; j >= i ; --j){ //move the elements (*L).data[j + 1] = (*L).data[j]; } (*L).data[i] = x; (*L).last++; } return 1; }// 2. 刪除元素 O(n) int deleteElem(list *L , int i){ if(i < 1 || i > (*L).last + 1){ //wrong location printf("Error\n"); return -1; } else { for(int j = i ; j <= (*L).last ; ++j){ (*L).data[j - 1] = (*L).data[j]; } (*L).last--; } }// 3. 按值查找 O(n) int searchElem(list *L , Datatype x){ int i = 1; while(i <= (*L).last && x != (*L).data[i - 1]){ ++i; } if(i <= (*L).last) return i - 1; return -1; //can not find }// 4. 按位置查找 O(1) int getElem(list *L , int i){ if(i < 1 || i > (*L).last + 1){ //wrong location printf("Error\n"); return -1; } return (*L).data[i - 1] }- 連續存儲的優缺點
- 優點
- 順序表的存儲結構簡單
- 隨機存儲，按位置取值速度快
- 存儲效率高，無需增加邏輯關係的占用空間
- 缺點
- 刪除插入速度慢
- 預先分配記憶體大
- 優點
-
\(\quad\)
\(存儲效率 = \frac{數據元素占用空間}{數據元素占用空間+邏輯關係占用空間}\)
\(\quad\)
-
鏈式存儲結構
- 存儲方式：用一組任意的存儲單元存儲線性表中的數據元素，通過每個結點的指針將數據元素連接在一起
- 單鏈表：具有一個指針，指向後繼元素
typedef struct Node{ datatype data; struct Node *next; }Node , *head;- \(Operations\)
// 1. 建立單鏈表 void createList(){ Node head = new Node(); head->next = NULL; }// 2. 插入元素 int insertList(Node &L , int i , datatype x){ Node *p = head; int j = 0; while(p && j < i - 1){ p = p->next; j++; } if(!p) return -1; Node *temp = new Node; temp->data = x; // insert temp->next = p->next; p->next = temp; return 1; }// 3. 刪除元素 int deleteList(Node &L , int i){ Node *p = head; int j = 0; while((p->next) && j < i - 1){ p = p->next; j++; } if(!(p->next)) return -1; Node *temp = p->next; p->next = temp->next; delete temp; return 1; }// 4. 通過位置查找元素 datatype getList(Node &L , int i){ Node *p = head; int j = 0; while(p && j < i - 1){ p = p->next; j++; } if(!p) return -1; return p->data; }// 5. 通過值來查找元素 int searchList(Node &L , datatype x){ Node *p = head; int j = 0; while(p && p->data != x){ p = p->next; ++j; } if(!p) { printf("Not Find!"); return -1; } return j; }- 雙鏈表：前驅指針
*prev和後繼指針*next - \(Operations\) 要處理兩個指針
// 1. 初始化 typedef struct DulNode{ datatype data; struct DulNode *prev , *next; }DulNode , *head;// 2. 插入元素(先右後左) s->data = _data; s->next = p->next; p->next->prev = s; p->next = s; s->prev = p;
// 3. 刪除元素 p->prev->next = p->next; p->next->prev = p->prev; delete p;
- 連續設計和連接設計的對比
Parameters 連續設計 鏈接設計 表的容量 固定，不易擴充 靈活，易擴充 存取操作 隨機訪問存取，速度快 順序訪問存取，速度慢 時間 插入、刪除操作費時間 訪問元素費時間 空間 估算長度，浪費空間 實際長度
- 鏈接存儲設計的數組實現
data next data1 1 2 \(\cdots\) \(\cdots\) max_size - 1 -1 - 結點：
#define max_size 1024 \\數組最大容量 typedef int datatype; typedef int cursor; typedef struct{ datatype data; cursor next; }node; node nodepool[max_size]; // 存儲池（數組） cursor avail; // 空閑空間的位置- 初始化
for(int i=0; i < max_size - 1; i++){ nodepool[i].next = i + 1; } nodepool[max_size - 1].next = -1; avail = 0; //avail 初始化- 結點
node的分配
cursor getNode(){ cursor p; if(avail == -1) p = -1; else { p = avail; avail = nodepool[avail].next; } return p; }- 結點
node的回收
void freeNode(cursor p){ nodepool[p].next = avail; avail = p; }- 靜態鏈表查找演算法
cursor findNode(cursor L , int i){ cursor p = L; int j = 0; while(nodepool[p].next != -1 && (j < i>)){ p = nodepool[p].next; ++j; } if(i == j) return p; else return -1; }
2. \(Applications\)
-
合併有向鏈表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* preHead = new ListNode(-1); ListNode* prev = preHead; while (l1 != nullptr && l2 != nullptr) { if (l1->val < l2->val) { prev->next = l1; l1 = l1->next; } else { prev->next = l2; l2 = l2->next; } prev = prev->next; } prev->next = (l1 == nullptr) ? l2 : l1;// 合併剩餘鏈表 return preHead->next; } -
反轉鏈表
- 就地反轉
反轉箭頭為：
graph LR A(head)-.->B(nextp) B-.->C(cur) C==>B C--> D(p) D-.->E(NULL)ListNode* reverseList(ListNode* head) { if(head == nullptr) return head; ListNode* nextp = nullptr; ListNode* cur = head; ListNode* p = head -> next; while(p){ cur -> next = nextp; nextp = cur; cur = p; p = cur -> next; } cur -> next = nextp; return cur; }- 遞歸：處理好
k之後，將k-1的箭頭倒轉；
ListNode* reverseList(ListNode* head) { if(!head || !(head -> next)) return head; ListNode* new_Head = reverseList(head -> next); head -> next -> next = head; head -> next = nullptr; return new_Head; }
