質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

2回答

405閲覧

データ構造 キューの拡張について

masuter0413

総合スコア50

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2018/10/28 06:28

学校で配列を用いたキューを作成する課題がでています。とりあえずキューを作成するところまでコードはかけていて、実行例とソースコードは以下のようです。8個の大きさのキューに、[1,2,3,4,5,6,7,8] を順に enqueue() で 入れ、次に 4回 dequeue() を行い、再度 4回 [9,10,11,12] を enqueue() で入れるようにし、最後に4回 dequeue() を実行しています。 この時、すべての enqueue(),dequeue() の後で printQueue() を実行して、実際にキューの先頭と後尾がどうなる かを観察しています。
この後のキューを拡張する方法が分かりません。

c

1#define SIZE 8 2#define QSIZE(x) (sizeof(x)/sizeof(x[0])) 3 4#include<stdio.h> 5#include<string.h> 6#include<stdlib.h> 7struct Queue { 8 int data[SIZE]; 9 int front;//先頭の要素番号 10 int rear; //末尾の要素番号 11 int free; //空き容量 12}; 13int main() { 14 int initQueue(struct Queue *);//キュー初期化 15 int enqueue(struct Queue *, int);//データを格納 16 void printQueue(struct Queue*);//キューを表示 17 int dequeue(struct Queue *que, int *); 18 int i; 19 struct Queue queue; 20 struct Queue*p = &queue; 21 initQueue(p); 22 for (i = 1; i <= 8; i++) { 23 enqueue(p, i); 24 printQueue(p); 25 } 26 for (i = 1; i <= 4; i++) { 27 dequeue(p, &i); 28 printQueue(p); 29 } 30 31 for (i = 9; i <= 12; i++) { 32 enqueue(p, i); 33 printQueue(p); 34 } 35 36 for (i =5; i <=8; i++) { 37 dequeue(p, &i); 38 printQueue(p); 39 } 40 return 0; 41} 42int initQueue(struct Queue *que) { 43 que->front = que->rear = 0; //先頭と末尾の要素番号に0を代入 44 que->free = QSIZE(que->data);//配列(先頭アドレス)を渡して配列全体の大きさを取得 45 //データを0で初期化 46 if (memset(que->data, 0, sizeof(que->data))) { 47 return 1; 48 } 49 else { 50 return 0; 51 } 52} 53int enqueue(struct Queue *que, int new) { 54 if (que->free == 0) { 55 return 0; /* 空きがない */ 56 } 57 else if (que->free == QSIZE(que->data)) { /* 空だったら(空き容量と配列全体の大きさが一緒だったら)*/ 58 que->data[que->rear] = new; 59 } 60 else { 61 ++que->rear; 62 if (que->rear >= QSIZE(que->data)) { /* 末尾に達した*/ 63 que->rear = 0; /* 先頭に戻る */ 64 } 65 printf("rear=%d\n", que->rear); 66 que->data[que->rear] = new; 67 } 68 que->free--; 69 return 1; 70} 71 72void printQueue(struct Queue *que) { 73 int i, size; char *q; 74 75 size = QSIZE(que->data); 76 q = (char*)malloc(size * 2 + 1); 77 memset(q, ' ', size * 2 + 1); 78 *(q + size * 2) = '\0'; 79 80 printf("status of Queue [F=%2d,R=%2d, free=%2d]\n", 81 que->front, que->rear, que->free); 82 for (i = 0; i < size; i++) { 83 if (que->free == size) { 84 q[2 * i] = '-'; q[2 * i + 1] = '-'; 85 } 86 else { 87 if (i == que->front) { 88 q[2 * i] = 'F'; 89 } 90 else if (i == que->rear) { 91 q[2 * i + 1] = 'R'; 92 } 93 else { 94 q[2 * i] = '-'; q[2 * i + 1] = '-'; 95 } 96 } 97 } 98 printf("%s\n", q); 99 for (i = 0; i < size; i++) { 100 if (que->rear <= que->front) { 101 if (i <= que->rear || que->front <= i) { 102 printf("%2d", que->data[i]); 103 } 104 else { 105 printf("--"); 106 } 107 } 108 else { 109 if (que->front <= i && i <= que->rear) { 110 printf("%2d", que->data[i]); 111 } 112 else { 113 printf("--"); 114 } 115 } 116 } 117 printf("\n"); 118 free(q); 119} 120int dequeue(struct Queue *que, int * get) { 121 if (que->free == QSIZE(que->data)) { 122 return 0; /* データがない */ 123 } 124 else { 125 *get = que->data[que->front++]; 126 if (que->front >= QSIZE(que->data)) { 127 que->front = 0; /* 先頭に戻る */ 128 } 129 que->free++; 130 return 1; 131 } 132} 133

