PPT

第11回講義課題
 リスト構造の強力な利点は，データサイズに制限がないこ
とである．そこで，リスト構造を用いてスタックを実装す
ることで，「オーバーフローしないスタック」を作ること
ができる．添付ソースの関数 push()，pop() を作成せよ．
 このスタックにデータをプッシュする場合：
head
push
1
push
2
1
1
第11回講義課題
 データのポップは以下のように行われる：
head
2
pop
1
*n
2
pop
1
*n
1
pop
データなし  エラー信号を返す
※ データ出力は「ポインタ渡し」で行っており，渡す先は main 関数
内のローカル変数 n (pop()にとっての *n) である．
2
第11回講義課題ソース・コードの解説
 ノードの構造体を struct tfield 型として定義し，こ
れを typedef によって「NODE型」と読み替えて (別名を
つけて) いる．
 構造体の変数名が「struct」を含んで長ったらしいので，
C言語ではこの方法がよく行われる．
 まとめて，
typedef struct tfield {
int data;
struct tfield *pointer;
} NODE;
と書いてもよい．
3
第11回講義課題ソース・コードの解説
 main 関数でやっているのは，キーボード入力された文字
列の 1 文字目をコマンドとして，‘i’ なら入力処理， ‘o’
なら出力処理， ‘d’ ならスタック内容の表示， ‘q’ ならプ
ログラム終了という場合分け処理を無限ループさせている．
 switch 文の使い方が曖昧な学生は，この機会に復習して
おくこと．
 ノード新規生成関数 talloc() では，malloc() による
メモリ動的確保の失敗 (このとき malloc() は NULL を返
す) に対応する処理 (標準エラー出力へのエラーメッセー
ジ出力とプログラム異常終了) を追加してある．
 main 関数の引数・戻り値については，講義ウェブサイト
上の第3回講義の宿題の「解説」の最後の方に簡単な説明
を書いておいた．
4
第11回講義課題ソース・コードの解説
関数 push()，pop() の第二引数が NODE ** 型である理由
 push 操作，pop 操作の双方で，main 関数のローカル変
数 head の書き換えが必要となる．
 変数 head の型は NODE * 型であり，これをポインタ渡し
で渡すには，関数 push()，pop() に対して「head のあ
りか (アドレス)」，すなわち「main 関数から見た場合の
&head」を教えてやる必要がある．
 &head の型は「ノードへのポインタ (head) へのポイン
タ」であるから，NODE ** 型でなければならない．
 関数 push()，pop() から main() 内の head を書き換
えるには，それぞれの関数内で「*head への書き込み」
を行う．
5

Download Report