Ⅱ．リスト構造

　　配列においては，あらかじめ設定した数のデータしか記憶できません．ここで述べるリスト構造においては，データをポインタによって繋げていくことにより，動的にその数を増減させることが可能です．一般に，配列とリスト構造との間には以下に示すような違いがあります．

　　以下，連結リスト（単方向リスト，双方向リスト），木構造，二分木（二分探索木）について，順に説明していきます．

  1. 単方向リスト

    　　単方向リストは，以下の図に示すように，次に来るデータだけをポインタで繋げています．プログラム例では，指定された位置，その位置の次，及び，その位置の前にあるデータの参照，与えられたデータのリストへの追加（昇順にソート，同じデータを許す），指定されたデータの削除を行っています．C++ 標準ライブラリ内には，単方向リストを扱うためのクラスとして，forward_list クラスが存在します． 

    001	/****************************/
002	/* 単方向リスト             */
003	/*      coded by Y.Suganuma */
004	/****************************/
005	#include <stdio.h>
006	#include <time.h>
007	#include "MT.h"
008	
009	/********************/
010	/* クラスListの定義 */
011	/********************/
012	class List
013	{
014			int data;
015			List *next;
016		public :
017				// コンストラクタ
018			List () { next = NULL; }
019	
020			List (int x)
021			{
022				next = NULL;
023				data = x;
024			}
025	
026			void add(List *);   // データの追加
027			void del(int);   // データの削除
028			void get(int, int[]);   // データの参照
029			void output();   // 出力
030	};
031	
032	List root;
033	
034	/********************/
035	/* データの追加     */
036	/*      dt : データ */
037	/********************/
038	void List::add(List *dt)
039	{
040		List *lt1, *lt2 = &root;
041		int sw = 0;
042	
043		while (sw == 0) {
044				// 最後に追加
045			if (lt2->next == NULL) {
046				lt2->next = dt;
047				sw        = 1;
048			}
049				// 比較し，途中に追加
050			else {
051				lt1 = lt2;
052				lt2 = lt2->next;
053				if (dt->data <= lt2->data) {   // 比較
054					dt->next  = lt2;
055					lt1->next = dt;
056					sw        = 1;
057				}
058			}
059		}
060	}
061	
062	/***********************/
063	/* データの削除        */
064	/*      x : 削除データ */
065	/***********************/
066	void List::del(int x)
067	{
068		List *lt1, *lt2 = &root;
069		int sw = 0;
070	
071		while (sw == 0) {
072				// データが存在しない場合
073			if (lt2->next == NULL) {
074				printf("   ***error*** データがありません！(del)\n");
075				sw = 1;
076			}
077				// 比較し，削除
078			else {
079				lt1 = lt2;
080				lt2 = lt2->next;
081				if (x == lt2->data) {   // 比較
082					lt1->next = lt2->next;   // 削除
083					sw        = 1;
084				}
085			}
086		}
087	}
088	
089	/*************************/
090	/* データの参照          */
091	/*      n : データの位置 */
092	/*************************/
093	void List::get(int n, int x[])
094	{
095		List *lt = &root;
096		x[0] = -1;
097		x[1] = -1;
098				// n 番目のデータ参照
099		if (lt->next != NULL) {
100			int k = 1;
101			while (lt->next != NULL) {
102				lt = lt->next;
103				if (k == n) {
104					x[0] = lt->data;
105					if (lt->next != NULL) {
106						lt   = lt->next;
107						x[1] = lt->data;
108					}
109					break;
110				}
111				else
112					k++;
113			}
114		}
115		if (x[0] < 0)
116			printf("***error*** データが存在しません！(get)\n");
117	}
118	
119	/**********************/
120	/* リストデータの出力 */
121	/**********************/
122	void List::output()
123	{
124		if (next == NULL)
125			printf("   データがありません(output)\n");
126		else {
127			List *lt = next;
128			printf("   data");
129			while (lt != NULL) {
130				printf(" %d", lt->data);
131				lt = lt->next;
132			}
133			printf("\n");
134		}
135	}
136	
137	/****************/
138	/* main program */
139	/****************/
140	int main ()
141	{
142				// 初期設定;
143		init_genrand((unsigned)time(NULL));
144		root.output();
145				// 追加1
146		int k = (int)(1000 * genrand_real3());
147		printf("%d を追加\n", k);
148		List *dt = new List(k);
149		root.add(dt);
150		root.output();
151				// 追加2
152		k = (int)(1000 * genrand_real3());
153		printf("%d を追加\n", k);
154		dt = new List(k);
155		root.add(dt);
156		root.output();
157				// 追加3
158		k = (int)(1000 * genrand_real3());
159		printf("%d を追加\n", k);
160		dt = new List(k);
161		root.add(dt);
162		root.output();
163				// 削除1
164		printf("%d を削除\n", k);
165		root.del(k);
166		root.output();
167				// 追加4
168		k = (int)(1000 * genrand_real3());
169		printf("%d を追加\n", k);
170		dt = new List(k);
171		root.add(dt);
172		root.output();
173				// 参照
174		int *x = new int [2];
175		for (int i1 = 0; i1 < 5; i1++) {
176			root.get(i1, x);
177			if (x[0] > 0) {
178				printf("%d 番目のデータは %d\n", i1, x[0]);
179				if (x[1] > 0)
180					printf("   %d 番目(後ろ)のデータは %d\n", i1+1, x[1]);
181				else
182					printf("   (後ろ)***error*** データが存在しません！(get)\n");
183				if (i1 == 1)
184					printf("   (前)");
185				root.get(i1-1, x);
186				if (x[0] > 0)
187					printf("   %d 番目(前)のデータは %d\n", i1-1, x[0]);
188			}
189		}
190		return 0;
191	}
    012 行目～ 030 行目

    　　クラス List の定義です．データ（ data ）と次のデータへのポインタ（ next ）を private なメンバー変数として持っています．018 行目は引数がない場合に対するコンストラクタ，また，020 行目～ 024 行目は，データを引数とした場合に対するコンストラクタです．クラス List は，4 つのメンバー関数（ add，del，get，output ）を持ちますが，その具体的な定義は，クラス定義の外側で行っています．

    032 行目

    　　リストのルートを表す変数 root を，グローバル変数として定義しています．この定義により，root のメンバー変数 next は，NULL に初期設定されます．

    038 行目～ 060 行目

    　　データをリストに追加するためのメンバー変数 add の定義です．root からリストをたどり，引数として与えられたデータが次のデータ以下の場合（ 053 行目），次のデータの前に，引数として渡された List クラスのオブジェクト dt を次のデータの前に挿入します（ 054 行目～ 056 行目）．そのようなデータが存在しない場合は，リストの最後に追加します（ 045 行目～ 048 行目）．

    066 行目～ 087 行目

    　　指定されたデータを削除するためのメンバー関数 del の定義です．データが見つかった場合は，そのデータを削除し（ 081 行目～ 084 行目），見つからなかった場合は，エラーメッセージを出力します（ 073 行目～ 076 行目）．

    093 行目～ 117 行目

    　　指定された位置にあるデータ及びその次にあるデータを返すための関数 get の定義です．データが存在した場合は，指定された位置にあるデータを x[0]，その次のデータを x[1] に入れて返します（ 103 行目～ 110 行目）．

    122 行目～ 135 行目

    　　リスト内の全てのデータを出力するための関数 output の定義です．

    （出力）　このプログラムによって，以下に示すような結果が得られます． 
       データがありません(output)
