プログラマ専用SNS ミクプラ

コード:

#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;
}