整数を要素とする1次元1方向連結リスト構造の基本的操作

Question

整数を要素とする1次元1方向連結リスト構造の基本的操作を行うプログラム作っています．ポインタと動的メモリの基本操作を学習するためにプログラムを作っているので，STLは使用しないこととします．
以下の操作命令を受け付け、対応する処理を行うことを繰り返します．
終了：プログラムを終了する。
挿入：連結リストの指定位置に整数値を挿入する。
削除：連結リストの指定位置から整数値を削除する。
探索：指定した整数値がリストの何番目の位置に含まれているか答える。
プッシュ：リストの先頭に整数値をプッシュする（先頭に挿入する）。
ポップ：リストの先頭から整数値をポップする（先頭から取り出し削除する）。
追加：リストの末尾に整数値を追加する。

・末尾ノードは有効な値を持たないダミーノードです．
・先頭と末尾のノードは、それぞれポインタ変数head、tailが参照しています．

以下が現在のコードです．

#include <iostream>
using namespace std;

#define END 0		// 終了命令
#define INSERT 1	// 挿入命令
#define DELETE 2	// 削除命令
#define SEARCH 3	// 探索命令
#define PUSH 4		// プッシュ命令
#define POP 5		// ポップ命令
#define ADD 6		// 追加命令

// プロトタイプ宣言
void initList(void);		// リストを初期化する
void showList(void);		// リストを表示する
int getCommand(void);		// 操作命令を受け取る
void insertNode(int number, int value);	// ノードを挿入する
void deleteNode(int number);		// ノードを削除する
void searchNode(int value);		// 値を探索する
void pushNode(int value);	// 値を先頭にプッシュする
void popNode(void);			// 値を先頭からポップする
void addNode(int value);	// ノードを末尾に追加する

class Node {		// リストノードの構造体定義
public:
	int value;			// ノードの値
	Node* next;			// 次ノードを参照するポインタ
};

Node* head = NULL;		// リストの先頭ノードを参照するポインタ（先頭ポインタ）
Node* tail = NULL;		// リストの末尾ノードを参照するポインタ（末尾ポインタ）

/**********
メイン関数
**********/
void main() {

	int command;	// 操作命令番号
	int number;		// ノード番号
	int value;		// ノード値

	// リストを初期化する
	initList();

	// リストを表示し操作命令を受け取る
	showList();
	command = getCommand();

	// 操作命令が終了でない限り以下を繰り返す
	while (command != END) {

		// 命令によって分岐する
		switch (command) {

			// 操作命令が挿入であれば以下を実行する
		case INSERT:

			// 挿入する位置と値を受け取る
			cout << "挿入位置のノードの番号(負/0は先頭、正はその番号ノードの後) = ";
			cin >> number;
			cout << "挿入する値(整数) = ";
			cin >> value;

			// リストに入力値を挿入する
			insertNode(number, value);
			break;

			// 操作命令が削除であれば以下を実行する
		case DELETE:

			// 削除するノード番号を受け取る
			cout << "削除するノードの番号 ＝ ";
			cin >> number;

			// リストからノードを削除する
			deleteNode(number);
			break;

			// 操作命令が探索であれば以下を実行する
		case SEARCH:

			// 探索する値を受け取る
			cout << "探索する値 ＝ ";
			cin >> value;

			// 値を探索して結果を表示する
			searchNode(value);
			break;

			// 操作命令がプッシュであれば以下を実行する
		case PUSH:

			// プッシュする値を受け取る
			cout << "プッシュする値 ＝ ";
			cin >> value;

			// 先頭に値をプッシュする
			pushNode(value);
			break;

			// 操作命令がポップであれば以下を実行する
		case POP:

			// 先頭から値をポップする
			popNode();
			break;

			// 操作命令が追加であれば以下を実行する
		case ADD:

			// 追加する値を受け取る
			cout << "追加する値 ＝ ";
			cin >> value;

			// 末尾に値を追加する
			addNode(value);
			break;
			// それ以外はエラー表示する
		default:
			cout << "★番号が不正です" << endl << endl;
			break;

		}

		// リストを表示し次の操作命令を受け取る
		showList();
		command = getCommand();
	}
}

