mallocの動作について

質問

RadixSort（基数ソート）で名簿のソートを行うプログラムを書いています。
Queueの挿入操作をする関数enqueueで処理が滞ってしまいます。
コンパイルは通りますが、どうやら「ココ→」（２箇所に書いておきました）で示した行が原因で止まってしまうらしいです。
対処方法が分からずに行き詰っています。どなたかご存知の方、教えていただけると嬉しいです。
ソースの前に、簡単ながらアルゴリズムを記しておきます。

１．名簿のテキストファイルを読み込む。
２．各人の名前は左詰で書かれている。
３．名前の右側にアルファベット順で'A'よりも先にくる文字'_'を詰める。
４．名前に使われる文字の種類だけキューを用意する。
５．名前の一番右側の文字を参照し、その文字に対応するキューに名前を入れる。
６．各キューに「落とし蓋」に相当する文字列を入れる。
７．最初のキューから順番にキューの後ろから名前を取り出し、名前の右から２番目の文字に対応するキューに名前を入れる。
８．取り出した名前が「落し蓋」であった場合は、次の番号のキューから名前を取り出すようにする。
９．全てのキューから全ての名前を取り出し、キューに入れなおす作業が終わったら、各キューに再び「落し蓋」をする。
１０．以下、７～９の作業を、参照する文字の位置を１つずつずらしながら行う。
１１．テキストファイルにソート結果を出力。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 80
#define FS '_' //名前の右に詰める文字

typedef struct cell{
　struct cell *next;
　struct cell *prev;
　char ch[N];
}cell;
typedef struct queue{
　struct cell *init;
　struct cell *final;
}queue;

void enqueue(queue *q, char *x);
int dequeue(queue *q, char *x);

int main(int argc, char *argv[]){
　FILE *fp_from, *fp_to;
　char temp[N], endline[N];
　int i, j;
　queue *q[54]; //0:空白用の文字, 1~52:アルファベット, 53:スペース
　for(i = 0; i < 54; i++){
　　q[i] = (queue *)malloc(sizeof(queue));
　　q[i]->init = NULL;
　　q[i]->final = NULL;
　}
　if(!argc){
　　printf("Please input a name of a listfile.\n");
　　return(1);
　}
　if(argc >= 3){
　　printf("You can input only two filenames.\n");
　　return(1);
　}
　if((fp_from = fopen(argv[0], "r")) == NULL){
　　printf("Reading error.\n");
　　return(1);
　}
　while(feof(fp_from) == 0){
　　fgets(temp, N, fp_from);
　　for(i = strlen(temp)-1; i < N; i++) temp[i] = FS; //空白用文字を名前の右側に詰める
　　enqueue(q[0], temp);
　}
　for(i = 0; i < N; i++) endline[i] = FS; //各キューの「落とし蓋」を用意
　for(i = N-1; i > 0; i--){
　　for(j = 0; j < 54; j++){
ココ→　enqueue(q[j], endline);　　//各キューに「落し蓋」を挿入する
　　}
　　for(j = 0; j < 54; j++){
　　　while(1){
　　　　dequeue(q[j], temp);
　　　　if(temp[0] == FS) break;
　　　　if(temp[i] == FS){
　　　　　enqueue(q[0], temp);
　　　　}else if((temp[i] >= 'A') && (temp[i] <= 'Z')){
　　　　　enqueue(q[temp[i]-'A'+1], temp);
　　　　}else if((temp[i] >= 'a') && (temp[i] <= 'z')){
　　　　　enqueue(q[temp[i]-'a'+27], temp);
　　　　}else if(temp[i] == ' '){
　　　　　enqueue(q[53], temp);
　　　　}else{
　　　　　printf("There was an unavailable symbol.\n");
　　　　　return(1);
　　　　}
　　　　free(temp);
　　　}
　　}
　}
　if(argc == 1) fp_to = fopen(strcat(argv[0], "_2.txt"), "w");
　else fp_to = fopen(argv[1], "w");
　for(i = 0; i < 54; i++){
　　while(1){
　　　if(dequeue(q[i], temp) == 1) break;
　　　　fputs(temp, fp_to);
　　　　　fputc('\n', fp_to);
　　}
　}
　fclose(fp_from);
　fclose(fp_to);
　return(0);
}

//キューqに１つの要素ｘを前から入れる。
void enqueue(queue *q, char *x){
　cell *r;
ココ→　r = (cell *)malloc(sizeof(cell));
　strcpy(r->ch, x);
　if(!q->init) q->final = r;
　r->prev = NULL;
　r->next = q->init;
　if(q->init) q->init->prev = r;
　q->init = r;
　return;
}

回答No.3

fonera · ベストアンサー

恐れ入ります。
No.2でお答えした者です。

pdfファイルの解説を読みました。
ご自分でお気づきになったようなので問題ないと思いますが、念のため解説しておきます。

