ep7_4.h
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:5k
源码类别:

书籍源码

开发平台:

Visual C++

  1. /*7.4 为单链表类模板增加一个拷贝构造函数和拷贝赋值运算符(=)。*/
  2. #include<iostream>
  3. using namespace std;
  4. //首先看结点组织,采用结点类,凡与结点数据和指针操作有关函数作为成员函数
  5. template<typename T>class List;
  6. template<typename T>class Node{
  7. T info;                                     //数据域
  8. Node<T> *link;                             //指针域
  9. public:
  10. Node();                                   //生成头结点的构造函数
  11. Node(const T & data);              //生成一般结点的构造函数
  12. void InsertAfter(Node<T>* P);      //在当前结点后插入一个结点
  13. Node<T>* RemoveAfter();            //删除当前结点的后继结点,返回该结点备用
  14. T & Getinfo();                     //增加取数据域函数
  15. friend class List<T>;
  16. //以List为友元类,List可直接访问Node的私有函数,与结构一样方便,但更安全
  17. };
  18. template <typename T> Node<T>::Node(){link=NULL;}
  19. template <typename T> Node<T>::Node(const T & data){
  20. info=data;
  21. link=NULL;
  22. }
  23. template<typename T>void Node<T>::InsertAfter(Node<T>* p){
  24. p->link=link;
  25. link=p;
  26. }
  27. template<typename T>Node<T>* Node<T>::RemoveAfter(){
  28. Node<T>* tempP=link;
  29. if(link==NULL) tempP=NULL;                 //已在链尾,后面无结点
  30. else link=tempP->link;
  31. return tempP;
  32. }
  33. template<typename T> T & Node<T>::Getinfo(){return info;}//增加取数据域函数
  34. //再定义链表类,选择常用操作:包括建立有序链表、搜索遍历、插入、删除、取数据等
  35. template<typename T>class List{
  36. Node<T> *head,*tail;//链表头指针和尾指针
  37. public:
  38. List();             //构造函数,生成头结点(空链表)
  39. List(List<T> &);       //拷贝构造函数
  40. ~List();                                   //析构函数
  41. List& operator=(List<T>&);
  42. void MakeEmpty();                              //清空一个链表,只余表头结点
  43. Node<T>* Find(T data);           //搜索数据域与data相同的结点,返回该结点的地址
  44. int Length();                                //计算单链表长度
  45. void PrintList();                    //打印链表的数据域
  46.     void InsertFront(Node<T>* p);      //可用来向前生成链表,在表头插入一个结点
  47. void InsertRear(Node<T>* p);       //可用来向后生成链表,在表尾添加一个结点
  48. void InsertOrder(Node<T> *p);  //按升序生成链表
  49. Node<T>*CreatNode(T data);             //创建一个结点(孤立结点)
  50. Node<T>*DeleteNode(Node<T>* p);        //删除指定结点
  51. Node<T>*RemoveAll(T &);/*删除链表中所有数据域为指定值的结点*/
  52. Node<T>*GetNode(int);/*取出链表中第K个元素(从1开始计数)*/
  53. };
  54. template<typename T>List<T>::List(){
  55. head=tail=new Node<T>();
  56. }
  57. template<typename T>List<T>::List(List<T> & ls){  //拷贝构造函数
  58. Node<T>* TempP=ls.head->link,*P1;
  59. head=tail=new Node<T>();
  60. while(TempP!=NULL){
  61. P1=new Node<T>(TempP->info);
  62. P1->link=tail->link;//向后生成list1
  63. tail->link=P1;
  64. tail=P1;
  65. TempP=TempP->link;
  66. }
  67. }
  68. template<typename T>List<T>::~List(){
  69. MakeEmpty();
  70. delete head;
  71. }
  72. template<typename T>List<T>& List<T>::operator=(List<T>& ls){
  73. Node<T>* TempP=ls.head->link,*P1;
  74. MakeEmpty();
  75. while(TempP!=NULL){
  76. P1=new Node<T>(TempP->info);
  77. P1->link=tail->link;//向后生成list1
  78. tail->link=P1;
  79. tail=P1;
  80. TempP=TempP->link;
  81. }
  82. return *this;
  83. }
  84. template<typename T>void List<T>::MakeEmpty(){
  85. Node<T> *tempP;
  86. while(head->link!=NULL){
  87. tempP=head->link;
  88. head->link=tempP->link;  //把头结点后的第一个节点从链中脱离
  89. delete tempP;            //删除(释放)脱离下来的结点
  90. }
  91. tail=head;  //表头指针与表尾指针均指向表头结点,表示空链
  92. }
  93. template<typename T> Node<T>* List<T>::Find(T data){
  94. Node<T> *tempP=head->link;
  95. while(tempP!=NULL&&tempP->info!=data) tempP=tempP->link;
  96. return tempP;        //搜索成功返回该结点地址,不成功返回NULL
  97. }
  98. template<typename T>int List<T>::Length(){
  99. Node<T>* tempP=head->link;
  100. int count=0;
  101. while(tempP!=NULL){
  102. tempP=tempP->link;
  103. count++;
  104. }
  105. return count;
  106. }
  107. template<typename T>void List<T>::PrintList(){
  108. Node<T>* tempP=head->link;
  109. while(tempP!=NULL){
  110. cout<<tempP->info<<'t';
  111. tempP=tempP->link;
  112. }
  113. cout<<endl;
  114. }
  115. template<typename T>void List<T>::InsertFront(Node<T> *p){
  116. p->link=head->link;
  117. head->link=p;
  118. if(tail==head) tail=p;
  119. }
  120. template<typename T>void List<T>::InsertRear(Node<T> *p){
  121. p->link=tail->link;
  122. tail->link=p;
  123. tail=p;
  124. }
  125. template<typename T>void List<T>::InsertOrder(Node<T> *p){
  126. Node<T> *tempP=head->link,*tempQ=head;        //tempQ指向tempP前面的一个节点
  127. while(tempP!=NULL){
  128. if(p->info<tempP->info)break; //找第一个比插入结点大的结点,由tempP指向
  129. tempQ=tempP;
  130. tempP=tempP->link;
  131. }
  132. tempQ->InsertAfter(p); //插在tempP指向结点之前,tempQ之后
  133. if(tail==tempQ) tail=tempQ->link;
  134. }
  135. template<typename T>Node<T>* List<T>::CreatNode(T data){//建立新节点
  136. Node<T>*tempP=new Node<T>(data);
  137. return tempP;
  138. }
  139. template<typename T>Node<T>* List<T>::DeleteNode(Node<T>* p){
  140. Node<T>* tempP=head;
  141. while(tempP->link!=NULL&&tempP->link!=p) tempP=tempP->link;
  142. if(tempP->link==tail) tail=tempP;
  143. return tempP->RemoveAfter();       //本函数所用方法可省一个工作指针,与InsertOrder比较
  144. }
  145. template<typename T> Node<T>* List<T>::RemoveAll(T &p){/*利用已有的DeleteNode()*/
  146. bool b=false;
  147. Node<T>*TempP=head->link,*TempR=NULL;
  148. while(TempP!=NULL){/*也可以利用尾指针*/
  149. if(TempP->info==p){
  150. delete TempR;  //释放上次找到的结点,第1次时因TempR为NULL不会出错
  151. TempR=DeleteNode(TempP);
  152. }
  153. TempP=TempP->link;
  154. }
  155. return TempR;         //仅返回最后一次找到的结点
  156. }
  157. template<typename T> Node<T>* List<T>::GetNode(int i){/*取出链表中第K个元素(从1开始计数)*/
  158. Node<T>*TempP=head->link;
  159. int j=1;
  160. if(i<0) return NULL;
  161. if(i==0) return head;
  162. while(TempP!=NULL&&j<i){
  163. TempP=TempP->link;
  164. j++;
  165. }
  166. return TempP;
  167. }