第3章链表 ∥.成员函数的实现 template <class Type> ListNode<Type>: ListNode(: link( NULL )0 ∥构造函数,仅初始化指针成员。 template <class Type> ListNode<Type> ListNode const Type item ) data( item ) link( NULL)0 ∥构造函数,初始化数据与指针成员。 template <class Type> List<Type>: List( const Type finishied) ∥创建一个带表头结点的有序单链表, finished是停止建表输入标志,是所有输入值中不可能出现的数值 first=last=new ListNode<Type>( ) ∥创建表头结点 Type value; ListNode<Type> *p, *g,*s: cin > value while( value 环建立各个结点 s= new ListNode<Type>( value ) q=first; p= first->link; while(p l=NULL && p->data <=value 找新结点插入位置 q->link =s; /在q,p间插入新结点 if( p= NULL )last=s cin > value: template <class Type> void List<Type>: Browse(i ∥浏览并输出链表的内容 cout<<\nThe list is \n" ListNode<Type>"p= first->link while(p I= NULL)t cout < p->data; if( pI= last )cout <<"->i else cout < endI: p= p->link; template <class Type> void List <Type>: Merge( List<Type>& hb) ∥将当前链表this与链表hb按逆序合并,结果放在当前链表this中。 pa= first->link; pb= hb. first->link ∥检测指针跳过表头结点 first->link NULL ∥结果链表初始化 while( pa= NULL & pb NULL )t 当两链表都未结束时 if( pa->data <=pb->data (q=pa: pa= pa->link; j ∥从pa链中摘下第 3 章 链表 25 //各成员函数的实现 template <class Type> ListNode<Type> :: ListNode ( ) : link ( NULL ) { } //构造函数, 仅初始化指针成员。 template <class Type> ListNode<Type> :: ListNode ( const Type & item ) : data ( item ), link ( NULL ) { } //构造函数, 初始化数据与指针成员。 template <class Type> List<Type> :: List ( const Type finishied ) { //创建一个带表头结点的有序单链表, finished 是停止建表输入标志, 是所有输入值中不可能出现的数值。 first = last = new ListNode<Type>( ); //创建表头结点 Type value; ListNode<Type> *p, *q, *s; cin >> value; while ( value != finished ) { //循环建立各个结点 s = new ListNode<Type>( value ); q = first; p = first->link; while ( p != NULL && p->data <= value ) { q = p; p = p->link; } //寻找新结点插入位置 q->link = s; s->link = p; //在 q, p 间插入新结点 if ( p == NULL ) last = s; cin >> value; } } template <class Type> void List<Type> :: Browse ( ) { //浏览并输出链表的内容 cout<<"\nThe List is : \n"; ListNode<Type> *p = first->link; while ( p != NULL ) { cout << p->data; if ( p != last ) cout << "->"; else cout << endl; p = p->link; } } template <class Type> void List <Type> :: Merge ( List<Type>& hb) { //将当前链表 this 与链表 hb 按逆序合并，结果放在当前链表 this 中。 ListNode<Type> *pa, *pb, *q, *p; pa = first->link; pb = hb.first->link; //检测指针跳过表头结点 first->link = NULL; //结果链表初始化 while ( pa != NULL && pb != NULL ) { //当两链表都未结束时 if ( pa->data <= pb->data ) { q = pa; pa = pa->link; } //从 pa 链中摘下