c - 使用冒泡排序对链表进行排序

Question

为什么这种对链表进行排序的冒泡排序实现不起作用？

它根本不排序。代码的主要问题区域是排序函数。我已经验证 main 工作正常，并且在调用排序函数之前将链表的最后一个指针(下一个)设置为 null。链接列表的链应该在字符串比较 block 内的 if 语句中链接，并且应该返回列表上的第一个链接，该链接将由 while 语句调用以访问已排序的所有成员，但是，它似乎不起作用。

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

#define NAME_SIZE 20

typedef struct record rec;
struct record
{
    char name[NAME_SIZE];
    int age;
    rec* next;
};

void getname(char* name);
rec* sort(rec**First,int i);/*we need to change the addresses they refer to */

int main(void)
{
    rec* Current = NULL;
    rec* Previous = NULL;
    rec* First = NULL;
    char check = '\0';
    int i = 0;

    for(; ;)
    {
        fflush(stdin);
        printf("\nDo you want to enter a%s record?(y/n): ", (check=='\0')?"":"nother");
        scanf("%c", &check);
        if(check == 'n')
            break;

        Current = (rec*)malloc(sizeof(rec));
        if(First == NULL)
        {
            First = Current;
        }
        if(Previous != NULL)
        {
            Previous->next = Current;
        }
        printf("\n");
        printf("\nPlease enter your name: ");
        getname(Current->name);
        printf("\nPlease enter your age: ");
        scanf("%d", &Current->age);
        Previous = Current;
        Current->next = NULL;
        i++;
    }

    Current = sort(&First, i);


    while(Current != NULL)
    {
        printf("\n%s is %d years old ", Current->name, Current->age);
        Current = Current->next;
    }

    return 0;
}

void getname(char *name)
{
    fflush(stdin);
    fgets(name, NAME_SIZE, stdin);
    int length = strlen(name);
    if(name[length - 1] == '\n')
        name[length -1 ] = '\0';
    return;
}


rec* sort(rec** first, int numbers)
{
    rec* pTemp1 = NULL;
    rec* pTemp2 = NULL;
    rec* Temp_first = *first;

    for(int j = 0; j < numbers; j++)
    {
        pTemp1 = *first;
        if(((*first) = (*first)->next)==NULL)
        {/*if end is reached, then break;*/
            break;
        }

        if(strcmp((*first)->name, ((*first)->next->name)) > 0)
        {


            if(((*first)->next) != NULL)
            {
                printf("\n***XXX***Entered***XXX");
                pTemp2 = (*first)->next;
                (*first)->next = pTemp1;
                pTemp1->next = pTemp2;
            }
        }

    }

    return Temp_first;

}

(为了简洁省略了释放内存)。输入

atest  
aatest  
btest  
abtest

并且输出未排序:

atest  
aatest  
abtest  

Answer 1

我认为你在 bubble sort 中做错了函数，您似乎正在重复列表的相邻比较 N 次，这没关系，但您只对列表的前两个元素进行比较。回想一下，冒泡排序是一种 O(N^2) 算法。您需要将相邻元素检查放入另一个循环中。

此外，您可以通过将外部循环更改为依赖于冒泡排序变体来对其进行一些优化，该变体将继续传递，直到列表中不再存在反转。我根据我的风格更改了您的冒泡排序方法，并且能够看到所需的输出:

rec* sort(rec** first, int numbers)
{
    int bSwap = 0;
    if(*first == NULL || (*first)->next == NULL)
      return;

    // outer loop for iterating till list is sorted
    while(!bSwap) {
      // iterating over the list comparing and
      // swapping adjacent elements
      rec *curNode = *first;
      rec *prev = *first;
      rec *fwd = (*first)->next;
      bSwap = 1;

      while(fwd) {
        int cmp = strcmp(curNode->name, fwd->name);

        if(cmp > 0) { // inversion found, swap and proceed forward
          if(curNode == *first)
            *first = fwd;
          else
            prev->next = fwd;

          curNode->next = fwd->next;
          fwd->next = curNode;
          prev = fwd;
          fwd = curNode->next;
          bSwap = 0;
        }
        else { // proceed forward
          curNode = prev->next;
          prev = fwd;
          fwd = fwd->next;
        }
      }

    }
    return *first;
}

这是我运行时得到的结果:

~/Documents/src : $ ./a.out 

Do you want to enter a record?(y/n): y


Please enter your name: Rohan

Please enter your age: 22

Do you want to enter another record?(y/n): y


Please enter your name: Hema

Please enter your age: 20

Do you want to enter another record?(y/n): y


Please enter your name: Asanala

Please enter your age: 31

Do you want to enter another record?(y/n): n

Asanala is 31 years old 
Hema is 20 years old 
Rohan is 22 years old 

我希望这会有所帮助。