441 を追加
   data 441
176 を追加
   data 176 441
949 を追加
   data 176 441 949
949 を削除
   data 176 441
636 を追加
   data 176 441 636
***error*** データが存在しません！(get)
1 番目のデータは 176
   2 番目(後ろ)のデータは 441
   (前)***error*** データが存在しません！(get)
2 番目のデータは 441
   3 番目(後ろ)のデータは 636
   1 番目(前)のデータは 176
3 番目のデータは 636
   (後ろ)***error*** データが存在しません！(get)
   2 番目(前)のデータは 441
***error*** データが存在しません！(get)

  2. 双方向リスト

    　　双方向リストは，以下の図に示すように，次，及び，その前に来るデータをポインタで繋げています．プログラム例では，指定された位置，その位置の次，及び，その位置の前にあるデータの参照，与えられたデータのリストへの追加（昇順にソート，同じデータを許す），指定されたデータの削除を行っています．プログラムは，単方向リストの場合とほとんど同じですが，前のデータに対するポインタ prev をメンバー変数として所有しているため，前方からだけでなく，後方から探索することも可能です．C++ 標準ライブラリ内には，双方向リストを扱うためのクラスとして，list クラスが存在します． 

    001	/****************************/
002	/* 双方向リスト             */
003	/*      coded by Y.Suganuma */
004	/****************************/
005	#include <stdio.h>
006	#include <time.h>
007	#include "MT.h"
008	
009	/********************/
010	/* クラスListの定義 */
011	/********************/
012	class List
013	{
014			int data;
015			List *next;
016			List *prev;
017		public :
018				// コンストラクタ
019			List () {
020				next = NULL;
021				prev = NULL;
022			}
023	
024			List (int x)
025			{
026				next = NULL;
027				prev = NULL;
028				data = x;
029			}
030	
031			void add(List *);   // データの追加
032			void del(int);   // データの削除
033			void get(int, int[]);   // データの参照
034			void output();   // 出力
035	};
036	
037	List root;
038	
039	/********************/
040	/* データの追加     */
041	/*      dt : データ */
042	/********************/
043	void List::add(List *dt)
044	{
045		List *lt1 = NULL, *lt2 = &root;
046		int sw = 0;
047	
048		while (sw == 0) {
049				// 最後に追加
050			if (lt2->next == NULL) {
051				lt2->next = dt;
052				sw        = 1;
053				if (lt2 != &root)
054					dt->prev = lt2;
055			}
056				// 比較し，途中に追加
057			else {
058				lt1 = lt2;
059				lt2 = lt2->next;
060				if (dt->data <= lt2->data) {   // 比較
061					dt->next  = lt2;
062					lt1->next = dt;
063					lt2->prev = dt;
064					sw        = 1;
065					if (lt1 != &root)
066						dt->prev = lt1;
067				}
068			}
069		}
070	}
071	
072	/***********************/
073	/* データの削除        */
074	/*      x : 削除データ */
075	/***********************/
076	void List::del(int x)
077	{
078		List *lt1, *lt2 = &root;
079		int sw = 0;
080	
081		while (sw == 0) {
082				// データが存在しない場合
083			if (lt2->next == NULL) {
084				printf("   ***error*** データがありません！(del)\n");
085				sw = 1;
086			}
087				// 比較し，削除
088			else {
089				lt1 = lt2;
090				lt2 = lt2->next;
091				if (x == lt2->data) {   // 比較
092					lt1->next = lt2->next;   // 削除
093					lt2->prev = lt1;
094					sw        = 1;
095				}
096			}
097		}
098	}
099	
100	/*************************/
101	/* データの参照          */
102	/*      n : データの位置 */
103	/*************************/
104	void List::get(int n, int x[])
105	{
106		List *lt = &root;
107		x[0] = -1;
108		x[1] = -1;
109		x[2] = -1;
110				// n 番目のデータ参照
111		if (lt->next != NULL) {
112			int k = 1;
113			while (lt->next != NULL) {
114				lt = lt->next;
115				if (k == n) {
116					x[0] = lt->data;
117					if (lt->next != NULL) {
118						List *lt1 = lt->next;
119						x[1]      = lt1->data;
120					}
121					if (lt->prev != NULL) {
122						List *lt1 = lt->prev;
123						x[2]      = lt1->data;
124					}
125					break;
126				}
127				else
128					k++;
129			}
130		}
131		if (x[0] < 0)
132			printf("***error*** データが存在しません！(get)\n");
133	}
134	
135	/**********************/
136	/* リストデータの出力 */
137	/**********************/
138	void List::output()
139	{
140		if (next == NULL)
141			printf("   データがありません(output)\n");
142		else {
143			List *lt = next, *wk = NULL;
144			printf("   data(順)");
145			while (lt != NULL) {
146				printf(" %d", lt->data);
147				wk = lt;
148				lt = lt->next;
149			}
150			printf("\n");
151	
152			lt = wk;
153			printf("   data(逆)");
154			while (lt != NULL) {
155				printf(" %d", lt->data);
156				lt = lt->prev;
157			}
158			printf("\n");
159		}
160	}
161	
162	/****************/
163	/* main program */
164	/****************/
165	int main ()
166	{
167				// 初期設定;
168		init_genrand((unsigned)time(NULL));
169		root.output();
170				// 追加1
171		int k = (int)(1000 * genrand_real3());
172		printf("%d を追加\n", k);
173		List *dt = new List(k);
174		root.add(dt);
175		root.output();
176				// 追加2
177		k = (int)(1000 * genrand_real3());
178		printf("%d を追加\n", k);
179		dt = new List(k);
180		root.add(dt);
181		root.output();
182				// 追加3
183		k = (int)(1000 * genrand_real3());
184		printf("%d を追加\n", k);
185		dt = new List(k);
186		root.add(dt);
187		root.output();
188				// 削除1
189		printf("%d を削除\n", k);
190		root.del(k);
191		root.output();
192				// 追加4
193		k = (int)(1000 * genrand_real3());
194		printf("%d を追加\n", k);
195		dt = new List(k);
196		root.add(dt);
197		root.output();
198				// 参照
199		int *x = new int [2];
200		for (int i1 = 0; i1 < 5; i1++) {
201			root.get(i1, x);
202			if (x[0] > 0) {
203				printf("%d 番目のデータは %d\n", i1, x[0]);
204				if (x[1] > 0)
205					printf("   %d 番目(後ろ)のデータは %d\n", i1+1, x[1]);
206				else
207					printf("   (後ろ)***error*** データが存在しません！(get)\n");
208				if (x[2] > 0)
209					printf("   %d 番目(前)のデータは %d\n", i1-1, x[2]);
210				else
211					printf("   (前)***error*** データが存在しません！(get)\n");
212			}
213		}
214		return 0;
215	}
    （出力） 
       データがありません(output)
