課題

[774]

こんばんわ、前回学校の課題で質問をしに来たものです。

今回も課題が詰まってしまい、悩んでおります。
今回の課題の内容は、構造体を使っての双方向の連結リストです。
０～９までの乱数を30個入れて、出来上がった連結リストを昇順でソートして表示、逆表示もする。
ソートにかかった時間も表示する事。
ただし、ソートはなるべく早くソートする。
という内容でした。

今回使うプログラムのソースファイルは3つに分かれています。

4-1.ｃ・・・乱数生成、ソート前とソート後の表示、ソート後の逆表示、かかった時間の表示に使う。書き換えはしない。
4-2.ｃ・・・ソートをするプログラムを書くところ。
ex4.h・・・構造体作って、関数の前宣言書いている。書き換えはしない。

という風になっております。

ソートを検索してバブルソートでソートしようとプログラムを書き込んだのですが、動かなくなってしまいました。
どうすればソートができるのかがわかりません、どうか教えてください・・・


今回3つのファイルになっているのでソートをする4-2.cを乗せて後は圧縮ファイルで付属させようと思います。
下が4-2.ｃのプログラムです。

#include <stdio.h>
#include <stdlib.h> /* NULLポインタ */
#include "ex4.h"
void sort(struct node **start, struct node **end)
{
	/* 変数宣言（必要に応じて増やす） */
	struct node *s, *e, *p, *q, *tmp;
	
	/* 初期値代入 */
	s = *start;
	e = *end;
	
	/* TO DO ここに必要な処理を記述する */
	for(p=s; p->next!=NULL; p = p->next)
	{
		for(q=e; q->prev!=NULL; q = q->prev)
		{
			if(p->data >= q->data)	//p->data　が　q->data以上の時
			{
				tmp = p;
				p->data = q->data;
				p->next = q->next;
				p->prev = q->prev;
				q = tmp;
			}
		}
	}
	/* 結果代入 */
	*start = s;
	*end = e;
}

あと・・・課題には関係ありませんが、前回の課題で色々と解説をしてくださったのに返信ができずに過去ログという形で終わらせてしまってすみませんでした・・・
この場をかりてお詫び申し上げます・・・OTL

[box]

双方向リストに格納する際に昇順（または降順）に並んでいる状態にしておいて、
先頭から出力すれば昇順（または降順）に並んでいますし、
最後から出力すれば降順（または昇順）に並んでいます。

乱数の発生順（未ソートの状態）で双方向リストに格納したデータを後からソートするのは、
できなくはないと思いますがそれなりに手間がかかりそうです。

[Sleepy]

ポインタと実体について復習が必要かと思われます。

それとデータ量30個程度であれば処理時間を図るのはかなり困難でしょう。

[non]

boxさんが言われるように、リスト作成時に並べ替えなければ、リスト構造の意味がないと思いますが、
これが、課題ならしょうがない。
まずは、通常のソートを考えるのではなく、既にあるリストを先頭から１つずつノードを読んで、別のリストに昇順にリスト構造を作成していくのを考えた方が良いと思います。（挿入場所を探してノードを入れる）
それが、出来てからもっとはやい方法を考えるのでしょうね。
この場合、リスト構造に番兵を付けた方が簡単だと思います。ないと、特別解が増えます。


>それとデータ量30個程度であれば処理時間を図るのはかなり困難でしょう。

プログラムを読むと実際は5000個のようです。
ちなみに私のボロノートでは55.11秒かかりました。

なお、clock()の使い方として１回目の時間も記憶しておいて、２回目との差を求めなくてはいけないと思うのですが私の勘違いかな？

[non]

>プログラムを読むと実際は5000個のようです。
50000個の間違いです。

[７７４]

返信ありがとうございます！

未ソートによる双方向のソートはそれくらい難しいのですか・・・
あといろいろとプログラムに沢山のミスがあったこともこのレスでわかりました。

アドバイスと説明をありがとうございました！

あと、non様の
clock()の使い方として１回目の時間も記憶しておいて、２回目との差を求めなくてはいけないと思うのですが私の勘違いかな？

ですが、聞いた話ですと

time(&t1);　//スタート
～間～
time(&t2);　//ストップ

printf("%d", t2-t1);　//経過時間表示

というのが

/*結果出力*/
ct = clock();
printf("\nResult of sorting:\n");　//昇順に並べるソート表示開始
print_list(start);
～間～
printf("Verify a reverse:\n");　//降順に表示開始
print_reverse(end);　//表示終了

printf("program costs %4.2f sec.\n", (double)ct/CLOCKS_PER_SEC);　//経過時間表示

(double)ct/CLOCKS_PER_SEC　が　上の　t2-t1　と同じで時間を表示している。

という風にex4-1.cに作られているのでソートだけを考えればいいといわれました。

説明不足でしたらすいません・・・

[non]

/* ソート */
	clock();
	sort(&start, &end);
	
	/* 結果出力 */
	ct = clock();
	printf("\nResult of sorting:\n");
	print_list(start);
	
	printf("Verify a reverse:\n");
	print_reverse(end);
	
	printf("Program costs %4.2f sec.\n", (double)ct/CLOCKS_PER_SEC);

１回目のclockでの戻り値を変数にいれなくていいのかなと思ったんです。
いつも私は、一度目も変数に入れて、(ct-ct1)/CLOCKS_PER_SEC してるものですから。
確か、clockは起動してからの経過時間だったと（確認してないけど）思うので、実行後の時間が表示されないのかなって。

[774]

