C++における単一チェーンテーブルの作成と操作

11521 ワード
データ構造 C++ チェーン？テーブル
データの準備
チェーンテーブル操作で使用する変数およびデータ構造の準備
サンプルコードは次のとおりです.
struct Data			//       
{
	string key;		//    
	string name;
	int age;
};
struct CLType		//       
{
	Data nodeData;
	CLType *nextNode;
};

 
チェーンテーブルデータ要素のタイプDataおよびチェーンテーブルのデータ構造CLTypeを定義します.ノードの特定のデータは構造データに保存され、ポインタnextNodeは次のノードを指すために使用されます.
このチェーンテーブルはクラスの学生の記録であり,keyは学号を表し,nameは学生の名前,ageは年齢であると考えられる.
ノードの追加
追加ノードはチェーンテーブルの末尾にノードを追加します.表末尾ノードのアドレス部分は元々空のアドレスNULLが保存されていたが、この場合は新規ノードのアドレス(すなわち、元の表末尾ノードが新規ノードを指す)に設定し、新規ノードのアドレス部分を空のアドレスNULL、すなわち新規ノードが表末尾に設定する必要がある.
一般に、チェーンテーブルにはヘッダポインタheadが1つしかないため、最後にノードを追加するには、最後のノード(すなわちテーブルの最後)が見つかるまで、ヘッダheadから個々のチェックを開始する必要があります.
ノードを追加する手順は次のとおりです.
(1)まずメモリアドレスを割り当て,新規ノードを保存する.
(2)最後のノード(すなわち表末尾)が見つかるまで、先頭ポインタheadから1つずつチェックを開始する.
(3)表末尾ノードのアドレスを新規ノードのアドレスに設定する.
(4)新規ノードのアドレス部分を空アドレスNULLとし,すなわち新規ノードが表末尾となる.
サンプルコードは次のとおりです.
CLType * CLAddEnd(CLType *head,Data nodeData)
{
	CLType *node,*htemp;
	if(!(node = new CLType))
	{
		cout<<"      ！"<<endl;		//       
		return NULL; 
	}
	else
	{
		node->nodeData = nodeData;			//       
		node->nextNode = NULL; 				//        ，      
		if(head == NULL)						//          
		{
			head = node;
			return head;
		}
		htemp = head;
		while(htemp->nextNode != NULL)			//       
		{
			htemp = htemp->nextNode;	
		}
		htemp->nextNode = node;
		return head; 
	} 
	
}

入力パラメータheadはチェーンヘッダポインタ、入力パラメータnodeDataはノードに保存されたデータです.プログラムではnewキーを使用してダイナミックスペースを申請し、内部割り当てに成功するとnodeにメモリ領域へのポインタが保存されます.
次に、入力されたnodeDataを申請のメモリ領域に保存し、次のノードへのポインタ値をNULLに設定します.
ヘッドノードの挿入
ヘッダノードの挿入とは、チェーンテーブルのヘッダにノードを追加するプロセスであり、テーブルの最後にノードを挿入するのとは逆に、ヘッダにノードを挿入し、ヘッダノードとして使用します.
ヘッダノードを挿入するには、次の手順に従います.
(1)まずメモリを割り当て,新しいノードを保存する.
(2)新たな姉弟の頭の針headを指す接点を
(3)次にヘッダポインタheadを新規ノードに向ける
サンプルコードは次のとおりです.
CLType *CLAddFirst(CLType *head,Data nodeData)
{
	CLType *node;
	if(!(node = new CLType))
	{
		cout<<"      "<<endl;
		return NULL;
	}
	else
	{
		node->nodeData = nodeData;		//       
		node->nextNode = head;		//            
		head = node;			//          
		return head;
	} 
}

 
入力パラメータheadはチェーンヘッダポインタ、入力パラメータnodeDataはノードに保存されているデータです.プログラムではまずnewキーを使用して新しいセーブポイントのメモリ領域を申請し、申請に成功するとnodeはメモリ領域へのポインタを保存します.
次に、入力されたnodeDataを申請のメモリ領域に保存し、新しいノードがヘッダポインタheadが指すノードを指し、ヘッダポインタheadが新しいノードを再び指すように設定します.
ノードの検索
ノードの検索とは、チェーンテーブル構造で必要な要素を検索することです.チェーンテーブル構造では、一般に、ノード番号で検索するクラスとキーワードで検索するクラスに分けられます.
ノード番号によるクエリー
つまり、チェーンテーブルのノードの数をクエリーします.その例のコードは次のとおりです.
CLType *CLFindNodeNum(CLType *head,int k)
{
	CLType *htemp;
	int i = 1;
	htemp = head;						//        
          for(i = 1;i<k&&htemp;i++)					//      
          {
    	   htemp = htemp->nextNode;
         }
          return htemp;						//     k       
}

