アルゴリズムの美しさソースコードリリース(3)

本論文は『アルゴリズムの美——データ構造の背後に隠れた言語』(電子工業出版社2016年出版)の第4章のコード(P 91~P 17)を収録している.全文目録、「45アルゴリズム」カタログ、「22つの経典問題リスト」、及び賞虫つかみ活動の詳細は下記のリンクをご覧ください.http://blog.csdn.net/baimafujinji/article/details/50484348
付録の中の経典筆記試験、面接問題の参考解答は以下の通りです.
http://blog.csdn.net/baimafujinji/article/details/50484683

シークレットアルゴリズムの世界、データ構造の道.経典の問題を集めて、プログラミングの技法の趣を楽しんでいます.就職活動のホットスポットを呼び出して、営業界の有名企業の門をたたく.この本はアルゴリズムとデータ構造という話題をめぐって、順を追って漸進的に、深く浅く近代的なコンピュータ技術でよく使われている四十余りの古典的アルゴリズムを紹介しました.この過程で、本書は、一方向リンク表、一方向循環チェーン表、双方向循環リンク表を含むリンク表、スタック、キュー(普通の列と優先列を含む)、ツリー(二叉樹、ハフマンツリー、ヒープ、赤黒い木、AVLツリー、辞書ツリーを含む)、図、集合(非交差を含む)、および辞書などの一般的なデータ構造を体系的に説明している.また、22の経典問題(ジョセフ環問題、ハノータ問題、八皇后問題、騎士周遊問題などを含む)について説明することによって、データ構造の背後に隠されたアルゴリズム原理を徐々に明らかにし、読者の知識準備を促進し、思考技術を活性化させ、プログラミング能力の向上を妨げる十重二十重の垣根を突き破ることができる.完全なC＋＋＋ソースコードを補間してSTLの様々な容器を紹介しました.
オンライン書店:
China-pub中国インタラクティブ出版ネット:http://product.china-pub.com/4911922
ネットに入れる:http://product.dangdang.com/23851244.html
アマゾン:http://www.amazon.cn/%E7%AE%97%E6%B3%95%E4%B9%8B%E7%BE%8E-%E 9%A%90%E 5%8 C%BF%E 5%9 C%A 8%E 6%B 0%E 6%E 6%E 6%8 D%E 7%BB%93%E 6%E 8%83%E 8%E 5%E 7%E 7%E 8%E 7%E 8%E 8%E 8%E 8%E 8%E 8%E 8%E 8%E 5%E 9%E 9%E 9%E 9%E 9%E 9%E 7%E 9%E 9%E 9%E 9%E 9%E 7%E 9%E 9%E 9%E 7%E 7%E 7%E 9%E 8%E 8%E 8%E 8%E 8%E 8%E 81_8ですか?ie=UTF 8&qid=1453527399&sr=8-8&keywords=%E 5%B 7%A 6%E 9%A 39 E
もしあなたが本の読者だったら、ぜひアルゴリズム学習群(495573865)を加えてください.中にはもっと多くの資源があります.あなたが本を読む中で出会った疑問も私の第一時間の解答を得られます.このブログにもっと注目してください.この本のソースコードを全部ブログに発表します.
P 94:チェーンノード類

// #ifndef _LISTNODE_H_
// #define _LISTNODE_H_

template <class T> class ListNode {
          
	T data;
	ListNode<T>*  link;

public:

	ListNode() : link(NULL){}
	ListNode (T value) : link(NULL) , data(value) {}
	~ListNode(){};
	void SetLink(ListNode<T>* next);
	void SetData(T value);
	ListNode<T>*  GetLink ();
	T& GetData ();
};

template <class T>
void ListNode<T>::SetLink(ListNode<T>* next){ 
	link = next;
}

template <class T>
void ListNode<T>::SetData(T value){
	data = value;
}

template <class T>
ListNode<T>* ListNode<T>::GetLink(){
	return link;
}

template <class T>
T&  ListNode<T>::GetData(){//        
	return data;
}

//#endif

P 96:チェーン類

 #ifndef _LIST_H_
 #define _LIST_H_

#include "ListNode.h"

