1.产生20个1到200的随机整数,并依次保存到带头结点的单链表中 2.计算单链表的长度,并将结果存放在头结点的数据域中,然后输出单链表 3.从单链表中删除与给定值x相等的所有结点,然后输出单链表 4.在3题的基础上将单链表降序排列,并输出结果
时间: 2024-10-08 21:26:36 浏览: 98
小白算法积累——单链表15#2个带头结点单链表+提取公共元素+二表合一
要实现这个功能,我们可以使用C语言中的`stdlib.h`库来生成随机数,`stdio.h`库来输入和输出数据,以及自己编写链表结构和操作。下面是逐步说明:
1. 首先,我们需要定义链表节点结构并初始化一个带头结点的链表。
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* createList() {
Node* head = (Node*)malloc(sizeof(Node));
head->data = 0;
head->next = NULL;
srand(time(0)); // 初始化随机数种子
for (int i = 0; i < 20; ++i) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = rand() % 200 + 1; // 生成1到200之间的随机数
newNode->next = head->next;
head->next = newNode;
}
return head;
}
```
2. 计算链表长度并将结果存储在头结点的`data`域中,然后遍历输出链表。
```c
void printList(Node* head) {
int length = 0;
Node* current = head->next;
while (current != NULL) {
++length;
current = current->next;
}
head->data = length;
printf("链表长度: %d\n", head->data);
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
```
3. 删除与给定值`x`相等的节点,并输出更新后的链表。
```c
void deleteNodes(Node** head, int x) {
Node* current = *head;
Node* prev = NULL;
while (current != NULL) {
if (current->data == x) {
if (prev == NULL) {
*head = current->next;
} else {
prev->next = current->next;
}
free(current);
current = current->next;
} else {
prev = current;
current = current->next;
}
}
}
void printUpdatedList(Node* head) {
printList(head);
}
```
4. 对于第3题的链表降序排列,这通常涉及到复杂的排序算法(如快速排序、归并排序),但由于链表不适合原地排序,我们可能需要创建一个新的链表。这里使用冒泡排序简化处理:
```c
// 注意:这个版本只适用于链表中的数值不大,不适用于大规模数据
void bubbleSort(Node* head) {
if (head == NULL || head->next == NULL) return;
Node* end = head;
while (end->next != NULL) {
end = end->next;
}
for (Node* start = head; start != end; start = start->next) {
for (Node* iter = start; iter->next != NULL && iter->next->data > iter->data; iter = iter->next) {
int temp = iter->data;
iter->data = iter->next->data;
iter->next->data = temp;
}
}
}
void printSortedList(Node* head) {
printList(head);
}
```
现在你可以根据这些函数完成整个程序:
```c
int main() {
Node* head = createList();
printList(head);
int x;
printf("请输入一个值进行删除操作: ");
scanf("%d", &x);
deleteNodes(&head, x);
printUpdatedList(head);
bubbleSort(head);
printSortedList(head);
return 0;
}
```
阅读全文