前回説明した、リスト構造について簡単なプログラム作成を通して、プログラミングに慣れてみよう。
簡単なリスト処理の例
// 全要素を表示する関数
void print( struct List* p ) {
for( ; p != NULL ; p = p->next )
printf( "%d " , p->data ) ;
printf( "¥n" ) ;
}
// データ数を返す関数
int count( struct List* p ) {
int c = 0 ;
for( ; p != NULL ; p = p->next )
c++ ;
return c ;
}
void main() {
struct List* top = cons( 111 , cons( 444 , cons( 333 , NULL ) ) ) ;
print( top ) ;
printf( "%d¥n" , count( top ) ) ;
}
リスト処理を自分で考えて作成
以下のようなプログラムを作ってみよう。意味がわかって慣れてくれば、配列の部分の for の回し方が変わっただけということに慣れてくるだろう。
// 全要素の合計
int sum( struct List* p ) {
// sum( top ) → 888
}
// リストの最大値を返す
int max( struct List* p ) {
// max( top ) → 444 (データ件数0の場合0を返す)
}
// リストの中から指定した値の場所を返す
int find( struct List* p , int key ) {
// find( top , 444 ) = 1 (先頭0番目)
// 見つからなかったら -1
}
途中でデータ挿入・データ削除
リスト構造の特徴は、途中にデータを入れたり、途中のデータを抜くのが簡単にできる所。そのプログラムは以下のようになるだろう。
void insert( struct List*p , int data ) {
// あえて、補助関数consを使わずに書いてみる
struct List* n ;
n = (struct List*)malloc( sizeof( struct List ) ) ;
if ( n != NULL ) {
n->data = data ;
n->next = p->next ;
p->next = n ;
}
// p->next = cons( data , p->next ) ;
}
void remove_after( struct List* p ) {
struct List* del = p->next ;
p->next = del->next ;
free( del ) ;
}
再帰呼び出しでリスト処理
リスト処理の応用のプログラムを作るなかで、2分木などのプログラミングでは、リスト処理で再帰呼出しを使うことも多いので、先に示したプログラムを再帰呼び出しで書いたらどうなるであろうか？
// 全データを表示
void print( struct List* p ) {
if ( p == NULL ) {
printf( "¥n" ) ;
} else {
printf( "%d " , p->data ) ;
print( p->next ) ; // 末尾再帰
}
}
// データ数を返す関数
int count( struct List* p ) {
if ( p == NULL )
return 0 ;
else
return 1 + count( p->next ) ; // 末尾再帰
}
// 全要素の合計
int sum( struct List* p ) {
// sum( top ) → 888
自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
// max( top ) → 444 (データ件数0の場合0を返す)
自分で考えよう
}
// リストの中から指定した値を探す。
int find( struct List* p , int key ) {
// find( top , 444 ) = 1
// 見つかったら1 , 見つからなかったら 0
自分で考えよう
}