单元2
下面是一个简洁的 C++ 程序示例,展示了**顺序表(使用 vector)和链表(使用自定义单向链表)**的基本操作对比,包括插入、删除和访问元素:
🧪 顺序表 vs 链表:C++ 示例对比 ✅ 顺序表(使用 std::vector) #include <iostream> #include <vector> using namespace std; int main() { vector<int> seqList; // 插入元素 seqList.push_back(10); seqList.push_back(20); seqList.push_back(30); // 删除元素(删除第二个) seqList.erase(seqList.begin() + 1); // 访问元素 for (int i = 0; i < seqList.size(); ++i) { cout << "顺序表元素[" << i << "] = " << seqList[i] << endl; } return 0; } ✅ 链表(自定义单向链表) #include <iostream> using namespace std; struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; void insert(Node*& head, int val) { Node* newNode = new Node(val); newNode->next = head; head = newNode; } void deleteNode(Node*& head, int val) { Node* curr = head; Node* prev = nullptr; while (curr) { if (curr->data == val) { if (prev) prev->next = curr->next; else head = curr->next; delete curr; return; } prev = curr; curr = curr->next; } } void printList(Node* head) { int index = 0; while (head) { cout << "链表元素[" << index++ << "] = " << head->data << endl; head = head->next; } } int main() { Node* head = nullptr; // 插入元素(头插法) insert(head, 30); insert(head, 20); insert(head, 10); // 删除元素(删除值为 20 的节点) deleteNode(head, 20); // 打印链表 printList(head); return 0; } 📊 对比总结 特性 顺序表(vector) 链表(自定义) 插入效率 中间插入需移动元素,较慢 修改指针即可,效率高 删除效率 删除需移动元素 修改指针即可 随机访问 支持 O(1) 下标访问 需遍历,O(n) 内存结构 连续内存,缓存友好 分散内存,灵活扩展 实现复杂度 简单(STL支持) 需手动管理指针 单链表中,做插入数据的操作时,是否需要同时做两处数据的操作? 也就是修改前一个数据的后置链接指向,并增加新数据,例如在数据A和B之间插入C,首先要生成新的数据C,其后驱指针指向B,再修改前一个数据A的后驱指针,删除其与B的链接,建立与C的链接。 此外删除操作也是类似的的需要修改两处,该规则适用于双链表和循环链表。
...