数据结构 第3--8章 应用和部分算法题.doc

第三章 （10）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： ① 求链表中的最大整数； ② 求链表的结点个数； ③ 求所有整数的平均值。 #include iostream.h //定义在头文件RecurveList.h中 class List; class ListNode { //链表结点类 friend class List; private: int data; //结点数据 ListNode *link; //结点指针 ListNode ( const int item ) : data(item), link(NULL) { } //构造函数 }; class List { //链表类 private: ListNode *first, current; int Max ( ListNode *f ); int Num ( ListNode *f ); float Avg ( ListNode *f, int n ); public: List ( ) : first(NULL), current (NULL) { } //构造函数 ~List ( ){ } //析构函数 ListNode* NewNode ( const int item ); //创建链表结点, 其值为item void NewList ( const int retvalue ); //建立链表, 以输入retvalue结束 void PrintList ( ); //输出链表所有结点数据 int GetMax ( ) { return Max ( first ); } //求链表所有数据的最大值 int GetNum ( ) { return Num ( first ); } //求链表中数据个数 float GetAvg ( ) { return Avg ( first ); } //求链表所有数据的平均值 }; ListNode* List :: NewNode ( const int item ) { //创建新链表结点 ListNode *newnode = new ListNode (item); 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’; } 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; //否则返回后继链表中的最大值 } int List :: Num ( ListNode *f ) { //递归算法 : 求链表中结点个数 if ( f == NULL ) return 0;