|
描述
利用单链表表示一个整数序列，利用递归的方法计算单链表中结点的个数。
输入
多组数据，每组数据有两行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔）。当n=0时输入结束。
输出
对于每组数据分别输出一行，对应链表中的各个结点个数。
输入样例 1?
4
1 2 3 4
6
1 2 43 5 7 2
0
输出样例 1
4
6
思路：
Num是我写的递归函数，因为计算节点数量的时候不想考虑头节点，所以传参数的时候直接传的是l->next，直接从首元节点开始。
首先是先找递归的出口，计算节点数量肯定要遍历整个链表，遍历到最后一个节点就必须要返回了，如果真的是一个只有一个节点的链表，那么立刻返回1（表示节点数量是1）。找出口以及返回值的思想可以借鉴分类讨论里先讨论最简单（最特殊）情况的思想，如果其他情况都符合通式，这个情况不符合通式，那这个情况就是特殊情况。
倒着往回想，如果有两个及以上的节点，那么每次只需要在该函数的返回值上依次加一就可以了，表示每次调用该函数都说明都比上次多一个节点。
代码：
#include<iostream>
using namespace std;
typedef struct LNode
{
int data;
struct LNode* next;
}*linklist, LNode;
void Insert(linklist& l, int n)
{
l = new LNode;
l->next = NULL;
linklist rear = l;
for (int i = 0; i < n; i++)
{
linklist p = new LNode;
cin >> p->data;
p->next = NULL;
rear->next = p;
rear = p;
}
}
int Num(linklist l)
{
return l->next == NULL ? 1 : Num(l->next)+1;
}
int main()
{
int n;
while (cin >> n && n != 0)
{
linklist l;
Insert(l, n);
cout<<Num(l->next)<<endl;
}
return 0;
}
|