バブルソートを使って文字列を辞書順に並べるプログラムを作成したいのです

質問

バブルソートを使って文字列を辞書順に並べるプログラムを作成したいのですがうま...
it200189さん

バブルソートを使って文字列を辞書順に並べるプログラムを作成したいのですがうまくいきません・・・。
バブルソートを使って文字列を辞書順に並べるプログラムを作成したいのですが、コンパイルはできますが実行してもうまく出力されません・・・。
どこがおかしいのか、わからないので詳しい方よろしくお願いします。
またこのやり方とは異なる方法で作成できるという方せひプログラムを掲載してください！
参考にさせていただきます！

#include<stdio.h>
#include<string.h>

struct QUEUE{
struct QUEUE *prev;
struct QUEUE *next;
char alpha[];
};

static struct QUEUE name[10];

void InQueue(struct QUEUE * dst ,struct QUEUE *src){
src->prev = dst->prev;

src->next = dst->prev->next;
dst->prev = src;
dst->prev->next = src;

}

void DeQueue(struct QUEUE *src){
src->prev->next = src->next;
src->next->prev = src->prev;
}

void InitQueue(struct QUEUE *pQueue ,int size){
int i;
struct QUEUE *pEndQueue;
struct QUEUE *pTempQueue;
pEndQueue = pQueue + size-1;

pQueue->prev = NULL;
pQueue->next = pEndQueue;

pEndQueue->prev = pQueue;

pEndQueue->next = NULL;

pTempQueue = pQueue + 1;
pEndQueue = pEndQueue - 1;

pTempQueue->prev = NULL;
pTempQueue->next = pEndQueue;
pEndQueue->prev = pTempQueue;
pEndQueue->next = NULL;

i = 3;
while ( i < size - 2) {
pTempQueue = pQueue + i;
InQueue(pEndQueue,pTempQueue);
i++;
}
}

void BubbleSort(struct QUEUE *pSort ,int size){
int i;
int j;
// struct QUEUE *pTemp;
// pTemp = pSort;
while(size > 0){
i = 0;
// pSort = pTemp;
pSort = name[1].next;
while(i < size - 1){
j = 0;
while(pSort->alpha[j] != '\0'){
if(pSort->alpha[j]>pSort->next->alpha[j]){
DeQueue(pSort->next);
InQueue(pSort,pSort->next);
break;
}
else if(pSort->alpha[j]<pSort->next->alpha[j]){
pSort = pSort->next;
break;
}
j++;
}
i++;
}
size--;
}
}

void main(){
int i;
// static struct QUEUE name[10];
struct QUEUE *pStr;
char str[4][10] = {"tani","okada","naka","oka"};

InitQueue(name,8);

i = 0;
while(i<4){
strcpy(name[i + 2].alpha,str[i]);
i++;
}
BubbleSort(name[1].next,4);

pStr = name[1].next;
i = 0;
while(i<4){
printf("%s\n",pStr->alpha);
pStr = pStr->next;
i++;
}
}

回答No.2

kmee · ベストアンサー

> DeQueue(pSort->next);
> InQueue(pSort,pSort->next);

この動作をよく考えてください

A⇔B(=pSort)⇔C(=pSort->next)⇔D⇔E
と並んでいるところで DeQueue(pSort->next)とすると
A⇔B(=pSort)⇔D(新しいpSort->next)⇔E
となります。
そこで InQueue(pSort,pSort->next);とすれば、pSortの位置にpSort->next、つまりBの位置にDを入れようとします。
Cではありません。この双方向リストからCにアクセスする方法は失われてしまいました。
動作がおかしくなるのも道理です。InQueueにこのBDを当てはめれば、リスト構造がぐちゃぐちゃになることがわかります。
/*
呼び出し時点では以下の通り
A->next = B
B->prev = A, B->next = D
D->prev = B, D->next = E
*/
D->prev = B->prev; /* → D->prev = A */
D->next = B->prev->next; /* → D->next = A->next → D->next =B */
B->prev = D;
B->prev->next = D; /* → A->next = D */
/*
終了では以下の通り
A->next = D
B->prev = D, B->next = D
D->prev = A, D->next =B
*/

対策するなら、 削除する要素(上の例のC)を覚えておく変数を用意して
t = pSort->next; /* struct QUEUE *t; と宣言しておく */
DeQueue(pSort->next);
InQueue(pSort,t);
とするか、入れかえ専用関数を用意するかです

他にも
> char alpha[];
大きさが指定されていないので、strcpyでコピーできるだけの大きさがありません。
とか、
> pSort = name[1].next;
ソートの途中過程で順番が入れ替わっているので、先頭を表しているとは限りません。
とか、
InitQueueの動作と、実際に使っている様子とが一致してないとか(QUEUEの仕様をちゃんとまとめてないのでは?)
とか、
BubbleSort関数の引数pSortの意味がない
とか、
そもそも、Queue(待ち行列)というデータ構造の名前と、実際の動作が一致してないのは、なんかしっくりこない
とか、色々とあります。

こちらで実際に動かせるようになるまで、そうとう箇所の変更が必要でした。

回答No.3

anicicle

http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1440578529

回答No.1

asuncion

リスト構造の配列、というデータ構造を採用した
理由を教えてください。

そのデータ構造を使っているために、本来はもっと簡単に
書けるプログラムを変にこねくり回しているように見えます。