Ｃ言語でリスト構造を自作してみました。
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; //先頭ノードへのポインタ
};
/*
* リストのコンストラクタ
*/
List newList(void){
//メモリ確保
List list=(List)malloc(sizeof(struct list));
if(!list){//メモリ確保失敗
abort();
}
//リストの先頭ノードをNULLにセットする
list->front=NULL;
return list;
}
/*
* リストの末尾に要素を追加
* 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;
}
}
/*
* リストの要素に処理を適用
* list : リスト
* func : 処理（関数）
*/
void foreach(List list, void (*func)(void*)){
for(Node* node=list->front;node;node=node->next){//リストの先頭からノードを辿っていく
//ノード内のデータに処理を適用
func(node->value);
}
}
リストに要素を追加する際にmallocを用いています。
プログラムの最後、または呼び出した関数から出る際は確実に解放しましょう。
また、リストの生成にもmallocを用いています。リスト自身も忘れずに解放しましょう。
/*
* リストの解放
* 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);
}
}
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：分割を求める
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