配列を使ったリスト

「C言語10課 データ構造とアルゴリズム編」

リストの機能

機能名	関数名	やること
初期化	init	リストを空にする
先頭を求める	top	リストの先頭位置を返す
次の要素を求める	next	次の要素位置を返す
要素数を求める	count	リストの要素数を求める
要素の値を求める	item	リストの要素を返す
追加	add	リストの末尾に要素を追加する
挿入	insert	指定した位置に要素を挿入する
削除	delete	リストから要素を削除する

/*
**	配列を使ったリスト
*/
#include <stdio.h>

#define	MAXSIZE	30		/* 配列のサイズ */

/* プロトタイプ */
void  init(void);
int   top(void);
int   next(int pos);
int   count(void);
int   item(int pos);
void  add(int value);
void  insert(int pos, int value);
void  delete(int pos);
void  showList(int list[]);

int   list[MAXSIZE];
int   tail;				/* リストの末尾 */

int main(void)
{
	int i;	/* カウンタ */

	init();

	puts("要素を追加!");
	for(i = 0 ; i < 5 ; i++){
		add(i + 1);
	}
	showList(list);
		
	puts("初期化!");
	init();
	showList(list);

	for(i = 1 ; i <= 3 ; i++){
	puts("要素を追加!");
	add(i);
	}
	showList(list);

	puts("先頭の要素を削除!");
	delete(top());
	showList(list);

	puts("要素(99)を先頭に挿入!");
	insert(top(), 99);
	showList(list);

	printf("listの要素数は%dです。\n", count());

	return 0;
}

/*
**	リストを初期化する
*/
void init(void)
{
	tail = 0;
}

/*
**	リストの先頭位置を返す
*/
int top(void)
{
	return 0;
}

/*
**	指定された位置の次の要素の位置を返す
*/
int next(int pos)
{
	if(pos < tail - 1){
		return pos + 1;
	}else{
		return -1;
	}
}

/*
**	要素数を返す
*/
int count(void)
{
	return tail;
}

/*
**	指定された位置にある要素を返す
*/
int item(int pos)
{
	if((0 <= pos) && (pos < tail)){
		return list[pos];
	}else{
		return 0;
	}
}

/*
**	要素を追加する
*/
void add(int value)
{
	if(tail < MAXSIZE){
		list[tail] = value;
		tail++;
	}
}

/*
**	要素を指定した位置に挿入する
*/
void insert(int pos, int value)
{
	if((0 <= pos) && (pos < tail) && (tail < MAXSIZE)){
		int i;	/* カウンタ */
				
		for(i = tail ; i > pos ; i--){
			list[i] = list[i - 1];
		}

		list[pos] = value;
		tail++;
	}
}

/*
**	要素を削除する
*/
void delete(int pos)
{
	if((0 <= pos) && (pos < tail)){
		int i;	/* カウンタ */
		for(i = pos ; i < tail ; i++){
				list[i] = list[i + 1];
		}
		tail--;
	}
}

/*
**	リストの中身を確認する
*/
void showList(int list[]){
	int i;
	printf("list={");
	for(i = top() ; i != -1 ; i = next(i)){
		if(i < tail - 1)
			printf("%d,", item(i));
		else
			printf("%d", item(i));
	}
	printf("}\n");
}

実行結果

要素を追加!
list={1,2,3,4,5}
初期化!
list={0}
要素を追加!
要素を追加!
要素を追加!
list={1,2,3}
先頭の要素を削除!
list={2,3}
要素(99)を先頭に挿入!
list={99,2,3}
listの要素数は3です。