>> C言語入門トップに戻る

線形リスト

今回からはリスト構造について説明していきます。
リスト構造とは、ある要素を動的に確保しながら、それらを各要素のポインタ同士で結びつけて関連を持たせ
一つのリストのようにしてデータを管理することです。
今日は単純な線形リストについて説明します。
線形リストとは次の要素のポインタだけを保持しており、
先頭から末尾の要素へ一方方向にだけ連結した構造になっています。
つまり先頭から次の要素へはアクセスできますが、後ろの要素から前の要素へはアクセスできないことになります。
まずはコードを見てください。

#include <stdio.h>
#include <stdlib.h>

//リスト用構造体定義
struct LIST{
	LIST *next;
	int value;
};

//リストの先頭を定義
LIST list;

//関数のプロトタイプ宣言
void Add(int);
void Del(int);
void Display();
void Release();

int main(void)
{
	//次の要素はまだ空なのでNULL入れとく
	list.next=NULL;
	char answer='5';
	int figure;

	puts("何をしますか?\n0.終了、1.追加、2.削除、3.表示\n");

	while(answer!='0'){

		scanf("%c",&answer);

		//入力バッファに残る\nをクリアする
		fflush(stdin);

		switch(answer){

			case '1':
				puts("追加する値を入力して下さい");
				scanf("%d",&figure);
				Add(figure);
				break;
			case '2':
				puts("削除する値を入力して下さい");
				scanf("%d",&figure);
				Del(figure);
				break;
			case '3':
				Display();
				break;
			default:
				puts("正しい値を入力して下さい");
				break;
		}
		//入力バッファに残る\nをクリアする
		fflush(stdin);
		puts("何をしますか?\n0.終了、1.追加、2.削除、3.表示\n");
	}

	//解放
	Release();

	return 0;

}

void Add(int temp){

	//新規確保用
	LIST *p;
	//現在の末尾のリストのポインタ;
	LIST *next;
	//末尾直前のポインタ
	LIST *prev;
	
	//新しいリストの領域を確保
	p=(LIST*)malloc(sizeof(LIST));

	//値を代入
	p->value=temp;
	//次の要素は末尾と分かるようにNULLを入れとく
	p->next=NULL;

	//最初は先頭が末尾直前のポインタになる
	prev=&list;

	//末尾のポインタまで移動
	for(next=list.next;next!=NULL;next=next->next){
			prev=next;
	}

	//リストを連結する。
	prev->next=p;

	puts("追加しました");
	
}

void Del(int temp){

	//削除要素の直前の要素のポインタ
	LIST* prev;

	//最初は先頭要素の次のリストからチェックしてるので、
	//削除要素の直前の要素は先頭要素になる。
	prev=&list;

	//リストを末尾(NULLになる)までループ
	for(LIST *p=list.next;p!=NULL;p=p->next){

		//その値があれば
		if(p->value==temp){

			//削除要素の前のリストにつなげる
			//その前に次の要素が末尾ならつなげる必要ないのでチェック
			if(p->next!=NULL){

				//削除直前の要素につなげる
				prev->next=p->next;

				//削除対象要素の解放
				free(p);

				return;
			}
			//削除要素が末尾の要素だった場合の処理
			//末尾要素にNULLを入れる。
			prev->next=NULL;

			//削除対象要素の解放
			free(p);

			puts("削除しました");

			return;			
		}

		prev=p;

	}
	puts("該当の値は見つかりませんでした");

}

void Display(){

	if(list.next==NULL){
		puts("まだ何もありません");
		return;
	}

	//NULLになるまで全部表示
	for(LIST *p=list.next;p!=NULL;p=p->next){

		printf("%d,",p->value);
	}

	puts("");

}

void Release(){

	//次のリストのポインタ
	LIST *next;
	//削除対象のポインタ
	LIST *del;

	next=list.next;

	//NULLになるまでループ
	while(next){
		//削除対象のポインタを保存	
		del=next;
		//次のリストのポインタを取得しとく
		next=next->next;

		free(del);
	}
}

