学校の課題を教えてください2

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
ほがら

学校の課題を教えてください2

#1

投稿記事 by ほがら » 2年前

コード:

/* インクルード宣言 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h> // 所要時間計測に必要

/* 定数宣言 */
#define SIZE 2000000 // 単語数
#define LEN  30     // 単語文字数

/* プロトタイプ宣言 */
void m_sort(char** list, int start, int end, int mode); // ソート部
int comp(char *w1, char* w2, int mode); // 用途別比較関数
long gettimeofday_micro(void); // 所要時間計測用関数

/* 変数宣言(マージ用)*/
char* m_space[SIZE];

int comp(char* s1, char* s2){
   if(strlen(s1) != strlen(s2))
     return strlen(s2) - strlen(s1);
   else
     return strcmp(s1, s2);
}

void q_sort(char** list, int start, int end){
   char pivot[LEN];
   int i, j;
   char *tmp;

   if(end - start < 1)return;
   strcpy(pivot, list[(start + end) / 2]);

   i = start; j = end;

   while(1){
     while(comp(list[i], pivot) < 0) i++;
     while(comp(list[j], pivot) > 0) j--;

     if(i >= j) break;

     tmp = list[i];
     list[i] = list[j];
     list[j] = tmp;
     i++; j--;
   }

   q_sort(list, start, i - 1);
   q_sort(list, j + 1, end);
}
    


/* メイン関数 */
int main(int argc, char *argv[]){
	/* 変数宣言 */
	FILE* fp = NULL; // ファイルポインタ
	char line[LEN]; // 文字列読み込み用
	char** strs = (char**)malloc(sizeof(char*) * SIZE); // 文字列格納用
	int count = 0; // 単語数格納用
	long time1, time2; // 時刻(単位マイクロセカンド)格納変数
	int i; // カウンタ変数

	// ファイル読み込み
	fp = fopen("wordlist.txt", "r");
	while(fscanf(fp, "%s", line) != EOF){
		strs[count] = (char*)malloc(sizeof(char) * LEN);
		sprintf(strs[count], "%s", line);
		count++;
	}
	fclose(fp);

	// マージソート
	time1 = gettimeofday_micro();
	m_sort(strs, 0, count - 1, 0); // アルファベット順でソート
	m_sort(strs, 0, count - 1, 1); // 長さでソート
	time2 = gettimeofday_micro();
	printf("マージソート:\t%6.3f 秒\n", (time2 - time1) / 1000000.0);

	// ソート結果出力
	fp = fopen("wordlist_m.txt", "w");
	for(i = 0 ; i < count ; i++){
		fprintf(fp, "%s\n", strs[i]);
	}
	fclose(fp);

	return 0;
}

/* ソート部 */
void m_sort(char** list, int start, int end, int mode){
	int i, j, k, m;

	// 要素数が2未満ならソート不要
	if(end - start < 1){
		return;
	}

	// 分割操作
	m = (start + end) / 2;
	m_sort(list, start, m, mode);
	m_sort(list, m + 1, end, mode);
	for(i = start ; i <= m ; i++){
		m_space[i] = list[i];
	}
	for(j = m + 1 ; j <= end ; j++){
		m_space[j] = list[j];
	}

	// マージ操作
	i = start;
	j = m + 1;
	for(k = start ; k <= end ; k++){
		if(i > m)
			list[k] = m_space[j++];
		else if(j > end)
			list[k] = m_space[i++];
		else{
			if(comp(m_space[i], m_space[j], mode) > 0){
				list[k] = m_space[i++];
			}
			else{
				list[k] = m_space[j++];
			}
		}
	}
}

/* 用途別比較関数 */
int comp(char *w1, char* w2, int mode){
	switch(mode)
	{
	case 0:
		return strcmp(w1, w2);
	case 1:
		return strlen(w1) - strlen(w2);
	}

	return 0;
}

/* 所要時間計測用関数 */
long gettimeofday_micro(void){
	struct timeval _tv;
	gettimeofday(&_tv, NULL);
	return _tv.tv_sec * 1000000 + _tv.tv_usec;
}

文字列データを読み込み,クイックソートでソートしてその結果をwordlist_q.txtに出力するプログラムを作成せよ.
ただし,(1) ソート結果は文字数の長い順で且つ同じ文字数同士はアルファベット順になるようにし,(2) ソートの所要時間を標準出力する機能を実装すること.また,(3) 添付のマージソート版より高速であること.
qsort関数などの既存の関数は利用せず,自分でクイックソートのコードを書くこと.

という課題でプログラムを書いてみましたがうまくいきません。どこが問題なのでしょうか?よければ教えてください。環境はLinaxです。

box
記事: 2002
登録日時: 13年前

Re: 学校の課題を教えてください2

#2

投稿記事 by box » 2年前

うまくいきません。
「何をしたとき」
「どのように」
うまくいかないかを具体的に書いてください。

comp()の実体が2つありますが大丈夫ですか?
クイックソートの結果をwordlist_q.txtに書き込むコードがないように見えますが大丈夫ですか?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

返信

“C言語何でも質問掲示板” へ戻る