【数据结构之线性表】

一、线性表的基本概念

1. 定义

线性表是一种最基本的数据结构，它由相同类型的元素按顺序排列而成。在计算机内存中，这些元素被依次存放，形成一个线性序列。线性表可以用来表示一系列有序的数据，如整数、字符、对象等。

2. 特点

2.1 元素有序排列

线性表中的元素按照某种顺序依次排列。每个元素都有一个唯一的位置，通常从第一个元素到最后一个元素的顺序排列，这些位置用索引标识。在数组中，这种索引从0开始，而在链表中，则由节点指针来确定顺序。

2.2 元素类型相同

线性表中的所有元素必须是相同类型的。这种同质性保证了数据的一致性和操作的统一性。例如，一个整数型线性表只能存储整数，不能混合存储其他类型的数据。这个特点使得线性表在处理一类数据时具有很高的效率和简洁性。

2.3 元素之间存在一对一的关系

在线性表中，每个元素都有一个前驱（除了第一个元素）和一个后继（除了最后一个元素）。这种一对一的关系确保了线性表的结构简单明了。在内存中，这种关系可以通过数组的索引或者链表的节点指针来体现。这种特性使得线性表在执行插入、删除等操作时非常直观，但也使得某些操作（如中间插入和删除）可能比较耗时，特别是在顺序存储结构中。

二、线性表的实现方式（C++）

在C++中，线性表可以通过两种主要方式来实现：顺序表（数组）和链表。每种方式都有其独特的优点和缺点，根据不同的应用场景，选择合适的实现方式能够显著提高程序的效率和灵活性。

1. 顺序表（数组）

顺序表是一种使用连续的内存空间来存储数据的线性表。在C++中，顺序表通常通过数组来实现。

1.1 定义

顺序表通过一个数组来存储所有元素。每个元素都占据数组的一个位置，这些位置由连续的内存地址表示。顺序表的大小在初始化时确定，因此它的容量是固定的。

1.2 实现示例

#include <iostream>
using namespace std;class SequenceList {
private:int *array;int capacity;int size;public:SequenceList(int capacity) {this->capacity = capacity;size = 0;array = new int[capacity];}~SequenceList() {delete[] array;}void insert(int value) {if (size < capacity) {array[size++] = value;} else {cout << "List is full" << endl;}}int get(int index) {if (index >= 0 && index < size) {return array[index];} else {throw out_of_range("Index out of range");}}void display() {for (int i = 0; i < size; ++i) {cout << array[i] << " ";}cout << endl;}
};int main() {SequenceList list(10);list.insert(1);list.insert(2);list.insert(3);list.display();cout << "Element at index 1: " << list.get(1) << endl;return 0;
}

1.3 优点

• 随机访问速度快: 由于数组中的元素具有连续的内存地址，可以通过元素的索引直接访问，这使得随机访问非常高效，时间复杂度为O(1)。

1.4 缺点

• 插入和删除操作较慢: 由于数组大小固定，在进行插入或删除操作时，可能需要移动大量元素来腾出空间或填补空缺，这使得这些操作的时间复杂度为O(n)。
• 固定大小: 数组的大小在创建时确定，如果需要存储的元素超过了数组的容量，就需要重新分配内存，这可能导致性能开销。

2. 链表

链表是一种使用节点存储数据的线性表，每个节点包含数据和指向下一个节点的指针。在C++中，链表通常通过类或结构体来实现。

2.1 定义

链表由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的第一个节点称为头节点，最后一个节点的指针为NULL，表示链表的结束。

2.2 实现示例

#include <iostream>
using namespace std;class Node {
public:int data;Node* next;Node(int value) : data(value), next(nullptr) {}
};class LinkedList {
private:Node* head;public:LinkedList() : head(nullptr) {}~LinkedList() {Node* current = head;Node* next;while (current != nullptr) {next = current->next;delete current;current = next;}}void insert(int value) {Node* newNode = new Node(value);newNode->next = head;head = newNode;}void display() {Node* current = head;while (current != nullptr) {cout << current->data << " ";current = current->next;}cout << endl;}
};int main() {LinkedList list;list.insert(1);list.insert(2);list.insert(3);list.display();return 0;
}

2.3 优点

• 插入和删除操作快: 链表中的插入和删除操作只涉及节点指针的修改，不需要移动其他元素，因此这些操作的时间复杂度为O(1)（假设已找到插入或删除位置）。

2.4 缺点

• 随机访问速度慢: 链表不支持随机访问，要访问特定位置的元素，必须从头节点开始逐个遍历，时间复杂度为O(n)。
• 内存占用多: 每个节点除了存储数据外，还需要存储一个指针，这会增加额外的内存开销。

三、线性表的操作

1. 增加操作

1.1 在顺序表中增加元素

