サイトマップ / C言語講座>出入り口>総目次>目次:ヒープ領域>リスト型のデータ構造
/* プログラムが起動するとメモリアドレスの小さい方から順に、コードセグメント、データセグメント、そしてプログラム実行時に必要に応じて、動的にメモリが確保されるヒープ領域が取られます。
ヒープ領域にメモリが確保されるのは、例えば、calloc( ) や malloc( ) の呼び出し時です。 */
/* これとは別に、上記のメモリと不連続に、上位のメモリから下位のメモリに向けて、スタックという領域がとられます。関数を呼び出すと、スタックに戻り場所や変数の値を ( 引数 ) を積んで制御が関数に移ります。呼ばれた関数はスタックから値を取り込みます ( Call by value )。
関数の再帰的呼び出しではスタックのメモリを大量に必要とすることがあります。これをスタックを大量に消費するといいます。
スタックのメモリ管理は後入先出法 ( LIFO: Last In First Out ) で行われます。後に入れたデータ ( 新しいデータ ) から順に出力されます。スタックは、データのリストを管理するためのアルゴリズムで、リストの末尾に対してのみ、追加削除が行われます。
リスト型とはあるデータの中に次のデータを指すポインタを含んでいて、次々にデータを辿れるようになっているデータ構造です。配列は添字を使ってデータにランダムアクセスできますが、サイズが決まっています。 */
/* 今回は前の構造体を指すポインタを含む構造体を使って、リスト型を実現し、データの追加削除をするプログラムです。その構造体を下記に示します。
#define NAME_SIZE 20 typedef struct item item_t; struct item { int no; // アイテム番号 char name[NAME_SIZE]; // 商品名 int prise; // 値段 item_t *previous; // 前の item 構造体へのポインタ };
*/
/* プログラムを実行すると、コンソールに下記の表示が現れます。番号を入力して、データの追加、削除、一覧表示、終了を選択します。
1: 追加 2: 削除 3: リスト 4: 終了
メモリ管理は後入先出法で行われます。データの追加は、最後に追加したデータの後ろに行われます。データの削除は、最後に追加したデータに対して行われます。
自作の関数には、次のものがあります。
item_t *AddItem(item_t *item); item を追加して、追加した item へのポインタを返す item_t *DelItem(item_t *item); item を表示後、メモリを解放し、一つ前のitem へのポインタを返す。 item がなければ受け取ったポインタをそのまま返す void ListItem(item_t *item); 登録されている item を全て表示 void FreeItem(item_t *item); calloc( ) で割り付けられたメモリの解放
後は、ソースプログラムのコメントを見て下さい。 */
#include <stdio.h> #include <stdlib.h> /* exit( ) calloc( ) で必要 */ #include <string.h> /* strcpy( ) で必要 */ #define NAME_SIZE 20 typedef struct item item_t; struct item { int no; /* アイテム番号 */ char name[NAME_SIZE]; /* 商品名 */ int prise; /* 値段 */ item_t *previous; /* 前の item 構造体へのポインタ */ }; enum { /* main( ) を参照のこと */ ADD = 1, /* 追加 */ REMOVE, /* 削除 */ LIST, /* 一覧表示 */ END /* 終了 */ }; item_t *AddItem(item_t *item); item_t *DelItem(item_t *item); void ListItem(item_t *item); void FreeItem(item_t *item); void main(void); /* item を追加して、追加した item へのポインタを返す */ item_t *AddItem(item_t *item) { item_t *p; char temp[256]; int x; if ((p = (item_t *)calloc(1, sizeof(item_t))) == NULL) { fprintf(stderr, "メモリ アロケーション エラー\n"); exit (2); /* メモリ割り当てに失敗したら、シェルに戻る */ } (*p).no = (*item).no + 1; /* item 番号を設定 */ printf("No %d 商品名を入力して下さい ", (*p).no); scanf("%s", temp); if (strlen(temp) < NAME_SIZE) strcpy((*p).name, temp); else { /* 文字列が長すぎたら */ printf("商品名が長過ぎます!\n"); /* 警告を発し */ free(p); /* メモリを解放して */ return(item); /* ポインタをそのまま返す */ } printf("値段を入力して下さい "); scanf("%d", &x); (*p).prise = x; printf("\tNo %d 商品名:%s 値段:%d を追加しました\n", (*p).no, (*p).name, (*p).prise); p->previous = item; /* 一つ前の構造体を指すようにする */ return (p); /* 追加した構造体へのポインタを返す */ } /* item を表示後、メモリを解放し、一つ前のitem へのポインタを返す*/ /* item がなければ受け取ったポインタをそのまま返す */ item_t *DelItem (item_t *item) { item_t *p; if (item->previous != NULL) { printf("\tNo %d 商品名:%s 値段:%d を削除しました\n", (*item).no, (*item).name, (*item).prise); p = item->previous; /* free( ) を実行する前に実行 */ free(item); return (p); } else { printf("\tアイテムがありません!\n");/* item がなければ */ return (item); /* 受け取ったポインタをそのまま返す */ } } /* 登録されている item を全て表示 */ void ListItem(item_t *item) { while (item->previous != NULL) { printf("\tNo %d 商品名:%s 値段:%d\n", (*item).no, (*item).name, (*item).prise); item = item->previous; /* 一つ前の item を指すようにする */ } } /* calloc( ) で割り付けられたメモリの解放 */ void FreeItem(item_t *item) { item_t *previous; /* 作業用ポインタ */ while (item->previous != NULL) { previous = item->previous; /* 次の構造体のアドレスを保存 */ free(item); /* メモリを解放 */ item = previous; /* 次の構造体のアドレスを */ } /* item に代入 */ } void main(void) { item_t *item; char buff[256]; int n; if ((item = (item_t *)calloc (1, sizeof(item_t))) == NULL) { fprintf(stderr, "Memory Allocation Error\n"); exit(2); /* メモリ割り当てに失敗したら、シェルに戻る */ } (*item).no = 0; /* item ナンバー 0 */ item->previous = NULL; /* この先には item はない */ for ( ; ; ) { printf("1: 追加 2: 削除 3: リスト 4: 終了\t"); fflush(stdin); /* 標準入力に残っているデータをクリア */ fgets(buff, sizeof(buff), stdin); /* buff に文字列を読み込む */ if(!sscanf(buff, "%d", &n)) /* 数字以外が入力されたら */ continue; /* 無視 */ switch (n) { case (ADD): item = AddItem(item); break; case (REMOVE): item = DelItem(item); break; case (LIST): ListItem(item); break; case (END): FreeItem(item); /* メモリブロックを解放して */ exit(0); /* 終了 */ default: /* ADD REMOVE END 以外は無視 */ continue; } } } |
/* スタックと違って、先入先出法 ( FIFO: First In First Out ) で、メモリを管理するアルゴリズムもあります。先入先出法では、最初に入れたデータ ( 古いデータ ) から順に出力されます。キュー ( 待ち行列 ) のアルゴリズムです。 */
/* (C) 2000- YFプロ. All Rights Reserved. */ 提供:C言語講座−それ自体コンパイルできる教材を使った講座です−