木構造編集プログラムのノードの削除機能について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
あや
記事: 21
登録日時: 2ヶ月前

木構造編集プログラムのノードの削除機能について

#1

投稿記事 by あや » 6日前

木構造編集プログラムに、ノードの削除機能を追加しています.
コマンドは、以下の形式とします.
「 D n L|R 」: n番ノードの左(L)または右(R)の子ノードを削除する.
削除対象ノードが1つの子を持つときには、その子を削除ノードのあった位置に接続します.2つの子を持つときには削除しません.
以下が現在のコードです.

コード:

#include <iostream>
#include <string>
using namespace std;

#define LINELENGTH 80    //一行の長さ
#define END    'E'        //終了
#define ADD    'A'        //追加
#define CUT    'X'        //切り取り
#define LEFT    'L'        //左
#define RIGHT    'R'        //右
#define INSERT   'I'       //挿入 
#define DELETE   'D'      //削除

class Node {            //ノードを表すクラス
public:
	string word;    //ノード格納単語
	Node* pLeft;    //左ノードを参照するポインタ
	Node* pRight;    //右ノードを参照するポインタ
};

//プロトタイプ宣言
void showTree();
void showTreeRecursive(Node* pNode, int nodeLevel);
Node* searchNode(int searchNodeNo);
Node* searchNodeRecursive(Node* pPresentNode, int searchNodeNo);
void addNode(string word, int nodeNo, char direction);
void cutNode(int nodeNo, char direction);
void deleteNodeRecursive(Node* pNode);
void showHelp();
void insertNode(string word, int nodeNo, char direction);
void deleteNode(int nodeNo, char direction);

Node* pRoot;        //根ノードを参照するポインタ
int nodeCounter;    //ノードの番号付けカウンタ

//
//----メイン関数-------
//
void main()
{
	char commandLine[LINELENGTH] = "";    //コマンド行(文字配列)
	char command = ' ';                    //コマンド文字
	char word[LINELENGTH] = "";            //単語(文字配列)
	char direction = LEFT;                //方向指示
	int nodeNo;                            //ノード番号

	//根ノードを生成して、その参照を根ノードポインタに入れる。
	pRoot = new Node;

	//根ノードの左右ポインタにNULLを、単語に"<"を入れる。
	pRoot->pLeft = pRoot->pRight = NULL;
	pRoot->word = "<";

	//現在の木構造を表示する。
	showTree();

	//コマンド行を受け取り、その先頭のコマンド文字を取り出す。
	cout << "> ";
	cin.getline(commandLine, LINELENGTH);
	sscanf_s(commandLine, "%c", &command, 1);

	//コマンドが「プログラム終了」でない限り、以下の処理を繰り返す。
	while (command != END) {

		//コマンドが「追加」であれば、以下を実行する。
		switch (command) {
		case ADD:

			//コマンド行から、コマンド、単語、ノード番号、方向指示を取り出せれば、追加を実行する。
			if (sscanf_s(commandLine, "%c %s %d %c", &command, 1, word, LINELENGTH, &nodeNo, &direction, 1) == 4) {
				addNode(word, nodeNo, direction);
			}
			break;

			//コマンドが「切り取り」であれば、以下を実行する。
		case CUT:

			//コマンド行から、コマンド、ノード番号、方向指示を取り出せたら、切り取りを実行する。
			if (sscanf_s(commandLine, "%c %d %c", &command, 1, &nodeNo, &direction, 1) == 3) {
				cutNode(nodeNo, direction);
			}
			break;

			//コマンドが「挿入」であれば、以下を実行する。
		case INSERT:

			//コマンド行から、コマンド、単語、ノード番号、方向指示を取り出せれば、挿入を実行する。
			if (sscanf_s(commandLine, "%c %s %d %c", &command, 1, word, LINELENGTH, &nodeNo, &direction, 1) == 4) {
				insertNode(word, nodeNo, direction);
			}
			break;

			//コマンドが「削除」であれば、以下を実行する。
		case DELETE:

			//コマンド行から、コマンド、ノード番号、方向指示を取り出せれば、削除を実行する。
			if (sscanf_s(commandLine, "%c %d %c", &command, 1, &nodeNo, &direction, 1) == 3) {
				cutNode(nodeNo, direction);
			}
			break;
			
			//コマンドがどれでもなければ、ヘルプ表示を行う。
		default:
			showHelp();
		}

		//現在の木構造を表示する。
		showTree();

		//コマンド行を受け取り、その先頭のコマンド文字を取り出す。
		cout << "> ";
		cin.getline(commandLine, LINELENGTH);
		sscanf_s(commandLine, "%c", &command, 1);
	}
}