在顺序表（数组）中增加元素通常涉及将新元素插入到现有数据的指定位置，并调整数组中的元素。

实现示例

#include <iostream>
using namespace std;class SequenceList {
private:int *array;int capacity;int size;public:SequenceList(int capacity) {this->capacity = capacity;size = 0;array = new int[capacity];}~SequenceList() {delete[] array;}void insert(int value, int index) {if (index < 0 || index > size || size >= capacity) {cout << "Invalid index or list is full" << endl;return;}for (int i = size; i > index; --i) {array[i] = array[i - 1];}array[index] = value;++size;}void display() {for (int i = 0; i < size; ++i) {cout << array[i] << " ";}cout << endl;}
};int main() {SequenceList list(10);list.insert(1, 0);list.insert(2, 1);list.insert(3, 1);  // Insert 3 at index 1list.display();return 0;
}

1.2 在链表中增加节点

在链表中增加节点通常涉及创建一个新节点，并将其插入到链表的指定位置。

实现示例

#include <iostream>
using namespace std;class Node {
public:int data;Node* next;Node(int value) : data(value), next(nullptr) {}
};class LinkedList {
private:Node* head;public:LinkedList() : head(nullptr) {}~LinkedList() {Node* current = head;Node* next;while (current != nullptr) {next = current->next;delete current;current = next;}}void insert(int value, int index) {Node* newNode = new Node(value);if (index == 0) {newNode->next = head;head = newNode;return;}Node* current = head;for (int i = 0; i < index - 1 && current != nullptr; ++i) {current = current->next;}if (current == nullptr) {cout << "Index out of bounds" << endl;delete newNode;return;}newNode->next = current->next;current->next = newNode;}void display() {Node* current = head;while (current != nullptr) {cout << current->data << " ";current = current->next;}cout << endl;}
};int main() {LinkedList list;list.insert(1, 0);list.insert(2, 1);list.insert(3, 1);  // Insert 3 at index 1list.display();return 0;
}

2. 删除操作

2.1 删除顺序表中的元素

删除顺序表中的元素涉及将指定位置的元素移除，并调整其后的所有元素。

实现示例

#include <iostream>
using namespace std;class SequenceList {
private:int *array;int capacity;int size;public:SequenceList(int capacity) {this->capacity = capacity;size = 0;array = new int[capacity];}~SequenceList() {delete[] array;}void remove(int index) {if (index < 0 || index >= size) {cout << "Invalid index" << endl;return;}for (int i = index; i < size - 1; ++i) {array[i] = array[i + 1];}--size;}void display() {for (int i = 0; i < size; ++i) {cout << array[i] << " ";}cout << endl;}
};int main() {SequenceList list(10);list.insert(1, 0);list.insert(2, 1);list.insert(3, 2);list.remove(1);  // Remove element at index 1list.display();return 0;
}

2.2 删除链表中的节点

在链表中删除节点通常涉及调整指针以绕过被删除的节点。

实现示例

#include <iostream>
using namespace std;class Node {
public:int data;Node* next;Node(int value) : data(value), next(nullptr) {}
};class LinkedList {
private:Node* head;public:LinkedList() : head(nullptr) {}~LinkedList() {Node* current = head;Node* next;while (current != nullptr) {next = current->next;delete current;current = next;}}void remove(int index) {if (index < 0 || head == nullptr) {cout << "Invalid index or list is empty" << endl;return;}Node* temp;if (index == 0) {temp = head;head = head->next;delete temp;return;}Node* current = head;for (int i = 0; i < index - 1 && current != nullptr; ++i) {current = current->next;}if (current == nullptr || current->next == nullptr) {cout << "Index out of bounds" << endl;return;}temp = current->next;current->next = temp->next;delete temp;}void display() {Node* current = head;while (current != nullptr) {cout << current->data << " ";current = current->next;}cout << endl;}
};int main() {LinkedList list;list.insert(1, 0);list.insert(2, 1);list.insert(3, 2);list.remove(1);  // Remove element at index 1list.display();return 0;
}

3. 查询操作

3.1 顺序访问和随机访问

在顺序表中，可以通过索引进行随机访问，而在链表中只能顺序访问。

顺序访问示例（链表）

#include <iostream>
using namespace std;// 链表节点类
class Node {
public:int data;Node* next;Node(int value) : data(value), next(nullptr) {}
};// 链表类
class LinkedList {
private:Node* head;
public:LinkedList() : head(nullptr) {}// 添加节点到链表末尾void append(int value) {Node* newNode = new Node(value);if (head == nullptr) {head = newNode;} else {Node* current = head;while (current->next != nullptr) {current = current->next;}current->next = newNode;}}// 顺序访问链表中的元素void sequentialAccess(int position) {if (position < 0) {cout << "Invalid position." << endl;return;}Node* current = head;int index = 0;while (current != nullptr) {if (index == position) {cout << "Element at position " << position << ": " << current->data << endl;return;}current = current->next;index++;}cout << "Position out of range." << endl;}// 打印链表中的所有元素void printList() {Node* current = head;while (current != nullptr) {cout << current->data << " -> ";current = current->next;}cout << "null" << endl;}
};int main() {LinkedList list;list.append(10);list.append(20);list.append(30);list.append(40);list.printList();  // 输出链表中的所有元素list.sequentialAccess(2);  // 顺序访问链表中的第2个元素list.sequentialAccess(5);  // 尝试访问链表中超出范围的元素return 0;
}

