3-2试编写一个算法,在带表头结点的单链表中寻找第i个结点。若找到,则函数返回第i个结点的 地址;若找不到,则函数返回0 【解答】 template <class Type> LisiNode <Type>* List <Type>: GetANode( int i)i ∥取得单链表中第i个结点地址,i从0开始计数,i<0时返回指针0,i=0时返回表头结点地址。 if( i< 1)return NULL ListNode <Type>*p=first; int k=0; while(p I=NULL &&k<i)p=p-link; A++;1 return p; 3-3设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个 有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占 用其它的存储空间。表中允许有重复的数据。 【解答】 #include <iostream h> template <class Type> class List; template <class Type> class Lisinode friend class LisKType> ListNode (i ListNode( const Type& item ) ∥构造函数 private Type data; template <class Type> class List i List( const Type finishied ) ∥建立链表 void Browse ( ∥打印链表 void Merge( Lis/<Type>&hb ) ∥连接链表 rivate ListNode<Type ∥.成员函数的实现 template <class Type> LisiNode<Type>: LisiNode ( link( NULl)& ∥构造函数,仅初始化指针成员 template <class Type> ListNodesType>: ListNode( const Type item ): data( item ), link( NULL)3-2 试编写一个算法，在带表头结点的单链表中寻找第 i 个结点。若找到，则函数返回第 i 个结点的 地址；若找不到，则函数返回 0。 【解答】 template <class Type> ListNode <Type> * List <Type> :: GetANode ( int i ) { //取得单链表中第 i 个结点地址, i 从 0 开始计数, i < 0 时返回指针 0, i = 0 时返回表头结点地址。 if ( i < 1 ) return NULL; ListNode <Type> * p = first; int k = 0; while ( p != NULL && k < i ) { p = p→link; k++; } return p; } 3-3 设 ha 和 hb 分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个 有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占 用其它的存储空间。表中允许有重复的数据。 【解答】 #include <iostream.h> template <class Type> class List; template <class Type> class ListNode { friend class List<Type>; public: ListNode ( ); //构造函数 ListNode ( const Type& item ); //构造函数 private: Type data; ListNode<Type> *link; }; template <class Type> class List { public: List ( const Type finishied ); //建立链表 void Browse ( ); //打印链表 void Merge ( List<Type> &hb ); //连接链表 private: ListNode<Type> *first, *last; }; //各成员函数的实现 template <class Type> ListNode<Type>::ListNode ( ) : link ( NULL ) { } //构造函数, 仅初始化指针成员。 template <class Type> ListNode<Type> :: ListNode ( const Type & item ) : data ( item ), link ( NULL ) { }