本题要求实现两个函数,分别将读入的数据存储为单链表、将链表中所有存储了某给定值的结点删除。链表结点定义如下: struct ListNode { int data; ListNode *next; };
时间: 2024-03-12 20:48:00 浏览: 80
【数据结构作业二】写出单链表结点的结构体类型定义及查找、插入、删除算法,并以单链表作存储结。。。 定义线性表节点的结构.pdf
好的,以下是两个函数的实现:
```c++
#include <iostream>
using namespace std;
// 链表结点定义
struct ListNode {
int data;
ListNode *next;
};
// 将读入的数据存储为单链表
ListNode* createList() {
ListNode *head = NULL; // 头指针
ListNode *p, *q; // 指针变量
int x;
while (1) {
cin >> x;
if (x == -1) {
break;
}
p = new ListNode;
p->data = x;
p->next = NULL;
if (head == NULL) {
head = p; // 空链表
} else {
q->next = p;
}
q = p;
}
return head;
}
// 将链表中所有存储了某给定值的结点删除
ListNode* removeNodes(ListNode *head, int value) {
ListNode *p, *q;
// 删除链表头部所有值为value的结点
while (head != NULL && head->data == value) {
p = head;
head = head->next;
delete p;
}
// 删除链表中间和尾部所有值为value的结点
p = head;
while (p != NULL && p->next != NULL) {
if (p->next->data == value) {
q = p->next;
p->next = q->next;
delete q;
} else {
p = p->next;
}
}
return head;
}
// 遍历并输出链表
void traverseList(ListNode *head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
ListNode *head = createList(); // 创建链表
int value;
cin >> value;
head = removeNodes(head, value); // 删除指定结点
traverseList(head); // 遍历并输出链表
return 0;
}
```
输入格式为:
```
1 2 3 4 3 -1
3
```
其中 `-1` 表示输入结束,第一个数字是链表的第一个结点的值。输出结果为删除指定结点后的链表内容,如果链表为空则输出空行。
如果需要使用 C 语言实现,只需要稍微修改一下代码即可。
阅读全文