866 を追加
   data(順) 866
   data(逆) 866
899 を追加
   data(順) 866 899
   data(逆) 899 866
240 を追加
   data(順) 240 866 899
   data(逆) 899 866 240
240 を削除
   data(順) 866 899
   data(逆) 899 866 240 0
497 を追加
   data(順) 497 866 899
   data(逆) 899 866 497
***error*** データが存在しません！(get)
1 番目のデータは 497
   2 番目(後ろ)のデータは 866
   (前)***error*** データが存在しません！(get)
2 番目のデータは 866
   3 番目(後ろ)のデータは 899
   1 番目(前)のデータは 497
3 番目のデータは 899
   (後ろ)***error*** データが存在しません！(get)
   2 番目(前)のデータは 866
***error*** データが存在しません！(get)

  3. 木構造

    　　連結リストでは，階層的な構造を持つデータの集まりを表すことは困難です．木構造は，以下の図に示すように，階層的なデータを表すためのデータ構造です．連結リストや木構造において，データの追加，削除，参照を行う場合は，必ず必要なデータを探索する必要があります．連結リストの場合は，ポインタを順にたどって探すことになりますが，木構造の場合は，それほど簡単ではありません．木構造における探索の問題は 4 章で説明することとし，プログラム例は，下図に示すような木構造を簡単に生成するだけのものです．

    　　一般に，木構造においては，子供が何人になるかを前もって知ることができない場合が多いと思います．従って，メンバー変数 children は，連結リストなどを使用して記述すべきですが，プログラムが複雑になるのを避けるため，ここでは，C++ 標準ライブラリ内の vector クラスを使用しています． 

    01	/****************************/
