Ex7_5.h
上传用户:wuzhousb
上传日期:2022-07-12
资源大小:380k
文件大小:4k
源码类别:

书籍源码

开发平台:

Visual C++

  1. //【例7.5_h】单链表类模板,本例作为一个头文件。单链表的结点采用类,与结点有关的基本
  2. //操作都作为结点类的成员函数。对链表整体的操作则作为链表类的成员函数,包括清空链表、
  3. //查找数据、计算单链表长度、打印链表数据、前生成链表、向后生成链表、按升序生成链表等等。
  4. #include<iostream>
  5. using namespace std;
  6. //首先看结点组织,采用结点类,凡与结点数据和指针操作有关函数作为成员函数
  7. template<typename T>class List;
  8. template<typename T>class Node{
  9. T info;                                     //数据域
  10. Node<T> *link;                             //指针域
  11. public:
  12. Node();                                   //生成头结点的构造函数
  13. Node(const T & data);//生成一般结点的构造函数
  14. void InsertAfter(Node<T>* P);                 //在当前结点后插入一个结点
  15. Node<T>* RemoveAfter();           //删除当前结点的后继结点,返回该结点备用
  16. friend class List<T>;
  17. //以List为友元类,List可直接访问Node的私有成员,与结构一样方便,但更安全
  18. };
  19. template <typename T> Node<T>::Node(){link=NULL;}
  20. template <typename T> Node<T>::Node(const T & data){
  21. info=data;
  22. link=NULL;
  23. }
  24. template<typename T>void Node<T>::InsertAfter(Node<T>* p){
  25. p->link=link;
  26. link=p;
  27. }
  28. template<typename T>Node<T>* Node<T>::RemoveAfter(){
  29. Node<T>* tempP=link;
  30. if(link==NULL) tempP=NULL;                 //已在链尾,后面无结点
  31. else link=tempP->link;
  32. return tempP;
  33. }
  34. //再定义链表类,选择常用操作:包括建立有序链表、搜索遍历、插入、删除、取数据等
  35. template<typename T>class List{
  36. Node<T> *head,*tail;//链表头指针和尾指针
  37. public:
  38. List();             //构造函数,生成头结点(空链表)
  39. ~List();                                   //析构函数
  40. void MakeEmpty();                              //清空一个链表,只余表头结点
  41. Node<T>* Find(T data);           //搜索数据域与data相同的结点,返回该结点的地址
  42. int Length();                                //计算单链表长度
  43. void PrintList();                    //打印链表的数据域
  44.     void InsertFront(Node<T>* p);      //可用来向前生成链表,在表头插入一个结点
  45. void InsertRear(Node<T>* p);       //可用来向后生成链表,在表尾添加一个结点
  46. void InsertOrder(Node<T> *p);  //按升序生成链表
  47. Node<T>*CreatNode(T data);             //创建一个结点(孤立结点)
  48. Node<T>*DeleteNode(Node<T>* p);        //删除指定结点
  49. };
  50. template<typename T>List<T>::List(){
  51. head=tail=new Node<T>();
  52. }
  53. template<typename T>List<T>::~List(){
  54. MakeEmpty();
  55. delete head;
  56. }
  57. template<typename T>void List<T>::MakeEmpty(){
  58. Node<T> *tempP;
  59. while(head->link!=NULL){
  60. tempP=head->link;
  61. head->link=tempP->link;  //把头结点后的第一个节点从链中脱离
  62. delete tempP;            //删除(释放)脱离下来的结点
  63. }
  64. tail=head;  //表头指针与表尾指针均指向表头结点,表示空链
  65. }
  66. template<typename T> Node<T>* List<T>::Find(T data){
  67. Node<T> *tempP=head->link;
  68. while(tempP!=NULL&&tempP->info!=data) tempP=tempP->link;
  69. return tempP;        //搜索成功返回该结点地址,不成功返回NULL
  70. }
  71. template<typename T>int List<T>::Length(){
  72. Node<T>* tempP=head->link;
  73. int count=0;
  74. while(tempP!=NULL){
  75. tempP=tempP->link;
  76. count++;
  77. }
  78. return count;
  79. }
  80. template<typename T>void List<T>::PrintList(){
  81. Node<T>* tempP=head->link;
  82. while(tempP!=NULL){
  83. cout<<tempP->info<<'t';
  84. tempP=tempP->link;
  85. }
  86. cout<<endl;
  87. }
  88. template<typename T>void List<T>::InsertFront(Node<T> *p){
  89. p->link=head->link;
  90. head->link=p;
  91. if(tail==head) tail=p;
  92. }
  93. template<typename T>void List<T>::InsertRear(Node<T> *p){
  94. p->link=tail->link;
  95. tail->link=p;
  96. tail=p;
  97. }
  98. template<typename T>void List<T>::InsertOrder(Node<T> *p){
  99. Node<T> *tempP=head->link,*tempQ=head;        //tempQ指向tempP前面的一个节点
  100. while(tempP!=NULL){
  101. if(p->info<tempP->info)break; //找第一个比插入结点大的结点,由tempP指向
  102. tempQ=tempP;
  103. tempP=tempP->link;
  104. }
  105. tempQ->InsertAfter(p); //插在tempP指向结点之前,tempQ之后
  106. if(tail==tempQ) tail=tempQ->link;
  107. }
  108. template<typename T>Node<T>* List<T>::CreatNode(T data){//建立新节点
  109. Node<T>*tempP=new Node<T>(data);
  110. return tempP;
  111. }
  112. template<typename T>Node<T>* List<T>::DeleteNode(Node<T>* p){
  113. Node<T>* tempP=head;
  114. while(tempP->link!=NULL&&tempP->link!=p) tempP=tempP->link;
  115. if(tempP->link==tail) tail=tempP;
  116. return tempP->RemoveAfter();       //本函数所用方法可省一个工作指针,与InsertOrder比较
  117. }