全ての課題は指定された言語で実装してください。C++など他の言語で書かれたレポートは採点対象外となります。
文字列の長さは100以下と仮定して構いません。
必要に応じて、"string.h"内で定義されている関数を利用して構いません。
以下のような構造体定義を用いてint型の整数値を格納するリストを表現する事を考える。
typedef struct node{
int number;
struct node *next;
} Node;
Nodeはリスト中の一つの要素を表現しており、numberはそのNodeが格納する整数値、*nextは次の要素へのポインタを示している。この定義を利用して、以下の関数を実装してリスト構造を完成させよ。なお、本課題はメモリ管理が適切に行われているかについても採点対象とする。
リストの先頭に要素を追加する関数 void Prepend(Node** list, int i);
リスト内に含まれるNode数をカウントする関数 int Count(Node* list);
リストのi番目のNodeを削除する関数 void Delete(Node** list, int i); (先頭の要素を0番目のNodeとみなす。iがリストに含まれるNode数以上である場合は何も消してはいけない。Nodeを削除する際にメモリ領域を解放する事を忘れずに。(2022.12 .8変更))
リストのi番目に要素を挿入する関数 void Insert(Node** list, int i, int j); (先頭の要素は0番目のNodeとみなす。iがリストに含まれるNode数+1以上である場合は何も挿入してはいけない。(2022.12 .8 変更))
リスト内の要素を、先頭から順に、半角スペース区切りで出力し、最後に改行する関数 void Print(Node** list); (2021.10.26 追記。)
引数及び返り値の型は上記の定義に従うこと。また、必要に応じて他の関数を実装してもよい。
提出する際には、「main」は以下をそのまま使用すること。
int main(void){
int Q;
scanf("%d", &Q);
Node* list = NULL;
for (int i = 0; i < Q; i++){
int T;
scanf("%d", &T);
if (T == 0) {
int N;
scanf("%d", &N);
Prepend(&list, N);
} else if (T == 1) {
printf("%d\n", Count(list));
} else if (T == 2) {
int N;
scanf("%d", &N);
Delete(&list, N);
} else if (T == 3) {
int N, M;
scanf("%d %d", &N, &M);
Insert(&list, N, M);
} else {
Print(&list);
}
}
return 0;
}
入力例
15
0 1
0 2
0 3
0 4
1
4
2 1
1
4
3 1 5
3 3 6
3 5 7
3 7 8
1
4
出力例
4
4 3 2 1
3
4 2 1
6
4 5 2 6 1 7
REの判定になる方へ: (可能であれば、)コンパイルするときに「-fsanitize=address」オプションを用いると、メモリエラーを発見しやすいです。(2022.12.29 追記)
締切: 12/22 23:59
以下の2つの条件を満たす '(' ')' '.' の３種の文字から構成される文字列Sを考える。ただし、Sのi番目の文字からj番目の文字への部分文字列をS[i..j]と表現する事とする。(Sの先頭の文字は0番目とする。)
文字列内に含まれる'('の数と')'の数は等しい。
任意のxに対して、部分文字列S[0..x]内に含まれる文字')'の数は同一部分文字列内に含まれる文字'('の数以下となる。
たとえば、文字列"(((...)))"は条件を満たすが、"(((..))"は条件1を、"((..)))((...)"は条件2をそれぞれ満たさない。ここで、文字列における'('と')'のペアを考え、i番目の文字'('とj番目の文字')'からなるペアを(i,j)と表現する事とする(ただしi<j)。文字列Sが入力として与えられた時に、下記の3つの条件を全て満たすペア集合の全ての要素を表示するプログラムを作成せよ。複数のペアを列挙する際には、ペア間の区切り文字は半角スペースとし、またペア内の二番目の数字が小さい順に列挙する事。ただし、データ構造としてスタックを実装しそれを利用する事。
ペア集合に含まれる任意の2つのペア(i,j)及び(k,l)において、i≠kかつj≠l
ペア集合に含まれる任意の2つのペア(i,j)及び(k,l)において、i<kであれば、i<j<k<lまたはi<k<l<jが成り立つ(i<k<j<lは成り立たない)
ペア集合に含まれるペアの数は文字列内に含まれる'('の数と同数。
入力例 1
(((...)))
出力例 1
2 6
1 7
0 8
入力例 2
((.).(.).(.))
出力例 2
1 3
5 7
9 11
0 12
条件を満たさないSが入力として与えられたケースは想定しなくて良い。
ヒントその1： 問題設定がやや複雑であるが、直感的にはSchemeにおいて対応している「かっこ」と「こっか」のリストを作成せよという事である。
ヒントその2： スタックはリスト構造を利用する事で実装可能である。課題AD1で定義したリスト構造に対してポップ関数とプッシュ関数を追加実装すれば良い。
締切: 12/22 23:59
Schemeでスタックを実装する事を考える。データ構造としては、スタックはリストであるとする。popとpushというリスト操作を実装することで、スタックを実現する。ここでは、扱いやすいように、popを「stack-read」と「stack-pop」という2つの操作に分解して
(define (stack-push st val)
;; スタック`st'の先頭に`val'を追加して、そのスタックを返す。
)
(define (stack-read st)
;; スタック`st'の先頭の要素を返す。
)
(define (stack-pop st)
;; スタック`st'から先頭の要素を取り除いたスタックを返す。
)
このスタックを用いて、整数上の演算を行うことのできる電卓プログラムを作成することにする。プログラムが受け付ける入力は、改行を区切りとする逆ポーランド記法による式である。ただし、「2 0 -」は通常の記法で「2 – 0」を意味するものとする。プログラムは入力途中には何も表示せず、「=」が入力されると直近の計算結果を表示して終了する。スタックを操作する関数と、以下のコードを動かすのに必要な関数「calc-add」他を定義せよ。（以下のコードはレポートには含めない。）
(let ((st (list)))
(define (main-loop st)
(let ((cmd (read)))
(cond
((or (equal? cmd '=) (eof-object? cmd))
(write (stack-read st)) (newline))
((equal? cmd '+)
(main-loop (calc-add st)))
((equal? cmd '-)
(main-loop (calc-sub st)))
((equal? cmd '*)
(main-loop (calc-mul st)))
((number? cmd)
(main-loop (stack-push st cmd)))
(else
(display "(unknown command)\n")
(main-loop st)))))
(main-loop st))
入力例:
1
2
3
*
*
4
5
*
-
6
7
*
8
9
*
+
+
=
上記入力を行なった場合、結果は100が表示されるはずである。正しくない結果が得られた場合、「2 0 - =」の結果が２となるかを確認すると間違いが見つかるかもしれない。
締切: 12/22 23:59
代数構造を持つ集合において、「1 + 2」のように、2項演算は、引数、演算子、引数の順で表記されるのが普通です。この順序を変えて、演算子を前に書く記法をポーランド記法と呼びます。3項以上の場合も同様に演算子を前に書きます。すぐに気がついたと思いますが、Schemeはポーランド記法を採用しています。ポーランド記法の利点として、演算子ごとに引数の数が決まっていれば、括弧が不要であるという性質が挙げられます。（Schemeは引数の数が不定なこともあるので、括弧を使っています。）逆ポーランド記法は、演算子を前ではなく後に書く方式です。逆ポーランド記法もポーランド記法と同じく括弧が不要です。また、逆ポーランド記法で書かれた式は、スタックを1つ使うことで、構文を解析することなく計算が可能です。このため、一部では非常に人気のある記法となっています。