//
//----木構造を表示する。-----
//
void showTree()
{
	int nodeLevel;    //ノードの根からの深さ

	//ノードカウンタ(ノード番号を数える)をリセットする。
	nodeCounter = 0;

	//ノードレベル(根からの深さ)をリセットにする。
	nodeLevel = 0;

	//木の表示再帰を呼び出す。
	showTreeRecursive(pRoot, nodeLevel);
}

//
//----木構造の再帰表示を行う。----
//
void showTreeRecursive(Node* pNode, int nodeLevel)
{
	//ノードポインタがnullならば戻る。
	if (pNode == NULL) return;

	//ノードレベルをインクリメントする。
	nodeLevel++;

	//ノードポインタの指すノード(現ノード)の右ポインタについて木の再帰表示を行う。
	showTreeRecursive(pNode->pRight, nodeLevel);

	//ノードカウンタをインクリメントする。
	nodeCounter++;

	//ノードレベルに合ったインデンションを付け、ノードカウンタと現ノードの単語を表示する。
	for (int i = 0; i < nodeLevel; i++) cout << "\t";
	cout << nodeCounter << ": " << pNode->word << endl;

	//現ノードの左ポインタについて木の再帰表示を行う。
	showTreeRecursive(pNode->pLeft, nodeLevel);
}

//
//----指定番号のノードを探索する。-----
//
Node* searchNode(int searchNodeNo)
{
	//ノードカウンタをリセットする。
	nodeCounter = 0;

	//ノードの再帰探索を行い、その戻り値を持って戻る。
	return searchNodeRecursive(pRoot, searchNodeNo);
}

//
//-----ノードの再帰探索を行う。------
//
Node* searchNodeRecursive(Node* pPresentNode, int searchNodeNo)
{
	Node* pFoundNode;    //発見したノードへのポインタ

	//ノードポインタがNULLならば、戻り値をNULLにして戻る。
	if (pPresentNode == NULL) return NULL;

	//ノードポインタが参照するノード(現ノード)の右ポインタについてノードの再帰探索を行う。
	pFoundNode = searchNodeRecursive(pPresentNode->pRight, searchNodeNo);

	//戻り値がNULLでなければ、その戻り値を持って戻る。
	if (pFoundNode != NULL) return pFoundNode;

	//ノードカウンタをインクリメントする。
	nodeCounter++;

	//ノードカウンタが探索ノード番号に等しければ、現ノードポインタを持って戻る。
	if (searchNodeNo == nodeCounter)    return pPresentNode;

	//現ノードの左ポインタについてノードの再帰探索を行う。
	pFoundNode = searchNodeRecursive(pPresentNode->pLeft, searchNodeNo);

	//その戻り値を持って戻る。
	return pFoundNode;
}

//
//----ノードを追加する。-----
//
void addNode(string word, int nodeNo, char direction)
{
	Node* pParentNode;    //親ノードへのポインタ
	Node* pChildNode;    //子ノードへのポインタ

	//ノード番号に対応する親ノードを探索してノードポインタを得る。
	pParentNode = searchNode(nodeNo);

	//ノードポインタがNULLであれば戻る(探索失敗)。
	if (pParentNode == NULL) return;

	//方向指示の先が空いていなければ戻る。
	if (direction == LEFT && pParentNode->pLeft != NULL)return;
	if (direction == RIGHT && pParentNode->pRight != NULL)return;

	//新しく子ノードのメモリ領域を確保する。
	pChildNode = new Node;

	//子ノードの内容を設定する。
	pChildNode->word = word;
	pChildNode->pLeft = pChildNode->pRight = NULL;

	//子ノードを親ノードの方向指示の先につなぐ。
	if (direction == LEFT)pParentNode->pLeft = pChildNode;
	if (direction == RIGHT)pParentNode->pRight = pChildNode;
}