template <class T> class List{

ListNode<T>* head;
ListNode<T>* tail;

public:

	List ();
	virtual ~List ();

	bool AddTail (T value);
	bool RemoveTail ();
	bool InsertAt (int index , T value);
	bool RemoveAt (int index);

	T& GetAt (int index);
	bool IsEmpty ();
	int GetCount ();
	void RemoveAll ();

	ListNode<T>* GetHead();
	ListNode<T>* GetTail();
	ListNode<T>* GetNodeAt(int index);
	ListNode<T>* GetCur();
	ListNode<T>* TowardCur();
};

template<class T>  
List<T>::List()  
{  
    head=new ListNode<T>();  
    tail=head;  
    tail->SetLink (NULL);  
} 

template<class T>  
List<T>::~List()  
{  
    RemoveAll();  
    delete head;  
} 

template <class T> 
bool List<T> :: AddTail (T value){ 
	ListNode<T>* add = new ListNode<T> (value);
	tail->SetLink (add);    	//         ，     
	tail = tail->GetLink();		//            
	tail->SetLink (NULL); 
	if (tail != NULL)
		return true;
	else  
		return false;
}

template <class T > 
bool List< T >::InsertAt ( int index,T value ) {
	//         
	if(index > this->GetCount ()-1 || index<0 ) {  
		cout<<"A wrong position!
";
		return false;
	}

	ListNode<T>* current = head; 		//          

	while(index) {
         current = current->GetLink ();  //     ，     cur
		 --index;
	}

	ListNode<T>* add = new ListNode<T> (value); 
	add->SetLink (current->GetLink ());           //         
	current->SetLink (add);

	if (current->GetLink () != NULL)
		return true;
	else
		return false;
}

template <class T> 
bool List<T>::RemoveTail() {//      
	//  RemoveAt（int index）  
	return RemoveAt(this->GetCount()-1);
}

template <class T> 
bool List<T>::RemoveAt(int index){ //         
	if(index > this->GetCount ()-1 || index<0){    
		cout<<"A wrong position!
";
		return false;
	}

	//             。  ，cur             
	//preCur        
	ListNode<T>* cur,* curPre;
	cur = head;                	//        index      
	curPre = cur->GetLink();    // preCur cur  

	while(index){
		cur = cur->GetLink();   //     ， cur  preCur    
		curPre = curPre->GetLink();
		--index;
	}

    //             ，  cur       
	if(tail == curPre)
		tail = cur;
	cur->SetLink (curPre->GetLink());  //            
	delete curPre;

	if(curPre != NULL)
		return true;
	else
		return false;
}

template <class T> 
T&  List<T>::GetAt(int index) {    //          value
	if (index > this->GetCount()-1 || index<0) {
		cout<<"A wrong position!
";
	}
	
	ListNode<T>* cur;
	cur = head->GetLink();
	while(index){            //     ，cur    
		cur = cur->GetLink();  
		--index;
	}
	return cur->GetData (); //       value
}

template <class T> 
bool List< T >::IsEmpty ( ) { //    
	return head ->GetLink()==NULL ;
}
 
template <class T> 
int List< T >::GetCount() {		//          （      ）
	int count = 0;             	// count      
	//            （      ）
	ListNode<T>* current = head->GetLink ( );
	while(current != NULL) { 
		++count; 
		current = current->GetLink ( );  //    cur 
	}
	return count;  
}

template <class T> 
void List< T >::RemoveAll() { //      
	ListNode<T>* cur;
    //             ，      
	while(head->GetLink() != NULL) {
		cur = head->GetLink(); 
		head->SetLink (cur->GetLink()); 
		delete cur;
	}
	tail = head; //       
}

template <class T> 
ListNode<T>* List<T>::GetHead(){//     
	return head;
}

template <class T> 
ListNode<T>* List<T>::GetTail(){//     
	return tail;
}

//        index       
template <class T > 
ListNode< T >* List< T >::GetNodeAt(int index){

	//         
	if(index > this->GetCount()-1 || index<0){
		cout<<"A wrong position!
";
	}  
	//handle       ，       index    。
	ListNode< T >* handle = head->GetLink();
	while(index){ //      index    
		handle = handle->GetLink();
		--index;
	}
	return handle;
}

