1

我正在尝试使用冒泡排序对单链表进行排序。如果有一个简单的错误，请原谅。请告诉我哪里出错了。当我尝试执行此操作时，程序意外停止。

void sortBubble()
{
      Node *i=start,*j=start;Node *temp;Node* prev=start;Node* agla;
      while(i->next!=NULL)
      {
           cout<<"\nhello 1";
           j=i;
           agla=j->next;
           while(agla!=NULL)
           {
                temp=NULL;temp->next=NULL;
                cout<<"\nhello2";

                if(*(j) > *(agla))
                {
                     temp=agla->next;
                     agla->next=j;
                     prev->next=agla;
                     prev=agla;
                     agla=j->next;
                     j->next=temp;
                }
                else{
                     prev=j;
                     j=agla;
                     agla=j->next;}
                }
                prev=i;
                i=i->next;
           }
      }
 }
4

2 回答 2

1

您绝对导致程序崩溃的第一个明显错误是：

       while(agla!=NULL)
       {
            temp=NULL;temp->next=NULL;

您将变量设置为NULL，然后设置其字段。空指针不指向任何地方，因此您无法编辑其内容。

消除temp->next=NULL;

编辑：

你的程序逻辑不正确。在循环的几次迭代之后，您破坏了列表，并且程序陷入了一个带有混合指针的无限循环。

在冒泡排序中，我们多次遍历项目。在每次迭代中，最大的项目会冒泡到列表的末尾。在第一次迭代之后，我们确定最大的元素在列表的末尾。在第二次迭代之后，我们确定第二大元素在列表的最后一个元素之前，依此类推。
您重复此过程，直到所有项目都在其位置：

int getListSize(Node* start)
{
    int count = 0;
    while(start != NULL)
    {
        count++;
        start = start->next;
    }
    return count;
}

void bubbleSort(Node *&start) // <-- Pass a reference to pointer, because we may need to modify the start pointer.
{
    int size = getListSize(start);
    int i = 0;

    while(size--)
    {
        Node
            *current = start,
            *prev = NULL; // We are at the beginnig, so there is no previous node.

        while(current->next != NULL) // We have at least one node (size > 0) so `current` itself is not NULL.
        {
            Node *after = current->next;
            if((*current) > (*after))
            {
                //swap the items
                current->next = after->next;
                after->next = current;
                if (prev == NULL) // we are at the beginning
                    start = after;
                else
                    prev->next = after;

                prev = after;
            }
            else
            {
                prev = current;
                current = current->next;
            }
        }
    }
}

我们重复“冒泡”过程size时间。这不是最有效的方法，因为我们甚至会比较已经排序的项目。一种更有效的方法是排序直到没有新的交换发生：

void bubbleSort(Node *&start) // <-- Pass a reference to pointer, because we may need to modify the start pointer.
{
    int size = getListSize(start);
    int i = 0;

    Node *lastSwapped = NULL;

    while(size--)
    {
        Node
            *current = start,
            *prev = NULL, // We are at the beginnig, so there is no previous node.
            *currentSwapped = NULL;

        while(current->next != lastSwapped) // We have at least one node (size > 0) so `current` itself is not NULL.
        {
            Node *after = current->next;
            if((*current) > (*after))
            {
                //swap the items
                current->next = after->next;
                after->next = current;
                if (prev == NULL) // we are at the beginning
                    start = after;
                else
                    prev->next = after;

                prev = after;
                currentSwapped = current;
            }
            else
            {
                prev = current;
                current = current->next;
            }
        }

        if (currentSwapped == NULL)
            break; // No swapping occured. The items are sorted.
        else
            lastSwapped = currentSwapped;
    }
}

这是完整的工作程序

于 2012-11-13T12:56:29.897 回答
0

您只是通过简单地比较元素*(j) > *(agla)，我不确定它是如何构建的，因为两者j都是agla指向结构的指针。结构不能直接比较。

于 2012-11-13T12:55:27.993 回答