第3章链表 create(A, n, i+1, p->link ) ∥递归返回时p->link中放入下层p的内容 template<Type> void List<Type> : create( Type A[l, int n )i ∥外部调用递归过程的共用函数 first=current=new ListNode<Typ ∥建立表头结点 create(A, n, 0, first->link ) ∥递弟归建立单链表 (5)实现在非递减有序的单链表中删除值相同的多余结点的函数如下 template <class Type> void List <Type>:: tidyup (i ListNode<Type> *p= first-> link, temp: ∥检测指针,初始时指向链表第一个结点 while( p I= nULL & p->link I= NULL ∥循环检测链表 if( p->data ==p->link->data )t ∥若相邻结点所包含数据的值相等 temp= p->first; p->link temp-> link ∥为删除后一个值相同的结点重新拉链 delete temp ∥删除后一个值相同的结点 ∥指针p进到链表下一个结点 3-3设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有 序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用 其它的存储空间。表中允许有重复的数据。 【解答】 #include <iostream h> template <class Type> class List; template <class Type> class ListNode friend class List<Type>: ∥构造函数 ListNode const Type& item ) ∥构造函数 private Type data; template <class Type> class List i List( const Type finishied ) ∥建立链表 void Browse(片; 印链表 void Merge( List<Type> &hb )i ∥连接链表 ListNode<Type> "first, 'last;第 3 章 链表 24 create ( A, n, i+1, p->link ); //递归返回时 p->link 中放入下层 p 的内容 } } template<Type> void List<Type> :: create ( Type A[ ], int n ) { //外部调用递归过程的共用函数 first = current = new ListNode<Type>; //建立表头结点 create ( A, n, 0, first->link ); //递归建立单链表 } (5) 实现在非递减有序的单链表中删除值相同的多余结点的函数如下： template <class Type> void List <Type> :: tidyup ( ) { ListNode<Type> * p = first->link, temp; //检测指针, 初始时指向链表第一个结点 while ( p != NULL && p->link != NULL ) //循环检测链表 if ( p->data == p->link->data ) { //若相邻结点所包含数据的值相等 temp = p->first; p->link = temp->link; //为删除后一个值相同的结点重新拉链 delete temp; //删除后一个值相同的结点 } else p = p->link; //指针 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; };