C言語関係掲示板

過去ログ

No655 キューのプログラム

[戻る] [ホームページ]
No.7189

キューのプログラム
投稿者---Dr.T(2003/06/08 03:54:14)


ポインタによるリストを用いたキューのプログラム
を作成せろという課題があり、
参考書など見ながら以下のようなプログラムを作ったのですが
うまくいきません。
よろしければ悪い部分を教えてください。

#include <stdio.h>
#include <stdlib.h>
#define MAXWORDLEN 32

typedef struct node
{
    char word[MAXWORDLEN];
    struct node *Next;
} node_t;

typedef struct queue
{
	node_t *front;
 	node_t *rear;
} Queue;


void enqueue(char *x,Queue *Q);
void dequeue(Queue *Q);

main(){

	Queue Q;
	node_t *q;
	int i;
	char x,*input;
	
 	Q.front = Q.rear = NULL;
	
	printf("Initialize a queue\n\n\t>");

	for(;;) {
		
		input = (char *)malloc(MAXWORDLEN);
		
		scanf("%c%s",&x,input);
	
		if(x == 'c') {
			Q.front = Q.rear = NULL;
			printf("\nInitialize a queue\n\n\t>");
		}
	
		if(x == 'e') {
			enqueue(input,&Q);
			printf("\nEnqueue:[%s]\n\n\t>",Q.rear->word);
		}
	
		if(x == 'd') {
			if(Q.rear ==NULL)
				printf("\nDequeue:[%s]\n\n\t>",Q.rear->word);
				
			dequeue(&Q);

		}
	
		if(x == '^D')
			break;
			
	}
	
 	return(0);
	
}

void enqueue(char *x,Queue *Q) {

 	node_t *p;
	
 	p = (node_t *)malloc(sizeof(node_t));
	
 	if(Q->rear != NULL)
		Q->rear->Next = p;
		
 	Q->rear = p;
	
 	if(Q->front == NULL)
		Q->front = p;
 		
	Q->rear->word = x;
	Q->rear->Next = NULL;
	
 	return;
	
}

void dequeue(Queue *Q) {

 	node_t *q;

 	if(Q->front == NULL)
		printf("No more data.\n");

 	else {
		q = Q->front;
		Q->front = Q->front->Next;
		free(q);
	}
 	
	if(Q->front == NULL)
		Q->rear = NULL;
		
 	return;
	
}


No.7190

Re:キューのプログラム
投稿者---Dr.T(2003/06/08 04:00:04)


すみません、付け加えです。
'c'を入力するとキューを初期化
'e'を入力するとENQUEUE
'd'を入力するとDEQUEUE
'^D'で終了する。

No.7191

Re:キューのプログラム
投稿者---あかま(2003/06/08 08:09:37)


3箇所
ここと
typedef struct node
{
    char *word;
    struct node *Next;
} node_t;

ここと
scanf("%c%s%*c",&x,input);//'\n'がバッファに残るので捨てなくてはいけない。

ここ
if(x == 'd') {
			if(Q.rear !=NULL)
				printf("\nDequeue:[%s]\n\n\t>",Q.front->word);
				
			dequeue(&Q);

		}



No.7192

Re:キューのプログラム
投稿者---あかま(2003/06/08 08:17:04)


そうそう、動くけど気になるところが2つほど。

'd'を入力した時に、意味のない何らかの文字列を入力しなければならない。
'c'を入力した時にfreeを使ったほうがいい。

あと%*cを詳しく知りたい時はこちらをどぞ
http://www9.plala.or.jp/sgwr-t/c/sec05.html#s5-4
過去これで何時間費やしたことか…

No.7195

Re:キューのプログラム
投稿者---かずま(2003/06/08 16:49:58)


> 'c'を入力するとキューを初期化
> 'e'を入力するとENQUEUE
> 'd'を入力するとDEQUEUE
> '^D'で終了する。

環境(OS や コンパイラが何か)が書かれていませんが、'^D' で終了するというのは、
Ctrl+D のことで、UNIX か、あるいは Windows だと cygwin ですね。

でも、C で、'^D' と書いても、それは Ctrl+D になりません。
'\4' または単に 4 と書けばいいのですが、そう書いても、キーボードから
Ctrl+D を文字として入力することは出来ません。
UNIX で Ctrl+D は、Enter と同様入力の完了になります。
Enter と違うのは、その文字自身が入力文字にならないことです。
入力の先頭で Ctrl+D を打つと、0バイトの入力がプログラムに渡され、
それは EOF と解釈されます。