c

1$ clang -o queue queue.c 2$ ./queue 3status of Queue [F= 0,R= 0, free= 7] 4F -------------- 5 1 0 0 0 0 0 0 0 6rear=1 7status of Queue [F= 0,R= 1, free= 6] 8F R------------ 9 1 2------------ 10rear=2 11status of Queue [F= 0,R= 2, free= 5] 12F -- R---------- 13 1 2 3---------- 14rear=3 15status of Queue [F= 0,R= 3, free= 4] 16F ---- R-------- 17 1 2 3 4-------- 18rear=4 19status of Queue [F= 0,R= 4, free= 3] 20F ------ R------ 21 1 2 3 4 5------ 22rear=5 23status of Queue [F= 0,R= 5, free= 2] 24F -------- R---- 25 1 2 3 4 5 6---- 26rear=6 27status of Queue [F= 0,R= 6, free= 1] 28F ---------- R-- 29 1 2 3 4 5 6 7-- 30rear=7 31status of Queue [F= 0,R= 7, free= 0] 32F ------------ R 33 1 2 3 4 5 6 7 8 34status of Queue [F= 1,R= 7, free= 1] 35--F ---------- R 36-- 2 3 4 5 6 7 8 37status of Queue [F= 2,R= 7, free= 2] 38----F -------- R 39---- 3 4 5 6 7 8 40status of Queue [F= 3,R= 7, free= 3] 41------F ------ R 42------ 4 5 6 7 8 43status of Queue [F= 4,R= 7, free= 4] 44--------F ---- R 45-------- 5 6 7 8 46rear=0 47status of Queue [F= 4,R= 0, free= 3] 48 R------F ------ 49 9------ 5 6 7 8 50rear=1 51status of Queue [F= 4,R= 1, free= 2] 52-- R----F ------ 53 910---- 5 6 7 8 54rear=2 55status of Queue [F= 4,R= 2, free= 1] 56---- R--F ------ 57 91011-- 5 6 7 8 58rear=3 59status of Queue [F= 4,R= 3, free= 0] 60------ RF ------ 61 9101112 5 6 7 8 62status of Queue [F= 5,R= 3, free= 1] 63------ R--F ---- 64 9101112-- 6 7 8 65status of Queue [F= 6,R= 3, free= 2] 66------ R----F -- 67 9101112---- 7 8 68status of Queue [F= 7,R= 3, free= 3] 69------ R------F 70 9101112------ 8 71status of Queue [F= 0,R= 3, free= 4] 72F ---- R-------- 73 9101112--------

(ちなみにFの位置のズレはしゅうせいできませんかね。)
このキューの問題は扱えるデータが限られていることです。そこで、次の課題はこのキューを拡張する関数を作成することです。
まず、構造体とinitQueue()とenqueue()を次のように変更しました。キューが一杯になったら、expand() 関数を呼び出すようにします。

c

