数据结构线性表链表实现C++

### C++ 实现线性表和链表数据结构 #### 线性表的顺序存储实现 线性表的顺序存储是通过一组地址连续的存储单元来存储线性表中的各个元素。以下是一个使用C++实现线性表顺序存储的示例代码，支持插入、删除和查找等功能。 ```cpp #include <iostream> #include <stdexcept> using namespace std; const int MAX_SIZE = 100; // 最大容量 class SeqList { private: int data[MAX_SIZE]; // 存储线性表元素的数组 int length; // 当前线性表的长度 public: SeqList() : length(0) {} // 构造函数初始化 // 插入元素到指定位置 bool insert(int pos, int value) { if (length >= MAX_SIZE || pos < 0 || pos > length) return false; for (int i = length; i > pos; --i) { data[i] = data[i - 1]; } data[pos] = value; ++length; return true; } // 删除指定位置的元素 bool remove(int pos) { if (pos < 0 || pos >= length) return false; for (int i = pos; i < length - 1; ++i) { data[i] = data[i + 1]; } --length; return true; } // 查找元素值，返回其位置 int search(int value) const { for (int i = 0; i < length; ++i) { if (data[i] == value) return i; } return -1; // 未找到 } // 打印线性表内容 void print() const { for (int i = 0; i < length; ++i) { cout << data[i] << " "; } cout << endl; } }; ``` 上述代码展示了如何使用数组实现线性表的顺序存储结构，并提供了插入、删除和查找功能[^2]。 --- #### 链表的实现 链表是一种动态数据结构，适合频繁插入和删除操作。以下是一个使用C++实现单链表的示例代码，同样支持插入、删除和查找等功能。 ```cpp #include <iostream> #include <stdexcept> using namespace std; struct Node { int data; // 数据域 Node* next; // 指针域 Node(int val) : data(val), next(nullptr) {} }; class LinkedList { private: Node* head; // 头指针 public: LinkedList() : head(nullptr) {} // 构造函数初始化 ~LinkedList() { // 析构函数释放内存 Node* current = head; while (current != nullptr) { Node* nextNode = current->next; delete current; current = nextNode; } } // 在链表末尾插入元素 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; } } // 删除指定值的节点 bool remove(int value) { Node* current = head; Node* prev = nullptr; while (current != nullptr && current->data != value) { prev = current; current = current->next; } if (current == nullptr) return false; // 未找到 if (prev == nullptr) { head = current->next; } else { prev->next = current->next; } delete current; return true; } // 查找指定值，返回是否找到 bool search(int value) const { Node* current = head; while (current != nullptr) { if (current->data == value) return true; current = current->next; } return false; } // 打印链表内容 void print() const { Node* current = head; while (current != nullptr) { cout << current->data << " "; current = current->next; } cout << endl; } }; ``` 上述代码展示了如何使用指针实现单链表，并提供了插入、删除和查找功能[^1]。 --- #### 总结 - 线性表的顺序存储适用于需要频繁查找且插入删除较少的场景。 - 链表适用于需要频繁插入和删除的场景，且不需要提前确定存储空间大小。 ---