p82_2.cpp

清华大学数据结构的教程源码,c++版的,有助于提高自已对数据结构的认识

		#include <stdio.h>

		enum Boolean { False, True };
		template <class Type> class List;					//链表类的前视定义
		template <class Type> class ListIterator;				//链表结点类的前视定义

		template <class Type> class ListNode {					//链表结点类的类声明
		friend class List <Type>;							//友元
		friend class ListIterator <Type>;					//友元
		friend class Polynomial;
		friend Polynomial operator + ( const Polynomial & ah, const Polynomial & bh );
		public:
		   ListNode ( const Type value ) : data (value), link (NULL) { }
		   //………
		private:
		   Type data;
		   ListNode<Type> *link;
		};

		template <class Type> class List {					//链表类的类声明
		public:
		   friend class ListIterator<Type>;
		   List ( const Type value) { last =first = new ListNode<Type> (value) ; }	//构造函数
		   int sum ();
		   void Add ( const Type value ) ;
		   //………
		private:
		   ListNode<Type> *first, *last;
		};

		template <class Type> class ListIterator {				//链表游标类的类声明
		public:
		   ListIterator ( const List<Type> & l ) : list (l), current (l.first) { }
		   Boolean NotNull ( );
		   Boolean NextNotNull ( );
		   ListNode<Type>* First ( );
		   ListNode<Type>* Next ( );
		private:
		   const List<Type> & list;						//引用一个已存在的链表
		   ListNode<Type> *current;						//指向链表中的一个结点
		}

		template <class Type> Boolean ListIterator<Type>::NotNull ( ) {
		//检查链表中当前元素是否非空
		   if ( current != NULL ) return True; 					//链表当前结点指针非空
		   else return False;
		}

		template <class Type> Boolean ListIterator<Type>::NextNotNull ( ) {
		//检查链表中下一元素是否非空
		   if ( current != NULL && current->link != NULL ) return True;
		   else return False;
		}

		template <class Type> ListNode<Type>* ListIterator<Type>::First ( ) {
		//返回指向链表中表头结点的指针
		   if ( list.first->link != NULL ) { current = list.first; }
		   else { current = NULL; }
		   return current ;
		}

		template <class Type> ListNode<Type>* ListIterator<Type>::Next ( ) {
		//返回指向链表中下一个结点的指针
		   if ( current != NULL && current->link != NULL ) { current = current->link; }
		   else { current = NULL; }
		   return current;
		}

		char compare ( int a, int b ) {
		    if ( a > b ) return '>';
		    else if ( a == b ) return '=';
		    else return '<';
		}

		struct Term {						//用链表表示的多项式中, 链表结点的定义
		   int coef;							//系数
		   int exp;							//指数
		   void Init ( int c, int e ) { coef = c;  exp = e; }
		};

		class Poly