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

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

ただいまの
回答率

89.99%

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

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 660

masuter0413

score 39

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

#define SIZE 8
#define QSIZE(x) (sizeof(x)/sizeof(x[0]))

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct Queue {
    int data[SIZE];
    int front;//先頭の要素番号
    int rear; //末尾の要素番号
    int free; //空き容量
};
int main() {
    int initQueue(struct Queue *);//キュー初期化
    int enqueue(struct Queue *, int);//データを格納
    void printQueue(struct Queue*);//キューを表示
    int dequeue(struct Queue *que, int *);
    int i;
    struct Queue queue;
    struct Queue*p = &queue;
    initQueue(p);
    for (i = 1; i <= 8; i++) {
        enqueue(p, i);
        printQueue(p);
    }
    for (i = 1; i <= 4; i++) {
        dequeue(p, &i);
        printQueue(p);
    }

    for (i = 9; i <= 12; i++) {
        enqueue(p, i);
        printQueue(p);
    }

    for (i =5; i <=8; i++) {
        dequeue(p, &i);
        printQueue(p);
    }
    return 0;
}
int initQueue(struct Queue *que) {
    que->front = que->rear = 0;  //先頭と末尾の要素番号に0を代入
    que->free = QSIZE(que->data);//配列(先頭アドレス)を渡して配列全体の大きさを取得
                                 //データを0で初期化
    if (memset(que->data, 0, sizeof(que->data))) {
        return 1;
    }
    else {
        return 0;
    }
}
int enqueue(struct Queue *que, int new) {
    if (que->free == 0) {
        return  0;                            /* 空きがない */
    }
    else if (que->free == QSIZE(que->data)) { /* 空だったら(空き容量と配列全体の大きさが一緒だったら)*/
        que->data[que->rear] = new;
    }
    else {
        ++que->rear;
        if (que->rear >= QSIZE(que->data)) {   /* 末尾に達した*/
            que->rear = 0;                     /* 先頭に戻る */
        }
        printf("rear=%d\n", que->rear);
        que->data[que->rear] = new;
    }
    que->free--;
    return 1;
}

void printQueue(struct Queue *que) {
    int i, size; char *q;

    size = QSIZE(que->data);
    q = (char*)malloc(size * 2 + 1);
    memset(q, ' ', size * 2 + 1);
    *(q + size * 2) = '\0';

    printf("status of Queue [F=%2d,R=%2d, free=%2d]\n",
        que->front, que->rear, que->free);
    for (i = 0; i < size; i++) {
        if (que->free == size) {
            q[2 * i] = '-'; q[2 * i + 1] = '-';
        }
        else {
            if (i == que->front) {
                q[2 * i] = 'F';
            }
            else if (i == que->rear) {
                q[2 * i + 1] = 'R';
            }
            else {
                q[2 * i] = '-'; q[2 * i + 1] = '-';
            }
        }
    }
    printf("%s\n", q);
    for (i = 0; i < size; i++) {
        if (que->rear <= que->front) {
            if (i <= que->rear || que->front <= i) {
                printf("%2d", que->data[i]);
            }
            else {
                printf("--");
            }
        }
        else {
            if (que->front <= i && i <= que->rear) {
                printf("%2d", que->data[i]);
            }
            else {
                printf("--");
            }
        }
    }
    printf("\n");
    free(q);
}
int dequeue(struct Queue *que, int * get) {
    if (que->free == QSIZE(que->data)) {
        return 0;                    /* データがない */
    }
    else {
        *get = que->data[que->front++];
        if (que->front >= QSIZE(que->data)) {
            que->front = 0;         /* 先頭に戻る */
        }
        que->free++;
        return 1;
    }
}
$ clang -o queue queue.c
$ ./queue
status of Queue [F= 0,R= 0, free= 7]
F --------------
 1 0 0 0 0 0 0 0
rear=1
status of Queue [F= 0,R= 1, free= 6]
F  R------------
 1 2------------
