リンクバッファの実装について
解決したいこと
BUF_SIZEを30まで減少させるためにリンクバッファを実装させようと考えましたが、enqueue,dequeueともに正しく座標を配列に格納することができませんでした。正しいリンクバッファの実装方法をご教授ください。
発生している問題・エラー
Segmentation fault
該当するソースコード
#include <stdio.h>
#include <stdlib.h>
#define BUF_SIZE 57
#define SIZE_X 20
#define SIZE_Y 10
int visit[SIZE_X][SIZE_Y];
struct coord {
int x; //x座標
int y; //y座標
int px; //一つ前のx座標
int py; //一つ前のy座標
};
struct queue {
struct coord buf[BUF_SIZE];
int first;
int last;
};
int enqueue(struct queue *s, struct coord p) {
printf("sf\n");
if(s->first+1 == s->last){
printf("overflow\n");
return -1;
}
if(s->last == BUF_SIZE ){
s->buf[s->last] = p;
s->last = 0;
}else{
s->buf[s->last] = p;
s->last++;
}
return 1;
}
struct coord *dequeue(struct queue *s) {
printf("sf\n");
if(s->first == s->last){
printf("under flow\n");
return NULL;
}
int n;
if(s->first == BUF_SIZE){
s->first = 0;
n = s->first;
}else{
s->first ++;
n = s->last;
}
return &(s->buf[n]);
}
/* display_queue関数
* 機能: スタックの内部（格納されている値）の表示
* 引数s: 内部を表示するスタック構造体へのポインタ
*/
void display_queue(struct queue *s) {
int i = s->last;
while(i >= 0){
printf("%d %d %d %d\n",s->buf[i].x,s->buf[i].y,s->first,s->last);
i--;
}
}
/* read_map関数
* 機能: ファイルからマップを読み込む
* 引数map: 読み込んだマップを格納する配列
*/
void read_map(char map[][SIZE_Y]) {
FILE *fp;
int ch;
int i=0;
int j=0;
fp =fopen("meiro2.txt","r");
while((ch = fgetc(fp)) != EOF){
if(ch == '\n'){
j++;
i = 0;
}else{
map[i][j] = ch;
i++;
}
}
fclose(fp);
}
/* print_map関数
* 機能: マップを画面に表示する。
* 引数map: 表示するマップが格納されている配列
*/
void print_map(char map[][SIZE_Y]) {
for(int j=0;j < SIZE_Y;j++){
for(int i=0;i < SIZE_X;i++){
printf("%c",map[i][j]);
}
printf("\n");
}
}
/* record_path関数
* 機能: 探索経路（探索順路）を記録する。新たなマスを探索する毎に、そのマスを記録するために呼び出すこと。
* 引数rec: 探索経路を記録する配列
* 引数x,y: 現在位置の座標
* 引数px,py: 一つ前の位置の座標
*/
void record_path(struct coord rec[][SIZE_Y], int x, int y, int px, int py) {
rec[x][y].px = px;
rec[x][y].py = py;
}
/* print_path関数
* 機能: 記録した探索経路を基に、SからGまでの経路を表示する。
* 引数map: 表示するマップの配列。これに経路を示す'.'を書き加える
* 引数rec: 探索経路が記録された配列
* 引数gx,gy: ゴールの座標
*/
void print_path(char map[][SIZE_Y], struct coord rec[][SIZE_Y], int gx, int gy) {
int x, y, tx, ty;
// ゴールの位置から始める
x = gx; y = gy;
// ゴールの前の座標に移動（ゴールに'.'を打たない）
tx = rec[x][y].px;
ty = rec[x][y].py;
x = tx; y = ty;
// スタートまで一手ずつ戻りながらmapに'.'を打つ
while(map[tx][ty] != 'S') {
map[tx][ty] = '.';
tx = rec[x][y].px;
ty = rec[x][y].py;
x = tx; y = ty;
}
print_map(map);
}
/**********************
* メイン関数
**********************/
int main(void) {
/***** 変数の宣言（必要に応じて変数を追加すること）*****/
char map[SIZE_X][SIZE_Y]; // マップを格納する配列
struct coord rec[SIZE_X][SIZE_Y]; // 探索経路を記録する配列
struct coord tmp; // 一時変数として利用可能
struct coord *p; // 一時変数として利用可能
struct queue s; // 探索に利用するスタック
int i,j; // ループ変数
int x,y,px,py; // 座標を格納する一時変数
int gx,gy; // ゴールの位置を格納
/***** 各変数の初期化 *****/
s.first = s.last = 0;
tmp.x = -1; tmp.y = -1; tmp.px = -1; tmp.py = -1;
for (i=0; i<SIZE_X; i++) {
for (j=0; j<SIZE_Y; j++) {
visit[i][j] = 0;
rec[i][j] = tmp;
}
}
/***** マップの読み込み *****/
read_map(map);
/***** スタート地点をpush *****/
tmp.x = 1; tmp.y = 1; tmp.px = -1; tmp.py = -1;
if (enqueue(&s, tmp) == -1) {
printf("Queue Overflow.\n");
return 1;
}
/***** 探索処理 *****/
while(1) {
// 処理する座標をdequeue
p = dequeue(&s);
if (p == NULL) {
printf("Queue Underflow.\n");
return 1;
}
x = p->x, y = p->y; px = p->px; py = p->py;
printf("%d %d %d %d\n",x,y,px,py);
if(map[x][y] == 'G'){
printf("Goal found:x=%d,y=%d,\n",x,y);
record_path(rec,x,y,px,py);
gx = x;
gy = y;
break;
}
if(map[x][y] == '#'){
continue;
}
if(visit[x][y] ==1) continue;
visit[x][y] = 1;
record_path(rec,x,y,px,py);
tmp.x = x;tmp.y = y-1;tmp.px = x;tmp.py = y;
if(map[x][y-1] != '#'){
if(visit[x][y-1] != 1){
if(enqueue(&s,tmp) < 0) return 1;
}
}
tmp.x = x-1;tmp.y = y;tmp.px = x;tmp.py = y;
if(map[x-1][y] != '#'){
if(visit[x-1][y] != 1){
if(enqueue(&s,tmp) < 0) return 1;
}
}
tmp.x = x;tmp.y = y+1;tmp.px = x;tmp.py = y;
if(map[x][y+1] != '#'){
if(visit[x][y+1] != 1){
if(enqueue(&s,tmp) < 0) return 1;
}
}
tmp.x = x+1;tmp.y = y;tmp.px = x;tmp.py = y;
if(map[x+1][y] != '#'){
if(visit[x+1][y] != 1){
if(enqueue(&s,tmp) < 0) return 1;
}
}
}
/***** 探索経路の表示 *****/
print_path(map,rec,gx,gy);
}
自分で試したこと
dequeueの後で座標がどのようになっているのか確認したところpのx,y,px,pyがそれぞれ1685382483,4,848,0となっていた。予想では配列の格納した場所とdequeueの位置がずれているのではないかと考えている。
0 likes
