はじめに
ポインタの練習等を兼ねて、
リンクリスト、二重リンクリスト、ツリーのデータ構造を
作成しようと思ったので、これはその記録のようなものになります。
今回は次の構造体を用いた整数データのリンクリストです。
（二つ作成したのでこれはその一つ目についての記事になります。）
struct list {
int data; /* このノードに格納するデータ */
struct list *next; /* 次のノードへのポインタ */
};
作成したリンクリストの説明
作成したリンクリストは以下のようなものです。
1. リンクリストの要素数を入力してもらう
2. 入力する要素を一行で入力してもらう
3. 入力を出力する
各手順に対して行う処理は以下のようなものです。
1. リストの要素数が入力された時点ですべてのノードを作成し、初期化する
2. 一行を読み取った後、各値を手順1.で作成した各ノードに代入する
3. 出力する
手順１はMake_List関数、手順２はInput_Data関数、手順３はOutput_Data関数を
それぞれ作成しました。
また、各ノードを作成する際mallocを用いてメモリの確保を行いますが、
メモリが足りない場合は以下に示したMemory_Error関数を呼び出して
プログラムを終了させます。
Memory_Error
/*
* Memory_Error -- メモリ不足を通知する
*/
void Memory_Error(void)
{
fprintf(stderr, "Out of memory\n");
exit(8);
}
まず初めにmain関数からMake_List関数を呼び出してリストを作成しますが、
その場合、main関数内で少なくとも一つ以上の初期化された構造体型ポインタが必要になります。
つまりMake_List関数自体は以下のようになりますが、
Make_List
/*
* Make_List -- リンクリストを作成する
*
* 引数
* size -- リストの大きさ
* before_ptr -- 一つ前のノードへのポインタ
*/
void Make_List(struct list *before_ptr, int size)
{
void Make_List(struct list*, int); /* 再帰用 */
void Memory_Error(void); /* メモリ不足の通知 */
static int index = 1; /* ループのインデックス */
struct list *current_ptr; /* 現在のノードへのポインタ */
/* 新しいノードのためのメモリを確保 */
current_ptr = malloc(sizeof(struct list));
if(current_ptr == NULL)
Memory_Error();
/* 各要素を初期化 */
current_ptr->data = 0;
current_ptr->next = NULL;
before_ptr->next = current_ptr;
/* リストを指定の大きさになるまで大きくする */
++index;
if(index < size)
Make_List(current_ptr, size);
else
return;
}
main関数は以下のようにして呼び出しを行わなければなりません。
main（一部）
void Make_List(struct list*, int size); /* リストの作成 */
void Memory_Error(void); /* メモリ不足の通知 */
struct list *top_ptr; /* 先頭のノードへのポインタ */
/* 先頭のノードのためのメモリを確保 */
top_ptr = malloc(sizeof(struct list));
if(top_ptr == NULL)
Memory_Error();
Make_List(top_ptr, size);
リンクリストを作成した時点でリストの要素数を値として保持できるので
リストへの値の入出力を再帰を使わずに行うことができます。
入出力のコードは以下のようになります。
Adjust_String関数については
前回書いた記事の追記の初めにある関数と全く同じものになります。
Input_Data
/*
* Input_Data -- リストにデータを入力する
*
* 引数
* current_ptr -- 現在のノードへのポインタ
* size -- リストの大きさ
*/
void Input_Data(struct list *current_ptr, int size)
{
int Adjust_String(char[], int); /* 文字列を調整する */
int index_int; /* 整数用のインデックス */
int index_str; /* 文字列用のインデックス */
int is_negative; /* 負の数かどうか */
int temp; /* 一時的に値を受け取る */
char line[MAX]; /* ユーザーの入力行 */
is_negative = 0;
fgets(line, sizeof(line), stdin);
for(index_int = 0, index_str = 0;
index_int < size;
++index_str)
{
/* 空白文字->読み飛ばす */
if(line[index_str] == ' ')
continue;
/* ハイフン->is_negativeをオンにする */
else if(line[index_str] == '-'){
line[index_str] = ' ';
is_negative = 1;
continue;
}
/* 要素を入力する */
else{
sscanf(line, "%d", &temp);
if(is_negative == 1)
temp *= -1;
current_ptr->data = temp;
current_ptr = current_ptr->next;
++index_int;
index_str
= Adjust_String(line, index_str);
}
}
return;
}
Output_Data
/*
* Output_Data -- リストデータを出力する
*
* 引数
* top_ptr -- 先頭のノードへのポインタ
* size -- リストの大きさ
*/
void Output_Data(struct list *top_ptr, int size)
{
int index; /* ループのインデックス */
int temp; /* 値を一時的に受け取る */
for(index = 0; index < size; ++index){
temp = top_ptr->data;
top_ptr = top_ptr->next;
printf("%d ", temp);
}
return;
}
出力が終了した後はmallocで確保したメモリを開放します。
これは以下のFree_List関数を用いて行います。
Free_List
/*
* Free_List -- メモリ領域を解放する
*
* 引数
* current_ptr -- 現在のノードへのポインタ
*/
void Free_List(struct list *current_ptr)
{
struct list *temp_ptr; /* ポインタを一時的に受け取る */
while(current_ptr != NULL){
temp_ptr = current_ptr->next;
free(current_ptr);
current_ptr = temp_ptr;
}
}
これらの関数をmain関数から次のように呼び出した場合、
例えば実行結果は以下のようになります。
main.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 500
int main()
{
void Make_List(struct list*, int size); /* リストの作成 */
void Input_Data(struct list*, int size); /* 入力 */
void Output_Data(struct list*, int size); /* 出力 */
void Free_List(struct list*); /* メモリ開放 */
void Memory_Error(void); /* メモリ不足の通知 */
int size; /* リストの大きさ */
char line[MAX]; /* ユーザーの入力行 */
struct list *top_ptr; /* 先頭のノードへのポインタ */
/* 先頭のノードのためのメモリを確保 */
top_ptr = malloc(sizeof(struct list));
if(top_ptr == NULL)
Memory_Error();
fgets(line, sizeof(line), stdin);
sscanf(line, "%d", &size);
Make_List(top_ptr, size);
Input_Data(top_ptr, size);
Output_Data(top_ptr, size);
Free_List(top_ptr);
return 0;
}
5
1 2 3 4 5
1 2 3 4 5
始めに入力を受け取ってそれをそのまま出力するのでは配列と何ら変わりはないので
これに要素を足せるように改良を加えます。
要素を追加する処理はAdd_List関数を用いて行います。
関数内の処理内容は以下のようなものです。
1. 適当なノードを先頭とした任意の個数のリストを別に作成する
2. 始めのリストの最も後ろにあるノードと1.のリストの先頭のノードをつなぐ
ただし、リストの要素数に数字以外の文字が入力されれば処理を終了します。
関数は以下の通りですが今回は初期化だけでは終わらないのでMake_List関数に変更を加えます。
Add_List
/*
* Add_List -- リストに要素を追加する
*
* 引数
* top_ptr -- 追加するリストの最上位のノードへのポインタ
* total_size -- リスト全体の大きさ
*/
void* Add_List(struct list *top_ptr, int *total_size)
{
void Make_List(struct list*, int); /* リストの作成 */
void Input_Data(struct list*, int); /* 値の入力 */
void Memory_Error(void); /* メモリ不足の通知 */
int size; /* 追加するリストの大きさ */
char line[MAX]; /* ユーザーの入力行 */
struct list *last_ptr; /* つなげるリストの先頭 */
fgets(line, sizeof(line), stdin);
/* line[0]が文字なら終了 */
if(!(line[0] >= '0' && line[0] <= '9'))
return NULL;
sscanf(line, "%d", &size);
(*total_size) += size;
last_ptr = malloc(sizeof(struct list));
if(last_ptr == NULL)
Memory_Error();
Make_List(last_ptr, size);
Input_Data(last_ptr, size);
while(top_ptr->next != NULL)
top_ptr = top_ptr->next;
top_ptr->next = last_ptr;
return last_ptr;
}
Make_List（変更点のみ）
//前略
/* リストを指定の大きさになるまで大きくする */
++index;
if(index < size)
Make_List(current_ptr, size);
else{
index = 1;
return;
}
静的変数はプログラムが終了するまで値を保持するのでMake_Listの処理が
終了するたびに値は1に戻しておく必要があります。
main関数からは次のようにして呼び出すことができます。
main(Add_Listの呼び出し)
int main()
{
//前略
while(Add_List(top_ptr, &total_size) != NULL)
continue;
}
プログラム全体と入出力例は以下に示す通りです。
完成したプログラム
Link_List01.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 500
//#define RECURSION
struct list
{
int data; /* このノードに格納するデータ */
struct list *next; /* 次のノードへのポインタ */
};
int main()
{
void Make_List(struct list*, int); /* リストの作成 */
void Input_Data(struct list*, int); /* 入力 */
#ifndef RECURSION
void Output_Data(struct list*, int); /* 出力 */
#else
void Output_Data(struct list*); /* 出力 */
#endif /* RECURSION */
void* Add_List(struct list*, int*); /* 追加 */
void Free_List(struct list*); /* メモリ開放 */
void Memory_Error(void); /* メモリ不足の通知 */
int size; /* 追加するリストの大きさ */
int total_size; /* リストの全体の大きさ */
char line[MAX]; /* ユーザーの入力行 */
struct list *top_ptr; /* 先頭のノードへのポインタ */
/* 先頭の要素のためのメモリを確保 */
top_ptr = malloc(sizeof(struct list));
if(top_ptr == NULL)
Memory_Error();
/* 初期化 */
top_ptr->data = 0;
top_ptr->next = NULL;
fgets(line, sizeof(line), stdin);
sscanf(line, "%d", &size);
total_size = size;
Make_List(top_ptr, size);
Input_Data(top_ptr, size);
while(Add_List(top_ptr, &total_size) != NULL)
continue;
#ifndef RECURSION
Output_Data(top_ptr, total_size);
#else
Output_Data(top_ptr);
#endif /* RECURSION */
Free_List(top_ptr);
return 0;
}
/*
* Add_List -- リストに要素を追加する
*
* 引数
* top_ptr -- 追加するリストの最上位のノードへのポインタ
* total_size -- リスト全体の大きさ
*/
void* Add_List(struct list *top_ptr, int *total_size)
{
void Make_List(struct list*, int); /* リストの作成 */
void Input_Data(struct list*, int); /* 値の入力 */
void Memory_Error(void); /* メモリ不足の通知 */
int size; /* 追加するリストの大きさ */
char line[MAX]; /* ユーザーの入力行 */
struct list *last_ptr; /* つなげるリストの先頭 */
fgets(line, sizeof(line), stdin);
/* line[0]が文字なら終了 */
if(!(line[0] >= '0' && line[0] <= '9'))
return NULL;
sscanf(line, "%d", &size);
(*total_size) += size;
/* 新しいノードのためのメモリを確保 */
last_ptr = malloc(sizeof(struct list));
if(last_ptr == NULL)
Memory_Error();
/* 初期化 */
last_ptr->data = 0;
last_ptr->next = NULL;
Make_List(last_ptr, size);
Input_Data(last_ptr, size);
while(top_ptr->next != NULL)
top_ptr = top_ptr->next;
top_ptr->next = last_ptr;
return last_ptr;
}
/*
* Make_List -- リンクリストを作成する
*
* 引数
* size -- リストの大きさ
* before_ptr -- 一つ前のノードへのポインタ
*/
void Make_List(struct list *before_ptr, int size)
{
void Make_List(struct list*, int); /* 再帰用 */
void Memory_Error(void); /* メモリ不足の通知 */
static int index = 1; /* ループのインデックス */
struct list *current_ptr; /* 現在のノードへのポインタ */
/* 新しいノードのためのメモリを確保 */
current_ptr = malloc(sizeof(struct list));
if(current_ptr == NULL)
Memory_Error();
/* 各要素を初期化 */
current_ptr->data = 0;
current_ptr->next = NULL;
before_ptr->next = current_ptr;
/* リストを指定の大きさになるまで大きくする */
++index;
if(index < size)
Make_List(current_ptr, size);
else{
index = 1;
return;
}
}
/*
* Input_Data -- リストにデータを入力する
*
* 引数
* current_ptr -- 現在のノードへのポインタ
* size -- リストの大きさ
*/
void Input_Data(struct list *current_ptr, int size)
{
int Adjust_String(char[], int); /* 文字列を調整する */
int index_int; /* 整数用のインデックス */
int index_str; /* 文字列用のインデックス */
int is_negative; /* 負の数かどうか */
int temp; /* 一時的に値を受け取る */
char line[MAX]; /* ユーザーの入力行 */
is_negative = 0;
fgets(line, sizeof(line), stdin);
for(index_int = 0, index_str = 0;
index_int < size;
++index_str)
{
/* 空白文字->読み飛ばす */
if(line[index_str] == ' ')
continue;
/* ハイフン->is_negativeをオンにする */
else if(line[index_str] == '-'){
line[index_str] = ' ';
is_negative = 1;
continue;
}
/* 要素を入力する */
else{
sscanf(line, "%d", &temp);
if(is_negative == 1)
temp *= -1;
current_ptr->data = temp;
current_ptr = current_ptr->next;
++index_int;
index_str
= Adjust_String(line, index_str);
}
}
return;
}
#ifndef RECURSION
/*
* Output_Data -- リストデータを出力する
*
* 引数
* top_ptr -- 先頭のノードへのポインタ
* size -- リストの大きさ
*/
void Output_Data(struct list *top_ptr, int size)
{
int index; /* ループのインデックス */
int temp; /* 値を一時的に受け取る */
for(index = 0; index < size; ++index){
temp = top_ptr->data;
top_ptr = top_ptr->next;
printf("%d ", temp);
}
return;
}
#else
/*
* Output_Data -- 入力されたリストを出力する
*
* 引数
* top_ptr -- 先頭のノードへのポインタ
*/
void Output_Data(struct list *top_ptr)
{
while(top_ptr != NULL){
printf("%d ", top_ptr->data);
top_ptr = top_ptr->next;
}
return;
}
#endif /* RECURSION */
/*
* Free_List -- メモリ領域を解放する
*
* 引数
* current_ptr -- 現在のノードへのポインタ
*/
void Free_List(struct list *current_ptr)
{
struct list
*temp_ptr; /* ポインタを一時的に受け取る */
while(current_ptr != NULL){
temp_ptr = current_ptr->next;
free(current_ptr);
current_ptr = temp_ptr;
}
}
/*
* Memory_Error -- メモリ不足を通知する
*/
void Memory_Error(void)
{
fprintf(stderr, "Out of memory\n");
exit(8);
}
/*
* Adjust_String -- 入力によって文字列を調整する
*
* 引数
* line -- 入力された数値
* index_str -- 操作するべき場所
*
* 戻り値
* 処理後のindex_strのあるべき値 -> index_str
*/
int Adjust_String(char line[], int index_str)
{
int index; /* 配列のインデックス */
char temp[MAX]; /* 一時的に値を受け取る */
sscanf(line, "%s", &temp);
for(index = 0; index < strlen(temp); ++index){
line[index_str + index] = ' ';
}
--index;
return (index_str + index);
}
出力例1
10
1 2 3 4 5 6 7 8 9 10
a
1 2 3 4 5 6 7 8 9 10
出力例2
5
1 1 1 1 1
5
2 2 2 2 2
5
3 3 3 3 3
5
4 4 4 4 4
5
5 5 5 5 5
a
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5
ただし、このプログラムのままでは毎回ノードを必ず二つは作成するので次のような入力例では
出力がおかしくなってしまいます。
(#define RECURSION を有効にしています)
出力例3
1
5
1
6
1
7
1
8
1
9
1
10
a
5 0 6 0 7 0 8 0 9 0 10 0
なので、Make_List関数に一文書き加えておきます。
Make_List
/*
* Make_List -- リンクリストを作成する
*
* 引数
* size -- リストの大きさ
* before_ptr -- 一つ前の要素へのポインタ
*/
void Make_List(struct list *before_ptr, int size)
{
void Make_List(struct list*, int); /* 再帰用 */
void Memory_Error(void); /* メモリ不足の通知 */
static int index = 1; /* ループのインデックス */
struct list *current_ptr; /* 現在の要素へのポインタ */
/* sizeが1であれば新しくノードは作成しない */
if(size == 1)
return;
//後略
}
感想
あらかじめ仕事をいくつかの関数に分け、
main関数は基本それらを呼び出すだけで処理が進行する。
という構造のプログラムは競技プログラミングの問題を解いたりして遊んでいたので、
久しく作っていなかったのですが、試行錯誤を重ねて上手く動くものが作れました。
mallocで確保したメモリはヒープにあるのでポインタ変数を関数内で宣言しても
全く問題ないということは分かっていても感覚的に少し不思議な感じがします。
(freeで開放しなきゃいけないから当たり前か......)
これはふと思っただけなんですが
連続でスペース刻みで値を入力する場合'\0'にたどり着いたか云々で
要素数を指定しなくてもリンクリストを使えば任意の要素数で配列みたいなのを作れるかも
しれないですね。（既にほかの人がやっているかもしれないけど）
リンクリストに全く関係ないことですがAdd_Listの戻り値に総称ポインタを使った理由は
特になく、完全に興味本位です。
また、最後の要素を一つずつ入力した場合のバグ修正に関しては完全に要らないんですが、
プリプロセッサを使ってみたかっただけです。#ifndefを使ってみたかっただけです。
便利だし楽しい。