template <class T> 
ListNode<T>* List<T>::GetCur(){
	return cur;
}

template <class T>  
ListNode<T>* List<T>::TowardCur(){
	cur = cur->GetLink();
	return cur
}

#endif

チェーンテストプログラム

#include "stdafx.h"
#include "List.h"
#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	List<int> list;
	for(int i = 0; i <9; i++)
		list.AddTail(i);

	cout<<list.GetCount()<<endl;

	cout<<list.GetAt(3)<<endl;

	list.RemoveAt(3);

	cout<<list.GetCount()<<endl;
	cout<<list.GetAt(3)<<endl;

	list.RemoveAll();
	cout<<list.GetCount()<<endl;

	system("PAUSE");
	return 0;
}

P 101:秩序チェーンの結合

#include "stdafx.h"
#include "List.h"
#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	//      listFirst, listSecond
	List<int> listFirst;
	List<int> listSecond;

	//     listFirst
	listFirst.AddTail(1);
	listFirst.AddTail(6);
	listFirst.AddTail(8);
	listFirst.AddTail(9);
	listFirst.AddTail(13);

	//     listSecond
	listSecond.AddTail(0);
	listSecond.AddTail(3);
	listSecond.AddTail(4);
	listSecond.AddTail(6);
	listSecond.AddTail(11);
	listSecond.AddTail(17);

	while (listSecond.GetCount() != 0){ // listSecond        
		int indexFirst = 0;
		//   listSecond            listFirst  
		// while          
		while (listSecond.GetAt(0)>listFirst.GetAt(indexFirst)){
			++indexFirst;
			//  listFirst      ，      
			if (indexFirst == listFirst.GetCount()){
				break;
			}
		}
		if (indexFirst == listFirst.GetCount()){//     listFirst    
			listFirst.AddTail(listSecond.GetAt(0));
			listSecond.RemoveAt(0);
		}
		else{//     listFirst    
			listFirst.InsertAt(indexFirst, listSecond.GetAt(0));
			listSecond.RemoveAt(0);
		}
	}

	ListNode<int> * curNode = listFirst.GetHead();
	while (curNode != listFirst.GetTail())
	{
		curNode = curNode->GetLink();
		cout << curNode->GetData() << endl;
	}
	

	system("PAUSE");

	return 0;
}

P 104:一方向循環チェーン類

//#ifndef _CIRLIST_H_
//#define _CIRLIST_H_

#include "ListNode.h"

template <class T > class CirList{

	ListNode<T>* head;
	ListNode<T>* tail;
	ListNode<T>* cur;

public :
	CirList();
	~CirList();

	bool AddTail(T value);
	void RemoveThis();
	void RemoveAll();
	void SetBegin();
	int GetCount();
	ListNode<T>* GetCur();

	bool IsEmpty();
	T GetNext();
};

template <class T >  
CirList<T>::CirList(){//       
	head = tail = new ListNode<T>; //    ，    head   tail 
	cur = head; 
	head->SetLink(head);
}

template <class T>  
CirList<T>::~CirList(){
	RemoveAll();
	delete head;
}

template <class T> 
bool CirList< T >::AddTail(T value){ //         
    //    ，     value 
	ListNode<T>* add = new ListNode<T>(value);

	tail->SetLink(add);			//        
	tail = tail->GetLink();		//  tail      
	tail->SetLink(head);		//         

	if(tail != NULL)
		return true;
	else
		return false;
}

template <class T> 
void CirList<T>::RemoveThis(){// cur        
	if(cur == head){
    	//    cur head  ，          ，    cur     
		//  。
	    cur = cur->GetLink();
	}
 
	//   preCur  cur     , node_del        
	ListNode<T>* node_del = cur;
	ListNode<T>* preCur = cur;
    //  cur     ，  preCur    
	for(int i=0;i<this->GetCount();i++){
	    preCur = preCur->GetLink();
	}

    // cur         cur    ，   cur     
	preCur->SetLink(cur->GetLink());
	delete node_del;
    //   cur        。
	cur = preCur->GetLink();
	preCur = NULL;
}

