链表字符串排序
时间: 2023-07-25 08:12:50 浏览: 46
链表字符串排序可以使用归并排序算法。
具体实现步骤如下:
1. 定义链表节点结构体,包含字符串和指向下一个节点的指针。
2. 定义归并排序函数,输入为链表的头指针,输出为排序后的链表头指针。
3. 在归并排序函数中,先对链表进行分割,直到链表只剩一个节点或为空。
4. 对分割后的链表进行归并,具体实现可以使用双指针法,依次比较两个链表节点的字符串大小,将较小的节点插入到新链表的尾部。
5. 最后返回新链表的头指针即可。
代码实现如下:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
char str[100];
struct Node* next;
} Node;
Node* merge(Node* l1, Node* l2) {
Node* head = (Node*)malloc(sizeof(Node));
Node* cur = head;
while (l1 && l2) {
if (strcmp(l1->str, l2->str) < 0) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return head->next;
}
Node* sortList(Node* head) {
if (!head || !head->next) {
return head;
}
Node* slow = head;
Node* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
Node* mid = slow->next;
slow->next = NULL;
Node* l1 = sortList(head);
Node* l2 = sortList(mid);
return merge(l1, l2);
}
int main() {
Node* head = (Node*)malloc(sizeof(Node));
head->next = NULL;
int n;
printf("Input n: ");
scanf("%d", &n);
printf("Input strings: ");
for (int i = 0; i < n; i++) {
char s[100];
scanf("%s", s);
Node* node = (Node*)malloc(sizeof(Node));
strcpy(node->str, s);
node->next = NULL;
Node* cur = head;
while (cur->next && strcmp(s, cur->next->str) > 0) {
cur = cur->next;
}
node->next = cur->next;
cur->next = node;
}
head = sortList(head->next);
printf("Sorted strings: ");
Node* cur = head;
while (cur) {
printf("%s ", cur->str);
cur = cur->next;
}
return 0;
}
```