02	/* 木構造                   */
03	/*      coded by Y.Suganuma */
04	/****************************/
05	#include <iostream>
06	#include <string>
07	#include <vector>
08	
09	using namespace std;
10	
11	/********************/
12	/* クラスListの定義 */
13	/********************/
14	class List
15	{
16			string data;
17			List *parent;
18			vector <List *> children;
19		public :
20				// コンストラクタ   p: 親に対するポインタ
21			List (string x, List *p)
22			{
23				parent = p;
24				data   = x;
25				if (parent != NULL)
26					(parent->children).push_back(this);
27			}
28	
29			void output();   // 出力
30	};
31	
32	/****************/
33	/* データの出力 */
34	/****************/
35	void List::output()
36	{
37		cout << data << endl;
38		if (children.size() > 0) {
39			cout << "   子供";
40			for (int i1 = 0; i1 < (int)children.size(); i1++)
41				cout << " " << children[i1]->data << "(親" << (children[i1]->parent)->data << ")";
42			cout << endl;
43		}
44	
45		for (int i1 = 0; i1 < (int)children.size(); i1++) {
46			if ((children[i1]->children).size() > 0)
47				children[i1]->output();
48		}
49	}
50	
51	/****************/
52	/* main program */
53	/****************/
54	int main ()
55	{
56		List S("S", NULL);
57		List A("A", &S);
58		List B("B", &S);
59		List C("C", &S);
60		List D("D", &A);
61		List E("E", &A);
62		List F("F", &C);
63		List G("G", &C);
64		S.output();
65		return 0;
66	}
    14 行目～ 30 行目

    　　クラス List の定義です．メンバー変数は，string クラスのオブジェクトである文字列データ（ data ），親に対するポインタ（ parent ），及び，子（ List クラスのオブジェクト）に対するポインタを要素とする vector クラスのオブジェクト（ children ）となっています．21 行目～ 27 行目のコンストラクタでは，親，及びデータの設定と共に，親が存在する場合は，親の子として現在のオブジェクトを children に追加しています（ 25，26 行目）．

    35 行目～ 49 行目

    　　クラス List のメンバー関数であり，木構造に含まれる全てのデータを，再帰的に（ 45 行目～ 48 行目）出力しています．

    （出力）　このプログラムによって，以下に示すような出力が得られます． 
    S
   子供 A(親S) B(親S) C(親S)