これを実行すると、リストに値を追加・削除・表示・終了するか聞いてくるので、
該当の番号を選んで、値を入力するとその動作が行われます。

コードの解説を行います。
まずリストそれぞれを構成する要素の構造体を定義しています。

struct LIST{
LIST *next;
int value;
};

ポイントは、LIST型のポインタをメンバとして持っていることです。
このポインタに次の要素のポインタを代入します。
valueはその要素がもつ値をあら和します。
このポインタに次のLIST型のポインタを代入するということは、
そのポインタの先のLIST構造体にもまたLIST型のポインタをメンバとして持っているということです。
そのポインタにまた新しい要素をつなげることで、リスト構造が出来上がっていくというわけです。

main関数内のscanfなどの細かい処理の説明は省きます。
fflush関数というのが有りますが、これは入力バッファをクリアするものです。
scanf等でデータを受け取った後は、改行(\n)が入力バッファに残ってて、
次にscanfを使ったときの動作に影響するので、
一旦バッファをクリアしているわけです。

まずは、add関数の説明をします。
引数には追加する値を渡して実行します。
malloc関数でLIST型構造体を動的確保しています。
で、そのメンバに値と、末尾の要素であることを示す為に次のポインタを示すnext変数にNULLを代入してます。
こうすることで、リストを最初からチェックしていった時に、このnext変数を調べることにより、
それが末尾の要素だと判断できます。
次のfor分ではnext変数がNULLである要素まで移動してます。
あとはその末尾の要素に追加しているだけです。

次にdel関数の説明をします。
引数には削除する値を渡して実行します。
これもforループ文でnext変数がNULLである要素までループします。
そのループ処理の中でvalue変数の値と一致するかを調べて、一致したらその要素を削除(解放)してます。
ポイントは、ループの最後で直前の要素のポインタを変数で保存してるところです。
目的の要素を削除すると、その部分だけぽっかり穴があいてしまうことになるので、
さらにその次の要素と削除要素の前の要素と連結しなければなりません。
そのために、目的要素の前の要素のポインタを保存してるのです。
if文の中でその連結を行っていますね。
もし削除対象の要素が最後だった場合は、NULLを入れています。
これも忘れないでくださいね。

次にdisplay関数です。
これは単純で、next変数がNULLになるまで、value変数の値を先頭から順番に表示していってるだけです。
これは大丈夫ですよね?

最後にrelease関数です。
確保したメモリは解放する必要があります。
これも原理は同じで、next変数がNULLになるまで、つまり末尾の要素までループを続け、
一つずつメモリを解放しています。

以上が線形リストの説明です。
リストはプログラミングにおいて非常に便利なので頑張って理解できるようにしましょう。

次回は循環リストについて説明します。


