c++学習ノート(21)チェーンテーブル化スタック

#include "iostream"  
#include "cstdlib"
using namespace std;  
  
/*********************************************create class********************************************/  
#define LIST_INIT_SIZE 100  
#define LISTINCREMENT 10  
   
class ChainNode
{
	friend class chain;   //friend class,the class chain can use the param of ChainNode
private:
	int data;
	ChainNode *link;
};
  
class chain  
{  
private:  
	ChainNode *first;
	ChainNode *last;
public:  
	chain(){ first  = last = 0; } //   InitList  
	~chain();
	bool ListEmpty()const {return first == 0;}  //     empty  
	int Length()const;  //the length of the chain
    bool find(int num, int &x) const; //          
    int Search (const int &e);  //  e       
    chain& ListInsert(int num, const int& e);  //      e,  num     
    chain& ListDelete(int num, int &x);  //  the place  ,and   ,      chain  
	chain& Append(const int &e); //      
    void displayElem(ostream &out)const;  //    //         ostream &out   。
	friend ostream & operator << (ostream & out, chain& rs); //       
};  
  
/******************************************************class functions**************************************************/  


chain::~chain()
{
	ChainNode *next;  //          
	while(first)  //           。
	{
		next = first->link;
		delete first;
		first = next;
	}
}


int chain::Length()const
{
	int count = 0;
	ChainNode *next;
	next = first;
	while(next)
	{
		count++;
		if(next == last)
		return count;
		else 
			next = next->link;
	}
	return count;
}




bool chain::find(int num, int &x) const
{
	if(num > Length())
	{
		cout << "the chain is over";
		return false;
	}
	ChainNode *next;     //        ，          
	next = first;
	for(;num > 0; num--)
	{
		x = next->data;
		next = next->link;
	}
	return true;
}


//      
int chain::Search (const int &e)
{
	int num = 1;
	ChainNode *next;
	next = first;    //   -
	last->link = first;		//   
	//next = first;   //   
	while(next->data != e)
	{
		if(next == first)     //    next = last
		{
			cout << "1" << endl;
			return 0;
		}
		next = next->link;
		num++;
	}
		return num;
}


//delete elem
chain& chain::ListDelete(int num, int &x) 
{
	int len = Length();
	if(len == 0 || len < num)
	{
		cout << "the num is wrong";
		abort();
	}


	ChainNode *next = first;
	ChainNode *Third = new ChainNode;
	if(num == 1)   //          
	{
		
		x = next->data;
		Third = next->link;
		delete next;
		first= Third;


		return *this;
	}   //end num== 1
	else if(num == len)  //end elem delete
	{
		for(int index = 1; index < num -1; index++)
		{
			next = next->link;
		}
			Third  =next->link;
			x = Third->data;
			delete Third;
			last = next;
			
			return *this;
	} //end num == len
	else
	{
		for(int index = 1; index < num -1; index++)
		{
			next = next->link;
		}
		Third = next->link;
		next->link = Third->link;
		x = Third->data;
		delete Third;


		return *this;
	}  //end num == middle
}


//insert elem
chain& chain::ListInsert(int num, const int& x)
{
	int len = Length();
	if(len == 0&& num != 1)   //      ，list   ，   num   1
	{
		cout << "the num is wrong";
		abort();
	}
	else if(num == len+1)  //     
	{
		Append(x);
	}


	ChainNode *next = first;   //     .
	for(int index = 1; index < num - 1; index++)  //index is the location of next
	{
		next = next->link;
	}
	ChainNode *Third = new ChainNode;
	Third->data = x;
	Third->link = next->link;
	next->link = Third;


	return *this;
}


//       
chain& chain::Append(const int &e)
{
	ChainNode *next = new ChainNode;
	next->data = e;
	next->link = 0;
	if(first)  //  
	{
		last->link = next;
		last = next;
	}
	else first = last = next;
	return *this;
}


//shoe the elem
void chain::displayElem(ostream &out)const
{
	int len = Length();
	int x;
	for(int i = 1; i <= len; i++)
	{
		find(i, x);
		out << x << " ";
	}
}


//friend function
ostream & operator << (ostream &out, chain &rs)
{
	rs.displayElem(out);
	return out;
}
 
/**************************************************************************************/
//     ，      
class NoMem {
public :
	NoMem(){}
};
//  new  NoMem     xalloc  
void my_new_handler()
{
throw NoMem();
}
new_handler Old_Handler_=set_new_handler(my_new_handler);




//template <class T>
class LinkedStack:private chain 
{
public:
	bool IsEmpty()const
	{return chain::ListEmpty();}
	bool IsFull() const;
	int top()const
	{
		if(IsEmpty())
			abort();
		int x;
		find(1, x);
		return x;
	}
	LinkedStack & Add(const int &x)
	{ListInsert(1, x); return *this;}
	LinkedStack & Delete(int &x)
	{
		int len = Length();
		ListDelete(1, x); return *this;
	}
};


bool LinkedStack::IsFull()const
{
	try{ChainNode *p = new ChainNode;
	delete p;
	return false;}
	catch(NoMem){return true;}
}
  
/*******************************************************use the class****************************************************/  
int main()  
{  
	LinkedStack newch;
	int insert = 4;
	int get;
	newch.Add(insert);
	newch.Add(insert-1);
	newch.Add(insert-2);
	newch.Add(insert-3);
	cout << "the top: " << newch.top() << endl;
	
	int DeleteElem;
	newch.Delete(DeleteElem);
	newch.Delete(DeleteElem);


	cout << DeleteElem << endl;


    cin.get();  
    cin.get();  
    return 0;  
}  

1.チェーンテーブルスタック複数のスタックが多重化されている場合、1つのスタックを定義するたびにサイズが申請されるので、使いきれないと無駄にならないので、チェーンテーブル化はこの問題を解決しました:)