1. 線性表

線性表的定義
1. 特點：
  1. 存在唯一一個被稱為第一個的資料元素
  2. 存在唯一一個被稱為最后一個的資料元素
  3. 除了第一個元素之外，其他的資料元素都有唯一一個直接前驅
  4. 除了最后一個元素之外，其他的資料元素都有唯一一個直接后驅
2. 定義：是由 \(n(n\ge 0)\) 個相同的資料元素組成的有限序列
3. 邏輯特征
  1. 有限性：資料元素的個數是有限的
  2. 相同性：資料元素的元素型別是相同的
  3. 相繼性（線性性）：\(a_1\) 為表中的第一個元素，無前驅元素，\(a_n\) 為表中最后一個元素，無后驅元素；對于 \(1<i<n\) ， \(a_{i-1}\) 為 \(a_{i}\) 的直接前驅， \(a_{i+1}\) 為 \(a_{i}\) 的直接后驅
4. 基本操作 \(Operations\)
  1. 求線性表的長度 Lenlist(L)
  2. 獲取線性表中的元素 GetElem(L , i)
  3. 通過值來查找線性表當中的元素 SearchElem(L , Val)
  4. 插入元素 InsertElem(L , i , Elem)
  5. 洗掉元素 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]
}

連續存盤的優缺點
1. 優點
  1. 順序表的存盤結構簡單
  2. 隨機存盤，按位置取值速度快
  3. 存盤效率高，無需增加邏輯關系的占用空間
2. 缺點
  1. 洗掉插入速度慢
  2. 預先分配記憶體大

\(\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 = https://www.cnblogs.com/RadiumGalaxy/archive/2022/10/03/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 = https://www.cnblogs.com/RadiumGalaxy/archive/2022/10/03/_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--> D(p) D-.->E(NULL)

反轉箭頭為：

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 的箭頭倒轉；

graph LR A(1)-->B(2) B-.-C(k -1) C-.-> D(k) D==>C E(k+1)-->D F(n)-.->E

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;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/510889.html

標籤：其他

上一篇：漢諾塔問題分治求解

下一篇：Go設計模式學習準備——下載bilibili合集視頻

02 線性表 | 資料結構與演算法

1. 線性表

2. \(Applications\)