【C++データ構造学習ノート---リニアテーブル】先頭ノードの双方向ループチェーンテーブル

【C++データ構造学習ノート---リニアテーブル】先頭ノードの双方向ループチェーンテーブル
単純な実装例では,挿入関数および出力関数のみを用いて26文字の英字を初期化した.
挿入アルゴリズムの考え方:(insert)本アルゴリズムはノード後挿入
1、ノードpがヘッダノードを指すことを宣言し、iを0から初期化する.
2、チェーンテーブルを遍歴し、ポインタpを要素を挿入するノード、すなわちk回後方に移動させる.
4、ポインタqをpの右側のノードに向ける.
5、システムに新しいノードsを作成する.
次に、画像の考え方に従ってノードを挿入します.
削除アルゴリズムの考え方:(erase)本アルゴリズムはk番目のノードを削除する
1、ノードpがチェーンテーブルの最初のノードを指すことを宣言し、iを0から初期化する.
2、チェーンテーブルを巡回し、ポインタpを後方に移動させ、ノードを削除する前のノード、すなわちk-1回後方に移動させる.
3、ポインタqをpの右側のノードに向ける.
4、q=p->rightを実行する.p->right=q->right; q->right->left=q;ノードを削除します.

#include 
using namespace std;
template 
class List;
template 
class Node{
	friend class List;
private:
	T data;
	Node *left,*right;
};
template 
class List{
public:
	List();									//    
	~List();								//    
	bool empty()const{return header->right==header->left;}//       
	int size()const;						//      
	bool retrieve(int k,T& x)const;			//     k    x
	int locate(const T& x)const;			//    x      
	List& insert(int k,const T& x);		//   k     x
	List& erase(int k);					//   k     
	void print_list()const;					//   
private:
	Node *header;
};
template 
List::List()
{
	Node *p=new Node;
	header=p->left=p->right=p;
}
template 
List::~List()
{
	Node *p=0,*q=0;
	p=header->right;
	while(header->right==header->left){
		q=p->right;
		header->right=q;
		q->left=header;
		delete p;
		p=q;
	}
	delete header;
}

template 
int List::size()const
{
	Node *p=header->right;
	int len=0;
	while(p!=header){
		p=p->right;
		++len;
	}
	return len;
}
template 
bool List::retrieve(int k,T& x)const
{
	Node *p=header->right;
	int i=0;
	while(iright;
		++i;
	}
	x=p->data;
	return true;
}
template 
int List::locate(const T& x)const
{
	Node *p=header->right;
	int i=1;
	while((p!=header)){
		if (p->data==x) return i;
		p=p->right;
		++i;
	}
	return 0;
}
template 
List& List::insert(int k,const T& x)
{
	Node *p=0,*q=0;
	p=header;
	int i=0;
	while(iright;
		++i;
	}
	q=p->right;
	Node *s=new Node;
	s->data=x;
	s->right=p->right;
	s->left=q->left;
	p->right=s;
	q->left=s;
	return *this;
}
template 
List& List::erase(int k)
{
	Node *p=0,*q=0;
	p=header;
	int i=0;
	while(iright;
		++i;
	}
	q=p->right;
	p->right=q->right;
	q->right->left=q;
	delete q;
	return *this;
}
template 
void List::print_list()const
{
	Node *p=header->right;
	while(p!=header){
		cout <data <right;
	}
}
int main()
{
	int s1,s2;
	s1='A';
	s2='Z';
	List p;
	for(int i=s2; i>=s1; --i){
		p.insert(0,i);
	}
	p.print_list();
	return 0;
}