Document

第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回講義課題ソース・コードの解説
関数 push()，pop() の第二引数が NODE ** 型である理由
 push 操作，pop 操作の双方で，main 関数のローカル変
数 head の書き換えが必要となる．
 変数 head の型は NODE * 型であり，これをポインタ渡し
で渡すには，関数 push()，pop() に対して「head のあ
りか (アドレス)」，すなわち「main 関数から見た場合の
&head」を教えてやる必要がある．
 &head の型は「ノードへのポインタ (head) へのポイン
タ」であるから，NODE ** 型でなければならない．
 関数 push()，pop() から main() 内の head を書き換
えるには，それぞれの関数内で「*head への書き込み」
を行う．
3
第11回講義課題解答例
 オーバーフローの
チェックは不要
 新規ノードに n を
記録し，head に連結
main()
head
ノード
1
2
pop() head
n
2
1
copy
n
 void push(int n, NODE **head)
{
NODE *p;
 p = talloc();
 p->data = n;
 p->pointer = *head;
 *head = p;
}
2
1
p
head
p
p
2
1
4
第11回講義課題解答例
 空かのチェック
 int pop(int *n, NODE **head)
{
 先頭ノードのデータ
NODE *p;
を *n に出力，リン
ク調整，メモリ解放．  if (*head == NULL) return -1;
else {
 p = *head;
 *n = p->data;
 *head = p->pointer;
 free(p);
 return 0;
}
main()
-1
0
head
ノード
1
2
pop() head
p
head
n
2
1
n
ノード
1
2
}
p
p
2
1
5
第11回講義課題注意点
 関数 pop() において，*head のメンバ変数を書き換えよ
うとするコードにおいて，
*head->data あるいは *head->pointer
とするとコンパイルエラーとなる．
 正しくは，
(*head)->data あるいは (*head)->pointer
6

Download Report