0

我想问你，是否可以简单地对名称按字母顺序排列的链表进行排序？我认为这是可能的，但我不知道如何。你能帮我解决这个问题吗？我将非常感激。

按下“i”应该扫描新名称并将这个名称添加到链接列表中，然后按字母顺序排序这个列表“d”按下应该显示整个排序列表

"k" 按下的程序结束

我用结构数组做到了这一点，它工作得很好，但我不知道如何用链表做同样的事情......

非常感谢 ：）

这是代码：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct list{
    char name[100];
    struct list *next;
}LIST;

int main()
{
    int i, n, k = 0, v = 0, m = 0, j = 0;
    char str[100], c;
    LIST *p_first = NULL, *p_act = NULL, *p_prev = NULL;

    while((c=getchar())!='k')
    {
        if(c=='i')
        {
            if(k == 0)
            {
                p_first = (LIST *) malloc(sizeof(LIST));  //scan first element of struct
                scanf("%s", p_first->name);
                p_act = p_first;
            }
            else
            {
                p_act->next = (LIST *) malloc(sizeof(LIST));  //scan next element of struct
                p_act = p_act->next;
                scanf("%s", p_act->name);

                //here should be code to sort text alphabetically
        }
        p_act->next = NULL;
        k++;
    }
    else if(c=='d')
    {
        //display all elements of linked list

        for(i = 0; i < k; i++) { 
            if(i == 0)
                p_act = p_first;
            else
                p_act = p_act->next;
            printf("%s\n", p_act->name);
        }
    }
    }
    getchar(); 
    return 0;
}
4

1 回答 1

0

如果你想要实际的代码，你来错地方了。但我可以给你基本的想法。

每当您尝试解决此类问题时，请尝试找到您需要解决的基本小问题。例如，排序（任何类型）需要交换元素的能力，并且在大多数情况下，需要比较元素。

比较非常直观：您需要对元素对调用 strcmp() 或类似方法。但是，您可能想要做一个功能来完成这项工作以保持您的代码干净。

交换有点困难。如果您分析交换过程，您会发现它包含两个基本操作：从列表中删除一个元素并在给定位置插入一个新元素。因此，您可能想要创建 2 个实现这些操作的函数。我建议你实现一个函数，在你提供的元素之后删除一个元素，并在你提供的元素之后插入（你的列表是一个单点列表，很难找到之前的元素）。

要删除 A 之后的元素，只需使用以下赋值：

a->next=(a->next)->next

（所以 A->next 指向它的邻居之后的元素）

在 A 之后插入 B：

B->next = A->next
A->next = B

现在，您有了这 2 个操作，创建一个交换 2 个元素的函数很简单（实际上，我建议创建一个在您指定的元素之后交换 2 个元素的函数，因此 swap(A, B) 交换 A->next和 B-> 下一个）。此外，比较功能应该比较您指定的元素之后的元素。

您可以将我上面描述的那些过程与任何排序算法一起使用，例如快速排序或冒泡排序来实现您的结果。

请注意，这只是实现的基本思想，以及一些关于您应该如何思考此类问题的指示。我希望它足够清楚。

于 2014-04-19T21:51:46.027 回答