質問編集履歴
2
修正
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -1,3 +1,5 @@
|
|
|
1
|
+
<追記>
|
|
2
|
+
|
|
1
3
|
```
|
|
2
4
|
|
|
3
5
|
#include <stdio.h>
|
|
@@ -124,7 +126,17 @@
|
|
|
124
126
|
|
|
125
127
|
free(q->que);/* 配列を解放 */
|
|
126
128
|
|
|
127
|
-
q->que =
|
|
129
|
+
q->que = NULL;
|
|
130
|
+
|
|
131
|
+
for(int i =0 ; i < q->num ; i ++ ){
|
|
132
|
+
|
|
133
|
+
free(q->que[i]);
|
|
134
|
+
|
|
135
|
+
q->que[i] = NULL;
|
|
136
|
+
|
|
137
|
+
|
|
138
|
+
|
|
139
|
+
}
|
|
128
140
|
|
|
129
141
|
q->max = q->num = q->front = q->rear = 0;
|
|
130
142
|
|
|
@@ -458,20 +470,18 @@
|
|
|
458
470
|
|
|
459
471
|
if (q->que != NULL) {
|
|
460
472
|
|
|
473
|
+
for(int i =0 ; i < q->num ; i ++ ){
|
|
474
|
+
|
|
475
|
+
free(q->que[i]);
|
|
476
|
+
|
|
477
|
+
q->que[i] = NULL;
|
|
478
|
+
|
|
479
|
+
}
|
|
480
|
+
|
|
461
481
|
free(q->que);/* 配列を解放 */
|
|
462
482
|
|
|
463
483
|
q->que = NULL;
|
|
464
484
|
|
|
465
|
-
for(int i =0 ; i < q->num ; i ++ ){
|
|
466
|
-
|
|
467
|
-
free(q->que[i]);
|
|
468
|
-
|
|
469
|
-
q->que[i] = NULL;
|
|
470
|
-
|
|
471
|
-
|
|
472
|
-
|
|
473
|
-
}
|
|
474
|
-
|
|
475
485
|
q->max = q->num = q->front = q->rear = 0;
|
|
476
486
|
|
|
477
487
|
}
|
1
修正
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -332,6 +332,352 @@
|
|
|
332
332
|
|
|
333
333
|
```
|
|
334
334
|
|
|
335
|
+
<追記>
|
|
336
|
+
|
|
337
|
+
```
|
|
338
|
+
|
|
339
|
+
#include <stdio.h>
|
|
340
|
+
|
|
341
|
+
#include <stdlib.h>
|
|
342
|
+
|
|
343
|
+
#include <string.h>
|
|
344
|
+
|
|
345
|
+
#include <limits.h>
|
|
346
|
+
|
|
347
|
+
typedef struct {/*--- キューを実現する構造体 ---*/
|
|
348
|
+
|
|
349
|
+
int max; /* キューの容量 */
|
|
350
|
+
|
|
351
|
+
int num; /* 現在の要素数 */
|
|
352
|
+
|
|
353
|
+
int front;/* 先頭要素カーソル */
|
|
354
|
+
|
|
355
|
+
int rear; /* 末尾要素カーソル */
|
|
356
|
+
|
|
357
|
+
char **que; /* キュー本体（の先頭要素へのポインタ） */
|
|
358
|
+
|
|
359
|
+
} StringsQueue;
|
|
360
|
+
|
|
361
|
+
|
|
362
|
+
|
|
363
|
+
char *bm_match(char *x , char *q){
|
|
364
|
+
|
|
365
|
+
char *pt; /* txt をなぞるカーソル */
|
|
366
|
+
|
|
367
|
+
char *pp; /* pat をなぞるカーソル */
|
|
368
|
+
|
|
369
|
+
int txt_len = strlen(q); /* txt の文字数 */
|
|
370
|
+
|
|
371
|
+
int pat_len = strlen(x); /* pat の文字数 */
|
|
372
|
+
|
|
373
|
+
int skip[UCHAR_MAX + 1]; /* スキップテーブル */
|
|
374
|
+
|
|
375
|
+
int i;
|
|
376
|
+
|
|
377
|
+
for (i = 0; i <= UCHAR_MAX; i++) /* スキップテーブルの作成 */
|
|
378
|
+
|
|
379
|
+
skip[i] = pat_len;
|
|
380
|
+
|
|
381
|
+
for (pp = x; *pp != '\0'; pp++)
|
|
382
|
+
|
|
383
|
+
skip[*pp] = strlen(pp) - 1;
|
|
384
|
+
|
|
385
|
+
skip[*(pp - 1)] = pat_len; /* パターンの最後文字の移動距離はパターンの文字数 */
|
|
386
|
+
|
|
387
|
+
pt = q + pat_len - 1; /* pat の末尾と比較する txt の文字を決定 */
|
|
388
|
+
|
|
389
|
+
while ( pt < q + txt_len) { /* txt の比較する文字の位置が txt の末尾を越えるまで */
|
|
390
|
+
|
|
391
|
+
pp = x + pat_len - 1; /* pat の最後の文字に着目 */
|
|
392
|
+
|
|
393
|
+
while (*pt == *pp) {
|
|
394
|
+
|
|
395
|
+
if (pp == x) return (pt); /* 一致した文字がパターンの最初の文字になれば終了 */
|
|
396
|
+
|
|
397
|
+
pp--;
|
|
398
|
+
|
|
399
|
+
pt--;
|
|
400
|
+
|
|
401
|
+
}
|
|
402
|
+
|
|
403
|
+
pt += (skip[*pt]> strlen(pp)) ? skip[*pt] : strlen(pp);
|
|
404
|
+
|
|
405
|
+
}
|
|
406
|
+
|
|
407
|
+
return (NULL);
|
|
408
|
+
|
|
409
|
+
}
|
|
410
|
+
|
|
411
|
+
|
|
412
|
+
|
|
413
|
+
int Count(StringsQueue *q , char *x){
|
|
414
|
+
|
|
415
|
+
int sum = 0;
|
|
416
|
+
|
|
417
|
+
char* s;
|
|
418
|
+
|
|
419
|
+
for(int i = 0 ; i < q->num ; i++){
|
|
420
|
+
|
|
421
|
+
s = bm_match(x , q->que[q->front]);
|
|
422
|
+
|
|
423
|
+
q->front ++;
|
|
424
|
+
|
|
425
|
+
if(s != NULL) sum++;
|
|
426
|
+
|
|
427
|
+
}
|
|
428
|
+
|
|
429
|
+
return sum;
|
|
430
|
+
|
|
431
|
+
}
|
|
432
|
+
|
|
433
|
+
|
|
434
|
+
|
|
435
|
+
/*--- キューの初期化 ---*/
|
|
436
|
+
|
|
437
|
+
int Initialize(StringsQueue *q, int max){
|
|
438
|
+
|
|
439
|
+
q->num = q->front = q->rear = 0;
|
|
440
|
+
|
|
441
|
+
if ((q->que = calloc(max, sizeof(char *))) == NULL) {
|
|
442
|
+
|
|
443
|
+
q->max = 0; /* 配列の確保に失敗 */
|
|
444
|
+
|
|
445
|
+
return -1;
|
|
446
|
+
|
|
447
|
+
}
|
|
448
|
+
|
|
449
|
+
q->max = max;
|
|
450
|
+
|
|
451
|
+
return 0;
|
|
452
|
+
|
|
453
|
+
}
|
|
454
|
+
|
|
455
|
+
/*--- キューの後始末 ---*/
|
|
456
|
+
|
|
457
|
+
void Terminate(StringsQueue *q){
|
|
458
|
+
|
|
459
|
+
if (q->que != NULL) {
|
|
460
|
+
|
|
461
|
+
free(q->que);/* 配列を解放 */
|
|
462
|
+
|
|
463
|
+
q->que = NULL;
|
|
464
|
+
|
|
465
|
+
for(int i =0 ; i < q->num ; i ++ ){
|
|
466
|
+
|
|
467
|
+
free(q->que[i]);
|
|
468
|
+
|
|
469
|
+
q->que[i] = NULL;
|
|
470
|
+
|
|
471
|
+
|
|
472
|
+
|
|
473
|
+
}
|
|
474
|
+
|
|
475
|
+
q->max = q->num = q->front = q->rear = 0;
|
|
476
|
+
|
|
477
|
+
}
|
|
478
|
+
|
|
479
|
+
}
|
|
480
|
+
|
|
481
|
+
/*--- キューにデータをエンキュー ---*/
|
|
482
|
+
|
|
483
|
+
int Enque(StringsQueue *q, char *x){
|
|
484
|
+
|
|
485
|
+
if (q->num >= q->max)return -1;
|
|
486
|
+
|
|
487
|
+
if ((q->que[q->rear] = calloc(strlen(x)+1, sizeof(char))) == NULL)return -1; /* キューは満杯 */
|
|
488
|
+
|
|
489
|
+
q->num++;
|
|
490
|
+
|
|
491
|
+
strcpy( q->que[q->rear] ,x);
|
|
492
|
+
|
|
493
|
+
q->rear++;
|
|
494
|
+
|
|
495
|
+
if (q->rear == q->max){
|
|
496
|
+
|
|
497
|
+
q->max = q->max + 10;
|
|
498
|
+
|
|
499
|
+
}
|
|
500
|
+
|
|
501
|
+
return 0;
|
|
502
|
+
|
|
503
|
+
}
|
|
504
|
+
|
|
505
|
+
/*--- キューからデータをデキュー ---*/
|
|
506
|
+
|
|
507
|
+
int Deque(StringsQueue *q, char *x){
|
|
508
|
+
|
|
509
|
+
if (q->num <= 0)/* キューは空 */
|
|
510
|
+
|
|
511
|
+
return -1;
|
|
512
|
+
|
|
513
|
+
q->num--;
|
|
514
|
+
|
|
515
|
+
strcpy( x ,q->que[q->front]);
|
|
516
|
+
|
|
517
|
+
q->front++;
|
|
518
|
+
|
|
519
|
+
if((q->max-q->num) >= 15){
|
|
520
|
+
|
|
521
|
+
q->max = q->max - 5;
|
|
522
|
+
|
|
523
|
+
}
|
|
524
|
+
|
|
525
|
+
if (q->front == q->max) q->front = 0;
|
|
526
|
+
|
|
527
|
+
return 0;
|
|
528
|
+
|
|
529
|
+
}
|
|
530
|
+
|
|
531
|
+
/*--- キューからデータをピーク 次のデキューで取り出される値を見る---*/
|
|
532
|
+
|
|
533
|
+
int Peek(const StringsQueue *q, char *x)
|
|
534
|
+
|
|
535
|
+
{
|
|
536
|
+
|
|
537
|
+
if (q->num <= 0)
|
|
538
|
+
|
|
539
|
+
return -1;
|
|
540
|
+
|
|
541
|
+
x = q->que[q->front];
|
|
542
|
+
|
|
543
|
+
return 0;
|
|
544
|
+
|
|
545
|
+
}
|
|
546
|
+
|
|
547
|
+
/*--- キューの容量 ---*/
|
|
548
|
+
|
|
549
|
+
int Capacity(const StringsQueue *q){
|
|
550
|
+
|
|
551
|
+
return (q->max);
|
|
552
|
+
|
|
553
|
+
}
|
|
554
|
+
|
|
555
|
+
/*--- キューに蓄えられているデータ数 ---*/
|
|
556
|
+
|
|
557
|
+
int Size(const StringsQueue *q){
|
|
558
|
+
|
|
559
|
+
return (q->num);
|
|
560
|
+
|
|
561
|
+
}
|
|
562
|
+
|
|
563
|
+
/*--- 全データの表示 ---*/
|
|
564
|
+
|
|
565
|
+
void Print(const StringsQueue *q){
|
|
566
|
+
|
|
567
|
+
int i;
|
|
568
|
+
|
|
569
|
+
|
|
570
|
+
|
|
571
|
+
for(i = 0; i < q->num; i++)
|
|
572
|
+
|
|
573
|
+
if(q->max < 3){
|
|
574
|
+
|
|
575
|
+
printf("%s \n", q->que[(i + q->front) % q->max]);
|
|
576
|
+
|
|
577
|
+
} else {
|
|
578
|
+
|
|
579
|
+
printf("%s \n", q->que[(i + q->front) % q->max]);
|
|
580
|
+
|
|
581
|
+
}
|
|
582
|
+
|
|
583
|
+
}
|
|
584
|
+
|
|
585
|
+
int main(void){
|
|
586
|
+
|
|
587
|
+
StringsQueue que;
|
|
588
|
+
|
|
589
|
+
|
|
590
|
+
|
|
591
|
+
if (Initialize(&que, 7) == -1) {
|
|
592
|
+
|
|
593
|
+
puts("キューの生成に失敗しました。");
|
|
594
|
+
|
|
595
|
+
}
|
|
596
|
+
|
|
597
|
+
while (1) {
|
|
598
|
+
|
|
599
|
+
int m;
|
|
600
|
+
|
|
601
|
+
char x[79];
|
|
602
|
+
|
|
603
|
+
|
|
604
|
+
|
|
605
|
+
printf("現在のデータ数：%d/%d\n", Size(&que), Capacity(&que));
|
|
606
|
+
|
|
607
|
+
printf("(1) エンキュー (2) デキュー (3) ピーク (4) 表示 (5)パターンの計数 (0) 終了：");
|
|
608
|
+
|
|
609
|
+
scanf("%d", &m);
|
|
610
|
+
|
|
611
|
+
if (m == 0) break;
|
|
612
|
+
|
|
613
|
+
|
|
614
|
+
|
|
615
|
+
switch(m){
|
|
616
|
+
|
|
617
|
+
case 1: printf("データ："); scanf("%s", x);
|
|
618
|
+
|
|
619
|
+
if (Enque(&que, x) == -1)
|
|
620
|
+
|
|
621
|
+
puts("\a エラー:データのエンキューに失敗しました。");
|
|
622
|
+
|
|
623
|
+
break;
|
|
624
|
+
|
|
625
|
+
case 2:
|
|
626
|
+
|
|
627
|
+
if (Deque(&que, x) == -1)
|
|
628
|
+
|
|
629
|
+
puts("\a エラー:デキューに失敗しました。");
|
|
630
|
+
|
|
631
|
+
else
|
|
632
|
+
|
|
633
|
+
printf("デキューしたデータは%s です。\n", x);
|
|
634
|
+
|
|
635
|
+
break;
|
|
636
|
+
|
|
637
|
+
case 3: /* ピーク */
|
|
638
|
+
|
|
639
|
+
if (Peek(&que, x) == -1)
|
|
640
|
+
|
|
641
|
+
puts("\a エラー：ピークに失敗しました。");
|
|
642
|
+
|
|
643
|
+
else
|
|
644
|
+
|
|
645
|
+
printf("ピークしたデータは%s です。\n", x);
|
|
646
|
+
|
|
647
|
+
break;
|
|
648
|
+
|
|
649
|
+
case 4: /* 表示 */
|
|
650
|
+
|
|
651
|
+
Print(&que);
|
|
652
|
+
|
|
653
|
+
break;
|
|
654
|
+
|
|
655
|
+
case 5:/* パターンの計数 */
|
|
656
|
+
|
|
657
|
+
scanf("%s",x);
|
|
658
|
+
|
|
659
|
+
int count = Count(&que,x);
|
|
660
|
+
|
|
661
|
+
if(count != 0)printf("パターン数は%d個です\n",count);
|
|
662
|
+
|
|
663
|
+
if(count == 0)puts("パターンは存在しません.");
|
|
664
|
+
|
|
665
|
+
break;
|
|
666
|
+
|
|
667
|
+
}
|
|
668
|
+
|
|
669
|
+
}
|
|
670
|
+
|
|
671
|
+
Terminate(&que);
|
|
672
|
+
|
|
673
|
+
return 0;
|
|
674
|
+
|
|
675
|
+
}
|
|
676
|
+
|
|
677
|
+
|
|
678
|
+
|
|
679
|
+
```
|
|
680
|
+
|
|
335
681
|
if((q->max-q->num) >= 15){
|
|
336
682
|
|
|
337
683
|
q->max = q->max - 5;
|
|
@@ -339,3 +685,5 @@
|
|
|
339
685
|
}でキュー拡張がされる前までは、文字化けはしないのですが、拡張後に、”デキュー”と”表示”を実行するとque[0]のみが文字化けしてしまいます。
|
|
340
686
|
|
|
341
687
|
解決法をご教授お願いします。
|
|
688
|
+
|
|
689
|
+
https://www.onlinegdb.com/という環境でプログラムを書いています。
|