//
//----ノードを切り取る。-----
//
void cutNode(int nodeNo, char direction)
{
	Node* pNode;    //ノードへのポインタ

	//ノード番号に対応するノードを探索してノードポインタを得る。
	pNode = searchNode(nodeNo);

	//ノードポインタがNULLならば戻る(探索失敗)。
	if (pNode == NULL) return;

	//方向指示が右であれば以下を実行する。
	if (direction == RIGHT) {

		//ノードの右ポインタについて再帰削除を行う。
		deleteNodeRecursive(pNode->pRight);

		//ノードの右ポインタをNULLにする。
		pNode->pRight = NULL;
	}

	//方向指示が左であれば以下を実行する。
	if (direction == LEFT) {

		//ノードの左ポインタについて再帰削除を行う。
		deleteNodeRecursive(pNode->pLeft);

		//ノードの左ポインタをNULLにする。
		pNode->pLeft = NULL;
	}
}

//
//-----ノードの再帰削除を行う。------
//
void deleteNodeRecursive(Node* pNode)
{
	//ノードポインタがNULLならば戻る。
	if (pNode == NULL) return;

	//ノードポインタの右ポインタについてノードの再帰削除を行う。
	deleteNodeRecursive(pNode->pRight);

	//ノードポインタの左ポインタについてノードの再帰削除を行う。
	deleteNodeRecursive(pNode->pLeft);

	//ノードポインタの参照するノードのメモリ領域を解放する。
	delete pNode;
}

//
//----ヘルプを表示する。------
//
void showHelp()
{
	//コマンド一覧を表示する。
	cout << "A word n L|R  = Add:wordをn番の左(L)または右(R)に追加" << endl;
	cout << "X      n L|R  = Cut:n番の(L)または右(R)を切り取り" << endl;
	cout << "E             = End:プログラムを終了" << endl;
}

//
//----ノードを挿入する。-----
//
void insertNode(string word, int nodeNo, char direction) {

	Node* pNode;    //ノードへのポインタ
	
	//ノード番号に対応するノード(以下、現ノード)を探索して、現ノードへのポインタを得る。
	pNode = searchNode(nodeNo);

	//ポインタがNULLならば探索失敗なので戻る。
	if (pNode == NULL) return;

	//挿入する新規ノードのメモリ領域を確保する。
	Node* pNewNode; //新規ノードへのポインタ

	pNewNode = new Node();

	//新規ノードに単語を設定し、左右ポインタをNULLにする。 
	pNewNode->word = word;
	pNewNode->pRight = NULL;
	pNewNode->pLeft = NULL;

	//方向指示が左ならば以下を実行する。
	if (direction == LEFT) {

		//新規ノードの左ポインタに、現ノードの左ポインタを入れる。 (新規ノードの左ポインタ「の変数領域」に、現ノードの左ポインタ「の値」を入れる。) 
		pNewNode->pLeft = pNode->pLeft;

		//現ノードの左ポインタに、新規ノードへのポインタを入れる。
		pNode->pLeft = pNewNode;
	}

	//方向指示が右ならば以下を実行する。
	if (direction == RIGHT) {
		
		//新規ノードの右ポインタに、現ノードの右ポインタを入れる。
		pNewNode->pRight = pNode->pRight;

		//現ノードの右ポインタに、新規ノードへのポインタを入れる。
		pNode->pRight = pNewNode;
	}
}