template <class T> 
void CirList< T >::RemoveAll(){//      
    SetBegin();//          
	int length = GetCount();//      
	for(int i=0;i<length;i++){ 
		RemoveThis();
	}
	cur = head;  // cur  head  
}

template <class T> 
void CirList< T >::SetBegin(){// cur  head  ，       
	cur = head;
}

template <class T> 
int CirList<T>::GetCount(){//      
	int num = 0;
	if (cur==NULL)
		this->SetBegin();
	ListNode<T>* here = cur;  //        
	while(cur->GetLink() != here){ //      ，      
		cur = cur->GetLink();
		++num;
	}
	//cur = cur->GetLink();// cur         
	cur = here;
	return 
		num;
}

template <class T> 
ListNode<T>* CirList< T >::GetCur(){//       cur
	return cur;
}

template <class T > 
bool CirList< T >::IsEmpty(){//        
	return 
		head->GetLink() == head;
}

//          ，  cur        
template <class T> 
T CirList< T >::GetNext(){
	if(cur == head){
        //      ，              
		cur = cur->GetLink();
	}
	T num = cur->GetData();	//    
	cur = cur->GetLink();	//    cur       
	return 	
	num; 
}

//#endif

P 107:ジョセフリング問題

#include "stdafx.h"
#include "CirList.h"
#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	CirList<int> jos; //        ，       
	
	//      1~15 ，     1~15   
	for(int i=1;i<16;i++){
		jos.AddTail(i);
	}

	jos.SetBegin();//         

	//         ，                
	//      14 
	int length = jos.GetCount();
	for(int i=1;i<length;i++)
	{
		for(int j=0;j<3;j++)
			jos.GetNext();
		jos.RemoveThis();
	}
	
	cout<<jos.GetNext()<<endl;

	system("PAUSE");
	return 0;
}

P 108:マジシャン発牌問題

#include "stdafx.h"
#include "CirList.h"
#include <iostream>
//#include "vld.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	CirList<int> poker;
	for(int i=0;i<13;i++){
		poker.AddTail(0);			//      ，  13    
	}
	cout<<poker.GetCount()<<endl;

	poker.SetBegin();
	poker.GetCur()->GetLink()->SetData(1);
	for(int i=2;i<14;i++){
		for(int j=0;j<i;j++){
			poker.GetNext();                //      
			if(poker.GetCur()->GetData() != 0){
				j--;			//         ，          
			}
		}
		poker.GetCur()->SetData(i);
	}

	poker.SetBegin();
	for(int i=0;i<13;i++){
		cout<<poker.GetNext()<<"*";
	}
	cout<<endl;

	system("PAUSE");
	return 0;
}

P 109:ラテン方陣問題

#include "stdafx.h"
#include "CirList.h"
#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	int num;
	cout<<"        (2<=N<=9):";
	cin>>num;
	CirList<int> latin;
	for(int i=1;i <= num; i++){
		latin.AddTail(i);				//      
	}

	latin.SetBegin();
	for(int i=1; i<=num; i++){
		for(int j=1; j<=num; j++){
			cout<<latin.GetNext()<<" ";	        //         
		}
		cout<<endl;
		latin.GetNext();				//             
	}

	system("PAUSE");
	return 0;
}

P 111:双方向循環チェーンノード類

#ifndef _DOULISTNODE_H
#define _DOULISTNODE_H

template <class T > class DouListNode{

	T data;
	DouListNode<T>* link;
	DouListNode<T>* prior;

public :

	DouListNode() : link(NULL),prior(NULL){}
	DouListNode(T value) : link(NULL),prior(NULL),data(value){}
	~DouListNode(){};
	void SetLink(DouListNode<T>* next);
	void SetPrior(DouListNode<T>* pre);
	DouListNode<T>* GetLink();
	DouListNode<T>* GetPrior();
	T& GetData();
};


template <class T > 
void DouListNode< T >::SetLink( DouListNode<T>* next ){ //  link  
	link = next;
}

template <class T > 
void DouListNode< T >::SetPrior( DouListNode<T>* pre ){ //  prior  
	prior = pre;
}

//                
template <class T > 
DouListNode<T>* DouListNode< T >::GetLink(){
	return link;
}

