帮我写一个C语言代码,动态链表排序
时间: 2023-05-26 09:02:44 浏览: 56
以下是一个简单的动态链表排序示例代码,可以通过插入排序法来实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 节点结构体
struct Node {
int data;
struct Node* next;
};
// 插入排序函数
void insertionSort(struct Node** headRef) {
struct Node* sorted = NULL;
struct Node* current = *headRef;
while (current != NULL) {
struct Node* next = current->next;
if (sorted == NULL || current->data < sorted->data) {
current->next = sorted;
sorted = current;
}
else {
struct Node* temp = sorted;
while (temp->next != NULL && current->data > temp->next->data) {
temp = temp->next;
}
current->next = temp->next;
temp->next = current;
}
current = next;
}
*headRef = sorted;
}
// 添加节点
void push(struct Node** headRef, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = (*headRef);
(*headRef) = newNode;
}
// 打印链表
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
int main() {
struct Node* head = NULL;
push(&head, 6);
push(&head, 2);
push(&head, 1);
push(&head, 9);
push(&head, 4);
printf("Before sorting: ");
printList(head);
insertionSort(&head);
printf("\nAfter sorting: ");
printList(head);
return 0;
}
```
分析:上面的代码中,我们使用了插入排序法,将节点插入到排序完成的链表中。首先,将空链表视为排序链表(`sorted`)。然后,从头结点开始遍历每个节点(`current`),并通过比较其数据将其插入到排序链表中正确的位置。最后将头结点指向排序链表的开头(`sorted`)。
上述链表排序代码中所使用的插入排序方法虽然简单易懂,但是时间复杂度为O(n^2),在处理大规模数据时不够高效。对于时间复杂度较高的排序算法,可以使用归并排序、快速排序等效率更高的算法来进行排序。