二分木における、部分木の移動・コピーを行う、プログラムを作っています。
長くなりますが、以下にソースを載せます。
このプログラムで、ビルドは通るのですが、移動やコピーを実行させたとき、
「問題が発生したため、プログラムが正しく動作しなくなりました。」のように表示がでます。
どのあたりが原因なのか、わからない状態です。教えていただけると嬉しいです。
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
#define LINELENGTH 80 //一行の長さ
#define END 'E' //終了
#define ADD 'A' //追加
#define LEFT 'L' //左
#define RIGHT 'R' //右
#define MOVE 'M' //移動
#define COPY 'C' //コピー
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 showHelp();
void moveNode(int fromNodeNo, char fromDirection, int toNodeNo, char toDirection);
void copyNode(int fromNodeNo, char fromDirection, int toNodeNo, char toDirection);
Node* copyNodeRecursive(Node* pFromNode) ;
Node* pRoot; //根ノードを参照するポインタ
int nodeCounter; //ノードの番号付けカウンタ
//
//----メイン関数-------
//
void main()
{
char commandLine[LINELENGTH]=""; //コマンド行(文字配列）
char command=' '; //コマンド文字
char word[LINELENGTH]=""; //単語（文字配列）
char direction=LEFT; //方向指示
int nodeNo; //ノード番号
int fromNodeNo;
char fromDirection=LEFT;
int toNodeNo;
char toDirection=LEFT;
//根ノードを生成して、その参照を根ノードポインタに入れる。
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 MOVE:
//コマンド行から、コマンド、移動元ノード番号、移動元方向指示、移動先ノード番号、
//移動先方向指示を取り出せたら、移動を実行する。
if(sscanf_s(commandLine, "%c %d %c %d %c", &command, 1, &fromNodeNo, &fromDirection, &toNodeNo, &toDirection,1) == 5){
moveNode(fromNodeNo, fromDirection, toNodeNo, toDirection);
}
break;
//コマンドが「コピー」であれば、以下を実行する。
case COPY:
//コマンド行から、コマンド、コピー元ノード番号、コピー元方向指示、コピー先ノード番号、
//コピー先方向指示を取り出せたら、コピーを実行する。
if(sscanf_s(commandLine, "%c %d %c %d %c", &command, 1, &fromNodeNo, &fromDirection, &toNodeNo, &toDirection, 1)==5){
copyNode(fromNodeNo, fromDirection, toNodeNo, toDirection);
}
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 showHelp()
{
//コマンド一覧を表示する。
cout<<"A word n L|R = Add：wordをn番の左(L)または右(R)に追加" <<endl;
cout<<"X n L|R = Cut：n番の(L)または右(R)を切り取り" <<endl;
cout<<"I word n L|R = Insert:単語wordをn番ノードの左（L）または右（R）に挿入" << endl;
cout<<"D n L|R = Delete:n番ノードの左（L）または右（R）の子ノードを削除" << endl;
cout<<"M n L|R m L|R = MOVE:n番ノードの左（L）または右（R）の子以下を、m番ノードの左（L）または右（R）に移動" << endl;
cout<<"C n L|R m L|R = n番ノードの左（L）または右（R）の子以下を、m番ノードの左（L）または右（R）にコピー" << endl;
cout<<"E = End：プログラムを終了" <<endl;
}
//
//-----部分木を移動する-----
//
void moveNode(int fromNodeNo, char fromDirection, int toNodeNo, char toDirection){
Node* fromNode;
Node* toNode;
//移動元ノード番号に対応するノードを探索してポインタを得る。
fromNode = searchNode(fromNodeNo);
//ポインタがNULLならば探索失敗なので戻る。
if(fromNode == NULL) return;
//移動元方向指示に対応する左右ポインタがNULLならば、移動元がないので戻る。
if(fromDirection == LEFT && fromNode->pLeft == NULL) return;
if(fromDirection == RIGHT && fromNode->pRight == NULL) return;
//移動先ノード番号に対応するノードを探索してポインタを得る。
toNode = searchNode(toNodeNo);
//ポインタがNULLならば探索失敗なので戻る。
if(toNode == NULL) return;
//移動先方向指示に対応する移動先ノード左右ポインタがNULLでないならば、移動先が空いていないので戻る。
if(toDirection == LEFT && toNode->pLeft != NULL) return;
if(toDirection == RIGHT && toNode->pRight != NULL) return;
//移動先方向指示に対応する移動先ノード左右ポインタに、移動元方向指示に対応する
//移動元ノード左右ポインタの値を移動して、元をNULLにする。
if(fromDirection == LEFT){
if(toDirection == LEFT){
toNode->pLeft = fromNode->pLeft;
fromNode->pLeft = NULL;
}
if(toDirection == RIGHT){
toNode->pRight = fromNode->pLeft;
fromNode->pLeft = NULL;
}
}
if(fromDirection == RIGHT){
if(toDirection == LEFT){
toNode->pLeft = fromNode->pRight;
fromNode->pRight = NULL;
}
if(toDirection == RIGHT){
toNode->pRight = fromNode->pRight;
fromNode->pRight = NULL;
}
}
}
//
//-----部分木のコピーをする-----
//
void copyNode(int fromNodeNo, char fromDirection, int toNodeNo, char toDirection){
Node* pFromNode;
Node* pToNode;
Node* newNode;
//コピー元ノード番号に対応するノードを探索してポインタを得る。
pFromNode = searchNode(fromNodeNo);
//ポインタがNULLならば探索失敗なので戻る。
if(pFromNode == NULL) return;
//コピー元方向指示に対応する左右ポインタがNULLならば、コピー元がないので戻る。
if(fromDirection == LEFT && pFromNode->pLeft == NULL) return;
if(fromDirection == RIGHT && pFromNode->pRight == NULL) return;
//コピー先ノード番号に対応するノードを探索してポインタを得る。
pToNode = searchNode(toNodeNo);
//ポインタがNULLならば探索失敗なので戻る。
if(pToNode == NULL) return;
//コピー先方向指示に対応するコピー先ノード左右ポインタがNULLでないならば、コピー先が空いてないので戻る。
if(toDirection == LEFT && pToNode->pLeft != NULL) return;
if(toDirection == RIGHT && pToNode->pRight != NULL) return;
//コピー元ノードの方向指示に対応する子ノードから再帰コピーを行い、新部分木を生成する。
if(fromDirection == LEFT) newNode = copyNodeRecursive(pFromNode->pLeft);
if(fromDirection == RIGHT) newNode = copyNodeRecursive(pFromNode->pRight);
//新部分木を、コピー先ノードの方向指示の方向につなぐ。
//（再帰コピーの戻り値が新部分木の根ノードを参照するので、これをコピー先方向指示に対応するコピー先ノード左右ポインタに入れる）。
if(toDirection == LEFT) pToNode->pLeft = newNode;
if(toDirection == RIGHT) pToNode->pRight = newNode;
}
//
//-----ノードの再帰コピーを行う-----
//
Node* copyNodeRecursive(Node* pFromNode){
Node* pToNode;
//コピー元ノードポインタがNULLならばNULLを戻す。
if(pFromNode == NULL) return NULL;
//コピー先ノードのメモリ領域を確保して、そのポインタを得る。
pToNode = new Node();
//コピー元ノードの単語をコピー先ノードに入れる。
pToNode->word = pFromNode->word;
//コピー元ノードの右ポインタについて再帰コピーを行い、戻り値をコピー先ノードの右ポインタに入れる。
pToNode->pRight = copyNodeRecursive(pFromNode->pRight);
//コピー元ノードの左ポインタについて再帰コピーを行い、戻り値をコピー先ノードの左ポインタに入れる。
pToNode->pLeft = copyNodeRecursive(pFromNode->pLeft);
//コピー先ノードのポインタを戻す。
return pToNode;
}
[2.1] OS ： Windows7
[2.2] コンパイラ名 ： VC++ 2010
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター