キューのサイズを必要に応じて追加する方法

[tutomeru]

お世話になっております。キューのサイズをが一杯だった場合にキューのサイズを3ずつ増やすプログラムを書きたいです。
Initialize2で追加しようと思ったのですが、どうにもprintfで正しく表示してくれません。正しく表示させる方法と正しく表示されない理由を教えていただけるとありがたいです。C言語の能力は低いです。よろしくお願いします。

コード:

#include <stdio.h> 
#include <string.h> 
#include <limits.h> 
#define mozisuu 80 
typedef struct{ 
    char *hyouzi;  
}KOU; 
 
typedef struct { 
    int max; 
    int yousosuu; 
    int sakuzyo; 
    int tuika; 
    KOU *que; 
}KYU; 
 
 
int Initialize(KYU *s, int max) 
{ 
    s->yousosuu = s->sakuzyo = s->tuika = 0;
    if ((s->que = (KOU *)calloc(max, sizeof(KOU))) == NULL) { 
        s->max = 0; 
        return -1; 
    } 
    s->max = max; 
    return 0; 
} 
 
int Initialize2(KYU *q, int max){
    int t;
    q->max = q->max+max; 
    t=q->max;
    if ((q->que = (KOU *)realloc(q->que, sizeof(KOU)*t)) == NULL) { 
        q->max=q->max-max;
        return -1; 
    } 
return 0; 
}
 
int Enkyu(KYU *s, KOU x){ 
    if (s->yousosuu >= s->max) {
    return -1;
}
    s->yousosuu++;
    s->que[s->tuika] = x; 
    if ((s->que[s->tuika].hyouzi =(char *)calloc(strlen(x.hyouzi)+1, sizeof(char))) == NULL) 
        return -1; 
    strcpy(s->que[s->tuika].hyouzi, x.hyouzi); 
    s->tuika++;
    if(s->tuika==s->max) 
        s->tuika=0;
    return 0; 
} 
 
int Capa(const KYU *s){ 
    return s->max; 
} 
 
int Size(const KYU *s){ 
    return s->yousosuu; 
} 
 
void hyouzi(const KOU *x){ 
    int i;
    printf("%-18.18s\n", x->hyouzi); 
} 
 
void Print(const KYU *s){ 
int i; 
    for(i = 0; i < s->yousosuu; i++) 
        hyouzi(s->que+(i+s->sakuzyo)%s->max); 
    putchar('\n'); 
} 
 
 
int main(void){ 
    KYU s; 
    int max; 
    KOU x; 
 
        if (Initialize(&s, 1)==-1){ 
        puts("キューの生成に失敗した。"); 
        return 1; 
    } 
 
    if ((x.hyouzi = (char *)calloc(mozisuu+1, sizeof(char))) == NULL){ 
        return 1; 
    } 
    while(1) { 
        int menu, pos; 
        printf("現在のデータ数：%d/%d\n",Size(&s), Capa(&s)); 
        printf("(1)エンキュー (2)表\示 (0)終了："); 
        scanf("%d", &menu); 
        if (menu == 0) break; 
        switch (menu) { 
            case 1: 
            printf("input "); scanf("%s", x.hyouzi);  
            if (Enkyu(&s, x) == -1){ 
                Initialize2(&s, 3);
                Enkyu(&s, x);
            }
            break;  
            case 2: 
            Print(&s); 
            break;  
        } 
    }
    return 0; 
}

[box]

せっかくcodeタグを使っているのに、インデントがなくて
読みづらいです。
何とかならないでしょうか。

[みけCAT]

最初にEnkyuした時点で51行目によりs.tuikaは0になっており、次にInitialize2の後Enkyuすると、そのまま0番目に書き込まれます。
このとき、1番目はreallocした時のままの不定値が入っています。
この状態でPrintすると、不定値をアドレスとしてそこのデータを読みに行くので、アクセス違反で死ぬ可能性が高くなります。
正しく表示させる方法は、正しいデータを作って格納することです(具体的な方法は考え中です)。

[tutomeru]

プログラムを見やすくしました。

[tutomeru]

返信ありがとうございました。
見落としていました。ということは単純に考えれば

コード:

 if(s->tuika==s->max) 
        s->tuika=0;

この部分をうまく変更すればよいようですね。一度考えてみます。

[tutomeru]

コード:

 
if(s->tuika==s->max) 
        s->tuika=0;

この部分を削除すればうまくいきますがそれではキューと呼んでよいのかどうか微妙な気がします。

[みけCAT]

領域を線形リストで管理すれば、領域の追加は楽になります。
イメージとしては、このような感じにすると良さそうだと思います。

ある時点での状態

front→領域A→領域B→領域C→NULL
領域ストック→NULL

エンキューする領域を追加:今は領域ストックが無いので新たに領域を確保

front→領域A→領域B→領域C→領域D→NULL
領域ストック→NULL

デキューして領域Aが空になったら、領域ストックに移動

front→領域B→領域C→領域D→NULL
領域ストック→領域A→NULL

さらに領域Bも空になったら、移動

front→領域C→領域D→NULL
領域ストック→領域B→領域A→NULL

エンキューする領域を追加:領域ストックがあるので、そこから取る

front→領域C→領域D→領域B→NULL
領域ストック→領域A→NULL

[みけCAT]

ということは単純に考えれば

コード:

 if(s->tuika==s->max) 
        s->tuika=0;

この部分をうまく変更すればよいようですね。一度考えてみます。

本当にそうでしょうか？
例えば、今4要素が全部埋まっていて、

コード:

4 1 2 3
  ^
  |
  m->tuika

というようになっていたとします(数字の順にエンキューしたとします)。
そこへ3個領域を追加しました。

コード:

4 1 2 3 x x x
  ^
  |
  m->tuika

xは不定値です。
さて、この後どのようにデータを管理すれば、キューの性質(FIFO)を失わず、エンキューやデキューができるでしょうか？
なお、データの取り出しができないという特徴を持つことは、一度使った領域を最利用しないという特徴を持つことよりも遥かにそのデータ構造をキューと呼べなくするでしょう。
従って、デキューを諦めてはいけません。

コード:

 
if(s->tuika==s->max) 
        s->tuika=0;

この部分を削除すればうまくいきますがそれではキューと呼んでよいのかどうか微妙な気がします。

キューが満たすべき性質を満たしていれば、キューと呼んでいいでしょう。
メモリの効率は、それがキューかどうかを考えるときは些細な問題でしょう。

[tutomeru]

返信ありがとうございます。線形ノードを利用すればよいというアドバイスありがとうございます。現在初期のキューのサイズを3に増やし、さらに単純にデキューを追加してみました。しかし、
エンキューで
takana
と入力し
デキューした後
aoyama
と入力すると強制終了されてしまうバグに見舞われています。
メモリの拡張をしていない状態なので何かトラブルになるようなことはしていないと思うのですが・・・。
教えていただけるとありがたいです。

コード:

#include <stdio.h> 
#include <string.h> 
#include <limits.h> 
#define mozisuu 80 
typedef struct{ 
    char *hyouzi;  
}KOU; 
 
typedef struct { 
    int max; 
    int yousosuu; 
    int sakuzyo; 
    int tuika; 
    KOU *que; 
}KYU; 
 
 
int Initialize(KYU *s, int max) 
{ 
    s->yousosuu = s->sakuzyo = s->tuika = 0;
    if ((s->que = (KOU *)calloc(max, sizeof(KOU))) == NULL) { 
        s->max = 0; 
        return -1; 
    } 
    s->max = max; 
    return 0; 
} 
 
int Initialize2(KYU *q, int max){
    int t;
    q->max = q->max+max; 
    t=q->max;
    if ((q->que = (KOU *)realloc(q->que, sizeof(KOU)*t)) == NULL) { 
        q->max=q->max-max;
        return -1; 
    } 
return 0; 
}
 
int Enkyu(KYU *s, KOU x){ 
    if (s->yousosuu >= s->max) {
    return -1;
}
    s->yousosuu++;
    s->que[s->tuika] = x; 
    if ((s->que[s->tuika].hyouzi =(char *)calloc(strlen(x.hyouzi)+1, sizeof(char))) == NULL) 
        return -1; 
    strcpy(s->que[s->tuika].hyouzi, x.hyouzi); 
    s->tuika++;
    //if(s->tuika==s->max) 
       // s->tuika=0;
    return 0; 
} 

int Dekyu(KYU *s, KOU *x){ 
	if (s->yousosuu <= 0) return -1; /* スタックは空 */ 
	s->yousosuu--; 
	*x = s->que[s->sakuzyo]; 
	strcpy(x->hyouzi, s->que[s->sakuzyo].hyouzi);
	printf("デキューしたデータは%s\n",s->que[s->sakuzyo].hyouzi);
	free(s->que[s->sakuzyo].hyouzi); /* ポップしたので，動的な文字列保存用配列を解放 */
	s->sakuzyo++;
	return (0); 
} 
 
int Capa(const KYU *s){ 
    return s->max; 
} 
 
int Size(const KYU *s){ 
    return s->yousosuu; 
} 
 
void hyouzi(const KOU *x){ 
    int i;
    printf("%-18.18s\n", x->hyouzi); 
} 
 
void Print(const KYU *s){ 
int i; 
    for(i = 0; i < s->yousosuu; i++) 
        hyouzi(s->que+(i+s->sakuzyo)%s->max); 
    putchar('\n'); 
} 
 
 
int main(void){ 
    KYU s; 
    int max, count; 
    KOU x; 
 
        if (Initialize(&s, 3)==-1){ 
        puts("キューの生成に失敗した。"); 
        return 1; 
    } 
 
    if ((x.hyouzi = (char *)calloc(mozisuu+1, sizeof(char))) == NULL){ 
        return 1; 
    } 
    while(1) { 
        int menu; 
        printf("現在のデータ数：%d/%d\n",Size(&s), Capa(&s)); 
        printf("(1)エンキュー (2)デキュー (3)表\示 (0)終了："); 
        scanf("%d", &menu); 
        if (menu == 0) break; 
        switch (menu) { 
            case 1: 
            printf("input "); scanf("%s", x.hyouzi);  
            if (Enkyu(&s, x) == -1){ 
                Initialize2(&s, 3);
                Enkyu(&s, x);
            }
            break; 
            case 2:
            Dekyu(&s, &x);
            break;
            case 3: 
            Print(&s); 
            break;  
        } 
    }
    return 0; 
}

[みけCAT]

無駄に記事を編集するのはやめてください。

3. 禁止行為について

以下の行為を禁止行為として定めます。

(中略)

[C言語何でも質問掲示板でのみ適用される事項]

名前を複数利用して質問する行為
記事の内容を無暗に変更する行為
(以下略)

新しいコードは新しい返信として投稿してください。

デキューの問題が追加される前のWebArchive

[みけCAT]

Initialize関数で1要素しか確保していないので、2要素目に書き込もうとするとアクセス違反のリスクが上がります。

【訂正】勘違いでした。callocなので、きちんとmax要素確保できるはずです。

[tutomeru]

申し訳ありません。
記事の内容を無暗に変更する行為に該当するのですね。
これからは基本的に返信で投稿するようにします。

[tutomeru]

Initialize関数で3要素の確保にしてみても結果は変わりませんでした。
デキューした後のメモリアクセスがおかしいのでしょうか？

[tutomeru]

ピークを追加していろいろ動かしてみたのですがメモリ管理がおかしいみたいです。どこで間違っているのか教えていただけるとありがたいです。

コード:

#include <stdio.h> 
#include <string.h> 
#include <limits.h> 
#define mozisuu 80 
typedef struct{ 
	char *hyouzi;  
}KOU; 
 
typedef struct { 
	int max; 
	int yousosuu; 
	int sakuzyo; 
	int tuika; 
	KOU *que; 
}KYU; 
 
 
int Initialize(KYU *s, int max) 
{ 
	s->yousosuu = s->sakuzyo = s->tuika = 0;
	if ((s->que = (KOU *)calloc(max, sizeof(KOU))) == NULL) { 
		s->max = 0; 
		return -1; 
	} 
	s->max = max; 
	return 0; 
} 
 
