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に設定してから、そのフィールドを設定しています。null ポインターはどこも指していないため、その内容を編集することはできません。

削除するtemp->next=NULL;

編集：

プログラム ロジックが正しくありません。ループを数回繰り返した後、リストが台無しになり、プログラムはポインターが混在する無限ループに陥ります。

バブルソートでは、アイテムを数回繰り返します。各反復で、最大のアイテムがリストの最後までバブルアップされます。最初の繰り返しの後、最大の要素がリストの最後にあることを確認します。2 回目の繰り返しの後、2 番目に大きい要素がリストの最後の要素の前にあることを確認します。
すべてのアイテムが配置されるまで、このプロセスを繰り返します。

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)ため、それがどのように構築されるかわかりません。構造を直接比較することはできません。jagla

于 2012-11-13T12:55:27.993 に答える