(1) 用头插法(或尾插法)建立带头节点的单向链表。 (2) 对已建立的单向链表实现有关查找,插入,删除,等操作。
时间: 2024-05-05 09:20:41 浏览: 80
头插法建立单链表
以下是用头插法建立带头节点的单向链表的示例代码:
```c++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* createLinkedList() {
Node* head = new Node;
head->next = nullptr;
Node* p = head;
int num;
cout << "请输入链表中节点个数:";
cin >> num;
for (int i = 0; i < num; i++) {
int value;
cout << "请输入第 " << i + 1 << " 个节点的值:";
cin >> value;
Node* newNode = new Node;
newNode->data = value;
newNode->next = nullptr;
p->next = newNode;
p = newNode;
}
return head;
}
void printLinkedList(Node* head) {
if (head->next == nullptr) {
cout << "链表为空" << endl;
return;
}
Node* p = head->next;
while (p != nullptr) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
Node* findNode(Node* head, int value) {
Node* p = head->next;
while (p != nullptr) {
if (p->data == value) {
return p;
}
p = p->next;
}
return nullptr;
}
Node* insertNode(Node* head, int value, int position) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = nullptr;
Node* p = head;
for (int i = 0; i < position && p != nullptr; i++) {
p = p->next;
}
if (p == nullptr) {
cout << "插入位置无效" << endl;
return head;
}
newNode->next = p->next;
p->next = newNode;
return head;
}
Node* deleteNode(Node* head, int value) {
Node* p = head;
while (p->next != nullptr) {
if (p->next->data == value) {
Node* q = p->next;
p->next = q->next;
delete q;
cout << "删除成功" << endl;
return head;
}
p = p->next;
}
cout << "节点不存在" << endl;
return head;
}
int main() {
Node* head = createLinkedList();
cout << "链表中的节点为:";
printLinkedList(head);
cout << "请输入要查找的节点的值:";
int value;
cin >> value;
Node* node = findNode(head, value);
if (node == nullptr) {
cout << "节点不存在" << endl;
} else {
cout << "节点存在" << endl;
}
cout << "请输入要插入的节点的值和位置:";
int newValue, position;
cin >> newValue >> position;
head = insertNode(head, newValue, position);
cout << "插入节点后的链表为:";
printLinkedList(head);
cout << "请输入要删除的节点的值:";
cin >> value;
head = deleteNode(head, value);
cout << "删除节点后的链表为:";
printLinkedList(head);
return 0;
}
```
示例代码实现了创建、打印、查找、插入和删除带头节点的单向链表的功能。其中,查找操作返回找到的节点,如果节点不存在则返回 `nullptr`;插入操作在指定位置插入新节点,如果插入位置无效则不进行插入;删除操作删除指定节点,如果节点不存在则不进行删除。
阅读全文