C言語教室 第23回 - スタックとキュー(回答提出)
こちらの課題回答です。
課題
コメント
さんざん書きまくってきたような気がする(笑)。
少し汎用性を持たせてみたけど、データがint型固定だから、まぁまぁまぁまぁみたいな(笑)。なかなか汎用的になりきらない。もっと頑張れるだろうか。
個々のデータサイズも初期化時に指定して、データはポインタ渡しとか。任意の型に対応できるかもしれないけど、そうすると扱う型はユーザ任せになっちゃう。バグの元か。
pushする都度にデータを可変長にする。
というのはさすがに頑張りすぎか。
SCB(Stack Control Block)というシンボリングにしてみた。よくTCB(Task Control Block)みたいなシンボルがあったので真似てみたわけだ。
ついでに構造体を定義。でも構造体の中身はユーザには見せない。「*.c」で構造体を宣言することはよくやる。外から見えなくなって隠蔽できる。でも、試験やデバッグがしにくいとよく言われる。試験デバッグのためにコードを変えるということが、どうにも解せないんだが。どっちが大事なんだ。
SCBはスタックを操作するたびに引数で渡さなきゃならない。これがC++だったらクラスにして、thisポインタにできるのに。ただ、こうしておけばスタックはパッコンパッコンと幾つも作ることができる。
リングバッファは、wp(ライトポインタ)1つと、rp(リードポインタ)1つ。この方法だと、どうしても1つ使えない。バッファ数を16にしても、15個しかキューイングできない。頑張ったらできないでもないけど、頑張るとこでもないような気がする。
プログラム(スタック)
stack.h
#include <stdbool.h>
typedef struct _StackControlBlock SCB;
SCB* stack_create(int size);
void stack_destroy(SCB* _scb);
bool stack_push(SCB* _scb, int data);
bool stack_pop(SCB* _scb, int* data);
void stack_dump(SCB* _scb);
stack.c
#include <stdlib.h>
#include "stack.h"
struct _StackControlBlock
{
int size;
int sp;
int* stack;
};
SCB* stack_create(int size)
{
SCB* _scb = malloc(sizeof(SCB));
_scb->size = size;
_scb->stack = malloc(size * sizeof(int));
_scb->sp = size - 1;
return _scb;
}
void stack_destroy(SCB* _scb)
{
free(_scb->stack);
free(_scb);
}
bool stack_push(SCB* _scb, int data)
{
if (_scb->sp < 0)
{
return false;
}
_scb->stack[_scb->sp] = data;
(_scb->sp)--;
return true;
}
bool stack_pop(SCB* _scb, int* data)
{
if ((_scb->sp) >= (_scb->size-1))
{
return false;
}
(_scb->sp)++;
*data = _scb->stack[_scb->sp];
return true;
}
void stack_dump(SCB* _scb)
{
printf("_scb->size %d\n", _scb->size);
printf("_scb->stack %p\n", _scb->stack);
printf("_scb->sp %d\n", _scb->sp);
int _sp;
printf("stack:");
for (_sp = (_scb->size-1); _sp > _scb->sp; _sp--)
{
printf("%d ", _scb->stack[_sp]);
}
printf("\n");
}
c23s.c
#include <stdio.h>
#include "stack.h"
int main()
{
SCB* _scb = stack_create(16);
printf("stack_create(16)\n");
stack_dump(_scb);
int i;
for (i = 0; i <= 16; ++i)
{
bool ok = stack_push(_scb, i);
printf("stack_push(_scb, %d) = %d\n", i, ok);
stack_dump(_scb);
}
for (i = 0; i <= 16; ++i)
{
int data;
bool ok = stack_pop(_scb, &data);
printf("stack_pop(_scb, %d) = %d\n", data, ok);
stack_dump(_scb);
}
stack_destroy(_scb);
return 0;
}
プログラム(リングバッファ)
ring_buffer.h
#include <stdbool.h>
typedef struct _RingbufferControlBlock RCB;
RCB* rb_create(int size);
void rb_destroy(RCB* _rcb);
bool rb_enqueue(RCB* _rcb, int data);
bool rb_dequeue(RCB* _rcb, int* data);
void rb_dump(RCB* _rcb);
ring_buffer.c
#include <stdlib.h>
#include "ring_buffer.h"
struct _RingbufferControlBlock
{
int size;
int wp;
int rp;
int* rb;
};
RCB* rb_create(int size)
{
RCB* _rcb = malloc(sizeof(RCB));
_rcb->size = size;
_rcb->wp = 0;
_rcb->rp = 0;
_rcb->rb = malloc(size * sizeof(int));
return _rcb;
}
void rb_destroy(RCB* _rcb)
{
free(_rcb->rb);
free(_rcb);
}
int rb_next(RCB* _rcb, int p)
{
p++;
if (_rcb->size <= p)
{
p = 0;
}
return p;
}
bool rb_enqueue(RCB* _rcb, int data)
{
int wp_next = rb_next(_rcb, _rcb->wp);
if (wp_next == _rcb->rp)
{
return false;
}
_rcb->rb[_rcb->wp] = data;
_rcb->wp = wp_next;
return true;
}
bool rb_dequeue(RCB* _rcb, int* data)
{
if (_rcb->rp == _rcb->wp)
{
return false;
}
*data = _rcb->rb[_rcb->rp];
_rcb->rp = rb_next(_rcb, _rcb->rp);
return true;
}
void rb_dump(RCB* _rcb)
{
printf("_rcb->size %d\n", _rcb->size);
printf("_rcb->rb %p\n", _rcb->rb);
printf("_rcb->wp %d\n", _rcb->wp);
printf("_rcb->rp %d\n", _rcb->rp);
int p;
printf("rb:");
for (p = _rcb->rp; p != _rcb->wp; p=rb_next(_rcb, p))
{
printf("%d ", _rcb->rb[p]);
}
printf("\n");
}
c23r.c
#include <stdio.h>
#include "ring_buffer.h"
int main()
{
RCB* _rcb = rb_create(16);
printf("rb_create(16)\n");
rb_dump(_rcb);
printf("\n");
int i;
for (i = 0; i <= 16; ++i)
{
bool ok = rb_enqueue(_rcb, i);
printf("rb_enqueue(_rcb, %d) = %d\n", i, ok);
rb_dump(_rcb);
printf("\n");
}
{
int data;
bool ok = rb_dequeue(_rcb, &data);
printf("rb_dequeue(_rcb, %d) = %d\n", data, ok);
rb_dump(_rcb);
printf("\n");
ok = rb_enqueue(_rcb, 111);
printf("rb_enqueue(_rcb, 111) = %d\n", ok);
rb_dump(_rcb);
printf("\n");
}
{
int data;
bool ok = rb_dequeue(_rcb, &data);
printf("rb_dequeue(_rcb, %d) = %d\n", data, ok);
rb_dump(_rcb);
printf("\n");
ok = rb_enqueue(_rcb, 222);
printf("rb_enqueue(_rcb, 222) = %d\n", ok);
rb_dump(_rcb);
printf("\n");
}
for (i = 0; i <= 16; ++i)
{
int data;
bool ok = rb_dequeue(_rcb, &data);
printf("rb_dequeue(_rcb, %d) = %d\n", data, ok);
rb_dump(_rcb);
printf("\n");
}
rb_destroy(_rcb);
return 0;
}
ダウンロードプログラム(スタック)
ダウンロードプログラム(リングバッファ)
この記事が気に入ったらサポートをしてみませんか?