C言語でリストのソートについて質問します。以下のmain()文を用いた昇順、降順のソートを行いたいのですが、何度やってもうまくいくアルゴリズムが組めません。アドバイスお願いします。
void main()
{
struct *head;
head = NULL;
head = add_ans(5,head);
head = add_ans(4,head);
head = add_ans(3,head);
head = add_ans(2,head);
head = add_ans(1,head);
show_ans(head);
head = sort_up(head);
show_ans(head);
head = sort_down(head);
show_ans(head);
}
以下自作のソートです。穴だらけですが…
struct ans *sort_up(struct ans *head)
{
struct ans *info;
struct ans *move_info;
struct ans *keep;
struct ans *temp;
for(info = head; info->next!=NULL; info=info->next)
keep = info;
for(move_info = info->next; move_info!=NULL; move_info->next)
{
if(info > info->next)
{
temp = info->next;
info->next = info;
info = temp;
head = info;
}
}
return head;
}
No.1ベストアンサー
- 回答日時:
まずは、新しいソートアルゴリズムを研究しているのでなければ、既存のアルゴリズムをよく理解することです。
また、
A→B→C→D
このような単方向リストでBとCを入れ替える場合
A->next=C
C->next=B
B->next=D
の3つの操作が必要です。
プログラムを見ると、 A->next=Cにあたるものがありません。
head=info; とありますが、headの初期値リストの先頭をあらわしているはずなので、かならずしも「直前」の要素ではないです。これを変えてしまったら、迷子になる要素が出てきます。
> keep = info;
> for(move_info = info->next; move_info!=NULL; move_info->next)
forループの最後がおかしいです。これでは「何もしない」と同じです。
また、move_infoが以降まったく使われていません。このループは特殊は場合を除いて無限ループになります。
また、keepも以降まったく使われていません。move_infoのループの後で、infoのループの元の位置に戻そうという考えなのでしょうが、順番が入れ替わっている可能性があり、「前回の続き」という使いかたには不向きです。
実際のところ、ランダムアクセスを使う配列のソートのアルゴリズムは、シーケンシャルアクセスが基本のリスト構造には不向きです。
マージソートを使ってみてください。配列で苦労したマージ操作が、リスト構造では簡単に書けます。
あとは、add_ansの実装方法も気になります。
malloc等で動的に確保しているのなら、対応するfreeを実行する関数も用意した方がいいです。
これくらいの長さですぐ終了するプログラムなら影響は無いでしょうが。
この回答への補足
回答ありがとうございます。手抜きになってしまっていてすみません。とりあえずすべてのソースを載せておきます。マージソートに関しては見様見真似でやってみましたが結果「1」しか帰ってきませんでした…
#include < stdio.h >
#include < stdlib.h >
struct ans
{
int data;
struct ans *next;
};
void main()
{
struct ans *head;
head = NULL;
head = add_ans(5,head);
head = add_ans(4,head);
head = add_ans(3,head);
head = add_ans(2,head);
head = add_ans(1,head);
show_ans(head);
head = merge_sort(head);
show_ans(head);
}
struct ans *add_ans(int x, struct ans *head)
{
struct ans *new_head;
new_head = (struct ans *)malloc(sizeof(struct ans));
new_head->data = x;
new_head->next = head;
return new_head;
}
void show_ans(struct ans *head)
{
if( head == NULL )
{
printf("\n\n");
}
else
{
printf("%d ",head->data);
show_ans(head->next);
}
struct ans *merge_ans(struct ans *head, struct ans *y)
{
struct ans z,*p;
p = &z;
while( head != NULL && y != NULL )
{
if( head->data <= y->data )
{
p->next = head;
p = head;
head = head->next;
}
else
{
p->next = y;
p = y;
y = y->next;
}
}
if( head == NULL )
{
p->next = y;
}
else
{
p->next = head;
}
return z.next;
}
struct ans *merge_sort(struct ans *head)
{
struct ans *a,*b,*y;
if( head == NULL || head->next == NULL )
{
return head;
}
a = head;
b = head->next;
if( b != NULL )
{
b = b->next;
}
while( b != NULL )
{
a = a->next;
b = b->next;
if( b!= NULL )
{
b = b->next;
}
}
y = a->next = NULL;
a->next = NULL;
return merge_ans( merge_sort(head), merge_sort(y));
}
No.3
- 回答日時:
y = a->next = NULL;
ってどういうこと?
回答ありがとうございます。申し訳ないですが、自分で書いていて中身がこんがらがってしまい意味不明な内容になってしまいました。ですので、一旦自分で納得できるようなアルゴリズムを組んでから再度質問させていただきます。本当にすみませんでした。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) pythonにおける単方向リストの実装について 4 2022/07/13 12:34
- JavaScript html5に変えるとスライドショーが消えてしまった。 3 2022/03/26 19:53
- PHP PHPプログラムの間違い 1 2022/10/06 14:33
- MySQL php テーブルを作れない 2 2022/11/17 18:22
- PHP php テーブルが作成できない 1 2022/11/17 23:41
- Visual Basic(VBA) InputBoxでキャンセルボタンを押したらファイル自体を閉じたい 3 2022/07/23 17:52
- PHP php ログイン 1 2022/11/01 00:24
- 英語 in the head の意味 4 2023/07/15 07:52
- PHP php エラー 2 2022/10/23 16:43
- JavaScript GoogleChart 階層ごとのブロックの長さを個別に設定したい 1 2022/07/06 14:27
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
VBA基本構文の作り方 2列の...
-
Excelですべての組合せ(重複組...
-
プログラミング(c言語)でのソー...
-
列のどこをクリックしてもソー...
-
リスト構造のソートで悩んでま...
-
Fortran77で多次元配列を並び替...
-
IPアドレスのSORTについて
-
【VBAマクロ:繰り返し処理に関...
-
ソート機能付きの成績表プログラム
-
vbでDataTableの抽出コピー
-
○番目に小さい数字を求める関数...
-
VB.NETでファイル名順にファイ...
-
excel VBA リストビューの行...
-
構造体配列の並べ替え
-
C言語でファイルの中身をソー...
-
自己参照構造体を使った2分探...
-
マクロ ソートを組み込みたい
-
ListViewのソートについて
-
選択された範囲の中からx番目に...
-
部分和問題がわかりません。
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
VB.NETでファイル名順にファイ...
-
C# DataGridView のヘッダーセ...
-
なぜ?counterintuitive
-
ファイル名「1.jpg ~10.jpg~...
-
Excelですべての組合せ(重複組...
-
C# DataTableの行をソートしてD...
-
n番目に大きい数を求めるアル...
-
リスト構造のソートで悩んでま...
-
C言語・要素除去
-
10個の整数を入力して小さい順...
-
VBA基本構文の作り方 2列の...
-
あるディレクトリ内のファイル...
-
excel VBA の条件をつけての列...
-
excel VBA リストビューの行...
-
数字文字列のソート方法
-
Excel VBAで並べ替えをしたい
-
VBScriptで重複レコードを削除...
-
vbでDataTableの抽出コピー
-
構造体配列のソート
おすすめ情報