用c语言完整编程假设带头结点的单链表是递增有序的,设计算法在其中插入一个值为x的结点,并保持其递增性。
时间: 2023-07-14 13:13:09 浏览: 148
3-2 试编写一个算法,在带表头结点的单链表中寻找第i个结点.doc
以下是用C语言实现在递增有序的带头结点单链表中插入一个值为x的结点的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义单链表结点结构体
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkedList;
// 创建带头结点的单链表
LinkedList createLinkedList() {
LinkedList head = (LinkedList) malloc(sizeof(Node));
head->next = NULL;
return head;
}
// 在递增有序的带头结点单链表中插入一个值为x的结点
void insert(LinkedList L, int x) {
Node *p = L; // p指向头结点
Node *newNode = (Node*) malloc(sizeof(Node)); // 创建新结点
newNode->data = x;
newNode->next = NULL;
while (p->next != NULL && p->next->data < x) { // 找到插入位置
p = p->next;
}
newNode->next = p->next; // 插入新结点
p->next = newNode;
}
// 输出单链表
void printLinkedList(LinkedList L) {
Node *p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
int main() {
LinkedList L = createLinkedList();
insert(L, 1);
insert(L, 3);
insert(L, 5);
insert(L, 4);
insert(L, 2);
printLinkedList(L);
return 0;
}
```
在这个程序中,我们首先定义了单链表结点结构体 `Node` 和带头结点的单链表结构体 `LinkedList`。然后,我们创建了一个带头结点的单链表 `L`。接着,我们定义了 `insert` 函数,该函数用于在递增有序的带头结点单链表中插入一个值为 `x` 的结点,并保持其递增性。最后,我们在 `main` 函数中测试了 `insert` 函数,并输出了带头结点的单链表 `L` 中的所有元素。
具体来说,`insert` 函数首先定义了指针 `p` 指向头结点,然后创建了一个新结点 `newNode`,该结点的数据域为 `x`,指针域为 `NULL`。接着,我们使用一个 `while` 循环找到插入位置,即找到第一个比 `x` 大的结点的前驱结点。最后,我们将新结点插入到该位置中,并保持单链表的递增有序性。
在 `main` 函数中,我们首先创建了一个带头结点的单链表 `L`,然后分别插入了值为 1、3、5、4、2 的五个结点。最后,我们输出了带头结点的单链表 `L` 中的所有元素,即 1 2 3 4 5。
阅读全文