ep7_6.h

这里有大量的c语言习题呢！真的是题海哦

/*7.6为单链表重载"+"运算符，实现两个单链表对象的连接，但要去除数据域相同的结点。可用友元函数。*/
//为了实现ls3=ls1+ls2,需重载=和+两个运算符

#include<iostream>
using namespace std;
//首先看结点组织，采用结点类，凡与结点数据和指针操作有关函数作为成员函数
template<typename T>class List;
template<typename T>class Node{
	T info;                                     //数据域
	Node<T> *link;                             //指针域
public:
	Node();                                   //生成头结点的构造函数
	Node(const T & data);//生成一般结点的构造函数
	void InsertAfter(Node<T>* P);                 //在当前结点后插入一个结点
	Node<T>* RemoveAfter();           //删除当前结点的后继结点，返回该结点备用
	T & Getinfo();//增加取数据域函数
	Node<T>* Getlink();//取指针域
	friend class List<T>;
	//以List为友元类，List可直接访问Node的私有函数，与结构一样方便，但更安全
};
template <typename T> Node<T>::Node(){link=NULL;}
template <typename T> Node<T>::Node(const T & data){
	info=data;
	link=NULL;
}
template<typename T>void Node<T>::InsertAfter(Node<T>* p){
	p->link=link;
	link=p;
}
template<typename T>Node<T>* Node<T>::RemoveAfter(){
	Node<T>* tempP=link;
	if(link==NULL) tempP=NULL;                 //已在链尾,后面无结点
	else link=tempP->link;
	return tempP;
}
template<typename T> T & Node<T>::Getinfo(){return info;}//增加取数据域函数
template<typename T> Node<T>* Node<T>::Getlink(){return link;}//取指针域
//再定义链表类，选择常用操作：包括建立有序链表、搜索遍历、插入、删除、取数据等
template<typename T>class List{
	Node<T> *head,*tail;//链表头指针和尾指针
public:
	List();             //构造函数，生成头结点(空链表)
	List(List<T> &);       //拷贝构造函数
	~List();                                   //析构函数
	void MakeEmpty();                              //清空一个链表，只余表头结点
	Node<T>* Find(T data);           //搜索数据域与data相同的结点，返回该结点的地址
	int Length();                                //计算单链表长度
	void PrintList();                    //打印链表的数据域
    void InsertFront(Node<T>* p);      //可用来向前生成链表，在表头插入一个结点
	void InsertRear(Node<T>* p);       //可用来向后生成链表，在表尾添加一个结点
	void InsertOrder(Node<T> *p);  //按升序生成链表
	Node<T>*CreatNode(T data);             //创建一个结点(孤立结点)
	Node<T>*DeleteNode(Node<T>* p);        //删除指定结点
	Node<T>*RemoveAll(T &);/*删除链表中所有数据域为指定值的结点*/
	Node<T>*GetNode(int);/*取出链表中第K个元素（从1开始计数）*/
	void Reverse();//翻转链表
	List<T> & operator=(List<T> &);//重载=运算符
	friend List<T> operator+(List<T> & ,List<T> & );//重载+运算符
};
template<typename T>List<T>::List(){
	head=tail=new Node<T>();
}
template<typename T>List<T>::List(List<T> & ls){  //拷贝构造函数
	Node<T>* TempP=ls.head->link,*P1;
	head=tail=new Node<T>();
	while(TempP!=NULL){		
		P1=new Node<T>(TempP->info);
		P1->link=tail->link;//向后生成list1
		tail->link=P1;
		tail=P1;
		TempP=TempP->link;
	}
}
template<typename T>List<T>::~List(){
	MakeEmpty();
	delete head;
}
template<typename T>void List<T>::MakeEmpty(){
	Node<T> *tempP;
	while(head->link!=NULL){
		tempP=head->link;
		head->link=tempP->link;  //把头结点后的第一个节点从链中脱离
		delete tempP;            //删除(释放)脱离下来的结点
	}
	tail=head;  //表头指针与表尾指针均指向表头结点，表示空链
}
template<typename T> Node<T>* List<T>::Find(T data){
	Node<T> *tempP=head->link;
	while(tempP!=NULL&&tempP->info!=data) tempP=tempP->link;
	return tempP;        //搜索成功返回该结点地址，不成功返回NULL
}
template<typename T>int List<T>::Length(){
	Node<T>* tempP=head->link;
	int count=0;
	while(tempP!=NULL){
		tempP=tempP->link;
		count++;
	}
	return count;
}
template<typename T>void List<T>::PrintList(){
	Node<T>* tempP=head->link;
	while(tempP!=NULL){
		cout<<tempP->info<<'\t';
		tempP=tempP->link;
	}
	cout<<endl;
}
template<typename T>void List<T>::InsertFront(Node<T> *p){
	p->link=head->link;
	head->link=p;
	if(tail==head) tail=p;
}
template<typename T>void List<T>::InsertRear(Node<T> *p){
	p->link=tail->link;
	tail->link=p;
	tail=p;
}
template<typename T>void List<T>::InsertOrder(Node<T> *p){
	Node<T> *tempP=head->link,*tempQ=head;        //tempQ指向tempP前面的一个节点
	while(tempP!=NULL){
		if(p->info<tempP->info)break; //找第一个比插入结点大的结点，由tempP指向
		tempQ=tempP;
		tempP=tempP->link;
	}
	tempQ->InsertAfter(p);	//插在tempP指向结点之前，tempQ之后
	if(tail==tempQ) tail=tempQ->link;
}
template<typename T>Node<T>* List<T>::CreatNode(T data){//建立新节点
	Node<T>*tempP=new Node<T>(data);
	return tempP;
}
template<typename T>Node<T>* List<T>::DeleteNode(Node<T>* p){
	Node<T>* tempP=head;
	while(tempP->link!=NULL&&tempP->link!=p) tempP=tempP->link;
	if(tempP->link==tail) tail=tempP;
	return tempP->RemoveAfter();       //本函数所用方法可省一个工作指针，与InsertOrder比较
}
template<typename T> Node<T>* List<T>::RemoveAll(T &p){/*利用已有的DeleteNode()*/
	bool b=false;
	Node<T>*TempP=head->link,*TempR=NULL;
	while(TempP!=NULL){/*也可以利用尾指针*/
		if(TempP->info==p){
			delete TempR;  //释放上次找到的结点，第1次时因TempR为NULL不会出错
			TempR=DeleteNode(TempP);
		}
		TempP=TempP->link;
	}
	return TempR;         //仅返回最后一次找到的结点
}
template<typename T> Node<T>* List<T>::GetNode(int i){/*取出链表中第K个元素（从1开始计数）*/
	Node<T>*TempP=head->link;
	int j=1;
	if(i<0) return NULL;
	if(i==0) return head;
	while(TempP!=NULL&&j<i){
		TempP=TempP->link;
		j++;
	}
	return TempP;
}
template<typename T> void List<T>::Reverse(){//链表翻转函数
	Node<T>*p1,*p2,*p3;
	if(head==tail||head->link==tail) return;//空链表和单结点链表不必处理
	tail=head->link;//尾指针指向第一个元素
	p3=head;	
	do{
		p1=tail;//以tail开始的链，最后一个元素取下来，链到新链的尾部
		do{
			p2=p1;
			p1=p1->link;
		}while(p1->link!=NULL);//找到以tail开始的链的链尾
		p3->link=p1;//取下链尾，链到新链上
		p3=p1;
		p2->link=NULL;
	}while(tail!=p2);//以tail开始的链只剩一个元素则停止
	p3->link=tail;
	tail->link=NULL;
}
template<typename T>List<T> & List<T>::operator=(List<T> & ls){//重载=运算符
	Node<T>* TempP=ls.head->link,*P1;
	MakeEmpty();
	while(TempP!=NULL){		
		P1=new Node<T>(TempP->info);
		P1->link=tail->link;//向后生成list1
		tail->link=P1;
		tail=P1;
		TempP=TempP->link;
	}
	return *this;
}
template<typename T>List<T> operator+(List<T> & ls1,List<T> & ls2){//重载+运算符
	List<T> ls(ls1);//新链表,生命期仅在本函数域中
	Node<T>* P1=ls2.head->Getlink(),*P2,*P3,*P4;
	//虽然本函数是List的友元，而List是Node的友类，但还是不能访问Node的私有成员
	while(P1!=NULL){
		P2=ls.CreatNode(P1->Getinfo());
		ls.InsertRear(P2);//向后生成list1
		P1=P1->Getlink();
	}
	P1=ls.head->Getlink();//删去重复的结点。
	while(P1!=NULL){//先用第一个结点，与后面结点逐个比较，有重复的就删去；再用第二个....
		P2=P1->Getlink();
		while(P2!=NULL){//与后面结点逐个比较					
			if(P1->Getinfo()==P2->Getinfo()){//有重复的就删去；
				P3=P2->Getlink();//删去后P2空悬
				P4=ls.DeleteNode(P2);
				delete P4;
				P2=P3;//已后移一个结点
			}
			else P2=P2->Getlink();//到后面一个结点			
		}
		P1=P1->Getlink();//再用第二个....
	}
	return ls;//为保证返回时用拷贝构造函数复制一个链表返回，返回类型不能是引用，
}