P77_79.cpp
上传用户:chaiyuqiu
上传日期:2022-08-03
资源大小:27k
文件大小:6k
源码类别:

数据结构

开发平台:

C/C++

  1. #include <stdio.h>
  2. enum Boolean { False, True };
  3. template <class Type> class List; //链表类的前视定义
  4. template <class Type> class ListIterator; //链表结点类的前视定义
  5. template <class Type> class ListNode { //链表结点类的类声明
  6. friend class List <Type>; //友元
  7. friend class ListIterator <Type>; //友元
  8. public:
  9.    ListNode ( const Type value ) : data (value), link (NULL) { }
  10.    //………
  11. private:
  12.    Type data;
  13.    ListNode<Type> *link;
  14. };
  15. template <class Type> class List { //链表类的类声明
  16. public:
  17.    friend class ListIterator<Type>;
  18.    List ( const Type value) { last =first = new ListNode<Type> (value) ; } //构造函数
  19.    void Add ( const Type value ) ;
  20.    //………
  21. private:
  22.    ListNode<Type> *first, *last;
  23. };
  24. template <class Type> class ListIterator { //链表游标类的类声明
  25. public:
  26.    ListIterator ( const List<Type> & l ) : list (l), current (l.first) { }
  27.    Boolean NotNull ( );
  28.    Boolean NextNotNull ( );
  29.    Type First ( );
  30.    Type Next ( );
  31. private:
  32.    const List<Type> & list; //引用一个已存在的链表
  33.    ListNode<Type> *current; //指向链表中的一个结点
  34. }
  35. template <class Type> Boolean ListIterator<Type>::NotNull ( ) {
  36. //检查链表中当前元素是否非空
  37.    if ( current != NULL ) return True;  //链表当前结点指针非空
  38.    else return False;
  39. }
  40. template <class Type> Boolean ListIterator<Type>::NextNotNull ( ) {
  41. //检查链表中下一元素是否非空
  42.    if ( current != NULL && current->link != NULL ) return True;
  43.    else return False;
  44. }
  45. template <class Type> Type ListIterator<Type>::First ( ) {
  46. //返回指向链表中表头结点的指针
  47.    Type temp;
  48.    if ( list.first->link != NULL ) {
  49.        current = list.first;
  50.        temp = current->data;
  51.    }
  52.    else { current = NULL; temp = 0;}
  53.    return temp;
  54. }
  55. template <class Type> Type ListIterator<Type>::Next ( ) {
  56. //返回指向链表中下一个结点的指针
  57.    Type temp;
  58.    if ( current != NULL && current->link != NULL ) {
  59.       current = current->link;
  60.       temp = current->data;
  61.    }
  62.    else { current = NULL; temp = 0;}
  63.    return temp;
  64. }
  65. int sum ( const List<int> &l ) {
  66.    ListIterator<int> li (l); //定义对象li为操作链表对象l的游标对象
  67.    if ( ! li.NextNotNull ( ) ) return 0; //空链表, 返回0
  68.    int retvalue = li.First ( ); //取得第一个元素的值
  69.    while ( li.NextNotNull ( ) ) retvalue += li.Next ( ); //看是否下一个结点存在,若有, 累加
  70.    return retvalue;
  71. }
  72. template <class Type> void List<Type>::Add(const Type value) {
  73.    last->link = new ListNode<Type> (value);
  74.                    last = last->link;
  75. }