以“工具设计者”角色,给出“链式线性表”的创建 Create、显示 Display、插入 Insert、删除 Delete、合并 Merge 接口函数的程序代码
时间: 2023-06-14 11:03:32 浏览: 77
假设链式线性表的节点结构体定义如下:
```c++
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
```
则可以定义链式线性表类 `LinkedList`,并在其中实现相关的接口函数,代码如下:
```c++
class LinkedList {
public:
// 创建链式线性表
ListNode* create(int n) {
if (n <= 0) {
return nullptr;
}
ListNode* head = new ListNode(-1);
ListNode* cur = head;
for (int i = 0; i < n; ++i) {
int val;
cin >> val;
cur->next = new ListNode(val);
cur = cur->next;
}
return head->next;
}
// 显示链式线性表
void display(ListNode* head) {
while (head != nullptr) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
// 插入节点
ListNode* insert(ListNode* head, int pos, int val) {
if (pos < 0) {
return head;
}
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* prev = dummy;
for (int i = 0; i < pos; ++i) {
if (prev->next == nullptr) {
return head;
}
prev = prev->next;
}
ListNode* cur = prev->next;
prev->next = new ListNode(val);
prev->next->next = cur;
return dummy->next;
}
// 删除节点
ListNode* remove(ListNode* head, int pos) {
if (pos < 0) {
return head;
}
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* prev = dummy;
for (int i = 0; i < pos; ++i) {
if (prev->next == nullptr) {
return head;
}
prev = prev->next;
}
ListNode* cur = prev->next;
if (cur == nullptr) {
return head;
}
prev->next = cur->next;
delete cur;
return dummy->next;
}
// 合并两个链式线性表
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while (head1 != nullptr && head2 != nullptr) {
if (head1->val < head2->val) {
cur->next = head1;
head1 = head1->next;
} else {
cur->next = head2;
head2 = head2->next;
}
cur = cur->next;
}
if (head1 != nullptr) {
cur->next = head1;
} else {
cur->next = head2;
}
return dummy->next;
}
};
```
其中,`create` 函数用于创建链式线性表,`display` 函数用于显示链式线性表,`insert` 函数用于在指定位置插入节点,`remove` 函数用于删除指定位置的节点,`merge` 函数用于合并两个链式线性表。这些函数可以根据具体的需求进行调用。
阅读全文