【第二節】C/C++數據結構之線性表

一、線性表基本說明

1.1 基本概念

1.2 抽象數據類型

1.3 存儲結構

1.4 插入與刪除的區別

1.5 順序存儲和鏈式存儲的優缺點

二、鏈表

2.1 基本概念

2.2 抽象數據類型

2.3 單鏈表的定義

2.4 單鏈表的基本操作

2.5 單鏈表模板形式的類定義與實現

三、單向循環鏈表

四、雙鏈表、雙向循環鏈表

一、線性表基本說明

1.1 基本概念

????????線性表,零個或多個數據元素的有限序列稱為線性表,例如一個字符串就是一個線性表比如一個結構體數組也是一個線性表。

1.2 抽象數據類型

ADT 線性表(List)
Data
除第一個元素外，每一個元素有且只有一個直接前驅元素,除了最后一個元素外，每個元素有且只有一個直接后繼元素，數據元素之間的關系是一對一的關系
Operation
初始化操作，建立一個空的線性表
若線性表為空，返回true，否則返回false
將線性表清空
將線性表中的第i個位置元素值返回給e在線性表中查找與給定值e相等的元素，成功返回序號，否則返回0在線性表中的第i個位置中插入新元素
在線性表中刪除第i個位置的元素，并用e返回其值
返回線性表L的元素個數
endADT

1.3 存儲結構

線性表的順序存儲

????????線性表的順序存儲結構，是指使用一段地址連續的存儲單元依次存儲線性表的數據元素。這種存儲方式通常通過數組（Array）來實現，其中數組的每個元素都對應線性表中的一個數據元素。

????????在數組中，數據元素按照其在線性表中的邏輯順序存儲，即第一個數據元素存儲在數組的第一個位置，第二個數據元素存儲在第二個位置，依此類推。這種存儲方式使得我們可以通過數組的索引直接訪問線性表中的任何數據元素，而不需要遍歷整個線性表。

????????需要注意的是，數組的總長度（即數據空間的總長度）并不一定等于線性表的長度。線性表的長度是指線性表中實際存儲的數據元素個數，而數組的長度是數組中可以存儲的最大數據元素個數。因此，數組的長度通常大于線性表的長度，以便在需要時可以動態擴展。

????????在實際編程中，我們通常會使用動態數組（Dynamic Array）來實現線性表的順序存儲結構，以便在需要時可以動態調整數組的大小。例如，當線性表的長度超過數組的長度時，可以創建一個新的更大的數組，并將原數組中的數據元素復制到新數組中。

線性表的鏈式存儲

????????線性表的鏈式存儲結構，是指使用鏈表（Linked List）來存儲線性表的數據元素。在鏈式存儲結構中，每個數據元素都包含一個數據項和一個指向下一個數據元素的指針。這種存儲方式可以靈活地進行插入和刪除操作，而不需要移動大量的數據。

????????鏈式存儲結構的優點在于，當需要插入或刪除元素時，只需要修改相關節點的指針，而不需要移動大量的數據。因此，鏈式存儲結構在執行插入和刪除操作時，通常比順序存儲結構更高效。

????????然而，鏈式存儲結構也有其缺點。由于每個數據元素都包含一個指針，因此存儲空間的利用率不如順序存儲結構高。此外，鏈式存儲結構在執行查找操作時，需要從頭開始遍歷鏈表，直到找到目標元素或到達鏈表的末尾。因此，如果需要頻繁地執行查找操作，順序存儲結構可能更適合。

????????總的來說，選擇使用順序存儲結構還是鏈式存儲結構，取決于具體的應用場景。如果需要頻繁地執行插入和刪除操作，并且數據量不大，那么鏈式存儲結構可能更適合。如果需要頻繁地執行查找操作，并且數據量較大，那么順序存儲結構可能更適合。

1.4 插入與刪除的區別

順序線性表的插入與刪除:
在順序存儲結構下，線性表在插入新數據前需要將其插入點后面的數據依次后移一個單位，以空出位置讓新數據插入
在順序存儲結構下，線性表在刪除數據后需要將其刪除點后面的數據依次前移一個單位，以補足刪除后空出位置