/*****************************************************
リストを初期化する
*****************************************************/
void initList(void) {

	// ダミーノードを作成し、先頭ノードを参照するポインタhead（以下、先頭ポインタ）と
	// 末尾ノードを参照するポインタtail（以下、末尾ポインタ）につなぐ
	head = tail = new Node();

	// ダミーノードの内容を設定する
	tail->value = 0;
	tail->next = NULL;
}

/****************************************************
リストを表示する
****************************************************/
void showList(void) {

	// ヘッダーを表示する
	cout << endl;
	cout << "-----List-----" << endl;
	cout << "No: \tValue" << endl;
	cout << "--------------" << endl;

	// 先頭ノードから始めて末尾ノードでない間、以下を繰り返す
	Node* p = head;
	int number = 1;
	while (p != tail) {

		// 現ノードの番号と値を表示する
		cout << number << ": \t" << p->value << endl;

		// 次のノードへ移動する
		p = p->next;
		number++;
	}

	// フッターを表示する
	cout << "--------------" << endl << endl;
}

/****************************************************
リスト操作の命令を受け取る
****************************************************/
int getCommand(void) {

	int number;	// 命令番号

	// メニューを表示する
	cout << "命令番号を入力してください" << endl;
	cout << END << ": 終了" << endl;
	cout << INSERT << ": 挿入" << endl;
	cout << DELETE << ": 削除" << endl;
	cout << SEARCH << ": 探索" << endl;
	cout << PUSH << ": プッシュ" << endl;
	cout << POP << ": ポップ" << endl;
	cout << ADD << ": 追加" << endl;

	// 命令番号を受け取る
	cout << "命令番号 = ";
	cin >> number;

	// 命令番号を返す
	return number;
}

/*****************************************************
値valueを持つノードをnumber番目のノードの次に挿入する
numberが負またはゼロの時は先頭の前に挿入する
numberが末尾より先の時は末尾に挿入する
*****************************************************/
void insertNode(int number, int value) {

	// 新たなノード（新ノード）の領域を確保し、ポインタpNewにつなぐ
	Node* pNew = new Node();

	// 新ノードに値を入れる
	pNew->value = value;

	// 指定ノード番号numberが負またはゼロの時、またはリストが空の時は、以下を実行する
	if ((number <= 0) || head == tail) {

		// 先頭ポインタheadが参照するノードの前に新ノードを挿入する
		pNew->next = head;
		head = pNew;
	}

	// それ以外の時は以下を実行する
	else {

		// 先頭からnumber-1ノード分先を探し現ノードとする
		// （ポインタpの参照先を先頭ノードから開始して次ノードへnumber-1回移動する）
		Node* p = head;
		for (int i = 1; i < number; i++) {

			// 次ノードが末尾のダミーノードならループを抜ける
			if (p->next == tail) break;

			// 次ノードを現ノードにする
			p = p->next;
		}

		// ポインタpの参照するノード(現ノード)の次に新ノードを挿入する
		pNew->next = p->next;
		p->next = pNew;
	}
}