>> 【循環リスト】に進む
>> C言語入門トップに戻る
●更新履歴
2016/08/16 Java入門ページにページを幾つか追加
2016/04/08 Java入門ページ作成
2016/03/09 メニューレイアウト変更。ブラウザキャッシュのクリアをお願い致します。
2016/03/09 PDOトランザクション、自動コミットモードをオフ追加
2016/03/09 PDO 例外処理 try catch追加
2016/03/09 PDO update文実行追加
2016/03/09 PDO delete文実行追加
2016/03/09 PDO insert文実行追加
2016/03/09 PDO selectでデータを取得、fetchAll、queryメソッド追加
2016/03/09 PDO bindValueとbindParamの違い追加
2016/03/09 PDO prepare プリペアドステートメントの使い方追加
2016/03/04 ソースコードをクリップボードにコピーする機能を追加
2016/03/04 C言語、C++のページのソースコードを一部修正
2014/01/31 C言語関数一覧ページに11ページほど追加
2014/01/31 C言語関数一覧ページに30ページほど追加
2014/01/30 C言語関数一覧ページ作成中
2013/07/01 レイアウト変更に伴いブラウザキャッシュのクリアをお願いします。
2013/07/01 MySQL入門ページ作成
2013/07/01 PHP入門ページにSQLite学習項目追加
2013/06/25 ドメイン変更、レイアウトを一部変更
2013/03/14 レイアウトを一部変更
2012/08/13 C言語よくある課題・宿題ページ開設!
2012/08/13 シューティングゲーム作成第33章追加!
2012/08/11 ドメイン変更&サーバ移設完了
2012/04/21 シューティングゲームプログラミング第2,3章の内容を修正
2012/04/19 シューティングゲームプログラミング第2章の内容を修正
2012/04/03 Googleカスタム検索を設置!
2012/04/03 シューティングゲームプログラミング第32章追加!
2012/04/03 シューティングゲームプログラミング第31章追加!
2012/03/31 サイトをリニューアルしました!
2012/03/25 シューティングゲームプログラミング第30章追加!
2012/03/19 シューティングゲームプログラミング第29章追加!
2012/03/16 シューティングゲームプログラミング第28章追加!
2012/02/27 シューティングゲームプログラミング第27章追加!
2012/02/03 シューティングゲームプログラミング第26章追加!
2012/01/31 シューティングゲームプログラミング第25章追加!
2012/01/20 シューティングゲームプログラミング第23,24章追加!
2012/01/11 シューティングゲームプログラミング第22章追加!
2012/01/05 トップページ、ゲームプログラミング関連のトップページのデザインを変更
2012/01/04 シューティングゲームプログラミング第21章追加!
2012/01/01 シューティングゲームプログラミング第20章追加!
2011/12/25 シューティングゲームプログラミング第19章追加!
2011/12/22 シューティングゲームプログラミング第18章追加!
2011/12/18 シューティングゲームプログラミング第17章追加!
2011/12/17 シューティングゲームプログラミングページOPEN!
2011/11/21 ゲームプログラミングページOPEN!
2011/11/21 サイトデザインを大幅に変更
2011/11/17 TOPページのデザインを変更。相互リンクページに、複数サイト追加。
2011/11/06 WINAPI学習ページ(33~36章)追加
2011/11/05 WINAPI学習ページ(20~32章)追加
2011/10/27 WINAPI学習ページ(14~19章)追加
2011/10/21 WINAPI学習ページ(13章)追加
2011/10/21 サイトマップ、連絡ページ追加
2011/10/17 WINAPI学習ページ(6~11章)追加
2011/10/16 WINAPI学習ページ(1~5章)追加
2011/10/13 全体のレイアウト変更
2011/10/07 PHP学習ページ(8~11章)追加
2011/10/06 PHP学習ページ(1~7章)作成
2011/10/06 JavaScriptリファレンスページ作成
2011/10/05 C言語学習ページ発展編(10~14章)追加
2011/10/04 C言語学習ページ発展編(1~9章)追加。
2011/10/03 HTML/CSSリファレンスのページ追加。(個々の詳細ページは作成中)
2011/09/30 HTML学習ページ(8章)追加
2011/09/29 JavaScript学習ページ(12~17章)追加
2011/09/28 JavaScript学習ページ(1~11章)追加
2011/09/27 HTML学習ページ(4~7章)追加
2011/09/26 C言語学習ページ(27章)追加、C++学習ページ(17章)、HTML学習ページ(1~3章)追加
2011/09/25 C言語学習ページ(23~26章)を追加
2011/09/24 C++学習ページ(9~16章)追加
2011/09/23 C++学習ページ(3~8章)追加
2011/09/22 C言語の学習ページ(22章)とC++学習ページ(1~2章)追加
2011/09/21 C言語の学習ページ(15章~21章)を追加
2011/09/20 C言語の学習ページ(10章~14章)を追加
2011/09/19 サイト作成(随時更新予定)