第3章链表 while( l=NULL &&k<i)p= p->link; k++1 ∥循环,p=NUIL表示链短,无第i个结点 return p; ∥若pl=NULL,则k=i返回第i个结点地址 (2)实现求最大值的函数如下: template <class Type> ListNode <Type>.List <Type>: Max ()i ∥在单链表中进行一趟检测,找出具有最大值的结点地址,如果表空,返回指针NULL if first-> link nulL )return NULL ∥空表,返回指针NUIL ListNode<Iype>*pmax=fist->link,p=fist->link->link;∥假定第一个结点中数据具有最大值 while(p I= NULL W循环,下一个结点存在 if( p->data >pma ∥指针pmax记忆当前找到的具最大值结点 ∥检测下一个结点 return pmax (3)实现统计单链表中具有给定值x的所有元素的函数如下 template <class Type> int List <Type>: Count(Type& x)i ∥在单链表中进行一趟检测,找出具有最大值的结点地址,如果表空,返回指针NULL ListNode <Type>*p=first->link ∥从第一个结点开始检测 while(p I= NULL )i ∥循环,下一个结点存在 if(p->data =x)n++; ∥找到一个,计数器加1 ∥检测下一个结点 return n: (4)实现从一维数组A[m建立单链表的函数如下: template <class Type> void List <Type>: Create( Type A[, int n)& ∥根据一维数组A[n]建立一个单链表,使单链表中各元素的次序与A[n]中各元素的次序相同 first=p= new ListNode<Type 建表头结点 for( int i=0;i<n; i++)i p->link =new ListNode<Type>(A[); ∥链入一个新结点,值为A ∥指针p总指向链中最后一个结点 p->link NULL 采用递归方法实现时,需要通过引用参数将已建立的单链表各个结点链接起来。为此,在递归地 扫描数组A[n]的过程中,先建立单链表的各个结点,在退出递归时将结点地址p(被调用层的形参) 带回上一层(调用层)的实参p->link template<Type> void List<Type>: create( Type all, int n, int 1, ListNode<Type> *&p)i ∥有函数:递归调用建立单链表 if(i==n)p=NULL; else( p= new ListNode<Type>( A[]) ∥建立链表的新结点第 3 章 链表 23 while ( p != NULL && k < i ) { p = p->link; k++; } //循环, p == NULL 表示链短, 无第 i 个结点 return p; //若 p != NULL, 则 k == i, 返回第 i 个结点地址 } (2) 实现求最大值的函数如下： template <class Type> ListNode <Type> * List <Type> :: Max ( ) { //在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULL if ( first->link == NULL ) return NULL; //空表, 返回指针 NULL ListNode <Type> * pmax = first->link, p = first->link->link; //假定第一个结点中数据具有最大值 while ( p != NULL ) { //循环, 下一个结点存在 if ( p->data > pmax->data ) pmax = p; //指针 pmax 记忆当前找到的具最大值结点 p = p->link; //检测下一个结点 } return pmax; } (3) 实现统计单链表中具有给定值 x 的所有元素的函数如下： template <class Type> int List <Type> :: Count ( Type& x ) { //在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULL int n = 0; ListNode <Type> * p = first->link; //从第一个结点开始检测 while ( p != NULL ) { //循环, 下一个结点存在 if ( p->data == x ) n++; //找到一个, 计数器加 1 p = p->link; //检测下一个结点 } return n; } (4) 实现从一维数组 A[n]建立单链表的函数如下： template <class Type> void List <Type> :: Create ( Type A[ ], int n ) { //根据一维数组 A[n]建立一个单链表，使单链表中各元素的次序与 A[n]中各元素的次序相同 ListNode<Type> * p; first = p = new ListNode<Type>; //创建表头结点 for ( int i = 0; i < n; i++ ) { p->link = new ListNode<Type> ( A[i] ); //链入一个新结点, 值为 A[i] p = p->link; //指针 p 总指向链中最后一个结点 } p->link = NULL; } 采用递归方法实现时，需要通过引用参数将已建立的单链表各个结点链接起来。为此，在递归地 扫描数组 A[n]的过程中，先建立单链表的各个结点，在退出递归时将结点地址 p（被调用层的形参） 带回上一层（调用层）的实参 p->link。 template<Type> void List<Type> :: create ( Type A[ ], int n, int i, ListNode<Type> *& p ) { //私有函数：递归调用建立单链表 if ( i == n ) p = NULL; else { p = new ListNode<Type>( A[i] ); //建立链表的新结点