双方向リストのバブルソートについて

質問

双方向リストをバブルソートを用いてソートしたいです。
下記がプログラム(一部)ですが、ソートした後にリスト表示すると
無限ループに陥ります。
どこがいけないのでしょうか。

#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

chie65535 · ベストアンサー

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;

と同じ意味になる。

「自分の前は自分」と言う状態になり、この状態で、もう一度上記のルーチンを通ると「自分の次は自分」と言う状況が出来上がる。

表示ルーチンは「自分の次が、次」とやっているのだから、リストが「自分の次は自分」になってれば、無限ループするのが当たり前。

ソートルーチンで、２つの要素を入れ替えする場合は、以下に示した[1]～[6]の６つのポインタを書き換えないといけない筈。

pの---[1]-->p---[3]-->p2---[5]-->p2の
前 <--[2]---　<--[4]---　 <--[6]---次

質問者さんのプログラムでは「５つしか書き換えてない」ので、それだけで「バグっている」のが明白。

以上を踏まえると、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.7

Tacosan

「どう悪いのか」は既にほかの回答者が書いているので省略するとして.

何が悪いのか, あなたはどのようにチェックしたのでしょうか. 紙の上に実際に構造を書いてポインタをどう張り替えればよいかを (まさに #3 でやられているように) 明確にしておけば割と簡単に見つかるはずですが, そういう手間をしっかりとかけましたか?

お礼

紙に書いてやった結果がこうだったので、わからず質問させてもらいました。
自分の能力低いですね。

回答No.6

chie65535

蛇足な追記。

「prev、nextのポインタじゃなく、データを入れ替えろ」と言う意見をしたが、データが大きい場合、質問者さんはこの意見には賛成できないと思う。

だって「巨大なデータを入れ替えると、入れ替えに時間がかかる」って思う筈だから。

でも、やはり「データだけ入れ替えた方が早い」のだ。

どうするかと言うと「リストに、データの実体ではなく、データのポインタだけを持つ」ようにするのだ。

そうすれば、データの実体は入れ替えずに済んで「ポインタが指すアドレス」だけを入れ替えれば済んじゃうようになる。

例えば、リスト構造を

struct cell{
void *data_ptr; /*数キロバイトの大きなデータのアドレスを指すポインタ*/
struct cell *next, *prev;
};

にして、データの実体は別の所に確保して、data_ptrに確保したアドレスを代入しとけば良い。

そうすりゃ

void *d_ptr;

の作業用変数１つと

d_ptr = p->next->data_ptr;
p->next->data_ptr = p->data_ptr;
p->data_ptr = d_ptr;

の3行で、数キロバイトの大きなデータが瞬時に入れ替わる事になる。

スワップ作業を「データのスワップ」にした場合、「リストへの要素の追加」と「リストから要素の削除」さえきちんと動けば「リストの繋がりは変わらない」のだから、バグが起きる余地が無くなる。

回答No.5

kmee

ポインタを数値で表現してみます。

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

chie65535

てゆ～か、折角「双方向リスト」になってんだから、リスト構造は書き換えちゃイカンよ。

入れ替え作業は

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

m-take0220

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

Tacosan

とりあえず
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;
のあたりは怪しい気がする.

補足

自分もそこがいけないとはわかっているのですが、
どこが違うのかが分かりません。
自分の中ではあっていると思うのですが、無限ループになっているので間違っているに決まってるんですよね。
どこがいけないのでしょうか。