第２回

Transcription

1 第 4 回基本データ構造 1 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 1 配列 スタック キューとその操作 4-1. 配列とその操作 配列型 同じ型の変数を並べたもの 配列にする型は 基本型 配列型 構造体 ポインタいずれでもよい 要素の並べ方を 次元 という 1 次元配列 ( 直線状 ) 2 次元配列 ( 平面状 ) 3 次元配列 ( 立体状 ) a[5] a[4][5] a[3][4][5] a[2][3][4][5] 表 4-1 配列の次元 要素の場所を示すものを 添え字 ( インデックス ) という [1/10]

2 4-2. スタックとその操作 スタック (stack) 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 2 データの追加 取り出しともに最後 ( 最近 ) のデータで行なう 最初に追加したものを最後に取り出すので FILO(First In Last Out) と表現したり 最後に追加したものを最初に取り出すので LIFO(Last In First Out) と表現したりする 日常でのイメージ レポートを書く わからないことに遭遇 調べ物をする メール着信 メールを読む 電話着信 電話をする スタック ( 作業の一時退避場所 ) メール 調べ物 調べ物 調べ物 レポートレポートレポートレポートレポート スタックを実現するデータ構造 スタックポインタ : 最後に積まれているデータの場所を指し示すポインタ スタックエリア : スタックとして使用する空間 ( メモリの場所 ) [2/10]

3 スタックへの追加 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 3 スタックへデータを追加する操作は 積む PUSH する 退避する 載せる と表現されることもある スタックに を追加する操作 スタックポインタ 元のデータ をこれから積む場所を指すように更新する の場所へ を入れる スタックからの取り出し スタックからデータを取り出す操作は 降ろす POP する 復帰する と表現されることもある スタックから取り出す操作 スタックポインタ 元のデータ の場所からデータを取り出す を次に取り出す場所へ更新する [3/10]

4 4-3. キューとその操作 キュー (queue) 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 4 データの追加は最後 ( 最近 ) 取り出しは先頭 ( 最古 ) のデータで行なう 最初に追加したものを最初に取り出すので FIFO(First In First Out) と表現したり 何かの順番を待って並んでいる列のようなので待ち行列と表現したりする 日常でのイメージ レジ 列の先頭からレジにつく 列の最後尾に並ぶ キューを実現するデータ構造 E F G 読み出しポインタ データを取り出す位置を示す 書き込みポインタ データを追加する位置を示す はデータを取り出すごとに右に移動する はデータを追加するごとに右に移動する データがない場合 ( 空の場合 ) と は同じ場所を指し キューは 下図のようになる [4/10]

5 リングバッファ 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 5 キューバッファとして確保した領域で 格納する場所が最後の位置まで来たとき 次の格納場所をキューバッファの先頭にすることで 効率よく使用できる このように バッファの末尾と先頭をつないで連続させたものを リングバッファ という n 0 n-1 1 E F G リングバッファ リングバッファによるキュー キューへの追加 キューへデータを追加する操作は enqueue( エンキュー ) と表現されることもある キューに を追加する操作 元のデータ の場所へ を入れる を次の場所へ更新する [5/10]

6 キューからの取り出し 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 6 キューからデータを取り出す操作は dequeue( デキュー ) と表現されることもある キューから取り出す操作 元のデータ の場所からデータを取り出す を次の場所へ更新する [6/10]

