用带头结点的单链表实现查找序号为i(1≤i≤n)的元素 ,查找第一个值为x的元素,插入第i(2≤i≤n)个元素,删除第i(2≤i≤n)个元素 (c++)
时间: 2024-01-24 17:05:26 浏览: 139
3-2 试编写一个算法,在带表头结点的单链表中寻找第i个结点.doc
好的,我会根据您的要求进行回答。以下是带头结点的单链表实现的代码:
```c++
#include <iostream>
using namespace std;
// 定义链表结点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 查找序号为i的元素
ListNode* findNode(ListNode* head, int i) {
if (!head) return NULL;
ListNode* node = head->next;
int count = 1;
while (node && count < i) {
node = node->next;
count++;
}
return node;
}
// 查找值为x的元素
ListNode* findNode(ListNode* head, int x) {
if (!head) return NULL;
ListNode* node = head->next;
while (node && node->val != x) {
node = node->next;
}
return node;
}
// 插入第i个元素
bool insertNode(ListNode* head, int i, int val) {
ListNode* prev = findNode(head, i - 1);
if (!prev) return false;
ListNode* node = new ListNode(val);
node->next = prev->next;
prev->next = node;
return true;
}
// 删除第i个元素
bool deleteNode(ListNode* head, int i) {
ListNode* prev = findNode(head, i - 1);
if (!prev || !prev->next) return false;
ListNode* node = prev->next;
prev->next = node->next;
delete node;
return true;
}
// 打印链表
void printList(ListNode* head) {
if (!head) return;
ListNode* node = head->next;
while (node) {
cout << node->val << " ";
node = node->next;
}
cout << endl;
}
int main() {
ListNode* head = new ListNode(0);
ListNode* node1 = new ListNode(1);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(3);
ListNode* node4 = new ListNode(4);
head->next = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
cout << "原链表:";
printList(head);
cout << "第3个元素为:" << findNode(head, 3)->val << endl;
cout << "值为3的元素为:" << findNode(head, 3)->val << endl;
insertNode(head, 2, 5);
cout << "插入元素5后的链表:";
printList(head);
deleteNode(head, 3);
cout << "删除第3个元素后的链表:";
printList(head);
return 0;
}
```
希望这段代码能够帮到您,如果您有其他问题,请随时提出。
阅读全文