単結合リストの修正のお願い@C++

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
YM

単結合リストの修正のお願い@C++

#1

投稿記事 by YM » 13年前

ものすごく単純な単連結リストを作りました。
個人的にしっくりこない所があり,悪い所/改善点が知りたいので指摘と修正をお願いします。

Webで調べてもC言語のものばかりで,Cをやっていないので読みづらい部分も多く(typedef struct {} name など)
理論は分かっていたので読み解く前に作ることにしました。(C++のものも一つあったがかなり本格的な双方向リストだったため)

コード:

#include <iostream>
#include <cstdlib>	// NULL

// 簡単な単連結リストの実験

class Node
{
	private:
		int value;			// ノードの保持する値
		Node* next;			// 次の要素へのポインタ。初期値NULL
	public:
		// コンストラクタ
		Node(int n) : value(n), next(NULL) {};

		int GetValue() { return value; }
		Node* GetNextNode() { return next; }
		void SetNextNode(Node* nextnode) { next = nextnode; }
		bool isLast() { return next == NULL ? true : false; }
};


class List
{
	private:
		Node* head;
	public:
		// コンストラクタ。
		List() : head(NULL) {};			// 最初は次が何もない状態
		
		// リストの最後尾に新ノードを追加する
		void AddNode(int num)
		{
			Node* finder = head;				// Node型を扱うポインタにリストの先頭アドレスを入れる。
			
			while(head != NULL && !finder->isLast())
			{
				finder = finder->GetNextNode();	// リストの最後にあるNodeにfinderを合わせる
			}
			
			if(head != NULL)
				finder->SetNextNode(new Node(num));	// 最後のノードの最後尾に新しいノードをセット。
			else
				head = new Node(num);
		}
		
		// リストの要素を先頭から出力する
		void OutputNodes()
		{
			Node* n = head;
			while(true)
			{
				std::cout << n->GetValue() << std::endl;
				n = n->GetNextNode();
				if(n == NULL)
					break;
			}
		}
		
		// デストラクタ
		~List()
		{
			Node* finder = head;
			Node* temp;
			while(true)
			{
				temp = finder->GetNextNode();		// 次の要素へのポインタを記憶
				delete finder;						// 現在選択中のポインタをdelete
				finder = temp;						// 次の要素へ移行
				if(finder == NULL)					// 次の要素がない場合
					break;
			}
		}		
};

int main()
{
	using namespace std;

	List list;	// リスト作成
	
	cout << "-1と入力するまでリストに整数値を格納し続けます" << endl;
	int a = 0;
	while(true)
	{
		std::cin >> a;
		
		if(a == -1)
			break;
		else
			list.AddNode(a);
	}
	
	cout << "リストの値を全て出力します" << endl;
	list.OutputNodes();

	return 0;
}
while(true)からbreakする処理,if(finder != NULL && finder->isLast())の処理が二重で嫌な感じです。
前者のは.isLast()でwhile文をまわした場合,最後のNodeに処理がいきません。(do whileは使わない方針でお願いします)
そのためwhile(true)を通してstd::coutなりdeleteしたあと,break;しました。
後者はListに要素が一つもない時,finder->isLast()で落ちるためです。


全く関係のない話ですが,この上のコードをコピペした後,文字を書き換えようとすると書き込み欄のスクロールバーが暴れてまともにかけないのですが
原因は分かりませんか・・・?

※2
spoilerを表示,はどのようなタグを使えばいいのでしょう?[spoiler]ではないようで。

アバター
bitter_fox
記事: 607
登録日時: 14年前
住所: 大阪府

Re: 単結合リストの修正のお願い@C++

#2

投稿記事 by bitter_fox » 13年前

YM さんが書きました: while(true)からbreakする処理,if(finder != NULL && finder->isLast())の処理が二重で嫌な感じです。
前者のは.isLast()でwhile文をまわした場合,最後のNodeに処理がいきません。(do whileは使わない方針でお願いします)
そのためwhile(true)を通してstd::coutなりdeleteしたあと,break;しました。
後者はListに要素が一つもない時,finder->isLast()で落ちるためです。
前者のwhile(true)からbreakする処理というのは
YM さんが書きました:

コード:

		// リストの要素を先頭から出力する
		void OutputNodes()
		{
			Node* n = head;
			while(true)
			{
				std::cout << n->GetValue() << std::endl;
				n = n->GetNextNode();
				if(n == NULL)
					break;
			}
		}
		
		// デストラクタ
		~List()
		{
			Node* finder = head;
			Node* temp;
			while(true)
			{
				temp = finder->GetNextNode();		// 次の要素へのポインタを記憶
				delete finder;						// 現在選択中のポインタをdelete
				finder = temp;						// 次の要素へ移行
				if(finder == NULL)					// 次の要素がない場合
					break;
			}
		}		
の二つですね?
ここは単に
while (n != NULL)[OutputNodes]
while (finder != NULL)[~List]
で良いように思います。

ちなみに今のプログラムで何も要素がセットされてないときにOutputNodesや~Listが呼ばれるとどのようになりますか?
恐らく不正な領域を参照して落ちると思うのですが・・・

後者の問題はAddNodeの事でしょうか?
これは最初にheadがNULLかどうかで分ければよいと思います。

