link_list.h

来自「学生运动会成绩数据库 学生运动会成绩数据库系统记录某校运动会上全部运动项目」· C头文件 代码 · 共 137 行

#ifndef Link_List_h
#define Link_List_h
// 初始化链表
template <typename T>
Linklist<T>::Linklist()
{
	first=new Node<T>;
	first->next=NULL;//初始化条件
	length=0;// 链表的长度初值为0
}

template <typename T>
Linklist<T>::~Linklist()
{
	//析构函数
	//在此处收回空间
	Node<T>* p=first;
	while(p)
	{
		Node<T> *q;
		q=p;
		p=p->next;
		delete q;
	}
	length=0;// 链表的长度复位
}

template <typename T>
void 	Linklist<T>::Insert(int i,const T& x)
{
	if(i<0||i>length+1)    //抛出异常
		throw   "ERROR1: INSERT";
	if(length==0)          //由于第一个节点不同于其它节点的插入
	{
	//可以直接把 pf节点连接在first(头接点)的后面
		Node<T> *pf=new Node<T>;
		pf->data=x;
		first->next=pf;
		pf->next=NULL;//最后pf要指向空
	}
	else
	{
		Node<T> *p=first;
		for(int j=0;j<=i-1&&p;j++)
			p=p->next;//找到要插入的位置
		Node<T> * newdata=new Node<T>;
		newdata->data=x;//一般插入节点
		newdata->next=p->next;
		p->next=newdata;
	}
	length++; // 链表的的长度增1
}

template <typename T>
void Linklist<T>::Delete(int i)
{
	if(i<0||i>length)//抛出异常
		throw "ERROR2: DELETE";
	else
	{
		Node<T> *p=first->next;
		if(i==1)
			//删除第一个元素，
		{
			delete first;
			first=p;
		}
		else
		{
			for(int j=0;j<i-2;j++)
				p=p->next;//找到要删除节点位置之前的节点
			Node<T> *q=new Node<T>;
			q=p->next;//删除节点	
			p->next=q->next;
				delete q;
		}
	}
	length--;
}

template <typename T>
 int Linklist<T>::Find(const T& x) const
{
	//查找元素所在的位置
	int k=-1;
	Node<T> *p=first;
	for(int i=0;i<=length;i++,p=p->next)
		if(p->data==x)
			k=i;
//	if(k==-1)
//		std::cout<<"没有找到!"<<std::endl;
	return k;
}

template <typename T>
	T& Linklist<T>::Get(int i) 
{//获取i位置的元素
	Node<T> *p=first->next;
	if(i<0||i>length)
		throw "ERROR3: GET";
	for(int j=0;j<i-1;j++)
		p=p->next;
	return p->data;
}

template <typename T>//判断链表是否为空
bool Linklist<T>::Empty() const
{
	return length==0?1:0;
}

template <typename T>
int Linklist<T>::Length() const
{
	return length;
}

template <typename T>
void Linklist<T>::Print() const
{
	//打印链表
	Node<T> *p=first->next;
	if(p==NULL)
		std::cout<<"空表"<<std::endl;
	while(p!=NULL)
	{
		std::cout<<p->data;
		p=p->next;
	}
}

template <typename T>
Node<T>* Linklist<T>::Getfirst() const
{
	return first;
}
#endif //Link_List_h