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

书籍源码

开发平台:

Visual C++

  1. /*7.2 给单链表类模板增加两个成员函数:删除链表中所有数据域为指定值的结点和
  2. 取出链表中第K个元素(从1开始计数)。*/
  3. /*这两个成员函数添在单链表类模板中(ep7_3.h),删除函数中要比较数据域,该比较运算符应该在
  4. 数据域类中重载(ep7_3data.h)。*/
  5. /*本例数据域用了类mystring,更通用。使用整数型见ep7_3_0。习题中仅此题作了标准编程*/
  6. #include<iostream>
  7. using namespace std;
  8. //首先看结点组织,采用结点类,凡与结点数据和指针操作有关函数作为成员函数
  9. template<typename T>class List;
  10. template<typename T>class Node{
  11. T info;                                     //数据域
  12. Node<T> *link;                             //指针域
  13. public:
  14. Node();                                   //生成头结点的构造函数
  15. Node(const T & data);//生成一般结点的构造函数
  16. void InsertAfter(Node<T>* P);                 //在当前结点后插入一个结点
  17. Node<T>* RemoveAfter();           //删除当前结点的后继结点,返回该结点备用
  18. T & Getinfo();//增加取数据域函数
  19. friend class List<T>;
  20. //以List为友元类,List可直接访问Node的私有函数,与结构一样方便,但更安全
  21. };
  22. template <typename T> Node<T>::Node(){link=NULL;}
  23. template <typename T> Node<T>::Node(const T & data){
  24. info=data;
  25. link=NULL;
  26. }
  27. template<typename T>void Node<T>::InsertAfter(Node<T>* p){
  28. p->link=link;
  29. link=p;
  30. }
  31. template<typename T>Node<T>* Node<T>::RemoveAfter(){
  32. Node<T>* tempP=link;
  33. if(link==NULL) tempP=NULL;                 //已在链尾,后面无结点
  34. else link=tempP->link;
  35. return tempP;
  36. }
  37. template<typename T> T & Node<T>::Getinfo(){return info;}//增加取数据域函数
  38. //再定义链表类,选择常用操作:包括建立有序链表、搜索遍历、插入、删除、取数据等
  39. template<typename T>class List{
  40. Node<T> *head,*tail;//链表头指针和尾指针
  41. public:
  42. List();             //构造函数,生成头结点(空链表)
  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. };
  56. template<typename T>List<T>::List(){
  57. head=tail=new Node<T>();
  58. }
  59. template<typename T>List<T>::~List(){
  60. MakeEmpty();
  61. delete head;
  62. }
  63. template<typename T>void List<T>::MakeEmpty(){
  64. Node<T> *tempP;
  65. while(head->link!=NULL){
  66. tempP=head->link;
  67. head->link=tempP->link;  //把头结点后的第一个节点从链中脱离
  68. delete tempP;            //删除(释放)脱离下来的结点
  69. }
  70. tail=head;  //表头指针与表尾指针均指向表头结点,表示空链
  71. }
  72. template<typename T> Node<T>* List<T>::Find(T data){
  73. Node<T> *tempP=head->link;
  74. while(tempP!=NULL&&tempP->info!=data) tempP=tempP->link;
  75. return tempP;        //搜索成功返回该结点地址,不成功返回NULL
  76. }
  77. template<typename T>int List<T>::Length(){
  78. Node<T>* tempP=head->link;
  79. int count=0;
  80. while(tempP!=NULL){
  81. tempP=tempP->link;
  82. count++;
  83. }
  84. return count;
  85. }
  86. template<typename T>void List<T>::PrintList(){
  87. Node<T>* tempP=head->link;
  88. while(tempP!=NULL){
  89. cout<<tempP->info<<'t';
  90. tempP=tempP->link;
  91. }
  92. cout<<endl;
  93. }
  94. template<typename T>void List<T>::InsertFront(Node<T> *p){
  95. p->link=head->link;
  96. head->link=p;
  97. if(tail==head) tail=p;
  98. }
  99. template<typename T>void List<T>::InsertRear(Node<T> *p){
  100. p->link=tail->link;
  101. tail->link=p;
  102. tail=p;
  103. }
  104. template<typename T>void List<T>::InsertOrder(Node<T> *p){
  105. Node<T> *tempP=head->link,*tempQ=head;        //tempQ指向tempP前面的一个节点
  106. while(tempP!=NULL){
  107. if(p->info<tempP->info)break; //找第一个比插入结点大的结点,由tempP指向
  108. tempQ=tempP;
  109. tempP=tempP->link;
  110. }
  111. tempQ->InsertAfter(p); //插在tempP指向结点之前,tempQ之后
  112. if(tail==tempQ) tail=tempQ->link;
  113. }
  114. template<typename T>Node<T>* List<T>::CreatNode(T data){//建立新节点
  115. Node<T>*tempP=new Node<T>(data);
  116. return tempP;
  117. }
  118. template<typename T>Node<T>* List<T>::DeleteNode(Node<T>* p){
  119. Node<T>* tempP=head;
  120. while(tempP->link!=NULL&&tempP->link!=p) tempP=tempP->link;
  121. if(tempP->link==tail) tail=tempP;
  122. return tempP->RemoveAfter();       //本函数所用方法可省一个工作指针,与InsertOrder比较
  123. }
  124. template<typename T> Node<T>* List<T>::RemoveAll(T &p){/*利用已有的DeleteNode()*/
  125. Node<T>*TempP=head->link,*TempR=NULL;
  126. while(TempP!=NULL){/*也可以利用尾指针*/
  127. if(TempP->info==p){
  128. delete TempR;  //释放上次找到的结点,第1次时因TempR为NULL不会出错
  129. TempR=DeleteNode(TempP);
  130. }
  131. TempP=TempP->link;
  132. }
  133. return TempR;         //仅返回最后一次找到的结点
  134. }
  135. template<typename T> Node<T>* List<T>::GetNode(int i){/*取出链表中第K个元素(从1开始计数)*/
  136. Node<T>*TempP=head->link;
  137. int j=1;
  138. if(i<0) return NULL;
  139. if(i==0) return head;
  140. while(TempP!=NULL&&j<i){
  141. TempP=TempP->link;
  142. j++;
  143. }
  144. return TempP;
  145. }