/****************************************************
number番目のノードを削除する
number番目のノードがない時は何もしない
****************************************************/
void deleteNode(int number) {

	// 番号が負またはゼロなら削除対象ノードがないので戻る
	if (number <= 0) return;

	// リストが空なら削除対象ノードがないので戻る
	if (head == tail) return;

	// 先頭から(number-1)ノード分先を探し、現ノードとする
	// （ポインタpの参照先を先頭ノードから開始して次ノードへnumber-1回移動する）
	Node* p = head;
	for (int i = 1; i < number; i++) {

		// 次ノードが末尾のダミーノードなら削除対象ノードがないので戻る
		if (p->next == tail) return;

		// 次ノードを現ノードとする
		p = p->next;
	}

	/***********************************************
	以下に、ポインタpが参照するノード（現ノード）を削除するコードを追加する。
	ただし、削除のためのリンク変更には直前ノードを参照するポインタが必要なので、
	ここでは、次ノードの内容を現ノードにコピーして、次ノードを削除する方法を取る。
	***********************************************/

	// 次ノードを参照するポインタpNextを作る。
	Node* pNext= new Node();

	// 次ノードの内容（valueとnext）を現ノードへコピーする。
	p->value = pNext->value;
	p->next = pNext->next;
	
	// 次ノードが末尾のダミーノードならば、末尾ポインタが現ノードを参照するように設定する。
	if (p->next == tail) {
		tail = p;
	}

	// 次ノードを削除する。
	delete pNext;
}

/****************************************************
値valueを持つノード番号を探索して表示する
****************************************************/
void searchNode(int value) {

	/*****************************************
	 以下に、引数で渡された値valueをリストから探すコードを追加する。
	ポインタpの参照を先頭ノードから次々に移動しながら、引数値とノード値を
	比較し、一致していればノード番号を表示することを、末尾（ダミーノード
	直前）まで繰り返す。
	*****************************************/

	// ノード番号nodeNoを1に設定する。
	int nodeNo = 1;

	// ポインタpが先頭ノードを参照するように設定する。
	Node* p = head;

	// ポインタpの参照先（現ノード）が末尾ノードでない間、以下を繰り返す。
	while (p != tail) {

		// 現ノードの値と引数の値が等しいならノード番号を表示する。
		if (p->value == value) {
			cout << nodeNo;
		}

		// 次ノードを現ノードとする。
		p = p->next;

		// ノード番号をインクリメントする。
		nodeNo++;
	}
}

/****************************************************
値valueをリストの先頭に入れる
****************************************************/
void pushNode(int value) {

	/***********************************************
	以下に、引数で渡された値valueをリストの先頭にプッシュするコードを追加する。
	なお、insertNode()等の関数を呼び出すのではなく、ポインタ操作で行うこと。
	***********************************************/

	// 新ノードの領域を確保し、ポインタpNewにつなぐ
	Node* pNew = new Node();

	// 新ノードに引数で渡された値valueを入れる。
	pNew->value = value;

	// 既存の先頭ノードを新ノードの後につなぎ、先頭ポインタheadに新ノードをつなぐ
	pNew->next = head;
	head = pNew;

}


/****************************************************
リストの先頭の値を削除して返す
****************************************************/
void popNode(void) {

	/**********************************************
	以下に、ポップのコードを追加する。
	なお、ここでポップとは、先頭の値を表示して削除することである。
	deleteNode()等の関数を呼び出すのではなく、ポインタ操作で行うこと。
	***********************************************/

	// リストが空ならば（headとtailが同じノードを指していれば）、エラーを表示して戻る。
	if(head==tail){
		cout << "★番号が不正です";
		return;
    }

	// それ以外は以下を実行する。
	else {

		// 先頭ノードの値を表示する
		cout << head->value;

		// 先頭ポインタheadを退避用のポインタ変数pSaveにコピーして、先頭ポインタheadを次ノードに移動する。
		Node* pSave = head;
		head->next = head;

		// 待避したポインタpSaveが参照するノードを削除する。
		delete pSave;
	}
}

/*****************************************************
値valueを持つノードをリストの末尾に追加する
*****************************************************/
void addNode(int value) {

	/************************************************
	以下に、引数で渡された値をリストの末尾に付け加えるコードを追加する。
	既存のダミーノードに値を設定し、その次に新規のダミーノードを付加する方法を取る。
	*************************************************/

	// 新ノードの領域を確保し、ポインタpNewにつなぐ（これが新規のダミーノードとなる）。
	Node* pNew = new Node();

	// 既存のダミーノードに引数で渡された値valueを設定する。
	tail->value = value;

	// 既存のダミーノードの次に新ノードをつなぐ。
	tail->next = pNew;

	// ポインタpNewが参照する新ノードを末尾ポインタtailにつなぐ。
	tail = pNew;

	// 新ノードの次ノード参照ポインタはNULLとする。
	pNew->next = NULL;
}

