在C语言中使用字符串对链表进行排序

Question

我有一个结构体，包含一个名称和一个名为nextName的单个节点。

这是一个单向链表，我的任务是根据字符串的字母顺序创建列表。

因此，如果我输入Joe、Zolt和Arthur，我的列表应该如下所示：

Joe

然后

Joe Zolt

然后

Arthur Joe Zolt

我在实现正确算法时遇到了麻烦，它会将指针放在正确的顺序中。

这是我目前的实现。Temp是用户刚刚输入并尝试放入列表的名称，namebox只是我的根的副本，即整个列表。

 if(temp != NULL)
      {
              struct node* namebox = root;
              while (namebox!=NULL && (strcmp((namebox)->name,temp->name) <= 0))
              {
                      namebox = namebox->nextName;
                      printf("here");
                 }
                temp->nextName = namebox;
    namebox = temp;
    root = namebox;

目前这段代码可以正常工作，如果我输入的名字是 CCC BBB 那么 AAA 就会排在后面。

但是当我输入 AAA BBB CCC 时，打印输出时只有 CCC 被输出，它截断了前面的。

编辑：

能否有人展示一下代码应该长什么样子？我自己写不出来。

- GreenMethod

Answer 1

当您输入AAA、BBB和CCC时，namebox在while循环结束时始终为NULL。

然后您正在执行以下操作：

// namebox is null
temp->nextName = namebox;
// namebox = CCC
namebox = temp;
// root = CCC
root = namebox;

所以这就是为什么你只得到了CCC。在这种情况下，你需要做的是确保将CCC添加到列表末尾，而不更改根目录。

- Pablo Santa Cruz

---

啊，好的，我明白了，现在只需要实现它。那么这是否意味着我应该为strcmp((namebox)->name,temp->name) >= 0（关键在于>=）创建一个场景？ - GreenMethod

Answer 2

   #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct node
    {
        char data[100];
        struct node* next;
    };
    
    struct node* head = NULL;
    
    struct node* getnode(char *v)
    {
        struct node* newnode = (struct node*)malloc(sizeof(struct node));
        strcpy(newnode->data,v);
        newnode->next = NULL;
        return newnode;
    };
    
    void insert(char *v)
    {
        struct node* newnode = getnode(v);
        newnode->next = head;
        head = newnode;
    }
    
    void print()
    {
        struct node* temp = head;
        //struct node* end = NULL;
        int c = 1;
        while(temp->next != NULL)
        {
            temp = temp->next;
            c++;
        }
        temp = head;
        char x[100];
        for(int i=0;i<c;i++)
        {
            temp = head;
            while(temp->next != NULL)
            {
                if(strcmp(temp->data,temp->next->data) > 0)
                {
                    strcpy(x,temp->data);
                    strcpy(temp->data,temp->next->data);
                    strcpy(temp->next->data,x);
                }
                temp = temp->next;
            }
            //end = temp;
        }
        temp = head;
        while(temp != NULL)
        {
            printf("%s\t",temp->data);
            temp = temp->next;
        }
        printf("\n\n The Length of the list : %d",c);
    }
    
    int main()
    {
        printf("Hello world!\n");
        char v[100];
        while(1)
        {
            printf("enter a string : ");scanf("%s",v);
            if(v[0] == 'Q' || v[0] == 'q')
            {
                break;
            }
            else
            {
                insert(v);
            }
        }
        print();
        return 0;
    }
    

- vijay sainaga

---

请修改您的答案，解释您的代码如何回答这个问题。 - Null

Answer 3

if(temp != NULL)
{
    struct node* namebox = root;
    while (namebox!=NULL)
    {
        if(strcmp(namebox->Name,temp->Name) > 0) // if temp comes before this
        {
            temp->nextName = namebox->nextName;
            namebox->nextName = temp;
            //printf("here"); I'm guessing this is debugging stuff?
        }
        namebox = namebox->nextName;
    }
}

这是通用插入，但是当您添加名字并将其添加到列表开头时，必须处理特殊情况。

- datdo

Answer 4

你所描述的是插入排序。

当你输入AAA、BBB，最后CCC时，当while循环完成时，namebox为NULL。

然后当你执行temp->nextName = namebox时，namebox为NULL。之后你将namebox设置为temp（它保存了CCC）。最后你将root设置为namebox，这也将其设置为CCC。这就是为什么你得到CCC的原因。

在你的算法中，你需要处理在列表末尾或中间添加内容的情况，并且在这些情况下不改变根节点。实际上，这应该是一般情况。在前面和后面添加东西应该是特殊情况。

- Vivin Paliath

---

所以我需要三种情况，一种是strcmp((namebox)->name,temp->name) = 0，一种是strcmp((namebox)->name,temp->name) <= 0，还有一种是strcmp((namebox)->name,temp->name) >= 0？ - GreenMethod

有一种方法可以优雅地处理你的算法，使其能够处理这种情况。插入排序与插入链接节点并没有太大区别，实际上是较简单的插入排序算法之一。 - Vivin Paliath

错误...我是指“链表”，而不是“链接节点”。 - Vivin Paliath