入力パラメータheadはチェーンヘッダポインタであり、入力パラメータkはクエリーするノードのシーケンス番号である.シーケンス番号で複数回ループし、そのノードを指すポインタを取得し、ポインタを返します.
キーワードによるクエリー
すなわち、チェーンテーブルのノードのキーワードに基づいてクエリーを行い、学生の名前(name)をクエリーする例では、次のコードの例を示します.
CLType *CLFindNodeKey(CLType *head,string name)
{
	CLType * htemp;
	htemp = head;							//        
	while(htemp)
	{
		if(htemp->nodeData.name == name)	//               
		{
			return htemp;				//        
		}
		htemp = htemp->nextNode; 
	}
	return NULL; 
}

入力パラメータheadはチェーンヘッダポインタ、入力パラメータnameはクエリーする同級生の名前です.すべての学生の名前を検索し、検索した名前と同じノードの名前がある場合は、そのノードのポインタを返します.
ノードの挿入
ノードを挿入すると、チェーンテーブルの中間部分の位置にノードが追加されます.
ノードを挿入するには、次の手順に従います.
(1)メモリ領域を割り当て,新規ノードを保存する.
(2)挿入する論理位置,すなわちそのノードの後ろに挿入する論理位置を見つける.
(3)挿入位置ノードのポインタを修正し、新規ノードを指し、新規ノードが元の挿入位置が指すノードを指すようにする.
サンプルコードは次のとおりです.
CLType *CLInsertNode(CLType *head,int k,Data nodeData)
{
	CLType *node,*nodetemp;
	if(!(node = new CLType))				//     
	{
		cout<<"      "<<endl;
		return NULL; 
	} 
	else
	{
		node->nodeData = nodeData;		//        
		nodetemp=CLFindNodeNum(head,k-1);//                      （    ） 
		if(nodetemp)
		{
			node->nextNode = nodetemp->nextNode;//                  
			nodetemp->nextNode = node;		  //          
		} 
		else
		{
			cout<<"           "<<endl;
			delete node;
		}
	} 
	return head;						//      
}