コード:


		void AddNode(int num)
		{
			if (head == NULL) // 1項目目
			{
				head = new Node(num);
			}
			else
			{
				Node* finder = head;				// Node型を扱うポインタにリストの先頭アドレスを入れる。

				while(!finder->isLast())
				{
					finder = finder->GetNextNode();	// リストの最後にあるNodeにfinderを合わせる
				}
				finder->SetNextNode(new Node(num));	// 最後のノードの最後尾に新しいノードをセット。
			}
		}
YM さんが書きました:
全く関係のない話ですが,この上のコードをコピペした後,文字を書き換えようとすると書き込み欄のスクロールバーが暴れてまともにかけないのですが
原因は分かりませんか・・・?
ウェブブラウザ等の環境や具体的な症状が分からないと管理人勢も調査しづらいように思います。
YM さんが書きました: ※2
spoilerを表示,はどのようなタグを使えばいいのでしょう?[spoiler]ではないようで。
spoilerとは具体的にどのような物でしょうか?
[hr][追記]
[ spoil]ではないですよね?
► スポイラーを表示
最後に編集したユーザー bitter_fox on 2011年10月28日(金) 10:53 [ 編集 1 回目 ]

アバター
へろりくしょん
記事: 92
登録日時: 14年前
住所: 福岡

Re: 単結合リストの修正のお願い@C++

#3

投稿記事 by へろりくしょん » 13年前

ケースバイケースではありますが、リスト構造は、ノード自体が再帰的に定義されるものですから、class Node を管理する class List なんて考えは、ちょっとはずれてるかと思わなくも無い気がしないでも無いです。
class List が管理する立場に立つのであれば、ノードの追加・削除・つなぎ変えは、class List の仕事ですので、Node::next は public にしてしまってもかまわないでしょう。

それをふまえた上で、

コード:

void List::AddNode(int num)
{
	Node **finder = &head;						// Node型を扱うポインタにリストの先頭アドレスを入れる。

	while(*finder) finder = &(*finder)->next;	//最後のノードを探す
	*finder = new Node(num);					//新しいノードをセット
}
で、いいかと。
また、ノードを追加する度に、毎回ノードを先頭から末尾までたぐり寄せるのは、ちょっと無駄ですので、
リストの先頭ノードだけで無く、末尾のノードも押さえておくといいかもしれません。
あるいは、順番にこだわらなければ、末尾にでは無く先頭に追加していくのも1つの手です。

while() 文については

コード:

void List::OutputNodes()
{
	Node *n = head;

	while(n){
		std:: cout << n->GetValue() << std::endl;
		n = n->next;
	}
}
で、いいかと。

可能な限り共通にできる処理は共通させ、if 文等による無駄な場分けを排除することで、
上から下へ順番に流れる素直な処理を書くことを念頭に置けば、よりスマートなプログラムになると思います。

後は、行き当たりばったりにメンバ関数を増やさない事でしょうか。
たとえば、isLast() メンバ関数などは、GetNextNode() メンバ関数とほとんど同じですね。 本当に必要ですか?
何となくですが、「ここで最後のノードかどうか調べる必要があるなぁ。。。 よし、チェックする関数でも作るる」
みたいな安易な流れなような気がしてなりません。 違ったらごめんなさい。


※全く関係のない話ですが,この上のコードをコピペした後,文字を書き換えようとすると書き込み欄のスクロールバーが暴れてまともにかけないのですが
原因は分かりません。 どういうアレですか。

YM

Re: 単結合リストの修正のお願い@C++

#4

投稿記事 by YM » 13年前

ありがとうございました。ポインタの有無も条件分岐に使えるんですね。
クラス設計法について今後も気をつけたいと思います。とりあえずbool型なら使いやすいかななどと勝手に作っていました。

スポイラー,「spoil」でしたか…  特にソースが長い時に使いたいなと思ったのでききました。



スクロール云々は説明しづらいので
http://firestorage.jp/download/71cc8ca7 ... 7f8b808fc6
に最初の投稿のコードを書いたソースファイル(.cpp)そのものをのせました。
これをエディタからこの返信欄にコピー&ペーストしたのち,改行してさらに下に文を付け加えようとすると
私の環境ではスクロールバーの動きがおかしくなりました。
(言うならば,30行目を描こうとして文字を打っても20行目に戻されて何を打鍵したのか見えない状態)
@Win7x64 IE8.07...。googlechromeでは発生しません。返信がかなり書きづらかったので報告してみた次第です。
どうなるか報告いただけるとありがたいです

アバター
bitter_fox
記事: 607
登録日時: 14年前
住所: 大阪府

Re: 単結合リストの修正のお願い@C++

#5

投稿記事 by bitter_fox » 13年前

YM さんが書きました: これをエディタからこの返信欄にコピー&ペーストしたのち,改行してさらに下に文を付け加えようとすると
私の環境ではスクロールバーの動きがおかしくなりました。
(言うならば,30行目を描こうとして文字を打っても20行目に戻されて何を打鍵したのか見えない状態)
@Win7x64 IE8.07...。googlechromeでは発生しません。返信がかなり書きづらかったので報告してみた次第です。
どうなるか報告いただけるとありがたいです
Win7・64bitのIE7で類似の挙動を確認しました。
Firefoxでも発生しませんでしたのでIE特有の症状なんでしょうかね・・・?
[hr][追記]
こちらに一連の問題をまとめて投稿しておきました。

閉鎖

“C言語何でも質問掲示板” へ戻る