第5章递归与广义表 ∥建立链表,以输入 结束 irst= NULL: int ListNode *q out<<" Input your data: n"; 提示 输入 while( value != revalue )4 输入有效 q=New Node( value ) ∥建立包含vaue的新结点 if first== NULL first=current=q ∥空表时,新结点成为链表第一个结点 else{ current->link=q; current=q;}∥空表时,新结点链入链尾 cin > value ∥再输入 current-> link NULL ∥链尾封闭 void List PrintList (t 输出链表 p=first while( p I=nUll)( cout << p->data<<; p=p->link; 3 cout<<“n’; (1)求链表中的最大整数 int List Max( listNode "f)i ∥递归算法:求链表中的最大值 if (f->link== NULL)return f->data; ∥递归结束条件 ∥在当前结点的后继链表中求最大值 if(f->data >temp )return f->data ∥如果当前结点的值还要大,返回当前检点值 lse return temp ∥否则返回后继链表中的最大值 2)求链表的结点个数 int List Num( ListNode *f)i ∥递归算法:求链表中结点个数 if (f== NULL )return 0; 空表,返回0 return 1+ Num(f->link ) ∥否则,返回后继链表结点个数加1 (3)求所有整数的平均值 float List Avg( ListNode *f, int& n)( ∥递归算法:求链表中所有元素的平均值 if (f->link = NULL ∥链表中只有一个结点,递归结束条件第 5 章 递归与广义表 59 return newnode; } void List :: NewList ( const int retvalue ) { //建立链表, 以输入 retvalue 结束 first = NULL; int value; ListNode *q; cout << "Input your data:\n"; //提示 cin >> value; //输入 while ( value != retvalue ) { //输入有效 q = NewNode ( value ); //建立包含 value 的新结点 if ( first == NULL ) first = current = q; //空表时, 新结点成为链表第一个结点 else { current->link = q; current = q; } //非空表时, 新结点链入链尾 cin >> value; //再输入 } current->link = NULL; //链尾封闭 } void List :: PrintList ( ) { //输出链表 cout << "\nThe List is : \n"; ListNode *p = first; while ( p != NULL ) { cout << p->data << ' '; p = p->link; } cout << ‘\n’; } (1) 求链表中的最大整数 int List :: Max ( ListNode *f ) { //递归算法 : 求链表中的最大值 if ( f ->link == NULL) return f ->data; //递归结束条件 int temp = Max ( f ->link ); //在当前结点的后继链表中求最大值 if ( f ->data > temp ) return f ->data; //如果当前结点的值还要大, 返回当前检点值 else return temp; //否则返回后继链表中的最大值 } (2) 求链表的结点个数 int List :: Num ( ListNode *f ) { //递归算法 : 求链表中结点个数 if ( f == NULL ) return 0; //空表, 返回 0 return 1+ Num ( f ->link ); //否则, 返回后继链表结点个数加 1 } (3) 求所有整数的平均值 float List :: Avg ( ListNode *f , int& n ) { //递归算法 : 求链表中所有元素的平均值 if ( f ->link == NULL ) //链表中只有一个结点, 递归结束条件