7 4-4.ppendix 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 配列操作のプログラム array.c #include <stdio.h> #define T_SIZE 10 /* データを格納する配列のサイズ */ #define LST_T (T_SIZE - 1) /* 配列の最後 */ unsigned char g_array[t_size+1]; /* データを格納する配列の宣言 */ /* +1 は この例のプログラムで終端記号を入れるために追加 */ void init( void ); void insert( int insert_point, unsigned char data ); void delete( int delete_point ); int main( void ) printf( " \n" ); init(); printf( "init %s\n", g_array ); insert( 3, '' ); printf( "insert 3,'' %s\n", g_array ); insert( 4, '' ); printf( "insert 4,'' %s\n", g_array ); insert( 5, '' ); printf( "insert 5,'' %s\n", g_array ); insert( 4, '' ); printf( "insert 4,'' %s\n", g_array ); insert( 6, 'E' ); printf( "insert 6,'E' %s\n", g_array ); delete( 5 ); printf( "delete 5 %s\n", g_array ); delete( 6 ); printf( "delete 6 %s\n", g_array ); insert( 6, 'F' ); printf( "insert 6,'F' %s\n", g_array ); delete( 2 ); printf( "delete 2 %s\n", g_array ); insert( 7, 'G' ); printf( "insert 7,'G' %s\n", g_array ); insert( 7, 'H' ); printf( "insert 7,'H' %s\n", g_array ); insert( 7, 'I' ); printf( "insert 7,'I' %s\n", g_array ); return ( 0 ); void insert( int insert_point, unsigned char data ) int i; for ( i = LST_T ; i > insert_point ; i-- ) g_array[i] = g_array[i-1]; /* データの移動 */ g_array[insert_point] = data; /* データ挿入 */ void delete( int delete_point ) int i; for ( i = delete_point ; i < LST_T ; i++ ) g_array[i] = g_array[i+1]; /* データの移動 */ void init( void ) /* 初期データの登録 */ int i; for ( i = 0 ; i < T_SIZE ; i++ ) g_array[i] = '.'; /* すべての領域を '.' で埋める */ g_array[lst_t+1] = '\0'; /* 最後を文字列終端記号に設定する */ [7/10]

8 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page スタック操作のプログラム stack.c #include <stdio.h> #include <stdlib.h> #define STK_SIZE 10 /* スタックのサイズ */ struct stack /* スタック管理の構造体定義 */ unsigned char *sp; /* スタックポインタ */ int remain; /* スタックの残量 */ ; struct stack stack_memory; /* スタック管理の構造体宣言 */ unsigned char *g_stack_limit; /* この例のプログラムでスタックを表示するために追加 */ void push( unsigned char data ); unsigned char pop( void ); void init( void ); int main( void ) unsigned char data; printf( " \n" ); init(); printf( "init %s\n", g_stack_limit ); push( '' ); printf( "push '' %s\n", g_stack_limit ); push( '' ); printf( "push '' %s\n", g_stack_limit ); push( '' ); printf( "push '' %s\n", g_stack_limit ); push( '' ); printf( "push '' %s\n", g_stack_limit ); data = pop(); printf( "pop %s pop data=%c\n", g_stack_limit, data ); data = pop(); printf( "pop %s pop data=%c\n", g_stack_limit, data ); push( 'E' ); printf( "push 'E' %s\n", g_stack_limit ); data = pop(); printf( "pop %s pop data=%c\n", g_stack_limit, data ); return ( 0 ); void push( unsigned char data ) if ( stack_memory.remain > 0 ) /* スタック残量があれば */ stack_memory.sp--; /* スタックポインタ更新 */ *(stack_memory.sp) = data; /* データを追加 */ stack_memory.remain--; /* スタック残量を減らす */ unsigned char pop( void ) unsigned char data; if ( stack_memory.remain < STK_SIZE ) /* スタックの底でなければ */ data = *(stack_memory.sp); /* データを取り出す */ *(stack_memory.sp) = '.'; /* この例のプログラムでデータの取り出しを明示するために追加 */ stack_memory.sp++; /* スタックポインタ更新 */ stack_memory.remain++; /* スタック残量を増やす */ else data = '\0'; /* スタックが空なら返すデータを空にする */ return ( data ); void init( void ) /* スタックメモリの確保と初期設定 */ unsigned char *tmp; stack_memory.sp = malloc( sizeof(unsigned char) * STK_SIZE + 1 ); /* スタックメモリの確保 */ /* +1 は この例のプログラムで終端記号を入れるために追加 */ [8/10]

