ヒント：リストの先頭の場所を記憶し、元の場所に戻ったら終了。
#include <stdio.h>
struct List {
int data ;
struct List* next ;
} ;
#define MALLOC(TYPE) (TYPE*)malloc( sizeof(TYPE) )
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(A)
/* 1つのセルを作り要素を代入する */
struct List* cons( int d , struct List* n ) {
struct List* nn ;
if ( (nn = MALLOC( struct List )) != NULL ) {
nn->data = d ;
nn->next = n ;
}
return nn ;
}
/* リストの中からデータを探す */
int find( struct List* p , int key ) {
if ( p == NULL )
return 0 ; /* 見つからなかった */
else if ( p->data == key )
return 1 ; /* 見つかった */
else /* 残りから探す */
return find( p->next , key ) ;
}
/* 集合和を求める関数 */
_______ union_set( _______ list1 , ______ list2 )
{
変数リストへのポインタ ans の宣言。
ans の初期値は、list2 全体とする。
list1 の全要素についての繰り返す。
list1 の要素が list2 に含まれていなければ、
その要素を ans の先頭に加える。
集合和の結果として ans を返す。
}
void main()
{
struct List *p1 = cons( 1 , cons( 2 , cons( 3 , NULL ))) ;
struct List *p2 = cons( 2 , cons( 4 , cons( 6 , NULL ))) ;
struct List *p3 = union_set( p1 , p2 ) ;
/* 何らかの処理.... */
}
数値の集合を扱うために、前述のプログラムを作成した。
この中の集合和を求める関数 union_set() が、未完成である。
プログラム中の説明に従って関数を完成させよ。
関数の戻り値や引数の宣言も含めて記述せよ。
設問1 のリスト処理で作られたリストを 解放する関数として、以下の freeList() を作った。 しかし、正しく動作しなかった。
void freeList( struct List* p ) {
/* リストの全要素を解放する関数のつもり */
/* ただし、正しく動作しない */
for( ; p != NULL ; p = p->next )
free( p ) ;
}
動かない理由を説明し、正しいプログラムを示せ。
#include <stdio.h>
struct List {
char* data ;
struct List* next ;
} ;
#define MALLOC(TYPE) (TYPE*)malloc( sizeof(TYPE) )
/* 1つのセルを作り要素を代入する */
struct List* cons( char* d , struct List* n ) {
struct List* nn ;
if ( (nn = MALLOC( struct List )) != NULL ) {
nn->data = d ;
nn->next = n ;
}
return nn ;
}
/* 循環リストに１要素を追加する */
void insert( struct List* r , char* d ) {
struct List* nn ;
if ( (nn = MALLOC( struct List )) ) {
nn->data = ; ~~~~~~~~(A)
~~~~~~~~~~~~~(B)
nn->next = ;
~~~~~~~~~~~~~(C)
;
} ~~~~~~~~~~~~~~~~~~~~~~~~(D)
}
void printRingList( struct List* p ) {
/* 循環リストの全データを表示する関数 */
/* ただしリストは必ず１件以上のデータを含む */
/* データ件数３だけ正しく動くのは不可 */
}
void main()
{
struct List* ring = cons( NULL , NULL ) ;
ring->next = ring ; /* (E) */
insert( ring , "Sadako" ) ; /* データを追加 */
insert( ring , "Ring2" ) ;
insert( ring , "Psyco" ) ;
printRingList( ring ) ; /* リストを全表示 */
}
以下の２つの用語について説明せよ。
#include <stdio.h>
#define SUCCESS 1
#define FAIL 0
/* - - - - - - - - - - - - - - - - - */
struct StackArray {
int sp ;
int array[ 100 ] ;
} ;
void initArray( stack ) {
~~~~~~~~~~~~~~~~~~(A)
stack->sp = 0 ;
}
int pushArray( struct StackArray* stack , int value ) {
if ( stack->sp < sizeof( stack->array ) ) {
stack->array[ ] = ;
~~~~~~~~~(B) ~~~~~(C)
~~~~~~~~~~~(D)
return SUCCESS ;
} else {
return FAIL ; /* 配列溢れで失敗 */
}
}
int popArray( struct StackArray* stack , int* ans ) {
if ( stack->sp > 0 ) {
stack->sp-- ;
*ans = stack->array[ stack->sp ] ;
return SUCCESS ;
} else {
return FAIL ; /* 配列が空で取り出せない */
}
}
/* - - - - - - - - - - - - - - - - - */
struct List {
int data ;
struct List* next ;
} ;
struct List* cons( int d , struct List* n ) {
struct List* ret
= (struct List*)malloc( sizeof( struct List ) ) ;
if ( ret != NULL ) {
ret->data = d ;
ret->next = n ;
}
return ret ;
}
struct StackList {
struct List* sp ;
} ;
void initList( struct StackList* stack ) {
stack->sp = NULL ;
}
int pushList( struct StackList* stack , int value ) {
struct List* n = cons( value , stack->sp ) ;
if ( n != NULL ) {
stack->sp = n ;
return SUCCESS ;
} else {
return FAIL ; /* ヒープ領域が不足 */
}
}
int popList( stack , ans ) {
~~~~~~~~~~~~~~~~~(E) ~~~~(F)
if ( stack->sp ) {
~~~~~~~(G)
struct List* del = stack->sp ;
stack->sp = (stack->sp)->next ;
*ans = del->data ;
free( del ) ;
return ;
} else ~~~~~~~(H)
return ; /* リストが空で失敗 */
} ~~~~~~~(I)
void main() {
struct StackArray stack1 ;
struct StackList stack2 ;
int x ;
initArray( &stack1 ) ; /* 配列 stack の初期化 */
pushArray( &stack1 , 12 ) ;
pushArray( &stack1 , 56 ) ;
if ( popArray( &stack1 , &x ) )
printf( "%d\n" , x ) ; /* 56 が表示される */
if ( popArray( &stack1 , &x ) )
printf( "%d\n" , x ) ; /* 12 が表示される */
initList( ) ; /* リスト stack の初期化 */
~~~~~~~(J)
pushList( &stack2 , 34 ) ;
pushList( &stack2 , 78 ) ;
if ( popList( &stack2 , &x ) )
printf( "%d\n" , x ) ; /* 78 が表示される */
if ( popList( &stack2 , &x ) )
printf( "%d\n" , x ) ; /* 34 が表示される */
}
(a)配列を使った Stack 構造と、(b)リストを使った Stack 構造を、
同じ使い方の関数を作ることで、データ構造を簡単に切替えることができるよ
うにプログラムを記述した。
ただし Stack への追加・取り出しの関数は、配列溢れやメモリ不足での
チェックができるように、定数値 SUCCESS,FAILを返す。
プログラム中の下線部(A)〜(J)を埋めよ。