simchain.cpp

模拟指针,使用固定的数组模拟指针的内存分配

#include "xcept.h"
#include "simchain.h"



template <typename T>
CSimSpace<T>::CSimSpace(int MaxSpaceSize)
{
	NumberOfNode=MaxSpaceSize;
	node=new CSimNode<int>[MaxSpaceSize];
	for(int i=0;i<MaxSpaceSize-1;i++)
	{
		node[i].data=T(0);
        node[i].link=i+1;
	}
	node[i].data=T(0);
	node[i].link=-1;
	first=0;
}

template <typename T>
CSimSpace<T>::~CSimSpace()
{
	if(node)
	{
		delete []node;
	}
	NumberOfNode=0;
	first=-1;
}


template <typename T>
int CSimSpace<T>::Allocate()
{
	if(first==-1) throw NoMem();
	int i=first;
	first=node[i].link;
	return i;
}


template <typename T>
void CSimSpace<T>::DeAllocate(int &i)
{
	node[i].link=first;
	first=i;
	i=-1;
}

template <typename T>
void CSimChain<T>::Destroy()
{
	if(first!=-1)
	{
		int next=first;
		while(first!=-1)
		{
			next=S.node[first].link;
			S.node[first].link=-1;
			S.DeAllocate(first);
			first=next;
		}
	}
}

template <typename T>
int  CSimChain<T>::Length() const
{
	int len=0,index=first;
	while(index!=-1)
	{		
		index=S.node[index].link;
        len++; 
	}
	return len;
}

template <typename T>
bool CSimChain<T>::Find(int k,T &x) const
{
	if(k<1)
	{
		x=T(0);
		return false;
	}
	int cur=first;
	int index=0;
	while( (cur!=-1)&&(index<k-1))
	{
		cur=S.node[cur].link;
		index++;
	}
	if(cur==-1)
	{
		return false;
	}
	x=S.node[cur].data;
	return true;
}

template <typename T>
int  CSimChain<T>::Search(const T&x) const
{
	int cur=first;
	int index=1;
	if(first==-1)
	{
		return -1;
	}
	while(cur!=-1 && S.node[cur].data!=x)
	{
		index++;
		cur=S.node[cur].link;
	}
	if(cur==-1)
		return -1;

	return index; 
}

template <typename T>
CSimChain<T>& CSimChain<T>::Delete(int k,T &x)
{
	if(k<1 || first==-1)
		throw OutOfBounds();

	int pretarget=first;
	if(k==1)//删除头节点
	{
		x=S.node[first].data;
		pretarget=S.node[first].link;
		S.DeAllocate(first);
		first=pretarget;
		return *this;
	}
	//走到k－2
	for(int i=0;i<k-2 && pretarget!=-1;i++)
		pretarget=S.node[i].link;
	int target=S.node[pretarget].link;
	if(pretarget==-1 || target==-1)
		throw OutOfBounds();

    if(S.node[target].link==-1)//删除尾节点
	{
		x=S.node[target].data;
		S.node[pretarget].link=-1;
	}
	else//删除中部
	{
		x=S.node[target].data;
		S.node[pretarget].link=S.node[target].link;
		S.node[target].link=-1;
	}
		
	S.DeAllocate(target);
	return *this;
}

template <typename T>
CSimChain<T>& CSimChain<T>::Insert(int k,const T &x)
{
	if(k<=0)
		throw OutOfBounds();
	int newnode=S.Allocate();
	S.node[newnode].link=-1;
	S.node[newnode].data=x;
	if(k==1)//在头部插入
	{
		S.node[newnode].link=first;
		first=newnode;
		return *this;
	}
	int pretarget=first;
	int index=0;
	while(pretarget!=-1&&index<k-2)//走到k－2
	{
		pretarget=S.node[pretarget].link;
		index++;
	}
	if(pretarget==-1)
		throw OutOfBounds();
	
	int target = S.node[pretarget].link;
	if(target==-1)//在尾部插入
	{
		S.node[pretarget].link=newnode;
		return *this;
	}

	//在中部插入
	S.node[newnode].link=target;
	S.node[pretarget].link=newnode;

	return *this;
}

template <typename T>
void CSimChain<T>::Output(ostream &out)const
{
	int current=first;
	while (current!=-1)
	{
		out<<S.node[current].data<<" ";
		current=S.node[current].link;
	}
	out<<endl;
	
}

template <typename T>
void CSimChain<T>::FillElem(T temp[],int len)
{
	for(int i=0;i<len;i++)
		Insert(i+1, temp[i]);	
}

template<typename T>
ostream &operator<<(ostream& out,const CSimChain<T> &list)
{
   list.Output(out);
   return out;
}

//此处不是声明是实现
CSimSpace<int> CSimChain<int>::S(10);

/*
void main()
{
try{
	
   int n[9];
   for(int i=0;i<9;i++)
   {
	   n[i]=i+1;
   }
   CSimChain<int> list1;
   list1.FillElem(n,9);
   cout<<list1; 
   


   //cout<<"the length is "<<list1.Length()<<endl;
   int x=10;
/ *
             
     if(list1.Find(0,x))
         cout<<"the index's value has found "<<x<<endl; 
* /
  / *
  
    
     list1.Delete(5,x);
         cout<<"after delete the list is "<<list1<<x<<endl;
     
    * /
  
  
  
   //list1.Insert(10,x);

/ *
   list1.Insert(10,x);
     cout<<"after insert the list is"<<list1;
* /

  
 cout<<list1.Search(10)<<endl;
  
 
}
catch(...)
{
	cout<<"error occur!"<<endl;
}
}*/