随机访问示例（顺序表）

#include <iostream>
using namespace std;class SequenceList {
private:int *array;int capacity;int size;public:SequenceList(int capacity) {this->capacity = capacity;size = 0;array = new int[capacity];}~SequenceList() {delete[] array;}int get(int index) {if (index < 0 || index >= size) {throw out_of_range("Index out of range");}return array[index];}void display() {for (int i = 0; i < size; ++i) {cout << array[i] << " ";}cout << endl;}
};int main() {SequenceList list(10);list.insert(1, 0);list.insert(2, 1);list.insert(3, 2);cout << "Element at index 1: " << list.get(1) << endl;return 0;
}

3.2 查找特定元素的位置

在顺序表中可以直接使用索引获取元素，而在链表中则需要遍历链表。

查找特定元素位置示例（链表）

#include <iostream>
using namespace std;class Node {
public:int data;Node* next;Node(int value) : data(value), next(nullptr) {}
};class LinkedList {
private:Node* head;public:LinkedList() : head(nullptr) {}~LinkedList() {Node* current = head;Node* next;while (current != nullptr) {next = current->next;delete current;current = next;}}int find(int value) {Node* current = head;int index = 0;while (current != nullptr) {if (current->data == value) {return index;}current = current->next;++index;}return -1;  // Element not found}void display() {Node* current = head;while (current != nullptr) {cout << current->data << " ";current =current->next;}cout << endl;}
};int main() {LinkedList list;list.insert(1, 0);list.insert(2, 1);list.insert(3, 2);cout << "Index of element 2: " << list.find(2) << endl;return 0;
}

4. 修改操作

4.1 修改顺序表中某个位置的元素

在顺序表中，修改某个位置的元素非常简单，只需通过索引直接访问并赋值。

实现示例

#include <iostream>
using namespace std;class SequenceList {
private:int *array;int capacity;int size;public:SequenceList(int capacity) {this->capacity = capacity;size = 0;array = new int[capacity];}~SequenceList() {delete[] array;}void set(int index, int value) {if (index < 0 || index >= size) {cout << "Index out of range" << endl;return;}array[index] = value;}void display() {for (int i = 0; i < size; ++i) {cout << array[i] << " ";}cout << endl;}
};int main() {SequenceList list(10);list.insert(1, 0);list.insert(2, 1);list.set(1, 5);  // Change element at index 1 to 5list.display();return 0;
}

4.2 修改链表中某个位置的元素

在链表中，修改某个位置的元素需要遍历链表到达该位置，然后进行修改。

实现示例

#include <iostream>
using namespace std;class Node {
public:int data;Node* next;Node(int value) : data(value), next(nullptr) {}
};class LinkedList {
private:Node* head;public:LinkedList() : head(nullptr) {}~LinkedList() {Node* current = head;Node* next;while (current != nullptr) {next = current->next;delete current;current = next;}}void set(int index, int value) {Node* current = head;for (int i = 0; i < index && current != nullptr; ++i) {current = current->next;}if (current != nullptr) {current->data = value;} else {cout << "Index out of range" << endl;}}void display() {Node* current = head;while (current != nullptr) {cout << current->data << " ";current = current->next;}cout << endl;}
};int main() {LinkedList list;list.insert(1, 0);list.insert(2, 1);list.set(1, 5);  // Change element at index 1 to 5list.display();return 0;
}

四、线性表的优势与局限

1. 优势

1.1 简单易用

线性表的结构非常直观，尤其是顺序表（如数组）和链表，其概念易于理解和实现。

• 顺序表: 使用连续的内存空间存储数据，数据存取简单，代码实现易于理解。
• 链表: 使用节点链式连接，可以灵活管理内存，无需考虑数组的容量限制。

示例:

• 顺序表：适用于对固定数量数据进行快速访问和操作的场景，如静态配置数据、日历数据等。
• 链表：适用于动态数据管理，如动态队列、链式栈等。

1.2 适合存储和管理有序数据

线性表中的元素具有明确的顺序，适合用于存储和管理有序数据集。

• 顺序性: 数据按照插入顺序存储，方便进行顺序遍历和操作。
• 一致性: 数据类型一致，便于进行批量操作和处理。

应用场景:

• 排序算法中的数据存储
• 图形绘制中的点阵数据
• 数据记录和日志管理

2. 局限

2.1 顺序表扩展性差

顺序表（数组）的大小通常是固定的，在插入新元素时可能需要重新分配内存空间，这会导致性能下降。

• 内存管理: 扩展顺序表的容量时，需要重新分配更大的数组，并将原数据复制到新数组中。
• 时间复杂度: 插入和删除操作可能导致大量数据移动，时间复杂度为 O(n)。

示例:

#include <iostream>
#include <vector>
using namespace std;int main() {vector<int> vec;for (int i = 0; i < 100; ++i) {vec.push_back(i);  // 当容量不足时，vector 会自动扩展容量}cout << "Vector size: " << vec.size() << endl;return 0;
}

2.2 链表的随机访问效率低

链表不支持快速随机访问，需要从头节点开始顺序遍历到目标位置，访问效率较低。

• 遍历性能: 由于链表的节点是链式存储，无法直接访问任意位置的节点，只能逐一遍历，时间复杂度为 O(n)。
• 内存消耗: 链表的每个节点除了存储数据外，还需要存储指针信息，导致内存开销较大。

示例:

#include <iostream>
using namespace std;class Node {
public:int data;Node* next;Node(int value) : data(value), next(nullptr) {}
};int main() {Node* head = new Node(1);head->next = new Node(2);head->next->next = new Node(3);Node* current = head;int index = 0;int targetIndex = 2;while (current != nullptr && index < targetIndex) {current = current->next;index++;}if (current != nullptr) {cout << "Element at index " << targetIndex << ": " << current->data << endl;} else {cout << "Index out of range" << endl;}return 0;
}

五、线性表与其他数据结构的比较

线性表是基本的数据结构之一，在计算机科学中还有许多其他常用的数据结构，如栈、队列、树等。了解这些数据结构之间的差异和优缺点，可以帮助开发者在实际应用中选择最合适的结构。

1. 线性表 vs. 栈

线性表

• 操作: 支持在任意位置进行插入、删除、查询和修改操作。
• 访问: 可以随机访问任意位置的元素。
• 实现: 顺序表（数组）和链表是线性表的常见实现。

栈

• 操作: 仅支持在栈顶进行插入和删除操作，遵循后进先出（LIFO）的原则。
• 访问: 只能访问栈顶的元素，不支持随机访问。
• 实现: 通常使用数组或链表实现。

示例比较:

• 线性表: 可以访问和操作任意位置的元素，如array[3] = 10。
• 栈: 只能操作栈顶的元素，如stack.push(10)、stack.pop()。

// 栈的基本实现
#include <iostream>
#include <stack>
using namespace std;int main() {stack<int> s;s.push(1);  // 压入栈顶s.push(2);cout << "Top element: " << s.top() << endl;  // 访问栈顶元素s.pop();  // 弹出栈顶元素cout << "Top element after pop: " << s.top() << endl;return 0;
}

2. 线性表 vs. 队列

线性表

• 操作: 支持任意位置的插入、删除、查询和修改操作。
• 访问: 可以随机访问任意位置的元素。

队列

• 操作: 仅支持在队列两端进行操作：一端入队（enqueue），另一端出队（dequeue），遵循先进先出（FIFO）的原则。
• 访问: 只能访问队头和队尾的元素，不支持随机访问。
• 实现: 通常使用数组或链表实现。

示例比较:

• 线性表: 可以对任意位置进行插入和删除，如list.insert(3, value)。
• 队列: 只能进行队列头尾的操作，如queue.push(value)、queue.pop()。

// 队列的基本实现
#include <iostream>
#include <queue>
using namespace std;int main() {queue<int> q;q.push(1);  // 入队q.push(2);cout << "Front element: " << q.front() << endl;  // 访问队头元素q.pop();  // 出队cout << "Front element after pop: " << q.front() << endl;return 0;
}

3. 线性表 vs. 树

线性表

• 关系: 元素之间存在线性关系，只有前驱和后继元素。
• 结构: 简单的线性结构，不支持分支或层次结构。

树

• 关系: 支持层次和分支结构，节点之间有父子关系，可以有多个子节点。
• 结构: 复杂的数据结构，常见的有二叉树、B树等，支持更复杂的数据关系。

示例比较:

• 线性表: 用于存储简单的线性数据，如列表、队列。
• 树: 用于表示层次化的数据，如组织结构、文件系统目录。

// 二叉树的基本节点定义
#include <iostream>
using namespace std;struct TreeNode {int data;TreeNode* left;TreeNode* right;TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};int main() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);cout << "Root node data: " << root->data << endl;cout << "Left child data: " << root->left->data << endl;cout << "Right child data: " << root->right->data << endl;return 0;
}