chain.cpp

关于数据结构的相关内容,表达式树,前中后序遍历,哈夫曼编码,线性表操作

#include "Chain.h"

template<class DataType>
Chain<DataType>::Chain(void)
{
	first=0;
}

template<class DataType>
Chain<DataType>::~Chain(void)
{
	this->Clear();    //调用清空函数，删除所有的元素
}

template<class DataType>
int Chain<DataType>::Length() const	//返回链表的长度
{
	int Len=0;
	ChainNode<DataType> *temp=first;
	while(temp)
	{
		temp=temp->link;
		Len++;
	}
	return Len;
}

template<class DataType>
bool Chain<DataType>::Find(int k, DataType& x) const		//查找第k个元素，如果第k个元素存在就将第k个元素的值赋给x
{
	if(k<1)
		throw Error("OutOfBounds");			//如果下标不正确，抛出异常

	int index=1;			//用于标记搜索元素的序号
	ChainNode<DataType> *temp=first;
	while(index<k && temp)			//当搜索到第k个元素或者指针为空（为了防止搜索的元素序号超出链表的长度）
	{
		temp=temp->link;		//遍历
		index++;				//相应加一
	}
	if(temp)			//如果不为空，即存在第k个元素
	{
		x=temp->data;		//赋值给x
		return true;
	}
	else			 //如果为空，返回false
		return false;

}

template<class DataType>
int Chain<DataType>::Search(const DataType& x) const			//搜索值为x的元素，如果有就返回元素的序号
{
	int index=1;
	ChainNode<DataType> *temp=first;

	while(temp && temp->data!=x)		//判断条件是元素不为空，元素的值不等于x
	{
		temp=temp->link;
		index++;
	}

	if(temp)		//如果存在，返回下标，否则返回0
		return index;
	else
		return 0;
}

template<class DataType>
Chain<DataType>& Chain<DataType>::Delete(int k, DataType& x)		//删除第k个元素，同时将元素的值赋给x
{
	if(k<1 || !first)			//如果下标不正确或者链表为空，抛出异常
		throw Error("OutOfBounds");

	ChainNode<DataType> *temp=first;		//分开两种情况处理，删除第一个元素和删除其他的非首元素
	if(k==1)
		first=first->link;		//将首指针后移一个元素，此时是temp指向原首元素
	else
	{
		ChainNode<DataType> *Node=first;		
		for(int i=1;i<k-1 && Node;i++)		//搜索第k-1个元素
		{
			Node=Node->link;
		}

		if(!Node || !Node->link)		//如果第k－1个元素和第k个元素都存在的话，就不抛出，否则就抛出异常
			throw Error("OutOfBounds");
		
		temp=Node->link;    //令temp等于被删除元素的地址
		Node->link=temp->link;  //断开temp的链接
	}
	x=temp->data;
	delete temp;
	return *this;
}

template<class DataType>
Chain<DataType>& Chain<DataType>::Insert(int k,const DataType x)
{
	if(k<1)							//如果下标不正确，抛出异常
		throw Error("OutOfBounds");

	ChainNode<DataType> *temp=first;
	int index=1;
	while(index<k-1 && temp)		//搜索第k-1个元素
	{
		temp=temp->link;
		index++;
	}

	if(k>1 && !temp)			//如果是插入到非首元素，而且又不存在第k-1个元素时就抛出异常
		throw Error("OutOfBounds");

	ChainNode<DataType> *Node=new ChainNode<DataType>; //创建新结点
	Node->data=x;		
	if(k>1)						//如果插入的是非首位置，就将新结点链接到第k个位置上去
	{
		Node->link=temp->link;
		temp->link=Node;
	}
	else
	{
		Node->link=first;
		first=Node;
	}
	return *this;
}

template<class DataType>
void Chain<DataType>::Output(std::ostream &out) 
{
	if(!first)
		throw Error("No Element!");

	ChainNode<DataType> *temp=first;
	while(temp)
	{
		out<<temp->data<<" ";		//输出数据
		temp=temp->link;
	}
}

template<class DataType>
void Chain<DataType>::Clear() 
{
	ChainNode<DataType> *temp;
	while(first)
	{
		temp=first;			//temp为要删除的元素
		first=first->link;
		delete temp;
	}

	first=0;
}

