- /*7.4 为单链表类模板增加一个拷贝构造函数和拷贝赋值运算符(=)。*/
- #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(); //增加取数据域函数
- 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>class List{
- Node<T> *head,*tail;//链表头指针和尾指针
- public:
- List(); //构造函数,生成头结点(空链表)
- List(List<T> &); //拷贝构造函数
- ~List(); //析构函数
- List& operator=(List<T>&);
- 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开始计数)*/
- };
- 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>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>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;
- }