データ構造の双方向サイクルチェーン操作4-(挿入、削除、確立など)

//         ，              
//                   

#include 
#include 

using namespace std;

template
struct Node{		//  
	T data;
	Node *next;		
	Node *prior;
};

template
class BcirList{
private:
	Node *head = NULL;		//   
public:
	BcirList();				//       (    )
	~BcirList();			//      
	void CreateBcirList(int n);		//     n     
	void Insert(int i, T e);	// i     e
	T Delete(int i);			//  i        
	void Clear();				//    (     )
	void  BcirListTraverse();	//       
};

//       (    )
template
BcirList::BcirList()
{
	head = new Node;
	if (!head)
		cout << "       
";
	head->next = head;
	head->prior = head;
}

//     n     
template
void BcirList::CreateBcirList(int n)
{
	cout << "     :";
	//s         ，p       ，t       
	Node *p = head, *s = NULL, *t = head;
	for (int i = 0; i < n; ++i)
	{
		s = new Node;
		cin >> s->data;
		p->next = s;
		s->prior = p;
		t->prior = s;
		s->next = t;
		p = s;		//p      
	}
}

// i     e
template
void BcirList::Insert(int i, T e)
{
	Node *p = head->next, *s = NULL;
	int j = 1;
	while (p != head && j < i)
	{
		j++;
		p = p->next;		//           
	}
	if (p == head || j > i)
		throw "       
";
	s = new Node;
	if (!s)
		throw "       
";
	s->data = e;
	s->prior = p->prior;
	s->next = p;
	p->prior->next = s;
	p->prior = s;
}

//  i        
template
T BcirList::Delete(int i)
{
	Node *p = head->next, *s = NULL;
	int j = 1, e = 0;
	while (p != head && j < i)
	{
		j++;
		p = p->next;		//           
	}
	if (p == head || j > i)
		throw "       
";
	s = p;	//        
	e = p->data;
	p->next->prior = p->prior;
	p->prior->next = p->next;
	delete s;	//          

	return e;
}

//       
template
void  BcirList::BcirListTraverse()
{
	Node *p = head->next;
	while (p != head)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

//    (     )
template
void BcirList::Clear()
{
	Node *p = head->next, *s = NULL;
	while (p != head)
	{
		s = p;
		p = p->next;
		delete s;
	}
	p->next = head;
	p->prior = head;
}

//      
template
BcirList::~BcirList()
{
	Node *p = head->next, *s = NULL;
	while (p != head)
	{
		s = p;
		p = p->next;
		delete s;
	}
	delete head;
}

int main()
{
	BcirList b1;
	int i = 0, j = 0;
	cout << "              :";
	cin >> i;
	b1.CreateBcirList(i);
	cout << "     :";
	b1.BcirListTraverse();
	cout << "            :";
	cin >> i >> j;
	b1.Insert(i, j);
	cout << "     :";
	b1.BcirListTraverse();
	cout << "          :";
	cin >> i;
	cout << "     :" << b1.Delete(i) << endl;
	cout << "     :";
	b1.BcirListTraverse();

	system("pause");
	return 0;
}