template<class DataType>
void Chain<DataType>::Sort()			//这个排序是创建一个链表，在另一个链表上进行排序，然后将排好序的链表
{							//逐个元素地赋给原来的链表，按升序排的喔
	if(!first)
		throw Error("NoElement");   //如果链表为空，则抛出异常

	ChainNode<DataType> *temp=first;
	Chain<DataType> TempChain;			//创建新的链表

	TempChain.Insert(1,temp->data);   //先插入一个元素
	temp=temp->link;					//此时temp指向原链表的第二个元素

	while(temp)					//判断是不是到了链表的尾端，temp是原链表的结点，每次循环
	{							//是判断temp的元素比新链表里面的元素应该在位置
		ChainNode<DataType> *Node=TempChain.first;  //这个Node是为了跟踪新链表

		if(temp->data < Node->data)    //如果比首元素少，即是插到新链表首位置的话
		{
			int NewData=temp->data;			//创建NewData元素值，然后用Insert函数插入到第一个位置
			TempChain.Insert(1,NewData);
		}

		else						//如果插入到非首位置
		{
			while( Node->link &&(temp->data >= Node->link->data) )  //不断地比较下去，直到找到比temp的元素
			{														//大的元素或者是到了链表的结尾
				Node=Node->link;
			}

			ChainNode<DataType> *NewNode=new ChainNode<DataType>;  //在新链表中创建一个结点
			NewNode->data=temp->data;			//将temp，即将原链表的结点元素值赋给新结点
			NewNode->link=Node->link;			//连接到Node之后
			Node->link=NewNode;
		}

		temp=temp->link;				//将temp移到下一个，原链表中的

	}

	ChainNode<DataType> *tempnode;				//此时进行元素的赋值操作，将新链表的值逐个赋给原链表，完成排序的功能
	temp=TempChain.first;				//而新链表会被自动清理

	for(tempnode=first;tempnode;tempnode=tempnode->link)
	{
		tempnode->data=temp->data;
		temp=temp->link;
	}

	
}

template<class DataType>
void Chain<DataType>::Combination(const Chain<DataType>& a,const Chain<DataType>& b)			//是以两个链表为参数，但不改变参数链表的结点
{																//此方法与老师在上课的时候将两个多项式合并的原理基本相同 
	(*this).Clear();			//防止问题，所以先将链表的元素给清空

	ChainNode<DataType> *ChainOne=a.first;   //创建参数链表的首指针
	ChainNode<DataType> *ChainTwo=b.first;
	ChainNode<DataType> *Track;			//因为参数链表是已经按升序排好的，所以这个合并之后的链表也应该是升序，
									//Track就是跟踪合并链表的尾结点
	while(ChainOne && ChainTwo)     //判断两个链表指针都不为空时为正
	{
		ChainNode<DataType> *Node=new ChainNode<DataType>;

		if(ChainOne->data < ChainTwo->data)   //如果第一个链表的结点小的话
		{
			Node->data=ChainOne->data;
			ChainOne=ChainOne->link;   //移到到下一个结点
		}
		else
		{
			Node->data=ChainTwo->data;  //如果是第二个链表的结点小的话
			ChainTwo=ChainTwo->link;	//同理移到下一个结点
		}

		if(!first)     //如果合并的链表为空，也就是插到第一个位置的时候
		{
			Node->link=first;
			first=Node;
			Track=first;     //Track跟踪最后的元素结点
		}
		else
		{
			Track->link=Node;   //如果为非首位置就链接上去
			Track=Node;			//Track就下移一个位置
		}
	}						//while结束，其中的一个参数链表的全部元素已经被完全接上了

	if(ChainOne)				//找到另一个元素还没有完全遍历过的链表，然后进行复制的操作
	{							//将其全部的元素原封不动的复制过来
		while(ChainOne)
		{
			ChainNode<DataType> *Node=new ChainNode<DataType>;  //创建新结点
			Node->data=ChainOne->data;		//赋值
			Track->link=Node;				//接到最后的结点
			Track=Node;						//Track移到最后的元素
			ChainOne=ChainOne->link;		//ChainOne也相应地移到一个元素
		}
	}

	else if(ChainTwo)					//这里也同上面一样
	{		
		while(ChainTwo)
		{
			ChainNode<DataType> *Node=new ChainNode<DataType>;
			Node->data=ChainTwo->data;
			Track->link=Node;
			Track=Node;
			ChainTwo=ChainTwo->link;
		}		
	}

	Track->link=0;				//此时Track为最后一个结点的指针，将最后一个结点的指针的Link元素赋值为0.结束链表
}

template<class DataType>
ostream& operator << (ostream& out,Chain<DataType>& x)			//重载输出操作符，其实那个out跟那个cout
{														//可以说是一样的，是一个输出流类的实例。	
	x.Output(out);
	return out;
}

template<class DataType>
Chain<DataType>::Chain(const Chain<DataType> &copy)				//复制构造函数，为了线性表的赋值操作能够将元素都复制
{																								//将copy对象中的元素都复制过去
	first=0;
	ChainNode<DataType> *temp=copy.first;
	ChainNode<DataType> *track;				//跟踪线性表的最后元素
	int count=0;
	while(count<copy.Length())
	{
		ChainNode<DataType> *Node=new ChainNode<DataType>();
		Node->data=temp->data;
		if(!first)
		{
			first=Node;
			track=first;
			Node->link=0;
		}
		else
		{
			Node->link=track->link;
			track->link=Node;
			track=Node;
		}
		temp=temp->link;
		++count;
	}
}

template<class DataType>
const Chain<DataType>& Chain<DataType>::operator =(const Chain<DataType> &c)		//道理同复制构造函数一样，方法也类同
{
	if( first != c.first)
	{
		ChainNode<DataType> *temp=copy.first;
		ChainNode<DataType> *track;
	while(temp)
	{
		ChainNode<DataType> *Node=new ChainNode<DataType>();
		Node->data=temp->data;
		if(!first)
		{
			first=Node;
			track=first;
			Node->link=0;
		}
		else
		{
			Node->link=track->link;
			track->link=Node;
			track=Node;
		}
		temp=temp->link;
	}
	}
	return *this;
}