入力パラメータheadはチェーンテーブルヘッダポインタ、入力パラメータfindkeyはチェーンテーブルで検索するノードキーであり、このノードを見つけた後、そのノードの後ろにノードデータを追加し、nodeDataは新しいノードのデータである.プログラムではまずnewを使用してノード空間を申請し、CLFindNodeNum関数を呼び出してノードを検索し、挿入操作を実行します.
ノードの削除
削除ノードとは、チェーンテーブル内のノードデータを削除することであり、その位置前後のノードには影響しません.
ノードを削除するには、次の手順に従います.
(1)削除するノードを検索する.
(2)前のノードを現在のノードの次のノードに向ける.
(3)このノードを削除する
削除ノードは、削除するノードをノードのシーケンス番号で決定したり、削除するノードをノードのキーワードで決定したりすることができます.
キーワードによるノードの削除を例にとると、次のようなコードがあります.
int CLDeleteNode(CLType *head,string name)
{
	CLType *node,*htemp;				//node            
	htemp = head;
	node =  head;
	while(htemp)
	{
		if(htemp->nodeData.name == name)//     ，       
		{
			node->nextNode = htemp->nextNode;//                
			delete htemp;					//        （ ，     ）
			return 1; 
		}
		else
		{
			node = htemp;					//       
			htemp = htemp->nextNode;		//        
		} 
	} 
	 return 0;								//     
}

 
headはチェーンヘッダポインタであり,パラメータnameを入力して削除する同級生の名前を表す.プログラムでは、削除するノードをキーワードでチェーンテーブル全体で検索します.削除されたノードが見つかった場合、前のノード(nodeポインタが指すノード)が現在のノード(hポインタが指すノード)の次のノードを指すように設定されます.すなわち、論理的にノードを削除し、そのノードに対してdelete操作を実行し、ノードが使用するメモリ領域を解放します.つまり、物理的に削除します.
チェーンテーブルの長さの計算
チェーンテーブルの長さを計算します.つまり、チェーンテーブル内のノードの数を統計します.シーケンステーブルではチェーンテーブルの長さを計算するのが便利ですが、チェーンテーブルは物理的に連続的に格納されていないため、チェーンテーブルの長さはチェーンテーブルを巡回することによって得る必要があります.
サンプルコードは次のとおりです.
int CLLength(CLType *head)
{
	CLType *htemp;
	int Len = 0;
	htemp = head;
	while(htemp)							//      
	{
		Len++;								//       
		htemp = htemp->nextNode; 			//        
	} 
	return Len;
}

 
パラメータheadはチェーンテーブルのヘッダポインタであり,プログラムではwhileによりポインタを遍歴し,Lenはカウンタとしてループの回数を記録することでチェーンテーブルの長さを求め,ポインタがNULLのときにカットオフし,カウンタの値を返す.
すべてのノードを表示
すべてのノードを巡り、出力します.
void CLAllNode(CLType *head) 
{
	CLType *htemp;
	htemp = head;
	while(htemp)							//      
	{
		nodeData = htemp->nodeData;			//       
		cout<<"key:"<<nodeData.key<<",name:"<<nodeData.name<<",age:"<<nodeData.age<<endl; 
		htemp = htemp->nextNode; 			//        
	} 
}

 
出力ノードの関数は、戻り値がなく、voidとして定義されています.毎回CLTypeタイプのノードからnodeDataの値を取得する
チェーンテーブル操作の完全な例
完全な例のコードは長いので、辛抱強く見てください......:)
#include<iostream>
#include<string>
using namespace std;
struct Data			//       
{
	string key;		//    
	string name;
	int age;
};
struct CLType		        //       
{
	Data nodeData;
	CLType *nextNode;
};
CLType * CLAddEnd(CLType *head,Data nodeData)
{
	CLType *node,*htemp;
	if(!(node = new CLType))
	{
		cout<<"      ！"<<endl;		//       
		return NULL; 
	}
	else
	{
		node->nodeData = nodeData;	        //       
		node->nextNode = NULL; 		//        ，      
		if(head == NULL)			//          
		{
			head = node;
			return head;
		}
		htemp = head;
		while(htemp->nextNode != NULL)	//       
		{
			htemp = htemp->nextNode;	
		}
		htemp->nextNode = node;
		return head; 
	} 
	
}
CLType *CLAddFirst(CLType *head,Data nodeData)
{
	CLType *node;
	if(!(node = new CLType))
	{
		cout<<"      "<<endl;
		return NULL;
	}
	else
	{
		node->nodeData = nodeData;		//       
		node->nextNode = head;		//            
		head = node;			//          
		return head;
	} 
} 
CLType *CLFindNodeNum(CLType *head,int k)
{
	CLType *htemp;
	int i = 1;
	htemp = head;				//        
    for(i = 1;i<k&&htemp;i++)			//      
    {
    	htemp = htemp->nextNode;
    }
    return htemp;					//     k       
} 
CLType *CLFindNodeName(CLType *head,string name)
{
	CLType * htemp;
	htemp = head;				//        
	while(htemp)
	{
		if(htemp->nodeData.name == name)	//               
		{
			return htemp;		//        
		}
		htemp = htemp->nextNode; 
	}
	return NULL; 
} 
CLType *CLInsertNode(CLType *head,int k,Data nodeData)
{
	CLType *node,*nodetemp;
	if(!(node = new CLType))			//     
	{
		cout<<"      "<<endl;
		return NULL; 
	} 
	else
	{
		node->nodeData = nodeData;		//        
		nodetemp=CLFindNodeNum(head,k-1);    //                      （    ） 
		if(nodetemp)
		{
			node->nextNode = nodetemp->nextNode;  //                  
			nodetemp->nextNode = node;		  //          
		} 
		else
		{
			cout<<"           "<<endl;
			delete node;
		}
	} 
	return head;					 //      
} 
int CLDeleteNode(CLType *head,string name)
{
	CLType *node,*htemp;				//node            
	htemp = head;
	node =  head;
	while(htemp)
	{
		if(htemp->nodeData.name == name)             //     ，       
		{
			node->nextNode = htemp->nextNode;  //                
			delete htemp;			//        （ ，     ）
			return 1; 
		}
		else
		{
			node = htemp;			//       
			htemp = htemp->nextNode;		//        
		} 
	} 
	 return 0;					//     
} 
int CLLength(CLType *head)
{
	CLType *htemp;
	int Len = 0;
	htemp = head;
	while(htemp)					//      
	{
		Len++;					//       
		htemp = htemp->nextNode; 			//        
	} 
	return Len;
} 
void CLAllNode(CLType *head) 
{
	CLType *htemp;
	Data nodeData; 
	htemp = head;
	cout<<"     ："<<CLLength(head)<<endl;
	while(htemp)					//      
	{
		nodeData = htemp->nodeData;			//       
		cout<<"key:"<<nodeData.key<<",name:"<<nodeData.name<<",age:"<<nodeData.age<<endl; 
		htemp = htemp->nextNode; 			//        
	} 
}
int main()
{
	CLType *node,*head = NULL;
	Data nodeData;
	string name;
	int k;
	cout<<"          ，   ：  ，  ，  （   0     ）"<<endl;
	while(1)
	{
		cin>>nodeData.key>>nodeData.name>>nodeData.age;
		if(nodeData.age==0)break;
		head=CLAddEnd(head,nodeData);		//           
	}
	CLAllNode(head);					//       
	//          
	cout<<"       ，         "<<endl;
	cin>>nodeData.key>>nodeData.name>>nodeData.age;
	head=CLAddFirst(head,nodeData);
	CLAllNode(head);
	//             
	cout<<"               ："<<endl; 
	cin>>nodeData.key>>nodeData.name>>nodeData.age;
	cout<<"         ：";
	cin>>k;
	head=CLInsertNode(head,k,nodeData);
	CLAllNode(head);	
	//           
	cout<<"                ：";
	cin>>k;
	node=CLFindNodeNum(head,k);
	cout<<"        ："<<endl;
	cout<<"key:"<<node->nodeData.key<<",name:"<<node->nodeData.name<<",age:"<<node->nodeData.age<<endl;
	//           
	cout<<"                   ：";
	cin>>name;
	node=CLFindNodeName(head,name); 
	cout<<"        ："<<endl;
	cout<<"key:"<<node->nodeData.key<<",name:"<<node->nodeData.name<<",age:"<<node->nodeData.age<<endl;
	//         
	cout<<"               ，         ：";
	cin>>name;
	if(CLDeleteNode(head,name))cout<<"      ！"<<endl;
	CLAllNode(head);
	return 0; 
}

プログラム実行結果の例:
O(n)時間でソートが完了するバケットソートをHaskellで実装する (2)
O(n)時間でソートが終了するバケットソートをHaskellで実装する (1)