だから、Ctrl+D で scanf の入力を終了させたかったら、scanf の返却値を
見ないといけないのです。

次に、e は、キューに入れるデータの文字列を必要としますが、c や d に
はデータは不要ですよね。

ということで、scanf("%c%s", &x, input) と一度に読むのはやめたほうが
いいと思います。今のままだと、どんどん malloc された input が
無駄になっています。

もう、説明がしんどくなったので、手直ししたプログラムを付けます。
どこがどうちがうのか、調べてみてください。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct node {
    char *word;
    struct node *Next;
} node_t;

typedef struct queue {
    node_t *front;
     node_t *rear;
} Queue;

void enqueue(char *x, Queue *Q);
void dequeue(Queue *Q);

int main(void)
{
    Queue Q;  char x;
    
     Q.front = Q.rear = NULL;
    printf("Initialize a queue\n\n\t>");
    while (scanf(" %c", &x) == 1) {
        if (x == 'c') {
            Q.front = Q.rear = NULL;
            printf("\nInitialize a queue\n\n\t>");
        } else if (x == 'e') {
            char input[1024];
            scanf("%s", input);
            enqueue(input, &Q);
            printf("\nEnqueue:[%s]\n\n\t>", Q.rear->word);
        } else if (x == 'd') {
            if(Q.rear != NULL)
                printf("\nDequeue:[%s]\n\n\t>", Q.front->word);
            dequeue(&Q);
        } else if (x == 'q')
            break;
    }
     return 0;
}

void enqueue(char *x, Queue *Q)
{
     node_t *p;
    
     p = (node_t *)malloc(sizeof(node_t));
     if (Q->rear != NULL)
        Q->rear->Next = p;
     Q->rear = p;
     if (Q->front == NULL)
        Q->front = p;
    Q->rear->word = strdup(x);
    Q->rear->Next = NULL;
}

void dequeue(Queue *Q)
{
     node_t *q;

     if (Q->front == NULL)
        printf("No more data.\n");
     else {
        q = Q->front;
        Q->front = Q->front->Next;
        free(q->word);
        free(q);
    }
    if (Q->front == NULL)
        Q->rear = NULL;
}


No.7196

Re:キューのプログラム
投稿者---Dr.T(2003/06/08 17:42:15)


お二方ありがとうございます。
参考にしてやってみます。
完成したら報告します。

No.7197

Re:キューのプログラム
投稿者---Dr.T(2003/06/08 18:44:35)


完成はしたのですが、いくつかわからない点があるので
よろしければ教えください。
1.
typedef struct node
{
char *word;
struct node *Next;
} node_t;
の部分で、何故
char word[256];
とするとだめなのですか?

2.
enqueue関数内で
  Q->rear->word = strdup(x);
の部分は
  Q->rear->word = x;
ではだめなのですか?
strdup()を調べると
領域を確保してコピーするだけと書いていたので、
なくしてもいいと思って消すとうまく動作しなかった。

3.
キューの初期化のとき
free(Q->front);
free(Q->rear);
とすれば途中確保した領域も全部
開放したことになりますか?

No.7202

Re:キューのプログラム
投稿者---かずま(2003/06/08 19:24:43)


> typedef struct node
> {
> char *word;
> struct node *Next;
> } node_t;
> の部分で、何故
> char word[256];
> とするとだめなのですか?

だめではありませんが、そうした場合は、
enqueue()内で、strcpy(Q->rear->word, x); としてください。

C では、配列を配列に代入することはできません。
各要素ごとに代入を行うか、strcpy や memcpy を使います。

また、struct node の中で、char word[256]; とすると、実際に
格納する文字列より多くのメモリが無駄になるのは分かりますよね。


> enqueue関数内で
>   Q->rear->word = strdup(x);
> の部分は
>   Q->rear->word = x;
> ではだめなのですか?

struct node で char *word; の場合ですね。
x が同一の input[1024] を指していたら、すべての word は
input を指します。だから、だめです。


> キューの初期化のとき
> free(Q->front);
> free(Q->rear);
> とすれば途中確保した領域も全部
> 開放したことになりますか?

malloc または strdup に対応する free が必要です。


それから、言い忘れましたが、scanf(" %c", &x) で、%c の前の
空白にはとても重要な意味があります。調べてみてください。

No.7203

Re:キューのプログラム
投稿者---Dr.T(2003/06/08 21:10:42)


"%"の前の空白について調べてみましたが
どこに載っているかわかりませんでした、すみません。
でも空白がある場合とない場合で下のようなプログラムを作って実行すると

