双方向リストをバブルソートを用いてソートしたいです。
下記がプログラム(一部)ですが、ソートした後にリスト表示すると
無限ループに陥ります。
どこがいけないのでしょうか。
#include <stdio.h>
#include <stdlib.h>
struct cell{
int data;
struct cell *next, *prev;
};
void insert_head(struct cell **head, int num){
struct cell *p, *p1;
p = *head;
p1 = make_cell();
*head = p1;
p1->data = num;
p1->next = p;
if(p1->next != (struct cell *)NULL){
p1->next = p;
p->prev = p1;
}
}
void print_list(struct cell *head){
struct cell *p;
p = head;
printf("data = \n");
while(p != (struct cell *)NULL){
printf("%d\n", p->data);
p = p->next;
}
}
void sort_list(struct cell **head){
struct cell *p, *p2;
int i, n;
n = 0;
p = *head;
while(p->next != (struct cell *)NULL){
p = p->next;
n++;
}
for(i = 0, p = *head; i < n-2; i++){
if(p->data > p->next->data){
if(p == *head){
*head = p->next;
}else{
p->prev->next = p->next;
}
p2 = p->next;
p->next = p->next->next;
p->next->next = p;
p->next->next->prev = p;
p->next->prev = p->prev;
p->prev = p2;
}else
p = p->next;
}
}
int main(void){
struct cell *head = (struct cell *)NULL;
int n;
while(1){
printf("1:Insert head 2:Insert tail 3:Delete 4:List 5:Sort 6:Exit\n");
scanf("%d", &n);
switch(n){
case 1:
printf("num = ");
scanf("%d", &n);
insert_head(&head, n);
break;
case 2:
printf("num = ");
scanf("%d", &n);
insert_tail(&head, n);
break;
case 3:
printf("num = ");
scanf("%d", &n);
delete_cell(&head, n);
break;
case 4:
print_list(head);
break;
case 5:
sort_list(&head);
break;
case 6:
return 0;
break;
}
}
}
No.3ベストアンサー
- 回答日時:
p2 = p->next;
p->next = p->next->next;
p->next->next = p;
p->next->next->prev = p;
p->next->prev = p->prev;
p->prev = p2;
の部分で
p->next->next = p;
の後に
p->next->next->prev = p;
をやると、これは
p->prev = p;
と同じ意味になる。
「自分の前は自分」と言う状態になり、この状態で、もう一度上記のルーチンを通ると「自分の次は自分」と言う状況が出来上がる。
表示ルーチンは「自分の次が、次」とやっているのだから、リストが「自分の次は自分」になってれば、無限ループするのが当たり前。
ソートルーチンで、2つの要素を入れ替えする場合は、以下に示した[1]~[6]の6つのポインタを書き換えないといけない筈。
pの---[1]-->p---[3]-->p2---[5]-->p2の
前 <--[2]--- <--[4]--- <--[6]---次
質問者さんのプログラムでは「5つしか書き換えてない」ので、それだけで「バグっている」のが明白。
以上を踏まえると、pとp2の入れ替えは、以下のようになる。
p2=p->next;
if (*head!=p) p->prev->next = p2; /*pに前が居る場合だけ、 [1]の付け替え*/
if (p2->next) p2->next->prev = p; /*p2に次が居る場合だけ、[6]の付け替え*/
p->next = p2->next; /* [3]の付け替え*/
if (*head!=p) p2->prev = p->prev; /*pに前が居る場合だけ、 [4]の付け替え*/
p2->next = p; /* [5]の付け替え*/
p->prev = p2 /* [2]の付け替え*/
if (*head==p) *head = p2; /*pがheadだったら、p2が新しいheadになる*/
No.6
- 回答日時:
蛇足な追記。
「prev、nextのポインタじゃなく、データを入れ替えろ」と言う意見をしたが、データが大きい場合、質問者さんはこの意見には賛成できないと思う。
だって「巨大なデータを入れ替えると、入れ替えに時間がかかる」って思う筈だから。
でも、やはり「データだけ入れ替えた方が早い」のだ。
どうするかと言うと「リストに、データの実体ではなく、データのポインタだけを持つ」ようにするのだ。
そうすれば、データの実体は入れ替えずに済んで「ポインタが指すアドレス」だけを入れ替えれば済んじゃうようになる。
例えば、リスト構造を
struct cell{
void *data_ptr; /*数キロバイトの大きなデータのアドレスを指すポインタ*/
struct cell *next, *prev;
};
にして、データの実体は別の所に確保して、data_ptrに確保したアドレスを代入しとけば良い。
そうすりゃ
void *d_ptr;
の作業用変数1つと
d_ptr = p->next->data_ptr;
p->next->data_ptr = p->data_ptr;
p->data_ptr = d_ptr;
の3行で、数キロバイトの大きなデータが瞬時に入れ替わる事になる。
スワップ作業を「データのスワップ」にした場合、「リストへの要素の追加」と「リストから要素の削除」さえきちんと動けば「リストの繋がりは変わらない」のだから、バグが起きる余地が無くなる。
No.5
- 回答日時:
ポインタを数値で表現してみます。
p=1000
1000->prev=999
1000->next=1001
1001->prev=1000
1001->next=1002
1002->prev=1001
1002->next=1003
だったとすると
p2=p->next ; //=1001
p->next=p->next->next; // =1001->next=1002
p->next->next=p; // 上でp->next=1002だから、 1002->next=1000
p->next->next->prev = p; // 上でp->next->next=1000だから 1000->prev = 1000
p->next->prev = p->prev; // 1002->prev = 999
p->prev=p2
結果
1000->prev=1001
1000->next=1002
1001->prev=1000
1001->next=1002
1002->prev=999
1002->next=1000
グチャグチャですね。
p->next->next=p;
で変えたいのは、1001->nextのはずです。それが、p->nextが変更されているにもかかわらず、そのままp->nextでやろうとしているのが間違いです。
いきなりソートするのではなく、「2つの要素を入れ替える」関数を作ってください。
そして、確実に入れ替わるか確認してください。
そうすれば、あとは、
if(p->data > p->next->data){
swap(p,p->next);
}
みたいに書けます。
で、そう考えると、n回の単純ループでしかないんですが、これではバブルソートにならないのでは?
リスト構造なら挿入ソートやマージソートの方が簡単に書けます。
No.4
- 回答日時:
てゆ~か、折角「双方向リスト」になってんだから、リスト構造は書き換えちゃイカンよ。
入れ替え作業は
void sort_list(struct cell **head){
struct cell *p, *p2;
int i, n,d;
n = 0;
p = *head;
while(p->next != (struct cell *)NULL){
p = p->next;
n++;
}
int d;
for(i = 0, p = *head; i < n-2; i++){
d = p->data;
if(d > p->next->data){
p->data = p->next->data;
p->next->data = d;
}
p=p->next;
}
で良いだろ?
構造(繋がり)はそのままで、データだけ取り替えろよ。
No.2
- 回答日時:
A B C D E F
というデータの並びを考えましょう。
pが Cを指しているとすると
> p2 = p->next;
p2はDになります。
> p->next = p->next->next;
CのnextはEになります。
> p->next->next = p;
CのnextはEになったので、p->next->nextはEのnextです。これがCになります。
> p->next->next->prev = p;
p->next->nextはCになったので、CのprevがCになります。
> p->next->prev = p->prev;
p->nextはEなので、EのprevがCのprevとなりますが、これはCになっています。
> p->prev = p2;
CのprevがDになります。
以上の操作で、CのprevがDでnextがE、EのprevがCでnextがCになります。
最初にCのnextをEにしたのに、Dのつもりで使ってませんか?
No.1
- 回答日時:
とりあえず
void sort_list(struct cell **head)
の中の
p->next = p->next->next;
p->next->next = p;
p->next->next->prev = p;
p->next->prev = p->prev;
p->prev = p2;
のあたりは怪しい気がする.
この回答への補足
自分もそこがいけないとはわかっているのですが、
どこが違うのかが分かりません。
自分の中ではあっていると思うのですが、無限ループになっているので間違っているに決まってるんですよね。
どこがいけないのでしょうか。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- その他(プログラミング・Web制作) pythonにおける単方向リストの実装について 4 2022/07/13 12:34
- C言語・C++・C# leetcode21 1 2022/04/21 11:53
- C言語・C++・C# C言語 leetcode21 Merge Two Sorted Lists 2 2022/04/24 19:35
- C言語・C++・C# カードシャッフルのブログラムを使ってc言語でブラックジャックをしたい 2 2022/04/12 15:13
- その他(プログラミング・Web制作) 十進BASICでの再帰についての質問です。 2 2022/11/18 09:17
- Visual Basic(VBA) ExcelVBAに関する質問 3 2023/02/17 10:47
- Excel(エクセル) B列に文字がはいったらA列に数字が入るマクロードを完成させたい 4 2023/04/21 01:58
- C言語・C++・C# バイナリファイルをコピーするのにかかる時間を測りたいのですが実行するとFatel error:gli 2 2022/11/03 01:10
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
InvokeMemberメソッドとは何を...
-
ばばぬきプログラムについて
-
構造体のリスト削除
-
「an=(n-1)/(n+1)のときlim[n→∞...
-
Enterキーを押されたら次の処理...
-
マイナスからプラスへ転じた時...
-
C言語での引数の省略方法
-
「指定されたキャストは有効で...
-
DWORDの実際の型は何でしょうか
-
fgetsなどのときのstdinのバッ...
-
c言語で、繰り返し文の中で、0....
-
2÷3などの余りについて
-
#define _CRT_SECURE_NO_WARNIN...
-
複数桁10進数の*桁目だけを抽出...
-
*をユーザーが入力した数字の数...
-
プログラムでの数字につく”f”の...
-
正負を反転させて出力するプロ...
-
(int *)の意味
-
sscanfとscanfの違いがよくわか...
-
C言語のプログラムで#include<m...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
InvokeMemberメソッドとは何を...
-
構造体のリスト削除
-
双方向リストのバブルソートに...
-
バブルソートを使って文字列を...
-
空のカラムを挿入
-
C言語 リスト
-
isset — 変数が宣言されている...
-
コールバック関数はnullになら...
-
C#でのEXCEL出力に関して
-
リスト構造
-
バグの原因がわかりません(c言...
-
API 録音 MCI
-
【C++】ストリームオブジェクト...
-
ポインタを使った連結リストへ...
-
C# ref引数のnull判定
-
.htaccessで
-
マイナスからプラスへ転じた時...
-
2÷3などの余りについて
-
信頼区間の1.96や1.65ってどこ...
-
「指定されたキャストは有効で...
おすすめ情報