//
//----ノードを削除する。-----
//
void deleteNode(int nodeNo, char direction) {

	Node* pNode;    //ノードへのポインタ

	//ノード番号に対応するノード(現ノード)を探索してポインタを得る。
	pNode = searchNode(nodeNo);

	//ポインタがNULLならば探索失敗であるので戻る。
	if (pNode == NULL) return;

	//方向指示に対応する左右ポインタから、削除対象ノードへのポインタを得る。
	Node* pDeleteNode=new Node;
	if (direction == RIGHT) pDeleteNode = pNode->pRight;
	if (direction == LEFT) pDeleteNode = pNode->pLeft;

	//ポインタがNULLであれば削除対象ノードが無いので戻る。
	if (pDeleteNode== NULL) return;
	
	//削除対象ノードの下に子ノードが2つあれば削除できないので戻る。
	if (pDeleteNode->pRight != NULL && pDeleteNode->pLeft != NULL)return;
	
	//存在する子ノードへのポインタを得る(子ノードが無いならばNULL)。
	Node* pChildNode;
	if (pDeleteNode->pRight == NULL && pDeleteNode->pLeft == NULL) pChildNode = NULL;
	else pChildNode = pDeleteNode->pRight ? pDeleteNode->pRight : pDeleteNode->pLeft;

	//子ノードへのポインタを、方向指示に対応して現ノードの左右ポインタのどちらかに入れる。
	if (direction == RIGHT)pNode->pRight = pChildNode;
	if (direction == LEFT)pNode->pLeft = pChildNode;

	//削除対象ノードのメモリ領域を解放する。
	delete pDeleteNode;
}
このコードで実行すると,削除対象ノードは削除されるのですが,削除対象ノードの子が削除ノードのあった位置に接続されません.
正しく出力されるには,削除する関数のコードをどのように直したら良いでしょうか?
教えてください.よろしくお願いします.

アバター
みけCAT
記事: 6235
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 木構造編集プログラムのノードの削除機能について

#2

投稿記事 by みけCAT » 4日前

「削除する関数」とは、deleteNode関数のことでしょうか?
だとすると、

コード:

	//方向指示に対応する左右ポインタから、削除対象ノードへのポインタを得る。
	Node* pDeleteNode=new Node;
	if (direction == RIGHT) pDeleteNode = pNode->pRight;
	if (direction == LEFT) pDeleteNode = pNode->pLeft;
のnew NodeをNULLに変えるといいでしょう。
なぜならば、ここで余計なノードを確保してしまうと、
その後の代入でメモリリークを起こす可能性がある上、
代入が行われない場合は不定のメンバを参照して変なことが起こる可能性があるからです。

修正したら、Dが入力された場合はcutNode関数ではなくdeleteNode関数を呼ぶようにするといいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

あや
記事: 21
登録日時: 2ヶ月前

Re: 木構造編集プログラムのノードの削除機能について

#3

投稿記事 by あや » 4日前

new NodeをNULLに変え、Dが入力された場合に、deleteNode関数を呼ぶように修正しましたが、削除対象ノードの子が削除ノードのあった位置に接続されません.
正しく出力されるには、他にコードをどのように直したら良いでしょうか?
教えてください.よろしくお願いします.

アバター
みけCAT
記事: 6235
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 木構造編集プログラムのノードの削除機能について

#4

投稿記事 by みけCAT » 4日前

2点の修正を加えて手元のVisual C++ 2008でコンパイルし、実行したところ、
以下の実行結果が得られ、削除対象ノードの子が削除ノードのあった位置に接続されること、
そして削除対象ノードに子が2個ある場合は削除されないことを確認できました。
► スポイラーを表示
ソースコードを直すだけでなく、
コンパイル・リンクを行ってそれを実行するバイナリコードに反映させると良いと考えられます。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

あや
記事: 21
登録日時: 2ヶ月前

Re: 木構造編集プログラムのノードの削除機能について

#5

投稿記事 by あや » 4日前

Visual Studio 2019でプログラムを作っているのですが、コンパイル・リンクを行ってそれを実行するバイナリコードに反映させるには、どのようにしたらよいのでしょうか?教えてください。よろしくお願いします。

かずま

Re: 木構造編集プログラムのノードの削除機能について

#6

投稿記事 by かずま » 3日前

あや さんが書きました:
4日前
Visual Studio 2019でプログラムを作っているのですが、コンパイル・リンクを行ってそれを実行するバイナリコードに反映させるには、どのようにしたらよいのでしょうか?教えてください。よろしくお願いします。
F7キーを押す。


返信

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