请用C语言实现:在一个有序(按非递减顺序)的链表中插入一个元素为x的结点,使插入后的链表仍然有序(链表数据域为整型数,N为6)。 **输入提示:"输入数组6个元素的值。\n" **输入格式:"%d" **输出提示:"此链表各个结点的数据域为:" **输出格式:"%d " (注:所有数据输出结束后有一个回车) **输入提示:"输入要插入的数据x:" **输入格式:"%d" **输出提示:"插入后链表各个结点的数据域为:" **输出格式:"%d " (注:所有数据输出结束后有一个回车) 程序运行示例如下: 输入数组6个元素的值。↙ 12 23 34 45 56 67 此链表各个结点的数据域为:12 23 34 45 56 67 ↙ 输入要插入的数据x:36 插入后链表各个结点的数据域为:12 23 34 36 45 56 67↙
时间: 2024-03-10 15:51:06 浏览: 54
c语言实现链表的基本操作,链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
以下是实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* insert(struct ListNode* head, int val) {
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = val;
node->next = NULL;
if (head == NULL) {
head = node;
return head;
}
struct ListNode *pre = NULL, *cur = head;
while (cur != NULL && cur->val < val) {
pre = cur;
cur = cur->next;
}
if (pre == NULL) {
node->next = head;
head = node;
} else {
pre->next = node;
node->next = cur;
}
return head;
}
int main() {
printf("输入数组6个元素的值。\n");
struct ListNode *head = NULL;
for (int i = 0; i < 6; i++) {
int val;
scanf("%d", &val);
head = insert(head, val);
}
printf("此链表各个结点的数据域为:");
struct ListNode *cur = head;
while (cur != NULL) {
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n输入要插入的数据x:");
int x;
scanf("%d", &x);
head = insert(head, x);
printf("插入后链表各个结点的数据域为:");
cur = head;
while (cur != NULL) {
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
return 0;
}
```
实现思路:
定义一个链表结构体`struct ListNode`,包含一个整型数`val`和一个指向下一个结点的指针`next`。
定义一个`insert`函数,它将一个元素为`val`的结点插入到有序链表中,并返回插入后的头结点`head`。具体实现是遍历链表,找到第一个比`val`大的结点的前一个结点`pre`和第一个比`val`大的结点`cur`,然后将新结点插入到它们之间。
在`main`函数中,先输入6个元素,然后输出链表,再输入要插入的数据`x`,然后输出插入后的链表。
阅读全文