データおよび次データへのポインタの組を1つの単位として、幾つもの組を1列に継いで管理するデータ構造を、線型リスト(linear list)という。
リスト構造の先頭ノードheadは、管理に使うノードであり、データを格納しない。２個目のノード以降がデータを格納する。最終のノードは、次ノードへのポインタをＮＵＬＬとする。
数の線型リストの例
/* linearlist00.c */
#include <stdio.h>
typedef struct lnode{
int val;
struct lnode *next;
} Node;
Node *list_make_node(int);
void list_print(Node *);
Node *list_make_node(int num) {
Node *ans;
ans = (Node *)malloc(sizeof(Node));
if( ans == NULL ){
fprintf(stderr,"list_make_node failed\n");
exit(0);
}
ans->val = num;
ans->next = NULL;
return ans;
}
void list_print(Node *head) {
Node *p;
p = head->next;
while( p != NULL ){
printf("%d\n", p-> val );
p = p -> next;
}
}
int main() {
Node head, *p;
int n, i;
head.next = NULL;
for( i = 0; i < 10; i ++ ){
printf("数を入力して下さい: ");
scanf("%d", &n);
p = list_make_node( n );
p->next = head.next;
head.next = p;
}
list_print( &head );
return 0;
}
|
プログラム linearlist00.c の動作イメージを以下に示す。
赤い部分が、変化している部分である。
ポインタ型の変数に代入すると、同じ終点を指す矢印ができる。
linearlist00.c では、リスト操作の基本的な関数と、メイン関数が一体 化している。そこで、linearlist00.c を、linearlist.h, linearlist.c, list0701.c の3つに分解しよう。
スタック構造にデータを追加したり取り出したりする操作に push 操作と pop 操作がある。スタック構造は、データを積み上げ式に並べた構造である。 push操作は、さらに上にデータを積む操作で、pop操作は一番上のデータを取 る操作である。
たとえば、机の上に本を山積みしている様子がスタック構造になっている。 push操作では、本の山の上にさらに本を積む。pop操作では、本の山の上から1 冊取り出す。ゆえに、山の一番下にある本を取り出すためには、それより上の 全ての本を pop 操作で取り除く必要がある。
list0701.c には、push操作が含まれている。上記の図でも list_make_node により作成したノードをリストの先頭に追加している。これ は push操作である。
list0701.c より push操作の部分を抽出し、linearlist.c と linearlist.h に定義せよ。list0702.c が動作するように、Makefile に記述 を追加せよ。
/* list0702.c */
#include "linearlist.h";
int main() {
Node head, *p;
int n, i;
head.next = NULL;
for( i = 0; i < 10; i ++ ){
printf("数を入力して下さい: ");
scanf("%d", &n);
list_push(&head,n);
}
list_print( &head );
return 0;
}
|
線型リストに登録されたデータ（数値int）から、条件を満たすノードを 検索する関数 Node *list_search_node_by_range(Node *, int, int) を作成せよ。 条件とは、第2引数の数値以上、かつ、第3引数の数値以下、とする。返り値は、 最初に検出したノード（ポインタ）とする。該当ノードが無い場合はNULLを返 せ。また、ノードの値を表示する関数void list_print_node(Node *)を作成せ よ。作成した関数は、linearlist.c および linearlist.h に登録せよ。以下 のプログラムを用いて動作を確認せよ。
/* list0703.c */
#include "linearlist.h"
int main() {
Node head, *p;
int n, i, min, max;
head.next = NULL;
for( i = 0; i < 10; i ++ ){
printf("数を入力して下さい: ");
scanf("%d", &n);
list_push(&head, n);
}
printf("最小値を入力して下さい: ");
scanf("%d", &min);
printf("最大値を入力して下さい: ");
scanf("%d", &max);
p = list_search_node_by_range(&head,min,max);
if( p == NULL )
printf("ありません。\n");
else
list_print_node( p );
return 0;
}
|
pop操作は、上記の図でいえば、(10)から(9)に戻る様子から理解できるだ ろう。head.nextの指している箱が、pop操作で取り出したい箱であるので、そ れを、p が指すようにする。head.next の指すところは、さらに next の箱と する。p をpop操作の返り値とすればよい。
pop操作を linearlist.c と linearlist.h に追加せよ。以下のプログラ ムを用いて動作を確認せよ。
/* list0704.c */
#include "linearlist.h"
int main() {
Node head, *p;
int n, i, min, max;
head.next = NULL;
for( i = 0; i < 10; i ++ ){
printf("数を入力して下さい: ");
scanf("%d", &n);
list_push(&head, n);
}
while( head.next != NULL ) {
p = list_pop(&head);
list_print_node( p );
}
return 0;
}
|
2006.5.29 by tokuhisa