リスト構造

001	/****************************/
002	/* リスト構造               */
003	/*      coded by Y.Suganuma */
004	/****************************/
005	#include <stdio.h>
006	#include <string.h>
007	
008	/********************/
009	/* クラスListの定義 */
010	/********************/
011	class List
012	{
013			char *st;   // データ（文字列）
014			List *next;   // 次のデータ
015	
016		public :
017					// コンストラクタ
018			List () { next = NULL; }
019	
020			List (char *s)
021			{
022				next = NULL;
023				st   = new char [strlen(s)+1];
024				strcpy(st, s);
025			}
026	
027			void add(List *);   // データの追加
028			void del(char *);   // データの削除
029			void output();   // 出力
030	};
031	
032	/**************************************/
033	/* データの追加                       */
034	/*      dt : Listクラスのオブジェクト */
035	/**************************************/
036	void List::add(List *dt)
037	{
038		List *lt1, *lt2 = this;
039		int sw = 1;
040	
041		while (sw > 0) {
042						// 最後に追加
043			if (lt2->next == NULL) {
044				lt2->next = dt;
045				sw        = 0;
046			}
047						// 比較し，途中に追加
048			else {
049				lt1 = lt2;
050				lt2 = lt2->next;
051				int k = strcmp(dt->st, lt2->st);   // 比較
052				if (k < 0) {                     // 追加
053					dt->next  = lt2;
054					lt1->next = dt;
055					sw        = 0;
056				}
057			}
058		}
059	}
060	
061	/*********************/
062	/* データの削除      */
063	/*      st1 : 文字列 */
064	/*********************/
065	void List::del(char *st1)
066	{
067		List *lt1, *lt2 = this;
068		int sw = 1;
069	
070		while (sw > 0) {
071						// データが存在しない場合
072			if (lt2->next == NULL) {
073				printf("      指定されたデータがありません！\n");
074				sw = 0;
075			}
076						// 比較し，削除
077			else {
078				lt1 = lt2;
079				lt2 = lt2->next;
080				int k = strcmp(st1, lt2->st);   // 比較
081				if (k == 0) {                 // 削除
082					delete [] lt2->st;
083					lt1->next = lt2->next;
084					sw        = 0;
085				}
086			}
087		}
088	}
089	
090	/**********************/
091	/* リストデータの出力 */
092	/**********************/
093	void List::output()
094	{
095		List *nt = this->next;
096	
097		while (nt != NULL) {
098			printf("   data = %s\n", nt->st);
099			nt = nt->next;
100		}
101	}
102	
103	/****************/
104	/* main program */
105	/****************/
106	int main ()
107	{
108		int sw = 1;
109		List base, *lt;
110	
111		while (sw > 0) {
112			char st[100];
113			printf("1:追加，2:削除，3:出力，0:終了？ ");
114			scanf("%d", &sw);
115			switch (sw) {
116				case 1:   // 追加
117					printf("   データを入力してください ");
118					scanf("%s", st);
119					lt = new List(st);
120					base.add(lt);
121					break;
122				case 2:   // 削除
123					printf("   データを入力してください ");
124					scanf("%s", st);
125					base.del(st);
126					break;
127				case 3:   // 出力
128					base.output();
129					break;
130				default :
131					sw = 0;
132					break;
133			}
134		}
135	
136		return 0;
137	}
		

011 行目

　　リストを構成するクラス List の定義の始まりであり，030 行目まで続きます．クラス List では，private メンバー変数として文字列データへのポインタ（ 013 行目）とリストを構成する次のオブジェクトへのポインタ（ 014 行目）を持っています．なお，2 つのコンストラクタはクラス内において定義されていますが，メンバー関数 add，del，output に対しては型宣言を行っているだけであり（ 027 行目～ 029 行目），実際の定義はクラス外で行っています．

018 行目

　　引数のないコンストラクタの定義です．次のデータを指すポインタを NULL（次のデータが無いことを意味する）に設定しています．

020 行目～ 025 行目

　　1 つの引数を持つコンストラクタの定義です．引数として与えられた文字列を記憶する領域を確保（ 023 行目）し，その領域に引数として与えられた文字列をコピー（ 024 行目）しています．また，次のデータを指すポインタを NULL に設定しています（ 022 行目）．

036 行目～ 059 行目

　　データを追加するための関数です．038 行目において，lt2 には，最初，リスト構造の最初のオブジェクト（ main プログラムの base．次のデータに対するアドレスだけを持つ）に対するアドレスが入ります．lt1 と lt2 を順に変更しながら（049，050 行目），引数として与えられたオブジェクトのデータが lt1 より大きく，かつ，lt2 より小さい場合，その間に与えられたデータを挿入します（ 052 行目～ 056 行目）．もし，そのような位置が存在しなければ，リスト構造の最後にデータを追加します（ 043 行目～ 046 行目）．

065 行目～ 088 行目

　　データを削除するための関数です．067 行目において，lt2 には，最初，リスト構造の最初のオブジェクトに対するアドレスが入ります．lt1 と lt2 を順に変更しながら（078，079 行目），引数として与えられた文字列と等しい文字列を持つオブジェクトが存在すると，そのデータを削除します（ 081 行目～ 085 行目）．もし，等しいデータが存在しなかった場合は，エラーメッセージを出力します（ 072 行目～ 075 行目）．

093 行目～ 101 行目

　　lt2 に，最初，リスト構造の最初のオブジェクトに対するアドレスを代入した後，リスト構造内のすべてのデータを出力します．

117 行目～ 121 行目

　　データの追加を要求された場合の処理です．入力されたデータ（文字列）に基づき，新しい List クラスのインスタンスを生成し（ 119 行目），それを引数として関数 add を呼びます．

123 行目～ 126 行目

　　データの削除を要求された場合の処理です．入力されたデータ（文字列）を引数として，関数 del を呼びます．

　　この例に見るように，リスト構造を生成するプログラムを書くのはかなり面倒です．C++ 標準ライブラリ内の set クラスなどを使用すれば，以下に示すように，同じ機能を簡単に実現できます．

/****************************/
/* リスト処理               */
/*      coded by Y.Suganuma */
/****************************/
#include <iostream>
#include <set>
#include <string>

using namespace std;

/**********************/
/* リストデータの出力 */
/*      lt : リスト   */
/**********************/
void output(set<string> &s) {
	set<string>::iterator it;
	cout << "要素数： " << s.size() << "\n";
	for (it = s.begin(); it != s.end(); it++)
		cout << "  " << *it;
	cout << "\n";
}

/****************/
/* main program */
/****************/
int main ()
{
	int sw = 1;
	string str;
	set <string> s;

	while (sw > 0) {
		cout << "1:追加，2:削除，3:出力，0:終了？ ";
		cin >> sw;
		switch (sw) {
			case 1:   // 追加
				cout << "   データを入力してください ";
				cin >> str;
				s.insert(str);
				break;
			case 2:   // 削除
				cout << "   データを入力してください ";
				cin >> str;
				s.erase(str);
				break;
			case 3:   // 出力
				output(s);
				break;
			default :
				sw = 0;
				break;
		}
	}

	return 0;
}