用c语言,改写链表创建函数,使得链表创建时为非递减有序的单链表
时间: 2023-12-12 16:51:02 浏览: 57
以下是一个使用C语言实现的创建非递减有序单链表的函数:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node;
Node *createList(int n) {
Node *head = NULL;
Node *tail = NULL;
Node *newNode = NULL;
int i, value;
for (i = 0; i < n; i++) {
printf("请输入第 %d 个节点的值: ", i+1);
scanf("%d", &value);
newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
if (value <= head->data) {
newNode->next = head;
head = newNode;
} else if (value >= tail->data) {
tail->next = newNode;
tail = newNode;
} else {
Node *p = head;
while (p->next->data < value) {
p = p->next;
}
newNode->next = p->next;
p->next = newNode;
}
}
}
return head;
}
void printList(Node *head) {
Node *p = head;
printf("链表的值为: ");
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int n;
Node *head = NULL;
printf("请输入链表的节点个数: ");
scanf("%d", &n);
head = createList(n);
printList(head);
return 0;
}
```
在这个函数中,我们使用了一个指针`tail`来记录链表的尾部,每次向链表中插入一个新节点时,我们需要判断新节点的值与链表中已有节点的值的大小关系,当新节点的值小于等于链表头节点的值时,将新节点插入到链表头部;当新节点的值大于等于链表尾节点的值时,将新节点插入到链表尾部;否则,遍历链表,找到第一个节点的值大于等于新节点值的节点,将新节点插入到该节点之前。这样,每次插入新节点后,链表仍然保持非递减有序。
阅读全文