C++シングルチェーンテーブルの作成(ヘッダノードあり)

#ifndef chainWithHeader_
#define chainWithHeader_
#include
#include    //  
#include //STL    
#include  //istringstream 
#include//    
#include//   
#include//           
#include
#include
#include "chainNode.h"
using namespace std;
template
class chainWithHeader
{
public:
	 chainWithHeader(int initialCapacity=10);
	~chainWithHeader();



	bool empty() const { return listSize == 0; }
	int size() const { return listSize; }
	void insert(int theIndex, const T& theElement);
	void insertsort();
	void output(ostream& out)const;
	void bubblingSort();
	void selectionSort();
	void rankSort();
private:
	chainNode*headerNode;   //            
	int listSize;
};
template
chainWithHeader::chainWithHeader(int initialCapacity)
{
	if (initialCapacity<1)
	{
		ostringstream s;
		s << "Initial capacity= " << initialCapacity << "Must be>0";
		throw illegalParameterValue(s.str());
	}
	headerNode = new chainNode();
	headerNode->next= NULL;
	listSize = 0;
}
//    ，~chain(),  ，        
template
chainWithHeader::~chainWithHeader()
{
	while (headerNode->next!= NULL)
	{
		chainNode* nextNode = headerNode->next;
		delete headerNode;
		headerNode = nextNode;
	}
}
//    
template
void chainWithHeader::insert(int theIndex, const T& theElement)
{
	if (theIndex == 0)//        
		headerNode->next = new chainNode(theElement, headerNode->next);
	else
	{
		chainNode* p =headerNode->next;
		for (int i = 0; i < theIndex - 1; i++)
			p = p->next;
		p->next = new chainNode(theElement, p->next);
	}
	listSize++;
}
//    
template
void chainWithHeader::output(ostream& out)const
{
	for (chainNode*p = headerNode; p->next != NULL; p = p->next)
		out << p->next->element << " ";
}
//    
template
void chainWithHeader::insertsort()
{
	//       ，   1   ，    n-1   ，    
	chainNode*p= headerNode->next->next;     //p       ，          
	headerNode->next->next = NULL;              //        ，              
	chainNode*r,*q;
	while (p!= NULL)
	{
		r = p->next;                           //  p         
		q = headerNode;                        //     ，        
		while (q->next != NULL&&q->next->element<= p->element)  //    p       
			q = q->next;
		p->next = q->next;                                 //p->next  q->next  
		q->next = p;               //q->next  p   ，    p            headerNode         
		p = r;                                             //       
	}
}
//    （    ）
template
void chainWithHeader::bubblingSort()
{
	    chainNode*pr, *pt,*pb,*pf,*pd;//pd           ,pr          ，pt          
	    pb = headerNode;            //pb           
	    pr = headerNode->next;
	    pd = NULL;
		pf = headerNode;            //pf               
		bool swapped = true;        //                
		while (pf->next!=pd&&swapped)
		{
			pb = pf;                //pb           
			pr = pf->next;
			swapped = false;        //       
			while (pr->next!=pd)
			{
                pt = pr->next;
				if (pr->element > pt->element)//          ，   
				{
					pb->next = pt;
					pr->next = pt->next;
					pt->next = pr;
					swapped = true;
				}
				pb = pb->next;
				pr = pb->next;
			}
			pd = pr;//    
		}
}
//    （    ）
template
void chainWithHeader::selectionSort()
{
	chainNode*pd,*pf,*pe,*pa,*pmax;
	pf = headerNode;
	pd = NULL;
	bool sorted = false;                         //           
	while (pf->next->next!=pd&&!sorted)
	{
		pmax = pf;
		pa= pf->next;
		sorted = true;
		T temp;
		while (pa->next!= pd)
		{
			if (pmax->next->element<=pa->next->element)//      
				pmax= pa;
			else sorted = false;
	        pe = pa;                           //                 
			pa= pa->next;
		}
		/*pb = pe->next;
		pbmax = pmax->next;

		pmax->next = pb;
		pbmax->next = pb->next;
		pb->next = pbmax->next;
		pe->next = pbmax;*/
		temp = pmax->next->element;          //         
		pmax->next->element=pe->next->element;
		pe->next->element = temp;
        
		pd = pe->next;                             //     ，   
	}
}
//    
template
void chainWithHeader::rankSort()
{
	//   
	chainNode*p, *pr;
	p = headerNode->next->next;       //       
	int*r= new int[listSize]();   //    ,      0
	int i = 1,j=0;
	while (p != NULL)
	{
		pr = headerNode->next;
		j = 0;
		while (pr!= p)
		{
            if(pr->element <= p->element)
				 ++r[i];
			else ++r[j];
			pr = pr->next;
			++j;
		}
		p = p->next;
		++i;
	}
	//      
	chainNode*pb = headerNode->next;
	int k = 0,t;
	T temp;
	while (pb != NULL)
	{
		 int i =0;
		chainNode*pd = headerNode->next;
		while (k!=r[i])
		{
			pd = pd->next;
			++i;
		}
		if (k!=r[k])         //           ，    
		{
			//    
			temp = pb->element;
			pb->element = pd->element;
			pd->element = temp;
            //    
			t = r[i];
			r[i] = r[k];
			r[k] = t;
		}
		pb = pb->next;
		++k;
	}
	delete [] r;
}

#endif