鏈式線性表的插入與刪除:
當我們想在鏈表中插入一個新數據的時候，只需要申請一段內存空間，然后將其前一個元素的指針指向自己，再將自己的指針指向下一個元素即可，無需操作其他元素
當我們想在鏈表中刪除一個節點時，只需要將前一個節點指向后一個節點，并釋放掉自己即可

1.5 順序存儲和鏈式存儲的優缺點

順序存儲和鏈式存儲是兩種基本的數據結構，它們在存儲和訪問數據元素時各有優缺點。

順序存儲（順序結構）：

優點：順序存儲的優點在于存儲效率高，存取速度快。由于數據元素存儲在連續的內存空間中，因此可以通過下標直接訪問任何元素，無需遍歷整個數據結構。
缺點：順序存儲的缺點在于空間大小固定，不易擴充。一旦定義了存儲空間的大小，就無法改變。此外，在插入或刪除元素時，需要移動大量元素，這會降低效率。

鏈式存儲（鏈式結構）：

優點：鏈式存儲的優點在于空間利用率高，可以動態分配和釋放存儲空間。此外，在插入和刪除元素時，只需要修改鏈接指針，而不需要移動數據元素，因此效率較高。
缺點：鏈式存儲的缺點在于存取元素時需要順序查找，因此存取效率不高。此外，由于每個元素都包含一個指針，因此存儲空間的利用率不如順序存儲高。

在實際應用中，選擇順序存儲還是鏈式存儲取決于具體的應用需求。如果需要頻繁地插入和刪除元素，并且數據量不大，那么鏈式存儲可能更適合。如果需要頻繁地查找元素，并且數據量較大，那么順序存儲可能更適合。

二、鏈表

2.1 基本概念

????????鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點(鏈表中每一個元素稱為結點)組成，結點可以在運行時動態生成。
????????每個結點包括兩個部分:一個是存儲數據元素的數據域,另一個是存儲下一個結點地址
的指針域循環鏈表是另一種形式的鏈式存貯結構。它的特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。

2.2 抽象數據類型

ADT 鏈表(List)
Data
除第一個元素外，每一個元素有且只有一個直接前驅元素,除了最后一個元素外,每個元素有且只有一個直接后繼元素，數據元素之間的關系是一對一的關系
Operation
初始化操作，建立一個空的鏈表
若鏈表為空，返回true，否則返回false
將鏈表清空
將鏈表中的第i個位置元素值返回給e
在鏈表中查找與給定值e相等的元素，成功返回序號，否則返回0
在鏈表中的第i個位置中插入新元素
在鏈表中刪除第i個位置的元素，并用e返回其值
返回鏈表的元素個數
endADT

2.3 單鏈表的定義

????????鏈表中最簡單的一種是單向鏈表，它包含兩個域，一個數據域和一個指針域。這個鏈接指向列表中的下一個節點，而最后一個節點則指向一個空值。
????????單向鏈表通常由一個頭指針(head)，用于指向鏈表頭。單向鏈表有一個尾結點，該結點的指針部分指向一個空結點(NULL)。

2.4 單鏈表的基本操作

對鏈表的基本操作有:
創建鏈表是指，從無到有地建立起一個鏈表，即往空鏈表中依次插入若干結點，并保持結點之間的前驅和后繼關系。
檢索操作是指,按給定的結點索引號或檢索條件,查找某個結點。如果找到指定的結點則稱為檢索成功;否則，稱為檢索失敗。
插入操作是指，在結點之間插入一個新的結點，使線性表的長度增1。
刪除操作是指，刪除結點ki，使線性表的長度減1
打印輸出。

2.5 單鏈表模板形式的類定義與實現

代碼示例：