・まず、キューに関して
今回のアルゴリズムにおけるキューは、（実装は双方向になっていますが）リストと、その先頭・末尾を示すポインタで実現できます。
Ａ→Ｂ→Ｃ→ＮＵＬＬ
↑　　　↑
末　　　先
キューに入れる（エンキュー）は、リストに追加して末尾のポインタを変えるだけ
Ｄ→Ａ→Ｂ→Ｃ→ＮＵＬＬ
↑　　　　　↑
末　　　　　先
キューから取り出す（デキュー）は、先頭のポインタを変えるだけ（リストから取り除くかはアルゴリズムによる）
Ｄ→Ａ→Ｂ→Ｃ
↑　　　↑
末　　　先

ココまででお気づきかと思いますが、これらは実態（メモリを確保してある部分）とは関係有りません。
その為、テンポラリキューを作ってもポインタ２つ分のメモリが増えるだけです。メモリの節約には、ほとんどなりません。（メモリを節約するなら、そもそも基数ソートは使わない）

#どうしても「落とし蓋」の概念を使ってみたいのでしたら、ポインタで実装した方が速いと思います。
#Ｄ→Ａ→Ｂ→Ｃ→ＮＵＬＬ
#↑　↑　　　↑
#末　蓋　　　先

>今までmalloc関数の行で止まったことが無かったものでして。
本当に
>ココ→　r = (cell *)malloc(sizeof(cell));
でエラーを出して止まりますか？
>strcpy(r->ch, x);
で止まっていませんか？
mallocは、（Cの標準ライブラリ関数を使用しているなら）失敗するとNULLを返します。メモリが確保できない（Windowsであればページングファイルを0にしたうえで、積んでいるメモリ以上のメモリを確保しようとすると簡単に再現できます）と、失敗します。
エラーチェックをしておられない様ですので、チェックを行ってみてはいかがでしょうか？

回答No.4

osamuy

なんとなくだけど、
＞ 　　for(i = strlen(temp)-1; i < N; i++) temp[i] = FS; //空白用文字を名前の右側に詰める
これで、文字列の終端を潰してしまって、
＞　strcpy(r->ch, x);
でメモリ破壊を起こしているような。
デバッガで追っかければすぐ分かる話なので、外してるかもしれませんが。

＃ところで「落し蓋」は、sentinelと呼ぶ方が一般的かと。

参考URL：

http://ja.wikipedia.org/wiki/%E7%95%AA%E5%85%B5

回答No.2

fonera

恐れ入ります。
とりあえずざっくり読みましたが、なぜendlineを配列にしているのか良くわかりません。（わざわざ文字列として扱わなくても問題ない気がしますが）

しかし、そもそもキューが空かどうかは「落とし蓋」のような事をしなくても、先頭がNULLになっているかどうかでチェックすれば良いのではないかと思います。

実装上の問題と言うよりも、設計段階ですっきり行っていないような気がします。
基数ソートの学習ですか？名簿のソートが目的ですか？
そのあたりによって、回答も異なると思います。

***
基数ソートは高速ですが、バイナリソートと同じく、正しく完璧に実装しようとするととても面倒です。実装リスクが高いので（数万の電話番号のような）長さが同じで分類が少なく非常に多くのリストに対して行うのが常道です。
本当にその速度が必要かどうか、もう一度考えてみることをお勧めします。
その上で、どうしても速度が必要なのであれば、下記の実装をまずすることをお勧めします。
・エンキュー、デキューを確実に実装する
・キューが空かどうかの関数を実装する
・Nを3（3文字の英字）程度で、正しくソートできるか確認する

お礼

あ、これだともう１セットキューを用意するのと変わりませんでしたｗ
foneraさんの仰る３項目についてまずは検討してみますが、やはりこのアルゴリズムで一度作ってみたいと思います。
プログラムが「ココ→」で停止する理由はご存知ないでしょうか。
今までmalloc関数の行で止まったことが無かったものでして。

補足

早速のお返事ありがとうございます。
たいへん遅ればせながら、asuncionさんとfoneraさんに質問の補足をしておこうと思います。
今回作っているプログラムの目的は基数ソートの学習にあります。
大学で教わった基数ソート（おそらくfoneraさんの仰っているソートの基本となるものだと思いますが）のアルゴリズムと、
授業を終えて自分なりに思いついたアルゴリズムを
計算時間や領域効率などの観点から比較したく、今回のプログラムを作りながら検討しようと思っています。
思いついたアルゴリズムのもうちょっと詳しい説明を以下のURLに置いておきましたので、お時間など差し支えなければご覧下さい。５分ほどでお読みいただけるかと思います。

http://wisteria.orz.ne.jp/download/RadixSort.pdf

回答No.1

asuncion

「落とし蓋」の概念がよくわかりません。
教えてください。