9 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 9 tmp = g_stack_limit = stack_memory.sp; /* この例のプログラムでスタックの内容を初期化するために追加 */ stack_memory.remain = STK_SIZE; /* スタックの残量初期化 */ stack_memory.sp += STK_SIZE; /* スタックポインタ初期化 */ while ( tmp!= stack_memory.sp ) /* この例のプログラムでスタックの内容を初期化 */ *tmp++ = '.'; /* すべての領域を '.' で埋める */ *tmp = '\0'; /* 最後を文字列終端記号に設定する */ キュー操作のプログラム queue.c #include <stdio.h> #include <stdlib.h> #define QUEUE_SIZE 10 /* キューのサイズ */ struct queue unsigned char *; /* 読み出しポインタ */ unsigned char *; /* 書き込みポインタ */ unsigned char *top; /* キューバッファの先頭 */ unsigned char *end; /* キューバッファの末尾 */ int remain; /* キューの残量 */ ; struct queue queue_buffer; /* キュー管理の構造体宣言 */ void enqueue( unsigned char data ); unsigned char dequeue( void ); void init( void ); int main( void ) unsigned char data; printf( " \n" ); init(); printf( "init %s\n", queue_buffer.top ); enqueue( '' ); printf( "enqueue '' %s\n", queue_buffer.top ); enqueue( '' ); printf( "enqueue '' %s\n", queue_buffer.top ); enqueue( '' ); printf( "enqueue '' %s\n", queue_buffer.top ); enqueue( '' ); printf( "enqueue '' %s\n", queue_buffer.top ); data = dequeue(); printf( "dequeue %s dequeue data=%c\n", queue_buffer.top, data ); data = dequeue(); printf( "dequeue %s dequeue data=%c\n", queue_buffer.top, data ); enqueue( 'E' ); printf( "enqueue 'E' %s\n", queue_buffer.top ); enqueue( 'F' ); printf( "enqueue 'F' %s\n", queue_buffer.top ); enqueue( 'G' ); printf( "enqueue 'G' %s\n", queue_buffer.top ); enqueue( 'H' ); printf( "enqueue 'H' %s\n", queue_buffer.top ); data = dequeue(); printf( "dequeue %s dequeue data=%c\n", queue_buffer.top, data ); data = dequeue(); printf( "dequeue %s dequeue data=%c\n", queue_buffer.top, data ); data = dequeue(); printf( "dequeue %s dequeue data=%c\n", queue_buffer.top, data ); enqueue( 'I' ); printf( "enqueue 'I' %s\n", queue_buffer.top ); enqueue( 'J' ); printf( "enqueue 'J' %s\n", queue_buffer.top ); enqueue( 'K' ); printf( "enqueue 'K' %s\n", queue_buffer.top ); enqueue( 'L' ); printf( "enqueue 'L' %s\n", queue_buffer.top ); enqueue( 'M' ); printf( "enqueue 'M' %s\n", queue_buffer.top ); return ( 0 ); [9/10]

10 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 10 void enqueue( unsigned char data ) if ( queue_buffer.remain > 0 ) /* キュー残量があれば */ *(queue_buffer.) = data; /* データを追加 */ if ( queue_buffer. == queue_buffer.end ) /* 書き込みポインタ更新 */ queue_buffer. = queue_buffer.top; else queue_buffer.++; queue_buffer.remain--; /* キュー残量を減らす */ unsigned char dequeue( void ) unsigned char data; if ( queue_buffer.!= queue_buffer. ) /* キューが空でなければ */ data = *(queue_buffer.); /* データを取り出す */ *(queue_buffer.) = '.'; /* この例のプログラムでデータの取り出しを明示するために追加 */ if ( queue_buffer. == queue_buffer.end ) /* 読み出しポインタ更新 */ queue_buffer. = queue_buffer.top; else queue_buffer.++; queue_buffer.remain++; /* キュー残量を増やす */ else data = '\0'; /* キューが空なら返すデータを空にする */ return ( data ); void init( void ) /* キューバッファの確保と初期設定 */ unsigned char *tmp; queue_buffer.top = malloc( sizeof(unsigned char) * QUEUE_SIZE + 1 ); /* キューバッファの確保 */ /* +1 は この例のプログラムで終端記号を入れるために追加 */ queue_buffer.end = queue_buffer.top + (QUEUE_SIZE -1); /* キュー末尾ポインタ設定 */ queue_buffer.remain = QUEUE_SIZE; /* キューの残量初期化 */ queue_buffer. = queue_buffer.top; /* 読み出しポインタ初期化 */ queue_buffer. = queue_buffer.top; /* 書き込みポインタ初期化 */ tmp = queue_buffer.top; while ( tmp!= queue_buffer.end ) /* この例のプログラムでスタックの内容を初期化 */ *tmp++ = '.'; /* すべての領域を '.' で埋める */ *tmp++ = '.'; *tmp = '\0'; /* 最後を文字列終端記号に設定する */ [10/10]