书籍源码

开发平台：
Visual C++

ep7_7.cpp：源码内容
							/*7.7	将两个有序的双向链表合并为一个有序的双向链表。*/
#include<iostream>
using namespace std;
template<typename T> class DblList;
template<typename T> class DblNode{   //结点类
	T info;//数据域
	DblNode<T> *llink,*rlink;         //前驱（左链）、后继（右链）指针
public:
	DblNode(T data);
	DblNode();
	T Getinfo(){return info;};
	friend class DblList<T>;
};
template<typename T> DblNode<T>::DblNode(){
	llink=rlink=NULL;
}
template<typename T> DblNode<T>::DblNode(T data){
	info=data;
	llink=NULL;
	rlink=NULL;
}
template<typename T>class DblList{ //双链表类
	DblNode<T> *head,*current;
public:
	DblList();
	~DblList();
	void Insert(const T & data);
	DblNode<T>* Remove(DblNode<T>* p);
	void Print();
	int Length();              //计算链表长度
	DblNode<T> *Find(T data);  //搜索数据与定值相同的结点
	void MakeEmpty();          //清空链表
	void Merge(DblList<T> & ,DblList<T> &); //归并
	//其它操作
};
template<typename T> DblList<T>::DblList(){ //建立表头结点
	head=new DblNode<T>();
	head->rlink=head->llink=head;
	current=NULL;
}
template<typename T> DblList<T>::~DblList(){
	MakeEmpty();                            //清空链表
	delete head;
}
template<typename T> void DblList<T>::MakeEmpty(){
	DblNode<T> *tempP;
	while(head->rlink!=head){
		tempP=head->rlink;
		head->rlink=tempP->rlink;   //把头结点后的第一个节点从链中脱离
		tempP->rlink->llink=head;   //处理左指针
		delete tempP;                //删除(释放)脱离下来的结点
	}
	current=NULL;  //current指针恢复
}
template<typename T> void DblList<T>::Insert(const T & data){//新节点在链尾
	current=new DblNode<T>;
	current->info=data;
	current->rlink=head;         //注意次序
	current->llink=head->llink;
	head->llink->rlink=current;
	head->llink=current;         //最后做
}
template<typename T> DblNode<T>* DblList<T>::Remove(DblNode<T>* p){
	current=head->rlink;
	while(current!=head&&current!=p) current=current->rlink;
	if(current==head) current=NULL;
	else{           //结点摘下
		p->llink->rlink=p->rlink;
		p->rlink->llink=p->llink;
		p->rlink=p->llink=NULL;
	}
	return current;
}
template<typename T> DblNode<T>* DblList<T>::Find(T data){
	current=head->rlink;
	while(current!=head&&current->info!=data) current=current->rlink;
	if(current==head) current=NULL;
	return current;
}
template<typename T> void DblList<T>::Print(){
	current=head->rlink;
	while(current!=head){
		cout<<current->info<<'t';
		current=current->rlink;
	}
	cout<<endl;
}
template<typename T> int DblList<T>::Length(){
	int count=0;
	current=head->rlink;
	while(current!=head){
		count++;
		current=current->rlink;
	}
	return count;
}
template<typename T>void DblList<T>::Merge(DblList<T> & dbl1,DblList<T> & dbl2){//归并
	DblNode<int> *tdp1=dbl1.head->rlink,*tdp2=dbl2.head->rlink;
	while(tdp1!=dbl1.head&&tdp2!=dbl2.head)
	if(tdp1->info<tdp2->info){
		Insert(tdp1->info);
		tdp1=tdp1->rlink;
	}
	else{
		Insert(tdp2->info);
		tdp2=tdp2->rlink;
	}
	if(tdp1!=dbl2.head) while(tdp1!=dbl1.head){
		Insert(tdp1->info);
		tdp1=tdp1->rlink;
	}
	if(tdp2!=dbl2.head) while(tdp2!=dbl2.head){
		Insert(tdp2->info);
		tdp2=tdp2->rlink;
	}
}
int main(){
	DblList<int> Dbl1,Dbl2,Dbl3;
	DblNode<int> *tp=NULL;
	int i,a[11]={9,11,17,23,27,32,33,35,43,51,59};
	int b[11]={1,3,12,13,17,24,30,45,53,63,69};
	for(i=0;i<11;i++) Dbl1.Insert(a[i]);
	cout<<"双向链表长度："<<Dbl1.Length()<<endl;
	Dbl1.Print();
	for(i=0;i<11;i++) Dbl2.Insert(b[i]);
	cout<<"双向链表长度："<<Dbl2.Length()<<endl;
	Dbl2.Print();
	Dbl3.Merge(Dbl1,Dbl2);
	cout<<"双向链表长度："<<Dbl3.Length()<<endl;
	Dbl3.Print();
	tp=Dbl3.Find(17);
	if(tp) cout<<"查到的结点数据为："<<tp->Getinfo()<<" 清除"<<endl;
	else cout<<"未查到结点数据"<<endl;
	delete Dbl3.Remove(tp);
	cout<<"双向链表长度："<<Dbl3.Length()<<endl;
	Dbl3.Print();
	cout<<"清空链表"<<endl;
	Dbl3.MakeEmpty();
	cout<<"双向链表长度："<<Dbl3.Length()<<endl;
	return 0;
}

						