読者です 読者をやめる 読者になる 読者になる

配列を使ったリスト

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です。