えーっと・・・これは学校の先生が用意した課題のソースで、この内容は書き換えないといわれているだけで説明は受けてないので確実にはいえないのですが・・・多分clock();でソートする時間を数えるのでスタートさせてソートが終了したらそれまでの値をctに入れて　printf（）で(double)ct/CLOCKS_PER_SECとするとスタートしてからソート終了までの時間をCLOCKS_PER_SECが割って秒単位にしてくれている。
・・・ということだと思っていたのですが・・・間違ってるかもしれません、これはわからないので、すいません・・・
とりあえず課題が完成した友達によるとちゃんと表示してくれているそうです。

[non]

まぁ、clockの方は置いといて、課題の方は出来ましたか？

[７７４]

えっと・・・自分なりに考えてfor文のまわし方を直したりもしソートをする時の条件分岐も作って見たのですが、まだどこかでダメのようです

一応、こんな風になっております。

#include <stdio.h>
#include <stdlib.h> /* NULLポインタ */
#include "ex4.h"
void sort(struct node **start, struct node **end)
{
	/* 変数宣言（必要に応じて増やす） */
	struct node *s, *e, *tmp, *p, *q, *r, *t, *u;
	
	/* 初期値代入 */
	s = *start;
	e = *end;
	
printf("ソートはりいます\n");
	/* TO DO ここに必要な処理を記述する */
	for(p=s; p!=NULL; p=p->next)
	{
		for(q=p->next; q!=NULL; q=q->next)
		{
			if(p->data >= q->data)
			{
				if(p->prev == NULL) //もし先頭だったら
				{
printf("先頭いきマス\t");
				
					tmp = p;
					p->next = q->next;
					p->prev = q->prev;
					q->next = tmp->next;
					q->prev = tmp->prev;
					
					t = q->prev;
					r = q->next;
				
					t->next = q;
					t->prev = p;
					t->prev = q;
					
printf("先頭おわり\n");					
				}
				else if(p->next == q) //隣同士だったら
				{
printf("となり\t");
					tmp = p;
					p->next = q->next;
					p->prev = q;
					q->next = p;
					q->prev = tmp -> prev;
					
					t = q->prev;
					r = p->next;
					
					tmp = t->next;
					t->next = p->prev;
					r->prev = tmp->prev;
					
printf("おわり\n");
				}
				else //間の開いた列だったら
				{
printf("ソート\n");
					tmp = p;
					p->next = q->next;
					p->prev = q->prev;
					q->next = tmp->next;
					q->prev = tmp->prev;
				
					t = q->prev;
					r = q->prev;
					u = p->next;
					
					t->next = q;
					r->next = p;
					r->prev = q;
					u->prev = q;
printf("ソートおわります\n");
					
				}
			}
		}
	}
			
	
	/* 結果代入 */
	*start = s;
	*end = e;
}

ところどころにあるprintfはどこを回っているかのチェックのためのものです。
隣同士とソートの所で無限ループには言っていると思うのですが・・・まだわかってないです・・・

[non]

本当にこのように繋ぎ変えなければいけない問題なのでしょうか？
中のデータだけ交換すればいいのではないでしょうか？繋ぎ変えずに。
その方が、遙かに簡単で早い。

それよりも、前に言ったように、リスト構造を作り直す方法がいいと思いますが。。。。
参考までに。

void sort(struct node **start,struct node **end)
{
	struct node *s,*e,*p,*q,*r;
	s=e=NULL;
	while(*start!=NULL){
		q=*start;
		*start=(*start)->next;
		if(s==NULL){
			q->next=NULL;
			s=e=q;
		}else{
			for(p=s;p!=NULL;p=p->next){
				if((p->data)>=(q->data)) break;
			}
			if(s==p){//先頭追加
				q->prev=NULL;
				q->next=s;
				s->prev=q;
				s=q;
			}
			else if(p==NULL){//最後尾追加
				q->next=NULL;
				q->prev=e;
				e->next=q;
				e=q;
			}
			else{ //途中追加
				q->next=p;
				q->prev=p->prev;
				p->prev->next=q;
				p->prev=q;
			}	
		}
	}
	*start=s;
	*end=e;
}

[non]

中のデータだけ交換し繋ぎ換えをしない場合のプログラムはこうなります。

void sort(struct node **start, struct node **end)
{
	/* 変数宣言（必要に応じて増やす） */
	struct node *p, *q;
	int tmp;
	/* TO DO ここに必要な処理を記述する */
	for(p=*start; p->next!=NULL; p=p->next){
		for(q=p->next; q!=NULL; q=q->next){
			if((p->data)>(q->data)){
				tmp=p->data;
				p->data=q->data;
				q->data=tmp;
			}
		}
	}
}

ほら、遙かに簡単でしょ。
でも、これなら、void sort(struct node **start, struct node **end)にしなくていいですね。
void sort(struct node *start)　これでいい。
だから、先生の意図と違います。
でも、ノードを繋ぎ変えてソートしたら、50000個やると、ものすごく時間がかかりますし、現実的でないのでいくら課題とはいえ、そんな問題出しますか？
僕が先生なら、リスト構造から２分木構造を作成して並び替えさせ、それを再び、リスト構造にする課題にしますけどね。
どうしても、今やってる方法でやるのならお手伝いしますけど、かなり無駄があるプログラムのようでしたよ。

[７７４]

こういうやり方もあったのですね・・・参考になりました！
えっと、この課題は双方向のリストは前と後ろからつなげるって言う考え方があると言う事を理解すると言うことらしいです。