第3章链表 第3章链表 单链表的结点类( List Node class)和链表类( ist class的类定义 前视的类定义 template <class Type> class ListNode i ∥链表结点类的定义 friend class List<Type>: List类作为友元类定义 Type data; ListNode<Type> *link ∥链指针域 public: ListNode(): link(NULL)0 ∥仅初始化指针成员的构造函数 ListNode const Type& item ) data(item), link (NULL)& ∥初始化数据与指针成员的构造函数 ListNode<Type> .getNode const Type& item, ListNode<Type> *next= NULL 以tem和next建立一个新结点 ListNode<Iype>* getLink O{ return link;}∥得结点的下一结点地址 Type getData(i return data; 3 取得结点中的数据 void setLink( ListNode<Type> *next)i link =next; 3 ∥修改结点的link指针 void setData( Type value)( data= value; ∥修改结点的data值 template <class Type> class List i ∥单链表类定义 private: ListNode<Type> 'first,*curren ∥链表的表头指针和当前元素指针 public: List( const Type& value)( first=current new ListNode<Type>( value );3 ∥构造函数 -List () MakeEmpty () delete first;) ∥析构函数 Make Empty ( ∥将链表置为空表 int Length()const; ∥计算链表的长度 ListNode<Type> *Find( Type value ) ∥搜索含数据 value的元素并成为当前元素 ListNode<Type> *Locate( int 1); ∥搜索第i个元素的地址并置为当前元素 Type* GetData (; /取出表中当前元素的值 int Insert( Type value ) ∥将vaue插在表当前位置之后并成为当前元素 ∥将链表中的当前元素删去,填补者为当前元素 ListNodetype>* Firster (i current first; return first; ∥当前指针定位于表头结点 Type*First ( ∥当前指针定位于表中第一个元素并返回其值 Type"Next ( 将当前指针进到表中下一个元素并返回其值 int notnull(){ return current=NUL;}表中当前元素空否?空返回1,不空返回0 int NextNotNull (i return current I= NULL & current->link I= NULL; ∥当前元素下一元素空否?空返回1,不空返回0 };第 3 章 链表 21 第 3 章 链表 单链表的结点类(ListNode class)和链表类(List class)的类定义。 template <class Type> class List; //前视的类定义 template <class Type> class ListNode { //链表结点类的定义 friend class List<Type>; //List 类作为友元类定义 private: Type data; //数据域 ListNode<Type> *link; //链指针域 public: ListNode ( ) : link (NULL) { } //仅初始化指针成员的构造函数 ListNode ( const Type& item ) : data (item), link (NULL) { } //初始化数据与指针成员的构造函数 ListNode<Type> * getNode ( const Type& item, ListNode<Type> *next = NULL ) //以 item 和 next 建立一个新结点 ListNode<Type> * getLink ( ) { return link; } //取得结点的下一结点地址 Type getData ( ) { return data; } //取得结点中的数据 void setLink ( ListNode<Type> * next ) { link = next; } //修改结点的 link 指针 void setData ( Type value ) { data = value; } //修改结点的 data 值 }; template <class Type> class List { //单链表类定义 private: ListNode<Type> *first, *current; //链表的表头指针和当前元素指针 public: List ( const Type& value ) { first = current = new ListNode<Type> ( value ); } //构造函数 ~List ( ) { MakeEmpty ( ); delete first; } //析构函数 void MakeEmpty ( ); //将链表置为空表 int Length ( ) const; //计算链表的长度 ListNode<Type> * Find ( Type value ); //搜索含数据 value 的元素并成为当前元素 ListNode<Type> * Locate( int i ); //搜索第 i 个元素的地址并置为当前元素 Type * GetData ( ); //取出表中当前元素的值 int Insert ( Type value ); //将 value 插在表当前位置之后并成为当前元素 Type *Remove ( ); //将链表中的当前元素删去, 填补者为当前元素 ListNode<Type> * Firster ( ) { current = first; return first; } //当前指针定位于表头结点 Type *First ( ); //当前指针定位于表中第一个元素并返回其值 Type *Next ( ); //将当前指针进到表中下一个元素并返回其值 int NotNull ( ) { return current != NULL; } //表中当前元素空否？空返回 1, 不空返回 0 int NextNotNull ( ) { return current != NULL && current->link != NULL; } //当前元素下一元素空否？空返回 1, 不空返回 0 };