bugfix> c > 投稿

私はCの二重リンクリストで挿入ソートを行おうとしています。この状態では、コードは8と9を吐き出す非終了ループに陥ります。

誰かが「insertionSort」メソッドがどのように設計されるべきかを説明するのに十分親切にしてくれませんか?

リンクリストは、head、previous、next、およびいくつかのデータを含むように設計されています。

ここに私のコードがあります

私の希望はNULLです。助けてください。

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
struct Node* previous;
}Node;
struct Node* head = NULL;
struct Node* current = NULL;
struct Node* headsorted = NULL;
int l = 0;
int empty = 1;
int length = 0;
int change = 0;
void InsertSort(){
Node* temp = (Node*)malloc(sizeof(struct Node));
temp = head;
current = head->next;
printf("\nInsert Sort begins...\n");
if (head != NULL && head->next != NULL)
{
   for (int i = 1; i < length; i++)
   {
        while(current->data > current->next->data && current->next != NULL && current != NULL)
        {
            temp = current;
            current = current->next;
            current->next = temp;
        }
   }
}
else
{
printf("\nList Error!\n");
}
temp = NULL;
}
void Insert(int x)
{
    Node* temp = (Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->next = head;
    temp->previous = NULL;
   if (head != NULL)
   {
       head->previous = temp;
   }
    head = temp;
}
void Print(){
    struct Node* temp = head;
    printf("List is: ");
    while(temp != NULL)
    {
        printf(" %d", temp->data);
        temp = temp->next;
    }
}
int main()
{
    head = NULL;
    FILE * file = fopen("List.txt", "r");
    fscanf(file, "%d", &l);
    while (!feof (file))
    {
        Insert(l);
        fscanf(file, "%d", &l);
        length++;
    }
    fclose(file);
    Print();
    printf("\n\n\n");
    printf("data: %d next: %d   " , head->data, head->next->data);
    InsertSort();
    Print();
    return 0;
}

回答 1 件
  • can someone please be kind enough to explain how the "insertionSort" method is supposed to be designed?

    そもそも、 length を取り除くことをお勧めします  変数、または少なくともソートルーチンで使用しない。それは必要ではありません。そして、それに依存することは、あなたの考えを配列スタイルの実装に向けすぎます。 next のノードを発見すると、リストの最後に到達したことがわかります。  ポインターがNULLです。

    第二に、二重リンクリストに対してノードスワップを正しく実行していないという私のコメントを繰り返します。単一リンクまたは二重リンクのリンクリストのノードスワップは、リストから2番目のノードを抽出し、最初のノードの前に再挿入するのと同じです。一般に、3つのノードに影響する単一リンクリスト:スワップされる2つに加えて、最初のノードの先行ノード。二重にリンクされたリストでは、2番目の後継者にも影響します。二重にリンクされたケースではこれは面倒で、挿入とそれに続く削除として明示的に構造化することをお勧めします。

    しかし、一歩下がって、アルゴリズムを高いレベルから見ることもお勧めします。各ノードを順番に検討し、2番目のノードから順番に検討し、必要に応じてそのノードを削除し、その前の(ソートされた)サブリストの正しい位置に再挿入します。それでは、ペアワイズスワッピングはそれと何の関係があるのでしょうか?なし。これは、配列にこのような並べ替えを実装するのに便利な詳細ですが、リンクリストを並べ替えるときに不必要な作業を行います。

    リンクされたリスト、特に二重にリンクされたリストについては、アルゴリズムの抽象的な説明により直接的に分割する実装をお勧めします。

    ポインターを維持する、 S 、ソートされた先行サブリストの最後のノードまで。最初は、リストの頭を指します。

    S の場合  最後のノードを指します( S->next で判断できます) )その後停止します。

    そうでない場合は、 *N かどうかを確認します 、 *S の後継者 、* Sに関連して正しく順序付けられます。

    その場合は、 S を設定します  (ポインターではなく、ポインター) N に等しい 。

    そうでない場合は、

    *N を切る  リストから(前任者と後任者があれば適切に更新する)、および

    最初のノードまたは先行ノードが *N に先行するノードに到達するまで、ソートされたサブリストを逆方向にステップします。 、どちらか最初に遭遇した方。

    *N を挿入  発見したノードの前。

    それが *N になる場合  リストヘッド( previous の新しい値で判断できます)  ポインター)、次にヘッドポインター(リファレントではなく)を N に等しく設定します 。

    ポイント2から繰り返す

    実際のコードは、目的の演習として残されています。

あなたの答え