1int initQueue( struct Queue *que ){ 2 que->data = (int*)malloc(SIZE*int); /* 新しい部分 */ 3 que->front = que->rear = 0; 4 que->free = QSIZE(que->data); 5 if(memset(que->data, 0, sizeof(que->data))){ 6 return 1; 7 }else{ 8 return 0; 9 } 10} 11int enqueue( struct Queue *que, int new ){ 12 if( que->free == 0 ){ 13 if(!expand(que)){ 14 return 0; /* キューが拡張できない時 */ 15 } 16 }else if(que->free==QSIZE(que->data)){ /* 空だったら */ 17 /* 省略 */ 18}

c

1int expand( struct Queue *que ){ 2 int *new; 3 ... 4 if( (new = (int*)malloc(sizeof(que->data)*2)) == NULL ){ 5 return 0; /* メモリ割当失敗 */ 6 } 7 ... 8 return 1; 9}

呼び出される expand() 関数で、より大きなメモリ領域を確保し、 以前のキューの内容をコピーし、メンバー front, rear, free などを更新 して、最後に古いキューを free して、呼び出し元に戻ります。
通常、このようにメモリを拡張する場合には、元の大きさの2倍程度を 取れば良いとされています。また、expand() はキューの大きさが 足りなくなれば何度も呼び出される点にも注意しましょう。 と先生は言っていました。
友達はこの先生が途中まで作っているexpand()を用いて作成するのは無理だ。先生は間違っていると言っています。本当にそうなのでしょうか?皆さん、プログラミングのエキスパートの人たちの意見を聞きたいです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

友達から「先生は間違っている」というエラーメッセージが出たなら、その詳細を確認してください。
エラーメッセージは省略や意訳をするのではなく、その正確な位置と理由を確認するのが鉄則です。

リストがいっぱいになった時、その倍のメモリを確保してそこに元のリストをコピーし、元のリストを廃棄して新しいリストを使用する手法自体はごく普通のもので、よく使われています。

投稿2018/10/28 06:40

Zuishin

総合スコア28656

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2018/10/28 07:02

あと、不明な点はなるべく先生に確認しましょう。 それによって生徒の状態が先生に伝わり、授業が最適化されます。 無理だと思うならそう思った理由を先生に伝えてください。 先生が間違っていたら訂正されるでしょうし、友達が間違っていたなら友達の理解が深まるよう先生が説明してくれるでしょう。 そのための先生です。 授業料を払っているんだから効率的に利用してください。
guest

0

ベストアンサー

(※エキスパートじゃないですが)

とってもかんたん★

新しいキューを用意する。 # 繰り返す 古いキューから一つデキューする。 新しいキューにエンキューする。

また、質問がちょっとネタっぽかったので行間を埋めてみました。

友達: この先生が途中まで作っているexpand()を用いて作成するのは(今の俺には)無理だ。(頭がいっぱいいっぱいで取り組めそうにもない)。(もっと補習をしてほしいぐらいなのに、こんな課題を出すなんて)先生は間違っている

マジレスすると、教科書や先生が間違っていることってままあります。
授業中のケアミスなら指摘するべきですが、それ以外のことで「間違っている!」と労力を割いても、あんまり得られるものはなく、徒労に終わりますのでお気を付けを。(研究はまたべつ)

投稿2018/10/28 07:07

編集2018/10/28 07:16
退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

masuter0413

2018/10/28 12:13

あれから何時間も悩んでますが解決の糸口が見つかりません。まず、 #define SIZE 8 struct Queue { int * data; int front;//先頭の要素番号 int rear; //末尾の要素番号 int free; //空き容量 }; int initQueue( struct Queue *que )において、 que->data = (int*)malloc(SIZE*sizeof(int)); ではint型配列がdata[8]のように確保されるという認識でよろしいでしょうか。 次に que->free = QSIZE(que->data);を実行すると、freeには1が代入されます。先生が準備した #define QSIZE(x) (sizeof(x)/sizeof(x[0]))はこの場合使えないのでしょうか。
退会済みユーザー

退会済みユーザー

2018/10/28 12:41 編集

ほかの質問でも話題になっていましたが、動的に確保した配列に対しては使えないそうです。次のサイトを読んだ感想としては、静的確保だろうが動的確保だろうが、配列のサイズを知るのにsizeofを使うのはやめたほうがよさそうですね。事前に定義していれば使える!なんて言って使ってたら、バグのもとになりそう(http://www.kis-lab.com/serikashiki/C/C03.html) コメントでご質問頂いたように、この場合使えないのでしょうか?と(デバッグの工程の一つとして)調査がしっかりできてらっしゃるみたいですし、素晴らしいと思います。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問