C语言 如何在运行时创建和排序单向链表?

Question

我正在尝试通过读取文本文件创建一个链表，并按升序输出已读单词及其计数。

除了尝试在运行时对节点进行排序外，一切都很好。

首先，我尝试了像气泡排序，但我无法绕过链表开头部分的逻辑。

其次，我试图继续比较x->next的计数，直到我找到一个比我想推回的那个更大的计数。然后我交换它们。我使用了很多指针，但它有时有效，但在某些边缘情况下失败。

我应该保存一些代码，让人们指出我的逻辑缺陷，但我有点沮丧，只是试图从头开始。

有人可以提供一些好的逻辑或明确的伪吗？谢谢

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#define MAX 999
typedef struct Node
{
    char *name;
    int count;
    struct Node *next;
}node;
void insert(node **,char *);
void freeNode(node **);
int main()
{
    char str[MAX];
    node *head = NULL;
    while(getword(str,MAX))
    {
        insert(&head,str);
    }
    print(head);
    free(head);
    return 0;
}
void insert(node **head,char *str)
{
     node *mid = *head;
node *left = NULL, *right = NULL;
while(mid)
{
    if(strcmp(mid->name,str) == 0)
    {
        ++(mid->count);
        node *temp = left;
        while(mid->count > right->count)
        {
            //printf("in %s %s %sn",left->name,mid->name, right->name);
            left->next = mid->next;
            mid->next = right->next;
            right->next = mid;
            left = left->next;
            if(mid->next != NULL) right = mid->next;
            if(left == mid) break;
            //printf("in %s %s %snn",left->name,mid->name, right->name);
           // sleep(3);
        }
        return;
    }
    left = mid;
    mid = mid->next;
    if(mid != NULL) right = mid->next;
}
    node *newnode = (node *) malloc(sizeof(node));
    newnode->name = (char *) malloc(MAX * sizeof(char));
    strcpy(newnode->name,str);
    newnode->count = 1;
    newnode->next = *head;
    *head = newnode;
}
void freeNodes(node **head)
{
    node *temp;
    while(*head)
    {
        temp = (*head)->next;
        free(*head);
        (*head) = NULL;
        (*head) = temp;
    }
}

Answer 1

我只是处理了一些边缘情况。我确保当第一个节点重复时，将确保向下移动一个

node *mid = *head;
node *left = NULL, *right = NULL;
while(mid)
{
    if(strcmp(mid->name,str) == 0)
    {
        ++(mid->count);
        if(mid->next == NULL) return;
        node *temp = left;
        if(left == NULL)
        {
            left = mid->next;
            mid->next = left->next;
            left->next = mid;
            *head = left;
            right = mid->next;
        }
            while(mid->count > right->count)
            {
                left->next = mid->next;
                mid->next = right->next;
                right->next = mid;
                left = left->next;
                if(mid->next != NULL) right = mid->next;
                if(left == mid) break;
                //printf("in %s %s %snn",left->name,mid->name, right->name);
               // sleep(3);
            }
        return;
    }
    left = mid;
    mid = mid->next;
    if(mid != NULL) right = mid->next;
}

Answer 2

谷歌合并排序。恕我直言，它是对单连接列表进行排序的最佳算法。

从列表节点开始：

node3 -> node7 -> node1 -> node20 -> node11 -> node13 -> NULL

长度为 1 的每个子列表都(微不足道地(排序：

{ node3 } is sorted
{ node7 } is sorted

然后将长度为 1 的两个连续子列表合并为长度为 2 的子列表：

node3 -> node7 -> node20 -> node1 -> node11 -> node13 -> node007 -> NULL

到

{node3 -> node7}->{node1 -> node20}->{node11 -> node13}->{node007} -> NULL

node007被视为等于 node7 。

然后将长度为 2 的两个连续子列表合并为长度为 4 的子列表：

{node3 -> node7}->{node1 -> node20}->{node11 -> node13}->{node007} -> NULL
merge(node3, node1, 2):
returns {node1 -> node3 -> node7 ->node20}
merge(node11, node007, 2):
returns {node007 -> node11 -> node13}

因此，您可以获得两个长度为 4 的排序子列表：

{node1 -> node3 -> node7 ->node20}->{node007 -> node11 -> node13}->NULL 
merge(node1,node007,4):
returns
{node1 -> node3 -> node7 -> node007 -> node11 -> node13 -> ode20}->NULL

因此，长度总是加倍，当它等于或大于整个列表的长度时，您就完成了。

合并始终比较每个列表的第一个元素，并从列表中弹出较小的元素并将其附加到结果尾部：

merge(n1 = {node3 -> node7}->t1 , n2 = {node1 -> node20}-> t2 , 2):

做

count1 = count2 = 2;
result = NULL;
as node1 < node3  : result = { node1 }-> NULL;
                    n2 = { node20 } -> t2;
                    count2 = 1;
as node3 < node20 : result = {node1 -> node3}-> NULL;
                    n1 = {node7}->t1;
                    count1 = 1;
as node7 < node20 : result = {node1 -> node3-> node7 }-> NULL;
                    n1 = t1;
                    count1 = 0; (merge finished);
as count2 != 0 :    result = {node1 -> node3-> node7 -> node20 } -> NULL.

这都是伪代码，应该给你一个想法。