アルゴリズムの美しさ:C++一方向チェーンテーブルADTを実現する

ヘッダファイルlist.h

#pragma once
#include 
using namespace std;
//ListNode 
template <class T>
class ListNode {
public:
	ListNode() :link(NULL) {}        //      
	ListNode(T value) :link(NULL), data(value) {}   //      
	~ListNode() {};
	void SetLink(ListNode<T>* next);   //   next            link
	void SetData(T value);
	ListNode<T>* GetLink();    //         link
	T& Getdata();
private:
	T data;
	ListNode<T>* link;
};
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;
}
//List 
template <class T>
class List {
public:
	List();
	~List();
	//           
	bool AddTail(T value);
	//      
	bool RemoveTail();
	//     index              value   
	bool InsertAt(int index, T value);
	//        index       
	bool RemoveAt(int index);
	//    index              data 
	T& GetAt(int index);
	//         
	bool IsEmpty();
	//            
	int GetCount();
	//          
	void RemoveAll();
	//             
	void printAll();
	//        
	ListNode<T>* GetHead();
	//        
	ListNode<T>* GetTail();
	//       index       
	ListNode<T>* GetNodeAt(int index);
	//    cur
	ListNode<T>* GetCur();
	// cur        ，       cur
	ListNode<T>* TowardCur();
private:
	ListNode<T>* head;
	ListNode<T>* tail;
};
//           
template <class T>
bool List<T>::AddTail(T value) {
	ListNode<T>* address = new ListNode<T>(value);
	//         ，     
	tail->SetLink(address);
	//           
	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!" << endl;
		return false;
	}
	//         
	ListNode<T>* current = head;
	while (index) {
		//      ，     cur
		current = current->GetLink();
		--index;
	}
	ListNode<T>* address = new ListNode<T>(value);
	//         
	address->SetLink(current->GetLink());
	current->SetLink(address);
	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!" << endl;
		return false;
	}
	//             ，  ，cur             
	//preCur        
	ListNode<T>* cur, * preCur;
	cur = head;
	// preCur cur 
	preCur = cur->GetLink();
	while (index) {
		cur = cur->GetLink();
		preCur = preCur->GetLink();
		--index;
	}
	//              ，  cur      
	if (tail == preCur) {
		tail = cur;
	}
	//            
	cur->SetLink(preCur->GetLink());
	delete preCur;
	if (preCur != NULL) {
		return true;
	}
	else {
		return false;
	}
}
//      ，    head tail
template <class T>
List<T>::List() {
	head = new ListNode<T>();
	tail = head;
	tail->SetLink(NULL);
}
template <class T>
List<T>::~List() {
	RemoveAll();
	delete head;
}
//         value
template <class T>
T& List<T>::GetAt(int index) {
	if (index > this->GetCount() - 1 || index < 0) {
		cout << "A wrong position!" << endl;
	}
	ListNode<T>* cur;
	cur = head->GetLink();
	while (index) {
		cur = cur->GetLink();
		--index;
	}
	return cur->Getdata();
}
//    
template <class T>
bool List<T>::IsEmpty() {
	return head->GetLink() == NULL;
}
//            
template <class T>
int List<T>::GetCount() {
	int count = 0;
	ListNode<T>* current = head->GetLink();
	while (current != NULL) {
		++count;
		current = current->GetLink();
	}
	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;  //       
}
//      Index      
template <class T>
ListNode<T>* List<T>::GetNodeAt(int index) {
	if (index > this->GetCount() - 1 || index < 0) {
		cout << "A wrong position!" << endl;
	}
	//handle      ，        index   
	ListNode<T>* handle = head->GetLink();
	while (index) {
		handle = handle->GetLink();
		--index;
	}
	return handle;
}
//             
template <class T>
void List<T>::printAll() {
	int count;
	int index = 0;
	ListNode<T>* ptr;
	count = this->GetCount();
	while (count) {
		ptr = GetNodeAt(index);
		printf("%d ", ptr->Getdata());
		--count;
		++index;
	}
	return;
}

main関数テストプログラム

//         
//    listSecond       ，        listFirst      
#include "list.h"
int main() {
	//      
	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);
	// listSecond       
	while (listSecond.GetCount() != 0) {
		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);
		}
	}
	listFirst.printAll();
	return 0;
}