rear=2
status of Queue [F= 0,R= 2, free= 5]
F -- R----------
 1 2 3----------
rear=3
status of Queue [F= 0,R= 3, free= 4]
F ---- R--------
 1 2 3 4--------
rear=4
status of Queue [F= 0,R= 4, free= 3]
F ------ R------
 1 2 3 4 5------
rear=5
status of Queue [F= 0,R= 5, free= 2]
F -------- R----
 1 2 3 4 5 6----
rear=6
status of Queue [F= 0,R= 6, free= 1]
F ---------- R--
 1 2 3 4 5 6 7--
rear=7
status of Queue [F= 0,R= 7, free= 0]
F ------------ R
 1 2 3 4 5 6 7 8
status of Queue [F= 1,R= 7, free= 1]
--F ---------- R
-- 2 3 4 5 6 7 8
status of Queue [F= 2,R= 7, free= 2]
----F -------- R
---- 3 4 5 6 7 8
status of Queue [F= 3,R= 7, free= 3]
------F ------ R
------ 4 5 6 7 8
status of Queue [F= 4,R= 7, free= 4]
--------F ---- R
-------- 5 6 7 8
rear=0
status of Queue [F= 4,R= 0, free= 3]
 R------F ------
 9------ 5 6 7 8
rear=1
status of Queue [F= 4,R= 1, free= 2]
-- R----F ------
 910---- 5 6 7 8
rear=2
status of Queue [F= 4,R= 2, free= 1]
---- R--F ------
 91011-- 5 6 7 8
rear=3
status of Queue [F= 4,R= 3, free= 0]
------ RF ------
 9101112 5 6 7 8
status of Queue [F= 5,R= 3, free= 1]
------ R--F ----
 9101112-- 6 7 8
status of Queue [F= 6,R= 3, free= 2]
------ R----F --
 9101112---- 7 8
status of Queue [F= 7,R= 3, free= 3]
------ R------F
 9101112------ 8
status of Queue [F= 0,R= 3, free= 4]
F ---- R--------
 9101112--------


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

int initQueue( struct Queue *que ){
    que->data = (int*)malloc(SIZE*int);    /* 新しい部分 */
    que->front = que->rear = 0;
    que->free = QSIZE(que->data);
    if(memset(que->data, 0, sizeof(que->data))){
        return 1;
    }else{
        return 0;
    }
}
int enqueue( struct Queue *que, int new ){
    if( que->free == 0 ){
        if(!expand(que)){
             return  0; /* キューが拡張できない時 */
        }
    }else if(que->free==QSIZE(que->data)){ /* 空だったら */
    /* 省略 */
}
int expand( struct Queue  *que ){
    int *new;
    ...
    if( (new = (int*)malloc(sizeof(que->data)*2)) == NULL ){
         return 0;      /* メモリ割当失敗 */
    }
    ...
    return 1;
}


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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+1

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/10/28 16:02

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

    キャンセル

  • 2018/10/28 16:12

    http://www.kis-lab.com/serikashiki/C/C03.html
    多分友達が言ってるのはこのあたり

    キャンセル

checkベストアンサー

0

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

とってもかんたん★

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

  

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/10/28 21: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 21:40 編集

    ほかの質問でも話題になっていましたが、動的に確保した配列に対しては使えないそうです。次のサイトを読んだ感想としては、静的確保だろうが動的確保だろうが、配列のサイズを知るのにsizeofを使うのはやめたほうがよさそうですね。事前に定義していれば使える!なんて言って使ってたら、バグのもとになりそう(http://www.kis-lab.com/serikashiki/C/C03.html

    コメントでご質問頂いたように、この場合使えないのでしょうか?と(デバッグの工程の一つとして)調査がしっかりできてらっしゃるみたいですし、素晴らしいと思います。

    キャンセル

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

  • ただいまの回答率 89.99%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る