<追記>
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> typedef struct {/*--- キューを実現する構造体 ---*/ int max; /* キューの容量 */ int num; /* 現在の要素数 */ int front;/* 先頭要素カーソル */ int rear; /* 末尾要素カーソル */ char **que; /* キュー本体(の先頭要素へのポインタ) */ } StringsQueue; char *bm_match(char *x , char *q){ char *pt; /* txt をなぞるカーソル */ char *pp; /* pat をなぞるカーソル */ int txt_len = strlen(q); /* txt の文字数 */ int pat_len = strlen(x); /* pat の文字数 */ int skip[UCHAR_MAX + 1]; /* スキップテーブル */ int i; for (i = 0; i <= UCHAR_MAX; i++) /* スキップテーブルの作成 */ skip[i] = pat_len; for (pp = x; *pp != '\0'; pp++) skip[*pp] = strlen(pp) - 1; skip[*(pp - 1)] = pat_len; /* パターンの最後文字の移動距離はパターンの文字数 */ pt = q + pat_len - 1; /* pat の末尾と比較する txt の文字を決定 */ while ( pt < q + txt_len) { /* txt の比較する文字の位置が txt の末尾を越えるまで */ pp = x + pat_len - 1; /* pat の最後の文字に着目 */ while (*pt == *pp) { if (pp == x) return (pt); /* 一致した文字がパターンの最初の文字になれば終了 */ pp--; pt--; } pt += (skip[*pt]> strlen(pp)) ? skip[*pt] : strlen(pp); } return (NULL); } int Count(StringsQueue *q , char *x){ int sum = 0; char* s; for(int i = 0 ; i < q->num ; i++){ s = bm_match(x , q->que[q->front]); q->front ++; if(s != NULL) sum++; } return sum; } /*--- キューの初期化 ---*/ int Initialize(StringsQueue *q, int max){ q->num = q->front = q->rear = 0; if ((q->que = calloc(max, sizeof(char *))) == NULL) { q->max = 0; /* 配列の確保に失敗 */ return -1; } q->max = max; return 0; } /*--- キューの後始末 ---*/ void Terminate(StringsQueue *q){ if (q->que != NULL) { free(q->que);/* 配列を解放 */ q->que = NULL; for(int i =0 ; i < q->num ; i ++ ){ free(q->que[i]); q->que[i] = NULL; } q->max = q->num = q->front = q->rear = 0; } } /*--- キューにデータをエンキュー ---*/ int Enque(StringsQueue *q, char *x){ if (q->num >= q->max)return -1; if ((q->que[q->rear] = calloc(strlen(x)+1, sizeof(char))) == NULL)return -1; /* キューは満杯 */ q->num++; strcpy( q->que[q->rear] ,x); q->rear++; if (q->rear == q->max){ q->max = q->max + 10; } return 0; } /*--- キューからデータをデキュー ---*/ int Deque(StringsQueue *q, char *x){ if (q->num <= 0)/* キューは空 */ return -1; q->num--; strcpy( x ,q->que[q->front]); q->front++; if((q->max-q->num) >= 15){ q->max = q->max - 5; } if (q->front == q->max) q->front = 0; return 0; } /*--- キューからデータをピーク 次のデキューで取り出される値を見る---*/ int Peek(const StringsQueue *q, char *x) { if (q->num <= 0) return -1; x = q->que[q->front]; return 0; } /*--- キューの容量 ---*/ int Capacity(const StringsQueue *q){ return (q->max); } /*--- キューに蓄えられているデータ数 ---*/ int Size(const StringsQueue *q){ return (q->num); } /*--- 全データの表示 ---*/ void Print(const StringsQueue *q){ int i; for(i = 0; i < q->num; i++) if(q->max < 3){ printf("%s \n", q->que[(i + q->front) % q->max]); } else { printf("%s \n", q->que[(i + q->front) % q->max]); } } int main(void){ StringsQueue que; if (Initialize(&que, 7) == -1) { puts("キューの生成に失敗しました。"); } while (1) { int m; char x[79]; printf("現在のデータ数:%d/%d\n", Size(&que), Capacity(&que)); printf("(1) エンキュー (2) デキュー (3) ピーク (4) 表示 (5)パターンの計数 (0) 終了:"); scanf("%d", &m); if (m == 0) break; switch(m){ case 1: printf("データ:"); scanf("%s", x); if (Enque(&que, x) == -1) puts("\a エラー:データのエンキューに失敗しました。"); break; case 2: if (Deque(&que, x) == -1) puts("\a エラー:デキューに失敗しました。"); else printf("デキューしたデータは%s です。\n", x); break; case 3: /* ピーク */ if (Peek(&que, x) == -1) puts("\a エラー:ピークに失敗しました。"); else printf("ピークしたデータは%s です。\n", x); break; case 4: /* 表示 */ Print(&que); break; case 5:/* パターンの計数 */ scanf("%s",x); int count = Count(&que,x); if(count != 0)printf("パターン数は%d個です\n",count); if(count == 0)puts("パターンは存在しません."); break; } } Terminate(&que); return 0; }
<追記>
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> typedef struct {/*--- キューを実現する構造体 ---*/ int max; /* キューの容量 */ int num; /* 現在の要素数 */ int front;/* 先頭要素カーソル */ int rear; /* 末尾要素カーソル */ char **que; /* キュー本体(の先頭要素へのポインタ) */ } StringsQueue; char *bm_match(char *x , char *q){ char *pt; /* txt をなぞるカーソル */ char *pp; /* pat をなぞるカーソル */ int txt_len = strlen(q); /* txt の文字数 */ int pat_len = strlen(x); /* pat の文字数 */ int skip[UCHAR_MAX + 1]; /* スキップテーブル */ int i; for (i = 0; i <= UCHAR_MAX; i++) /* スキップテーブルの作成 */ skip[i] = pat_len; for (pp = x; *pp != '\0'; pp++) skip[*pp] = strlen(pp) - 1; skip[*(pp - 1)] = pat_len; /* パターンの最後文字の移動距離はパターンの文字数 */ pt = q + pat_len - 1; /* pat の末尾と比較する txt の文字を決定 */ while ( pt < q + txt_len) { /* txt の比較する文字の位置が txt の末尾を越えるまで */ pp = x + pat_len - 1; /* pat の最後の文字に着目 */ while (*pt == *pp) { if (pp == x) return (pt); /* 一致した文字がパターンの最初の文字になれば終了 */ pp--; pt--; } pt += (skip[*pt]> strlen(pp)) ? skip[*pt] : strlen(pp); } return (NULL); } int Count(StringsQueue *q , char *x){ int sum = 0; char* s; for(int i = 0 ; i < q->num ; i++){ s = bm_match(x , q->que[q->front]); q->front ++; if(s != NULL) sum++; } return sum; } /*--- キューの初期化 ---*/ int Initialize(StringsQueue *q, int max){ q->num = q->front = q->rear = 0; if ((q->que = calloc(max, sizeof(char *))) == NULL) { q->max = 0; /* 配列の確保に失敗 */ return -1; } q->max = max; return 0; } /*--- キューの後始末 ---*/ void Terminate(StringsQueue *q){ if (q->que != NULL) { for(int i =0 ; i < q->num ; i ++ ){ free(q->que[i]); q->que[i] = NULL; } free(q->que);/* 配列を解放 */ q->que = NULL; q->max = q->num = q->front = q->rear = 0; } } /*--- キューにデータをエンキュー ---*/ int Enque(StringsQueue *q, char *x){ if (q->num >= q->max)return -1; if ((q->que[q->rear] = calloc(strlen(x)+1, sizeof(char))) == NULL)return -1; /* キューは満杯 */ q->num++; strcpy( q->que[q->rear] ,x); q->rear++; if (q->rear == q->max){ q->max = q->max + 10; } return 0; } /*--- キューからデータをデキュー ---*/ int Deque(StringsQueue *q, char *x){ if (q->num <= 0)/* キューは空 */ return -1; q->num--; strcpy( x ,q->que[q->front]); q->front++; if((q->max-q->num) >= 15){ q->max = q->max - 5; } if (q->front == q->max) q->front = 0; return 0; } /*--- キューからデータをピーク 次のデキューで取り出される値を見る---*/ int Peek(const StringsQueue *q, char *x) { if (q->num <= 0) return -1; x = q->que[q->front]; return 0; } /*--- キューの容量 ---*/ int Capacity(const StringsQueue *q){ return (q->max); } /*--- キューに蓄えられているデータ数 ---*/ int Size(const StringsQueue *q){ return (q->num); } /*--- 全データの表示 ---*/ void Print(const StringsQueue *q){ int i; for(i = 0; i < q->num; i++) if(q->max < 3){ printf("%s \n", q->que[(i + q->front) % q->max]); } else { printf("%s \n", q->que[(i + q->front) % q->max]); } } int main(void){ StringsQueue que; if (Initialize(&que, 7) == -1) { puts("キューの生成に失敗しました。"); } while (1) { int m; char x[79]; printf("現在のデータ数:%d/%d\n", Size(&que), Capacity(&que)); printf("(1) エンキュー (2) デキュー (3) ピーク (4) 表示 (5)パターンの計数 (0) 終了:"); scanf("%d", &m); if (m == 0) break; switch(m){ case 1: printf("データ:"); scanf("%s", x); if (Enque(&que, x) == -1) puts("\a エラー:データのエンキューに失敗しました。"); break; case 2: if (Deque(&que, x) == -1) puts("\a エラー:デキューに失敗しました。"); else printf("デキューしたデータは%s です。\n", x); break; case 3: /* ピーク */ if (Peek(&que, x) == -1) puts("\a エラー:ピークに失敗しました。"); else printf("ピークしたデータは%s です。\n", x); break; case 4: /* 表示 */ Print(&que); break; case 5:/* パターンの計数 */ scanf("%s",x); int count = Count(&que,x); if(count != 0)printf("パターン数は%d個です\n",count); if(count == 0)puts("パターンは存在しません."); break; } } Terminate(&que); return 0; }
if((q->max-q->num) >= 15){
q->max = q->max - 5;
}でキュー拡張がされる前までは、文字化けはしないのですが、拡張後に、”デキュー”と”表示”を実行するとque[0]のみが文字化けしてしまいます。
解決法をご教授お願いします。
https://www.onlinegdb.com/という環境でプログラムを書いています。
Window10のWSL(SUSE Linux)で、”gcc -std=c99 "使ってコンパイルしたものは、拡張した後もデキュー、表示とも正常に動いているようです。どういったコンパイラを使っているのか等の情報も記載してもらえると、再現できる方が回答してくださるかもしれません。
気になったのは、Terminate()関数の処理がまずいです。キューを管理するポインタの配列はfreeしていますが、キューに積んだデータはfreeしていないように見受けられます。
ご指摘ありがとうございます。
void Terminate(StringsQueue *q){
if (q->que != NULL) {
free(q->que);/* 配列を解放 */
q->que = NULL;
for(int i =0 ; i < q->num ; i ++ ){
free(q->que[i]);
q->que[i] = NULL;
}
q->max = q->num = q->front = q->rear = 0;
}
}
キューに積んだデータをfreeするとはこういうことでしょうか。
free(q->que)する前にq->que[i]をfreeすべきですね。free(q->que)した後も各queの要素にアクセス可能な場合もあるかもしれませんが、それはあくまでも偶然であって、不正な領域へのアクセスと考えておいた方が良いです。
void Terminate(StringsQueue *q){
if (q->que != NULL) {
for(int i =0 ; i < q->num ; i ++ ){
free(q->que[i]);
q->que[i] = NULL;
}
free(q->que);/* 配列を解放 */
q->que = NULL;
q->max = q->num = q->front = q->rear = 0;
}
}
このようにしたのですが、double freeとなってしまいます。