このコードで実行すると，正しく出力されない点が２つあります
・削除：2 を入力すると，指定したノード番号の値が0になって，プログラムが終了してしまいます．指定したノードが削除され，再度，命令番号のメニューが表示されるには，現在のコードをどのように修正したらよいでしょうか？
・ポップ：5を入力すると，ノード番号1の値が-572662307となり他のノードがすべて消えて，プログラムが終了してしまいます．先頭のノードだけが削除され，再度，命令番号のメニューが表示されるには,現在のコードをどのように修正したらよいのでしょうか？
以上の2点を教えてください．よろしくお願いします．

Comments

[fana]

「相互利用が可能な場合…」は意味的に同じことを数回書けば達成できるわけですから，
（中身読んでませんが）仮にinsertNode()が妥当に動くコードなのであれば，少なくもと「プッシュ」と「追加」はそれをコピペしてくれば作れますよね．それすらやらないのは「わからない」じゃなく単に「自分でやりたくない」に見えてしまいます．

[episteme]

> 整数を要素とする1次元1方向連結リスト構造の基本的操作を行うプログラム作っています．
目的は?

> STLは使用しないこととします．
なぜ?

[退会済みユーザー]

ポインタと動的メモリの基本操作を学習するためにプログラムを作っているので，STLは使用しません．

Answer 1

削除

A→B→C→... というノードの並びからBを削除した場合に A→C→... となるようにA->Nextを更新してやれば良いです．
新しいノードをnewで作ったりする必要はないハズです．

ポップ

上記「削除」の削除対象が先頭である場合です．

---

• このプログラムでは「リストの先頭のノードをheadが指し示す」ルールになっていますから，

先頭のノードを削除する場合には，新たに先頭となったノードを指すようにheadの値を更新せねばなりません．

• tail側も同様です．
• 要素数が１個しか無い状態で削除操作を行う場合はheadとtailの両方を更新する必要があります．

---

冷静に

head        tail
 ↓           ↓
[A]→[B]→[C]→[D]

みたいな絵でも描いて，各処理後に{head,tail,各要素のnext}がそれぞれどうなっているべきなのかを考えれば良いかと思います．

Comments

[退会済みユーザー]

具体的にどのようにコードを修正すればよいでしょうか？教えてください。
よろしくお願いします。

[fana]

記述を追記しました．
この(Ａ~Dの例で）ポップについて考えれば，
「headの指し示す先をB（すなわちA.next）に更新した後で，Aを削除」すれば良いことがわかるかと思います．

[退会済みユーザー]

次ノードの内容を現ノードにコピーして、次ノードを削除する方法を取るには，具体的にコードをどのように修正したらよいでしょうか？

[fana]

> 次ノードの内容を現ノードにコピーして、次ノードを削除する
これがちょっと何言ってるかわからないです．
「次ノード」と「現ノード」って具体的にどれのことですか？
例えばこのＡ~Ｄの例で言えばどれになるんですか？

[fana]

ああ，「２番目を削除しろ」言われた時にＢを削除するんじゃなくて代わりにＣを削除するって話ですか．
あなたのdeleteNode()で言えば，「現ノード」とはpが指すノードであり，「次ノード」はp->nextが指すノードってことですか．
Node *pDeleteTgt = p->next; //削除対象は「次ノード」
p->value = p->next->value; //「次ノード」の内容を「現ノード」にコピー
p->next = p->next->next; //「次ノード」の内容を「現ノード」にコピー
delete pDeleteTgt; //削除対象を削除
とかで良いんじゃないですか？　ただし，
・「次のノード」が存在しないパターン
・「次のノード」がtailである場合はtailを更新
とかを考える必要があります．