リスト構造によるFIFO
リスト構造によるStackの続きの話しとして、リスト構造にてFIFOを作るプログラム の解説。
リストでqueue
最初に、配列を使ったFIFOのプログラムを示し、 (1)プログラムにリング操作となる処理の追加、 (2)read pointer がwrite pointer を追い抜くなどの対処の必要性を示す。 最終的に リングバッファ という名前を示し、実例としてキーボードなどの、 受け側が忙しい時の一時データ保管という意味合いを説明。 その後で,リストでFIFOの説明として、以下のコードを示す。
struct List* queue ; // 初期状態は最初伏せて説明
struct List** tail ;
void put( int x )
{ (*tail) = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
int get()
{ struct List*d = queue ;
int ans = queue->data ;
queue = queue->next ;
free( d ) ;
return ans ;
}
課題の提示
演習課題として、リスト構造のプログラム作成として、 (1) 文字列,(2)複素数,(3)名前と電話番号のいずれかのリスト構造を定義し、 (a) 先頭挿入型、(b)末尾追加型のいずれかの方法で入力データを保存し、 データ検索などの処理を行った後、全データを表示する。
データの途中への挿入・削除
void insert( struct List* p , int x )
{ struct List* n ;
n = (struct List*)malloc( sizeof( struct List ) ) ;
if ( n != NULL ) {
n->data = x ;
n->next = p->next ;
p->next = n ;
}
}
void del( struct List* p ) // 関数名にC++キーワードdeleteは避ける
{ struct List* d = p->next ;
p->next = d->next ;
free( d ) ;
}