#include <iostream>// 定義鏈表節點結構體
template <typename T>
struct Node {T data;Node* next;Node(const T& value) : data(value), next(nullptr) {}
};// 單鏈表類模板
template <typename T>
class SingleLinkedList {
private:Node<T>* head;int size;public:SingleLinkedList() : head(nullptr), size(0) {}~SingleLinkedList() {while (head != nullptr) {Node<T>* temp = head;head = head->next;delete temp;}}// 插入元素到鏈表頭部void push_front(const T& value) {Node<T>* newNode = new Node<T>(value);newNode->next = head;head = newNode;size++;}// 刪除鏈表頭部元素void pop_front() {if (head != nullptr) {Node<T>* temp = head;head = head->next;delete temp;size--;}}// 查找元素Node<T>* find(const T& value) {Node<T>* current = head;while (current != nullptr) {if (current->data == value) {return current;}current = current->next;}return nullptr; // 未找到返回nullptr}// 刪除指定元素void remove(const T& value) {if (head == nullptr) return;if (head->data == value) {pop_front();return;}Node<T>* current = head;while (current->next != nullptr) {if (current->next->data == value) {Node<T>* temp = current->next;current->next = current->next->next;delete temp;size--;return;}current = current->next;}}// 獲取鏈表大小int getSize() const {return size;}// 顯示鏈表元素void display() const {Node<T>* current = head;while (current != nullptr) {std::cout << current->data << " ";current = current->next;}std::cout << std::endl;}
};// 示例使用
int main() {SingleLinkedList<int> list;// 插入元素list.push_front(10);list.push_front(20);list.push_front(30);list.display(); // 輸出: 30 20 10// 刪除元素list.pop_front();list.display(); // 輸出: 20 10// 查找元素Node<int>* foundNode = list.find(20);if (foundNode != nullptr) {std::cout << "Found: " << foundNode->data << std::endl;} else {std::cout << "Not found" << std::endl;}// 刪除指定元素list.remove(10);list.display(); // 輸出: 20// 獲取鏈表大小std::cout << "Size: " << list.getSize() << std::endl; // 輸出: Size: 1return 0;
}

????????在這個代碼中，我們定義了一個Node結構體模板來表示鏈表中的節點，每個節點包含一個數據項和一個指向下一個節點的指針。SingleLinkedList類模板定義了單鏈表的主要操作，包括構造函數、析構函數、push_front（在鏈表前端插入元素）、pop_front（從鏈表前端刪除元素）、find（查找元素）、remove（刪除指定元素）、getSize（獲取鏈表大小）和display（顯示鏈表中的所有元素）。

????????在main函數中，我們創建了一個SingleLinkedList<int>對象，并進行了一些操作，以展示如何使用這個模板類。這些操作包括插入元素、刪除元素、查找元素、顯示鏈表和獲取鏈表大小。

三、單向循環鏈表

四、雙鏈表、雙向循環鏈表

????????單向鏈表、單向循環鏈表、雙向鏈表和雙向循環鏈表都是鏈表數據結構的不同類型，它們在結構和操作上有所不同。以下是這些鏈表類型之間的主要區別：

單向鏈表:
- 每個節點包含一個數據項和一個指向下一個節點的指針。
- 鏈表的末尾節點的指針通常設置為NULL，表示鏈表的結束。
- 單向鏈表不是循環的，它只能從頭到尾遍歷。
單向循環鏈表:
- 與單向鏈表類似，但鏈表的最后一個節點的指針指向鏈表的第一個節點，形成一個循環。
- 這種類型的鏈表可以從任何節點開始遍歷，并且可以無限期地繼續。
雙向鏈表:
- 每個節點包含一個數據項、一個指向下一個節點的指針和一個指向前一個節點的指針。
- 鏈表的第一個節點的前向指針通常設置為NULL，表示鏈表的開始。
- 鏈表的最后一個節點的后向指針通常設置為NULL，表示鏈表的結束。
- 雙向鏈表可以從任意節點開始向前或向后遍歷。
雙向循環鏈表:
- 與雙向鏈表類似，但鏈表的第一個節點的后向指針指向鏈表的最后一個節點，形成一個循環。
- 鏈表的最后一個節點的前向指針指向鏈表的第一個節點，形成另一個循環。
- 雙向循環鏈表可以從任意節點開始向前或向后遍歷，并且可以無限期地繼續。