Ｃでリスト構造を自作してみた

Ｃ言語でリスト構造を自作してみました。
- ###### [今回やりたいこと](https://github.com/anonymously115/repository115/blob/main/list.h)
```list.h
#ifndef LIST_H_
#define LIST_H_

/* リスト構造体 */
typedef struct list* List;

/* コンストラクタ */
List newList(void);

/* リストに要素を追加 */
void add(List, void*);

/* リストの要素に処理を適用 */
void foreach(const List, void (*)(void*));

/* リスト解放 */
void clear(List, int);

#endif /* LIST_H_ */
```
- - -
- ###### リスト構造体定義
```list.c
#include <stdlib.h>
#include "list.h"

/* ノード（単方向リスト） */
typedef struct node{
	void* value; //データ
	struct node* next; //次のデータの格納位置を示すポインタ
}Node;

/* リスト構造 */
struct list{
	Node* front; //先頭ノードへのポインタ
};
```
- - -
- ###### コンストラクタ
```c
/*
 * リストのコンストラクタ
 */
List newList(void){
	//メモリ確保
	List list=(List)malloc(sizeof(struct list));
	if(!list){//メモリ確保失敗
		abort();
	}

	//リストの先頭ノードをNULLにセットする
	list->front=NULL;
	return list;
}
```
- - -
- ###### リストに要素を追加
```c
/*
 * リストの末尾に要素を追加
 * list : リスト
 * value : 追加するデータ
 */
void add(List list, void* value){
	//メモリ確保
	Node* node=(Node*)malloc(sizeof(Node));
	if(!node){//メモリ確保失敗
		abort();
	}

	//ノードにデータをセット
	node->value=value;

	//新しいノードの次はNULL
	node->next=NULL;

	//末尾ノードの次に新しいノードをセット
	if(!list->front){//空リストの場合
		//先頭要素に追加
		list->front=node;
	}else{
		//現在の末尾ノード（「次のノードがNULL」となっているノード）を探す
		Node* n=list->front;
		while(n->next){
			n=n->next;
		}

		//末尾ノードの次が新しいノード
		n->next=node;
	}
}
```
- - -
- ###### リストの要素に処理を適用
```c
/*
 * リストの要素に処理を適用
 * list : リスト
 * func : 処理（関数）
 */
void foreach(List list, void (*func)(void*)){
	for(Node* node=list->front;node;node=node->next){//リストの先頭からノードを辿っていく
		//ノード内のデータに処理を適用
		func(node->value);
	}
}
```
- - -
- ###### リストの解放
:::note warn
リストに要素を追加する際に`malloc`を用いています。
プログラムの最後、または呼び出した関数から出る際は確実に解放しましょう。
また、リストの生成にも`malloc`を用いています。リスト自身も忘れずに解放しましょう。
:::
```c
/*
 * リストの解放
 * list : リスト
 * flag : malloc等でメモリ確保した要素を追加した場合は非零
 */
void clear(List list, int flag){
	//リストの先頭から順にノードを解放していく
	while(list->front){
		Node* node=list->front;

		//malloc等で確保した要素を追加した場合、そのメモリを解放
		if(flag){
			free(node->value);
		}

		//リストの先頭ノードを繋ぎ替える
		list->front=node->next;

		//ノード解放
		free(node);
	}
}
```
- - -
- ###### サンプルプログラム1 ： 順列を求める
```permutation.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

/* 番兵 */
const int SENTINEL=0x80000000;

/*
 * 順列を求める
 * list : 得られた順列を格納するリスト
 * n : 順列のサイズ
 * A : 元の配列
 * k : 処理中の順列のサイズ
 * B : 順列を格納していく配列（処理中の順列）
 */
void permutation(List list, int n, int A[n], int k, int B[n]){
	if(k==n){//順列が得られたらリストに格納
		//得られた順列を格納するメモリを確保（番兵付き）
    	int* array=(int*)malloc(sizeof(int)*(n+1));

		//順列を格納
		memcpy(array,B,sizeof(int)*n);

		//番兵を格納
		array[n]=SENTINEL;

		//リストに順列を格納
		add(list,(void*)array);
	}else{
		for(int i=0;i<n;i++){
			if(A[i]!=SENTINEL){//処理中の順列に格納されていなければ（番兵でなければ）
				//処理中の順列に要素を格納
				B[k]=A[i];

				//元の配列をダミー値（番兵）に置き換える
				A[i]=SENTINEL;

				//再起処理
				permutation(list,n,A,k+1,B);

				//配列を元に戻す
				A[i]=B[k];
			}
		}
	}
}

/*
 * 順列を出力する
 * _ : 順列を表す配列の先頭へのポインタ
 */
void print(void* _){
	//整数へのポインタ（整数配列）にキャスト
	int* array=(int*)_;

	for(int i=0;array[i]!=SENTINEL;i++){//番兵まで繰り返し
		//空白区切り（先頭を除く）
		if(i)putchar(' ');

		//要素を出力
		printf("%d", array[i]);
	}

	//順列を出力したら改行区切り
	putchar('\n');
}

int main(int argc, char* argv[]){
	//元の配列
	int A[]={1,2,3,4};

	//配列のサイズ
	int n=(int)(sizeof(A)/sizeof(A[0]));

	//リストを生成
	List list=newList();

	//生成した順列を格納する配列
	int B[n];

	//順列を求める
	permutation(list,n,A,0,B);

	//順列を出力する
	foreach(list,print);

	//リストの要素を解放（要素もmallocでメモリ確保しているのでフラグを立てる）
	clear(list,1);

	//リスト自身を解放
	free(list);

	//プログラム終了
	return 0;
}

```
実行結果
```
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
```
- - -
- ###### サンプルプログラム2：[分割](https://ja.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E6%95%B0%E3%81%AE%E5%88%86%E5%89%B2 "自然数の分割")を求める
```partition.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

#define MIN(a,b) ((a)<(b)?(a):(b))

/*
 * m以下の正整数で構成されたnの分割を求める
 * list : リスト
 * n : nの分割を求める
 * m : 分割の要素の最大値
 * k : 作業配列に格納された要素数
 * B : 作業配列
 */
void partition(List list, int n, int m, int k, int B[n]){
	if(!n){//nが0になった
		//分割を格納するメモリ領域を確保する（要素数k＋番兵）
		int* array=(int*)malloc(sizeof(int)*(k+1));

		//分割を格納する
		memcpy(array,B,sizeof(int)*k);

		//番兵として0を格納する（分割の後は0が無限に続くと考えてよい）
		array[k]=0;

		//リストに分割を格納する
		add(list,(void*)array);
	}else{
		for(int i=MIN(n,m);i>0;i--){//降順に処理
			//作業領域に要素を格納する
			B[k]=i;

			//再起的に処理
			partition(list,n-i,i,k+1,B);
		}
	}
}

/*
 * 分割を出力する
 * _ : 分割を表す配列の先頭へのポインタ
 */
void print(void* _){
	//整数へのポインタ（整数配列）にキャスト
	int* array=(int*)_;

	for(int i=0;array[i]!=0;i++){//番兵まで繰り返し
		//空白区切り（先頭を除く）
		if(i)putchar(' ');

		//要素を出力
		printf("%d", array[i]);
	}

	//順列を出力したら改行区切り
	putchar('\n');
}

int main(int argc, char* argv[]){
	int n=10;

	//リストを生成する
	List list=newList();

	//作業配列を確保
	int B[n];

	//分割を取得する
	partition(list,n,n,0,B);

	//分割を出力する
	foreach(list,print);

	//リストの要素を解放（要素もmallocでメモリ確保しているのでフラグを立てる）
	clear(list,1);

	//リスト自身を解放
	free(list);

	//プログラム終了
	return 0;
}
```
実行結果
```
10
9 1
8 2
8 1 1
7 3
7 2 1
7 1 1 1
6 4
6 3 1
6 2 2
6 2 1 1
6 1 1 1 1
5 5
5 4 1
5 3 2
5 3 1 1
5 2 2 1
5 2 1 1 1
5 1 1 1 1 1
4 4 2
4 4 1 1
4 3 3
4 3 2 1
4 3 1 1 1
4 2 2 2
4 2 2 1 1
4 2 1 1 1 1
4 1 1 1 1 1 1
3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
```