過去ログ
No．１２１１ リストのバブルソート
[戻る] [ホームページ]No.15942 |
リストのバブルソートについて 投稿者---Zk(2004/07/28 02:34:25) |
||
以前こちらでリストのクイックソートについて質問させていただいた者です。 ヒントやプログラムを教えていただき、自分なりの理解をすることができました。その後、リストのバブルソートを行うプログラムを作成しているのですが、どうもうまく動きません。(最後の構造体がNULLの場合の処理方法と、一連のソートの動作を繰り返す方法についてです。) 本来ならソート部分は関数として別に作るものだとは思いますが、あえてmain関数の中で作成しようと思っています。 どうかヒントを宜しくお願いします。 number.txtの内容↓ 321 285 154 675 972 158 環境：Borland 5.5 /*リストによるバブルソート*/
#include <stdio.h>
#include <string.h>
typedef struct Number *num_p;
typedef struct Number {
num_p next;
int num;
}num_t;
num_p start=NULL;
/*バブルで使用*/
num_p first=NULL;
num_p second=NULL;
num_p third=NULL;
main() {
FILE *infp;
char buf[256];
num_t *p,*q;
int *strp;
if ((infp = fopen("number.txt", "r")) == NULL) exit(-1);
while (fgets(buf, sizeof(buf), infp)!=NULL) {
if((p = (num_t *) malloc(sizeof(num_t)))==NULL) exit(-1);
strp=strtok(buf, " ");
p->num=atoi(strp);
if(start==NULL){
start=p;
p->next=NULL;
}
else{
for(q=start;q!=NULL;q=q->next){
if(q->next==NULL) break;
}
}
q->next=p;
p->next=NULL;
}
/*バブルソート開始*/
for(p=start;p!=NULL;p=p->next){
/*別の箱にポインタを格納しておく*/
first=p;
second=p->next;
third=p->next->next;
if(first->num > second->num){ /*firstとsecondの値を比較*/
if(third==NULL){
printf("####first>second and third==NULL####\n");
p->next->next=first;
p->next=NULL;
p=second;
/*動作確認用印刷*/
printf("%d %d %d\n",first->num,second->num,third->num);
printf("%d %d %d\n",p->num,p->next->num,p->next->next->num);
}
else {
printf("####first>second and third->not NULL####\n");
p->next->next=first;
p->next=third;
p=second;
/*動作確認用印刷*/
printf("%d %d %d\n",first->num,second->num,third->num);
printf("%d %d %d\n",p->num,p->next->num,p->next->next->num);
}
}
else if(first->num < second->num){
if(third==NULL){
printf("####first<second and third==NULL####\n");
third=NULL;
}
}
else {
if(third==NULL){
third=NULL;
}
}
}
for (p=start; p!=NULL; p=p->next) {
printf("%d\n",p->num);
}
fclose(infp);
}
|
|||
| No.15946 |
Re:リストのバブルソートについて 投稿者---タコな人(2004/07/28 11:50:45) |
||
バブルソートですが、 for(... for(.... とループが２重になると思うのですが、 隣り合うデータを比較しながら、交換して。最後までいったら、もう一度最後よりひとつ手前までを交換するという手順では、なかったでしょうか。 |
|||
| No.15947 |
Re:リストのバブルソートについて 投稿者---Zk(2004/07/28 12:39:47) |
||
レスありがうございます。 >とループが２重になると思うのですが、 >隣り合うデータを比較しながら、交換して。最後までいったら、もう一度最後よりひとつ手前までを交換するという手順では、なかったでしょうか。 たしかに、そうでした。 最後より一つ手前まで、という動作をどのようにリストでうごかしていいものか現在悩んでいます…。 |
|||
| No.15952 |
Re:リストのバブルソートについて 投稿者---タコな人(2004/07/28 13:50:20) |
||
>最後より一つ手前まで、という動作をどのようにリストでうごかしていいものか現在悩んでいます…。 望んでいる回答とは違うかもしれませんが /*リストによるバブルソート*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Number *num_p;
typedef struct Number {
num_p next;
int num;
}num_t;
num_p start=NULL;
/*バブルで使用*/
num_p first=NULL;
num_p second=NULL;
num_p third=NULL;
main() {
FILE *infp;
char buf[256];
num_t *p,*q;
int *strp;
/* 追加 */ int i, n, temp ;
n = 0 ;
if ((infp = fopen("number.txt", "r")) == NULL) exit(-1);
while (fgets(buf, sizeof(buf), infp)!=NULL) {
if((p = (num_t *) malloc(sizeof(num_t)))==NULL) exit(-1);
strp=strtok(buf, " ");
p->num=atoi(strp);
n++ ; /* 追加 */
if(start==NULL){
start=p;
p->next=NULL;
}
else{
for(q=start;q!=NULL;q=q->next){
if(q->next==NULL) break;
}
}
q->next=p;
p->next=NULL;
}
for (p=start; p!=NULL; p=p->next) {
printf("%d\n",p->num);
}
/*バブルソート開始*/
for (i = 0; i < n - 1; i++)
for(p=start;p->next!=NULL;p=p->next){
/*別の箱にポインタを格納しておく*/
first=p;
second=p->next;
if(first->num > second->num){ /*firstとsecondの値を比較*/
printf("####first>second ####\n");
temp = first->num ;
first->num = second->num ;
second->num = temp ;
} else
printf("Not Change\n") ;
printf("%d %d\n",first->num,second->num);
printf("%d %d\n",p->num,p->next->num);
}
for (p=start; p!=NULL; p=p->next) {
printf("%d\n",p->num);
}
fclose(infp);
}
|
|||
| No.15948 |
Re:リストのバブルソートについて 投稿者---ニタチ(2004/07/28 12:47:50) |
||
strp=strtok(buf, " ");
p->num=atoi(strp);
ここは sscanf(buf, "%d", &p->num); としていいのでは？
それから、strtok()の戻り値はchar *型です。
if(start==NULL){
start=p;
p->next=NULL;
}
else{
for(q=start;q!=NULL;q=q->next){
if(q->next==NULL) break;
}
}
q->next=p;
p->next=NULL;
この2行はelse文の中ですね。
first=p;
second=p->next;
third=p->next->next;
ソート内のここも問題です。
pがNULLの時はp->next、p->next->next等を参照してはいけないはずです。
ソートもバブルソートと言えない気がしますが･･･。
|
|||
| No.15951 |
Re:リストのバブルソートについて 投稿者---Zk(2004/07/28 13:35:24) |
||
失礼しました！NULLの存在がすっかり抜けてしまっていました。 まず、上でご指摘いただいた部分は直し、途中までは正確に動くことを確認しました。 > first=p; > second=p->next; > third=p->next->next; >ソート内のここも問題です。 >pがNULLの時はp->next、p->next->next等を参照してはいけないはずです。 >ソートもバブルソートと言えない気がしますが･･･。 現段階では、『バブルソート』を行う前に、一回目のソート(入れ替え)ができるように作成しています。 (この考え方がいけないのかもしれません…) セグメントエラーが出ているのですが、多分その部分ではないかと考えています。 NULLの場合、入れ替えるべき矢印がないので、どのようにすればよいか悩んでいます。 |
|||
| No.15953 |
Re:リストのバブルソートについて 投稿者---かずま(2004/07/28 14:16:17) |
||
リストのバブルソートのプログラムを書いてみました。リンクをどうつなぎ 換えているかは図を描いてみるとわかると思いますが、いかがでしょうか？
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
struct Node *next;
int data;
} Node;
int main(void)
{
Node *head = NULL, *p, *t, dummy;
int data, swap;
FILE *fp = fopen("number.txt", "r");
if (fp == NULL) puts("can't open number.txt"), exit(1);
while (fscanf(fp, "%d", &data) == 1) {
p = malloc(sizeof(Node));
if (p == NULL) puts("out of memory"), exit(1);
p->next = NULL; p->data = data;
if (head) t = t->next = p;
else head = t = p;
}
if (head && head->next)
do {
dummy.next = head;
swap = 0;
for (p = &dummy; p->next->next; p = p->next)
if (p->next->data > p->next->next->data) {
swap = 1;
t = p->next;
p->next = t->next;
t->next = p->next->next;
p->next->next = t;
}
head = dummy.next;
} while (swap);
for (p = head; p; p = p->next) printf("%d\n", p->data);
return 0;
}
|
|||
| No.15956 |
Re:リストのバブルソートについて 投稿者---Zk(2004/07/28 15:19:43) |
||
みなさま、本当にありがとうございます。 載せていただいた解答を元に、自分のプログラムを少しずつ動かすことができました。少し改良の余地があるので研究していきます。 とても勉強になりますね。 また、行き詰まったら質問させていただくかもしれませんが、どうぞ宜しくお願いします。 |
|||
| No.15973 |
Re:リストのバブルソートについて 投稿者---かずま(2004/07/28 20:25:58) |
||
バブルソートの処理を少し修正します。
if (head) {
dummy.next = head;
do {
swap = 0;
for (p = &dummy; p->next->next; p = p->next)
if (p->next->data > p->next->next->data) {
swap = 1;
t = p->next;
p->next = t->next;
t->next = p->next->next;
p->next->next = t;
}
} while (swap);
head = dummy.next;
}
|
|||