A
   子供 D(親A) E(親A)
C
   子供 F(親C) G(親C)

  4. 二分木（二分探索木）

    　　二分木（バイナリーツリー，Binary Tree ）は，各ノードが最大で 2 つの子ノードしか持たない木構造です．ヒープ（ heap ）とは，親ノードは子ノードよりも小さい（大きい）か等しいという条件を満たす木構造のことです．単にヒープと呼ぶ場合，二分木として構成されるバイナリヒープを指します．また，二分探索木も，二分木の一種であり，各ノードにデータと 2 つのポインタを持ち，左のポインタでつながるデータはすべて自分より小さく，また，右のポインタでつながるデータはすべて自分より大きくなるような二分木です．例えば，13 個の単語が，「 network parameters are network optimized from empirical data and are the optimal number 」という順に入力された場合は以下のようになります（同じデータ，network と are があえて加えてあるが，同じデータは一つだけ二分探索木に付加される）．二分探索木は，Ⅳ 章で説明するように，探索のために使用されます．C++ 標準ライブラリ内の set クラス，multiset クラス，map クラス，multimap クラスは，一般に，二分木として実装されています．

    ［演習２］上の図に示した二分探索木を実現するためのプログラムを書け．プログラムは，データの追加と結果の出力を行う関数を必ず含むこと．また，様々なケースに対して正しく動作することを確認すること．ただし，C++ 標準ライブラリ内の set クラス，multiset クラス，map クラス，multimap クラスは使用しないこと．

講義内容目次 菅沼ホーム 前ページ 次ページ