int Initialize2(KYU *q, int max){
	int t;
	q->max = q->max+max; 
	t=q->max;
	if ((q->que = (KOU *)realloc(q->que, sizeof(KOU)*t)) == NULL) { 
	q->max=q->max-max;
	return -1; 
	} 
	return 0; 
}
 
int Enkyu(KYU *s, KOU x){ 
	if (s->yousosuu >= s->max) {
	return -1;
}
	s->yousosuu++;
	s->que[s->tuika] = x; 
	if ((s->que[s->tuika].hyouzi =(char *)calloc(strlen(x.hyouzi)+1, sizeof(char))) == NULL) 
	    return -1; 
	strcpy(s->que[s->tuika].hyouzi, x.hyouzi); 
	s->tuika++;
	
	return 0; 
} 

int Dekyu(KYU *s, KOU *x){ 
	if (s->yousosuu <= 0) return -1; /* スタックは空 */ 
	s->yousosuu--; 
	*x = s->que[s->sakuzyo]; 
	strcpy(x->hyouzi, s->que[s->sakuzyo].hyouzi);
	printf("デキューしたデータは%s\n",s->que[s->sakuzyo].hyouzi);
	free(s->que[s->sakuzyo].hyouzi); /* ポップしたので，動的な文字列保存用配列を解放 */
	s->sakuzyo++;
	return (0); 
} 
 
int Capa(const KYU *s){ 
	return s->max; 
} 
 
int Size(const KYU *s){ 
	return s->yousosuu; 
} 
 
void Dhyouzi(const KOU *x){ 
	int i;
	printf("%-18.18s\n", x->hyouzi); 
} 
int Peek(KYU *s, KOU *x){ 
	if (s->yousosuu <= 0) return -1; 
	*x = s->que[s->sakuzyo]; 
	strcpy(x->hyouzi, s->que[s->sakuzyo].hyouzi); 
	return 0; 
} 
 
void Print(const KYU *s){ 
int i; 
	for(i = 0; i < s->yousosuu; i++) 
		Dhyouzi(s->que+(i+s->sakuzyo)%s->max); 
	putchar('\n'); 
} 
 
 
int main(void){ 
	KYU s; 
	int max; 
	KOU x; 
	if (Initialize(&s, 3)==-1){ 
	puts("キューの生成に失敗した。"); 
	return 1; 
	} 
	if ((x.hyouzi = (char *)calloc(mozisuu+1, sizeof(char))) == NULL){ 
		return 1; 
	} 
	while(1) { 
		int menu, pos; 
		printf("現在のデータ数：%d/%d\n",Size(&s), Capa(&s)); 
		printf("(1)エンキュー (2)デキュー (3)表\示 (4)ピーク (0)終了："); 
		scanf("%d", &menu); 
		if (menu == 0) break; 
		switch (menu) { 
			case 1: 
			printf("input "); scanf("%s", x.hyouzi);  
			if (Enkyu(&s, x) == -1){ 
				Initialize2(&s, 3);
				Enkyu(&s, x);
			}
			break; 
			case 2:
			Dekyu(&s, &x);
			break;
			case 3: 
			Print(&s); 
			break; 
			case 4:
			if (Peek(&s, &x) == -1) 
			puts("\aエラー：ピークに失敗しました．\n"); 
			else{ 
			printf("ピークしたデータは，"); 
			Dhyouzi(&x); 
			} 
			break;
		} 
	}
	return 0; 
}

[みけCAT]

Dekyu関数において、

• 58行目で、重なる領域へのstrcpyを行っており、未定義動作となるかもしれません。
• 57行目でmain関数のx.hyouziをs->que[s->sakuzyo].hyouziにし、60行目でそれを開放しているため、111行目で死ぬリスクが高まります。

オフトピック

電池が切れそうなスマホでプレビューせずに慌てて送信したらタグのtypoがあった…残念。

[tutomeru]

申し訳ありません。理解は出来るのですが、すぐに対処法が思いつかないので考えてみます。