先日の演習で、配列が途中データ挿入にあたり、O(N)の処理を要する問題提起を踏まえ、 今回はリスト構造を説明。
次のデータの場所
途中にデータを挿入する手間を簡単にする方法として、リスト構造を説明するために、 最初に以下のプログラムを示す。このプログラムでは、一見デタラメな数字が 並んでいるように見えるが、table[*].data部が 1,2,5,7,8 と昇順に表示される。 これは、table[*].next 部に、次に大きいデータの場所が記載されているため。
int top = 3 ; struct DataNext { int data ; int next ; } table[ 10 ] = { 5 , 1 , 7 , 4 , 2 , 0 , 1 , 2 , 8 , -1 , } ; for( int i = top ; i >= 0 ; i = table[ i ].next ) printf( "%d" , table[ i ].data ) ;
このような方法を取っていれば、data に3を加えたい時は、 table[5].data = 3 ; table[5].next = 0 ; table[2].next = 5 ; を実行すれば、 データ順序を守ったまま、2と5の間に3を挿入できる。
しかし、このままでは、配列のサイズが固定値の問題を解決できない。
リスト構造
これらの問題を解決するために、必要に malloc で data と next の記憶場所を確保すれば良い。
(( まずは基本 )) struct List { int data ; struct List* next ; } ; struct List* top ; top = (struct List*)malloc( sizeof(struct List) ) ; top->data = 1 ; top->next = (struct List*)malloc( sizeof(struct List) ) ; top->next->data = 2 ; top->next->next = (struct List*)malloc( sizeof(struct List) ) ; top->next->data = 3 ; top->next->next = NULL ; // top ◯→[1|◯]→[2|◯]→[3|×] struct List* p ; for( p = top ; p != NULL ; p = p->next ) printf( "%d" , p->data ) ; (( 補助関数を作ってシンプルに )) struct List* cons( int x ; struct List* n ) { struct List* nw ; nw = (struct List*)malloc( sizeof( struct List ) ) ; if ( nw != NULL ) { nw->data = x ; nw->next = n ; } return nw ; } struct List* top = cons( 1, cons( 2, cons( 3, NULL ) ) ) ;
typedef命令
時間が微妙に会ったので、補足説明として typedef を説明する。 ただし、リスト宣言を typedef で記載するのは、C言語の場合だけ。 C++では、構造体・クラス名はそのまま型名として使用できる。
(( typedef の使い方の基本 )) // 符号なし16bit整数をいつも書くと面倒 typedef unsigned short int uint16 ; uint16 x = 0x1234 ; (( typedefでList宣言 )) typedef struct LIST { int data ; struct LIST* next ; } List ; List* cons( int x , List* n ) { // 補助関数の宣言もシンプルに } List* top = cons(1,cons(2,cons(3,NULL)));