分别用头插法和尾插法创建并输出带附加头结点的单链表。 头插法是指每个新元素都插入到链表的最前面,即头结点和链表第一个元素之间; 尾插法指的是每个新元素都插入到链表的最后面。
时间: 2024-05-05 11:19:33 浏览: 61
好的,关于你的问题,我来给你讲一下:
头插法创建带附加头结点的单链表
```C++
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val; // 数据域
ListNode* next; // 指针域
ListNode(int x): val(x), next(nullptr) {} // 构造函数
};
// 头插法创建链表
ListNode* createListHead() {
ListNode* head = new ListNode(0); // 头结点,数据域设为0
int n, val;
cout << "请输入要插入的节点个数: ";
cin >> n;
cout << "请依次输入要插入的节点的值: ";
for (int i = 0; i < n; i++) {
cin >> val;
ListNode* node = new ListNode(val);
node->next = head->next;
head->next = node;
}
return head;
}
// 遍历链表
void printList(ListNode* head) {
ListNode* cur = head->next;
while (cur != nullptr) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
int main() {
ListNode* head = createListHead();
cout << "头插法创建的链表:";
printList(head);
return 0;
}
```
在控制台输入:
```
请输入要插入的节点个数: 5
请依次输入要插入的节点的值: 1 2 3 4 5
```
输出:
```
头插法创建的链表:5 4 3 2 1
```
尾插法创建带附加头结点的单链表
```C++
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val; // 数据域
ListNode* next; // 指针域
ListNode(int x): val(x), next(nullptr) {} // 构造函数
};
// 尾插法创建链表
ListNode* createListTail() {
ListNode* head = new ListNode(0); // 头结点,数据域设为0
ListNode* tail = head; // 指向尾节点
int n, val;
cout << "请输入要插入的节点个数: ";
cin >> n;
cout << "请依次输入要插入的节点的值: ";
for (int i = 0; i < n; i++) {
cin >> val;
ListNode* node = new ListNode(val);
tail->next = node;
tail = tail->next;
}
return head;
}
// 遍历链表
void printList(ListNode* head) {
ListNode* cur = head->next;
while (cur != nullptr) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
int main() {
ListNode* head = createListTail();
cout << "尾插法创建的链表:";
printList(head);
return 0;
}
```
在控制台输入:
```
请输入要插入的节点个数: 5
请依次输入要插入的节点的值: 1 2 3 4 5
```
输出:
```
尾插法创建的链表:1 2 3 4 5
```
这两种方法都是常用的单链表创建方法,需要注意的是带附加头结点的单链表相较于没有头结点的单链表更加方便编写和更容易理解。
阅读全文