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

书籍源码

开发平台:

Visual C++

  1. /*7.6为单链表重载"+"运算符,实现两个单链表对象的连接,但要去除数据域相同的结点。可用友元函数。*/
  2. //为了实现ls3=ls1+ls2,需重载=和+两个运算符
  3. #include<iostream>
  4. using namespace std;
  5. //首先看结点组织,采用结点类,凡与结点数据和指针操作有关函数作为成员函数
  6. template<typename T>class List;
  7. template<typename T>class Node{
  8. T info;                                     //数据域
  9. Node<T> *link;                             //指针域
  10. public:
  11. Node();                                   //生成头结点的构造函数
  12. Node(const T & data);//生成一般结点的构造函数
  13. void InsertAfter(Node<T>* P);                 //在当前结点后插入一个结点
  14. Node<T>* RemoveAfter();           //删除当前结点的后继结点,返回该结点备用
  15. T & Getinfo();//增加取数据域函数
  16. Node<T>* Getlink();//取指针域
  17. friend class List<T>;
  18. //以List为友元类,List可直接访问Node的私有函数,与结构一样方便,但更安全
  19. };
  20. template <typename T> Node<T>::Node(){link=NULL;}
  21. template <typename T> Node<T>::Node(const T & data){
  22. info=data;
  23. link=NULL;
  24. }
  25. template<typename T>void Node<T>::InsertAfter(Node<T>* p){
  26. p->link=link;
  27. link=p;
  28. }
  29. template<typename T>Node<T>* Node<T>::RemoveAfter(){
  30. Node<T>* tempP=link;
  31. if(link==NULL) tempP=NULL;                 //已在链尾,后面无结点
  32. else link=tempP->link;
  33. return tempP;
  34. }
  35. template<typename T> T & Node<T>::Getinfo(){return info;}//增加取数据域函数
  36. template<typename T> Node<T>* Node<T>::Getlink(){return link;}//取指针域
  37. //再定义链表类,选择常用操作:包括建立有序链表、搜索遍历、插入、删除、取数据等
  38. template<typename T>class List{
  39. Node<T> *head,*tail;//链表头指针和尾指针
  40. public:
  41. List();             //构造函数,生成头结点(空链表)
  42. List(List<T> &);       //拷贝构造函数
  43. ~List();                                   //析构函数
  44. void MakeEmpty();                              //清空一个链表,只余表头结点
  45. Node<T>* Find(T data);           //搜索数据域与data相同的结点,返回该结点的地址
  46. int Length();                                //计算单链表长度
  47. void PrintList();                    //打印链表的数据域
  48.     void InsertFront(Node<T>* p);      //可用来向前生成链表,在表头插入一个结点
  49. void InsertRear(Node<T>* p);       //可用来向后生成链表,在表尾添加一个结点
  50. void InsertOrder(Node<T> *p);  //按升序生成链表
  51. Node<T>*CreatNode(T data);             //创建一个结点(孤立结点)
  52. Node<T>*DeleteNode(Node<T>* p);        //删除指定结点
  53. Node<T>*RemoveAll(T &);/*删除链表中所有数据域为指定值的结点*/
  54. Node<T>*GetNode(int);/*取出链表中第K个元素(从1开始计数)*/
  55. void Reverse();//翻转链表
  56. List<T> & operator=(List<T> &);//重载=运算符
  57. friend List<T> operator+(List<T> & ,List<T> & );//重载+运算符
  58. };
  59. template<typename T>List<T>::List(){
  60. head=tail=new Node<T>();
  61. }
  62. template<typename T>List<T>::List(List<T> & ls){  //拷贝构造函数
  63. Node<T>* TempP=ls.head->link,*P1;
  64. head=tail=new Node<T>();
  65. while(TempP!=NULL){
  66. P1=new Node<T>(TempP->info);
  67. P1->link=tail->link;//向后生成list1
  68. tail->link=P1;
  69. tail=P1;
  70. TempP=TempP->link;
  71. }
  72. }
  73. template<typename T>List<T>::~List(){
  74. MakeEmpty();
  75. delete head;
  76. }
  77. template<typename T>void List<T>::MakeEmpty(){
  78. Node<T> *tempP;
  79. while(head->link!=NULL){
  80. tempP=head->link;
  81. head->link=tempP->link;  //把头结点后的第一个节点从链中脱离
  82. delete tempP;            //删除(释放)脱离下来的结点
  83. }
  84. tail=head;  //表头指针与表尾指针均指向表头结点,表示空链
  85. }
  86. template<typename T> Node<T>* List<T>::Find(T data){
  87. Node<T> *tempP=head->link;
  88. while(tempP!=NULL&&tempP->info!=data) tempP=tempP->link;
  89. return tempP;        //搜索成功返回该结点地址,不成功返回NULL
  90. }
  91. template<typename T>int List<T>::Length(){
  92. Node<T>* tempP=head->link;
  93. int count=0;
  94. while(tempP!=NULL){
  95. tempP=tempP->link;
  96. count++;
  97. }
  98. return count;
  99. }
  100. template<typename T>void List<T>::PrintList(){
  101. Node<T>* tempP=head->link;
  102. while(tempP!=NULL){
  103. cout<<tempP->info<<'t';
  104. tempP=tempP->link;
  105. }
  106. cout<<endl;
  107. }
  108. template<typename T>void List<T>::InsertFront(Node<T> *p){
  109. p->link=head->link;
  110. head->link=p;
  111. if(tail==head) tail=p;
  112. }
  113. template<typename T>void List<T>::InsertRear(Node<T> *p){
  114. p->link=tail->link;
  115. tail->link=p;
  116. tail=p;
  117. }
  118. template<typename T>void List<T>::InsertOrder(Node<T> *p){
  119. Node<T> *tempP=head->link,*tempQ=head;        //tempQ指向tempP前面的一个节点
  120. while(tempP!=NULL){
  121. if(p->info<tempP->info)break; //找第一个比插入结点大的结点,由tempP指向
  122. tempQ=tempP;
  123. tempP=tempP->link;
  124. }
  125. tempQ->InsertAfter(p); //插在tempP指向结点之前,tempQ之后
  126. if(tail==tempQ) tail=tempQ->link;
  127. }
  128. template<typename T>Node<T>* List<T>::CreatNode(T data){//建立新节点
  129. Node<T>*tempP=new Node<T>(data);
  130. return tempP;
  131. }
  132. template<typename T>Node<T>* List<T>::DeleteNode(Node<T>* p){
  133. Node<T>* tempP=head;
  134. while(tempP->link!=NULL&&tempP->link!=p) tempP=tempP->link;
  135. if(tempP->link==tail) tail=tempP;
  136. return tempP->RemoveAfter();       //本函数所用方法可省一个工作指针,与InsertOrder比较
  137. }
  138. template<typename T> Node<T>* List<T>::RemoveAll(T &p){/*利用已有的DeleteNode()*/
  139. bool b=false;
  140. Node<T>*TempP=head->link,*TempR=NULL;
  141. while(TempP!=NULL){/*也可以利用尾指针*/
  142. if(TempP->info==p){
  143. delete TempR;  //释放上次找到的结点,第1次时因TempR为NULL不会出错
  144. TempR=DeleteNode(TempP);
  145. }
  146. TempP=TempP->link;
  147. }
  148. return TempR;         //仅返回最后一次找到的结点
  149. }
  150. template<typename T> Node<T>* List<T>::GetNode(int i){/*取出链表中第K个元素(从1开始计数)*/
  151. Node<T>*TempP=head->link;
  152. int j=1;
  153. if(i<0) return NULL;
  154. if(i==0) return head;
  155. while(TempP!=NULL&&j<i){
  156. TempP=TempP->link;
  157. j++;
  158. }
  159. return TempP;
  160. }
  161. template<typename T> void List<T>::Reverse(){//链表翻转函数
  162. Node<T>*p1,*p2,*p3;
  163. if(head==tail||head->link==tail) return;//空链表和单结点链表不必处理
  164. tail=head->link;//尾指针指向第一个元素
  165. p3=head;
  166. do{
  167. p1=tail;//以tail开始的链,最后一个元素取下来,链到新链的尾部
  168. do{
  169. p2=p1;
  170. p1=p1->link;
  171. }while(p1->link!=NULL);//找到以tail开始的链的链尾
  172. p3->link=p1;//取下链尾,链到新链上
  173. p3=p1;
  174. p2->link=NULL;
  175. }while(tail!=p2);//以tail开始的链只剩一个元素则停止
  176. p3->link=tail;
  177. tail->link=NULL;
  178. }
  179. template<typename T>List<T> & List<T>::operator=(List<T> & ls){//重载=运算符
  180. Node<T>* TempP=ls.head->link,*P1;
  181. MakeEmpty();
  182. while(TempP!=NULL){
  183. P1=new Node<T>(TempP->info);
  184. P1->link=tail->link;//向后生成list1
  185. tail->link=P1;
  186. tail=P1;
  187. TempP=TempP->link;
  188. }
  189. return *this;
  190. }
  191. template<typename T>List<T> operator+(List<T> & ls1,List<T> & ls2){//重载+运算符
  192. List<T> ls(ls1);//新链表,生命期仅在本函数域中
  193. Node<T>* P1=ls2.head->Getlink(),*P2,*P3,*P4;
  194. //虽然本函数是List的友元,而List是Node的友类,但还是不能访问Node的私有成员
  195. while(P1!=NULL){
  196. P2=ls.CreatNode(P1->Getinfo());
  197. ls.InsertRear(P2);//向后生成list1
  198. P1=P1->Getlink();
  199. }
  200. P1=ls.head->Getlink();//删去重复的结点。
  201. while(P1!=NULL){//先用第一个结点,与后面结点逐个比较,有重复的就删去;再用第二个....
  202. P2=P1->Getlink();
  203. while(P2!=NULL){//与后面结点逐个比较
  204. if(P1->Getinfo()==P2->Getinfo()){//有重复的就删去;
  205. P3=P2->Getlink();//删去后P2空悬
  206. P4=ls.DeleteNode(P2);
  207. delete P4;
  208. P2=P3;//已后移一个结点
  209. }
  210. else P2=P2->Getlink();//到后面一个结点
  211. }
  212. P1=P1->Getlink();//再用第二个....
  213. }
  214. return ls;//为保证返回时用拷贝构造函数复制一个链表返回,返回类型不能是引用,
  215. }