赞
踩
题目:已知L为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算的递归算法:
①求链表中的最大整数;
②求链表的结点个数;
③求链表中所有节点数据的平均值。
#include<iostream> #include<algorithm> using namespace std; typedef struct node* LinkList; struct node { int data; LinkList next; }; LinkList Intialization();//链表初始化,给链表添加新的节点 int return_max(LinkList L);//返回最大值 int get_length(LinkList L);//返回长度 double get_average(LinkList L,int len);//返回平均值 int main() { LinkList L = Intialization(); int max = return_max(L); cout << "max:" << max << endl; int length = get_length(L); cout << "length:" << length << endl; double average = get_average(L, length); cout << "average:" << average << endl; return 0; } double get_average(LinkList L,int len) { //已知链表节点长度,可以直接计算每个节点占平均值的大小,叠加 if (L->next == NULL) return ((double)L->data)/len; //因为一开始定义的data是int类型,所以可以采用强制转换转换成double类型 else return get_average(L->next,len) + ((double)L->data)/len; } int get_length(LinkList L) { if (L->next == NULL) return 1;//当下一个节点为NULL,此时记作第一个节点 else return get_length(L->next) + 1;//往上回溯过程中每一次++ } int return_max(LinkList L) { if (L->next == NULL) return L->data; else return max(L->data, return_max(L->next));//这里用到max函数,返回较大的一个数 } LinkList Intialization() { //为什么这里不能对于空链表进行正确的反馈呢 //因为在这里头指针指向链表的首元素,当链表为空的时候,L=NULL,此时L->next并没有指向 LinkList point1 = new node; point1->data = 4; LinkList point2 = new node; point2->data = 5; point1->next = point2; LinkList point3 = new node; point3->data = 7; point2->next = point3; LinkList point4 = new node; point4->data = 6; point3->next = point4; LinkList point5 = new node; point5->data = -3; point4->next = point5; point5->next = NULL; return point1; }
结果就是这样的
但后来我们看到老师给的实验知道上说明要考虑空链表的存在
才发现我们之前的代码存在错误
下面是更正后的代码
#include<iostream> #include<algorithm> #define Min -1000000 using namespace std; typedef struct node* LinkList; struct node { int data; LinkList next; }; LinkList Intialization(); int return_max(LinkList L); int get_length(LinkList L); double get_average(LinkList L, int len); int main() { LinkList L = Intialization(); int length = get_length(L); if (length == 0) { cout << "无节点" << endl << "不存在平均值和最大值" << endl; exit(0); } cout << "length:" << length << endl; int max = return_max(L); cout << "max:" << max << endl; double average = get_average(L, length); cout << "average:" << average << endl; return 0; } double get_average(LinkList L, int len) { if (L == NULL) return 0; else return get_average(L->next, len) + ((double)L->data) / len; } int get_length(LinkList L) { if (L == NULL) return 0; else return get_length(L->next) + 1; } int return_max(LinkList L) { if (L == NULL) return Min;//定义一个极小值来进行比较 else return max(L->data, return_max(L->next)); } LinkList Intialization() { LinkList head = NULL, tail = NULL; int k;//输入节点个数 cin >> k; for (int i = 0; i < k; i++) { LinkList temp = new node; cin >> temp->data; temp->next = NULL; if (head == NULL) head = temp;//尾插法 else tail->next = temp; tail = temp; } return head; }
测试结果1
测试结果2
测试结果3
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。