/*空白なしの場合*/
r
0 : r
1 :

t
2 : t
3 :

y
4 : y
5 :

/*空白ありの場合*/
r
0 : r
t
1 : t
y
2 : y

となったので、多分ですけど
%*cを入れるのと同じ役目をしているんですよね?



#include<stdio.h>

main() {
    
    char x;
    int i = 0;
    
    for(;;i++) {
    
        scanf("%c",&x);
        printf("%d : %c \n",i,x);
    
    }
    
}



No.7205

Re:キューのプログラム
投稿者---Dr.T(2003/06/08 22:44:55)


またエラーが起きました。
実行中のエラーなんですが、
5、6個のデータをENQUEUEした後に、全部DEQUEUEし
またENQUEUEしていくとき、2つ目をENQUEUEするとこでエラーになります。
どうしてでしょうか?
DEQUEUEするときに領域は開放しているから、
それは問題じゃないですよね?

実行したプログラムは以下のとおりです。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXWORDLEN 128

typedef struct node
{
    char word[MAXWORDLEN];
    struct node *Next;
} node_t;

typedef struct queue
{
    node_t *front;
     node_t *rear;
} Queue;


void enqueue(char *x,Queue *Q);
void dequeue(Queue *Q);

main(){

    Queue Q;
    node_t *q;
    int i;
    char x,input[MAXWORDLEN];
    
     Q.front = Q.rear = NULL;
    
    printf("Initialize a queue\n\n\t>");

    for(;;) {
        
        scanf(" %c",&x);
    
        if(x == 'c') {
            Q.front = Q.rear = NULL;
            printf("\nInitialize a queue\n\n\t>");
        }
        
        if(x == 'e') {
            scanf("%s",input);
            enqueue(input,&Q);
            printf("\nEnqueue:[%s]\n\n\t>",Q.rear->word);
        }
    
        if(x == 'd') {
            if(Q.rear != NULL)
                printf("\nDequeue:[%s]\n\n\t>",Q.front->word);
                
            dequeue(&Q);
        }
    
        if(x == -1)
            break;
            
    }
    
     return(0);
    
}

void enqueue(char *x,Queue *Q) {

     node_t *p;
    
     p = (node_t *)malloc(sizeof(node_t));
    
     if(Q->rear != NULL)
        Q->rear->Next = p;
        
     Q->rear = p;
    
     if(Q->front == NULL)
        Q->front = p;
         
    strcpy(Q->rear->word,strdup(x)); 
    Q->rear->Next = NULL;
    
}

void dequeue(Queue *Q) {

     node_t *q;

     if(Q->front == NULL)
        printf("\nNo more data.\n\n\t>");

     else {
        q = Q->front;
        Q->front = Q->front->Next;
        free(q->word);
        free(q);
    }
     
    if(Q->front == NULL)
        Q->rear = NULL;
    
}


No.7209

Re:キューのプログラム
投稿者---かずま(2003/06/09 01:55:20)


> scanf(" %c",&x);

scanf が返す値をチェックしないと、^D (EOF) が検出できませんよ。

> if(x == -1)

scanf で x に -1 は、多分はいりませんよ。

> strcpy(Q->rear->word,strdup(x));

struct node の word を配列にするんだったら、
strcpy(Q->rear->word, x);

struct node の word をポインタにするんだったら、
Q->rear->word = x;


> free(q->word);

struct node の word を配列にするんだったら、これは不要。

No.7213

Re:キューのプログラム
投稿者---かずま(2003/06/09 11:46:21)


> struct node の word をポインタにするんだったら、
> Q->rear->word = x;

訂正
Q->rear->word = strdup(x);

No.7228

Re:キューのプログラム
投稿者---Dr.T(2003/06/09 18:20:44)


かずまさんありがとうございます。
ちゃんと動作するようになりました。


No.7207

Re:キューのプログラム
投稿者---ともじ(2003/06/08 23:59:35)


こんばんは。

>%*cを入れるのと同じ役目をしているんですよね?

" %c" は空白類文字(スペース、復帰、改行、水平タブ、垂直タブ)
だけを読み飛ばし、"%*c" は全ての文字を代入抑止します。
だから、"123 \n" と入力すると、" %c" では、' ' も '\n' も読み飛す
のですが、"%*c" では、'' だけを読み飛ばし、'\n' は代入するので、
やっぱり次の "%c" が入力できなくなってしまうので、
" %c" の方が '\n' の読み捨てには適当なようです。

#本編にも追記が必要ですね。