//                
template <class T > 
DouListNode<T>* DouListNode< T >::GetPrior(){
	return prior;
}

template <class T > 
T& DouListNode< T >::GetData(){//          
	return data;
}

#endif

P 14:双方向循環チェーン類

#ifndef _DOULIST_H
#define _DOULIST_H

#include "DouListNode.h"

template <class T> class DouList{
	DouListNode<T>* head;
	DouListNode<T>* tail;
	DouListNode<T>* cur;

public :
	DouList();
 	~DouList();

	bool AddTail(T value);
	bool AddHead(T value);
	void RemoveThis(bool direction);
	void RemoveAll();
	void SetBegin();
	int GetCount();
	void TowardCur();
	void BackCur();
	DouListNode<T>* GetCur();
	DouListNode<T>* GetHead();
	DouListNode<T>* GetTail();
	void InsertAfter(T value);

	bool IsEmpty();
	T GetNext();
	T GetPrior();
};


template <class T>  
DouList<T>::DouList(){//       

	//      ，    head    tail    
	head = tail = new DouListNode<T>; 
	cur = head; 
	head->SetLink(head); //      。
	head->SetPrior(tail);
}

template <class T>  
DouList<T>::~DouList(){
	RemoveAll();
	delete head;
}

template <class T> 
bool DouList<T>::AddTail(T value){ //          

	//     ，        value   
	DouListNode<T>* add = new DouListNode<T>(value);
    tail->SetLink(add);  //               
	add->SetPrior(tail);  
	tail = tail->GetLink(); 
	tail->SetLink(head);  //           

	//              ，        
	head->SetPrior(add);
    //            ，     。
	if(tail != NULL){
		return true;
	}
	else 
		return false;
}

//                          
template <class T> 
bool DouList<T>::AddHead(T value){

    //     ，    value 
	DouListNode<T>* add = new DouListNode<T>(value);
	add->SetPrior(head);          
	add->SetLink(head->GetLink()); 

	//             add
        //  add           
	head->GetLink()->SetPrior(add);
	head->SetLink(add);      

 	//            ，        tail 
	if(tail == head){
		tail = head->GetLink();
	}
	if(add != NULL){
		return true;
	}
	else 
	    return false;
}

//   cur        ，   cur       direction   
template <class T>
void DouList<T>::RemoveThis(bool direction){
    //    cur      ，           ，    cur
    //      
	if(cur == head){
		//  direction==0，  link     cur
		if(direction == 0)
	    	cur = cur->GetLink();
		//  direction==1，  prior      cur
		if(direction == 1)
			cur = cur->GetPrior();
	}
	
 	//    preCur   nextCur。
	//preCur   cur      
	//nextCur    cur      
	DouListNode<T>* preCur = NULL;
	DouListNode<T>* nextCur = NULL;
	preCur = cur->GetPrior();        
	nextCur = cur->GetLink(); 
	DouListNode<T>* node_del = cur;
	preCur->SetLink(cur->GetLink());  // cur              
	nextCur->SetPrior(cur->GetPrior()); // cur             
 
    //  direction     cur      
    // direction ==0，  link     cur 
	if(direction == 0)
		cur = nextCur;
	// direction ==1，  prior     cur
	if(direction == 1)
		cur = preCur;
	delete node_del;
}

template <class T > 
void DouList<T>::RemoveAll(){//      （      ）

	SetBegin();            //      
	int length = GetCount();  //        
	for(int i=0;i<length;i++){ //    
		RemoveThis(0);
	}
	cur = head;
}

template <class T > 
void DouList<T>::SetBegin(){// cur     
	cur = head;
}

//           (      )
template <class T > 
int DouList<T>::GetCount(){
	int num = 0;   //         
	DouListNode<T>* here = cur; // here           
	while(cur->GetLink() != here){ //    
		cur = cur->GetLink();
		++num;
	}

	cur = cur->GetLink();    //     ， cur      
	//      
	return num;
}

template <class T> 
void DouList<T>::TowardCur(){// cur link    
	cur = cur->GetLink();
}

template <class T > 
void DouList<T>::BackCur(){// cur prior    
	cur = cur->GetPrior();
}

template <class T > 
DouListNode<T>* DouList<T>::GetCur(){//    cur 
	return 
		cur;
}

template <class T > DouListNode<T>* DouList<T>::GetHead(){
	return 
		head;
}

template <class T > DouListNode<T>* DouList<T>::GetTail(){
	return 
		tail;
}

//        。
template <class T > 
bool DouList<T>::IsEmpty(){
	//                
	return 
		head->GetLink() == head;
}

// cur                value     
//            ，     AddTail（ T value ）
template <class T > 
void DouList<T>::InsertAfter(T value){

	DouListNode<T>* add = new DouListNode<T>(value);
	DouListNode<T>* nextCur = cur->GetLink();  //  cur      
	cur->SetLink(add);    // cur             
	add->SetLink(nextCur); 
    nextCur->SetPrior(add); // cur             
	add->SetPrior(cur);   

	if(cur==tail){
		tail = cur->GetLink();
	}
}

//  cur         ，  cur  link     
template <class T > 
T DouList<T>::GetNext(){
    //  cur     ，     cur
	if(cur == head){
		cur = cur->GetLink();
	}
	T num = cur->GetData();  //          
	cur = cur->GetLink();//       cur（link   ）
	return 	
		num;
}

//  cur         ，  cur  prior     
template <class T > 
T DouList<T>::GetPrior(){
	//  cur     ，     cur
	if(cur == head){
		cur = cur->GetPrior();
	}
	T num = cur->GetData(); //          
	cur = cur->GetPrior();   //       cur (prior   )
	return 
		num;
}

#endif

P 115:バージニア暗号化問題

#include "stdafx.h"
#include "DouListNode.h"
#include "DouList.h"
#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	DouList<char> planText;
	DouList<char> cryptograph;
	DouList<int> key;
	DouList<char> trans;
	planText.SetBegin();
	planText.AddTail('y');
	planText.AddTail('o');
	planText.AddTail('u');
	planText.AddTail('a');
	planText.AddTail('r');
	planText.AddTail('e');
	planText.AddTail('i');
	planText.AddTail('n');
	planText.AddTail('d');
	planText.AddTail('a');
	planText.AddTail('n');
	planText.AddTail('g');      
	planText.AddTail('e');
	planText.AddTail('r');

	planText.SetBegin();
	cout<<"  :"<<'\t';
        for(int z=0;z<planText.GetCount();z++){
		cout<<planText.GetNext()<<" ";
	}
	cout<<endl<<endl;

       key.SetBegin(); //      
       for(int i=0;i<6;i++){
	   key.AddTail(1+rand()%9);
       }

	cout<<"  :"<<'\t';
	for(int i=0;i<key.GetCount();i++){
		cout<<key.GetNext()<<" ";
	}
	cout<<endl<<endl;

	planText.SetBegin();
	key.SetBegin();
	cryptograph.SetBegin();
	for(int i=0;i<planText.GetCount();i++){

		char c = planText.GetNext();
		int num = key.GetNext();
		if('a'<=c&&c<='z'-num)
			c=c+num;
		else if('z'-num<c&&c<='z')
			c = c+num-1-'z'+'a';
		cryptograph.AddTail(c);
	}

	cryptograph.SetBegin();
	cout<<"  :"<<'\t';
        for(int j=0; j<cryptograph.GetCount(); j++){
		cout<<cryptograph.GetNext()<< " ";
	}
	cout<<endl<<endl;

	trans.SetBegin();
	planText.SetBegin();
	key.SetBegin();
	for(int k=0; k<planText.GetCount(); k++){


		char c = cryptograph.GetNext();
		int num = key.GetNext();
		if('a'<=c-num && c-num<='z')
			c=c-num;
		else if('a'>c-num && c>='a')
			c = 'z'-('a'-c+num)+1;

		cryptograph.AddTail(c);
		trans.AddHead(c);
	}

	trans.SetBegin();
	cout<<"  :"<<'\t';
        for(int k=0;k<trans.GetCount();k++){
		cout<<trans.GetPrior()<<" ";
	}
	cout<<endl<<endl;

	system("PAUSE");
	return 0;
}