递归算法-不带头节点的单链表

朱雀 2022-07-28 10:52 160阅读 0赞

问题及代码：

/*    
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院    
    * All rights reserved.    
    * 文件名称：LinkList.cpp    
    * 作    者：单昕昕    
    * 完成日期：2016年4月14日    
    * 版 本 号：v1.0    
    * 问题描述：有一个不带头节点的单链表，设计递归算法：
                （1）求以h为头指针的单链表的节点个数
                （2）反向显示以h为头指针的单链表的所有节点值
    * 程序输入：数组A[n]。   
    * 程序输出：n个元素的平均值。  
    */      
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <time.h>
    #include <stdlib.h>
    using namespace std;
    //不带头节点的单链表的节点类型
    typedef struct Node
    {
        int data;
        struct Node *next;
    } LinkList;
    LinkList *h;
    void Create(LinkList *&h,int a[],int n)
    {
        //建立一个不带头节点的单链表
        int i;
        LinkList *s,*r;
        h=(LinkList *)malloc(sizeof(LinkList));
        h->data=a[0];
        h->next=NULL;
        r=h;
        for(i=1; i<n; ++i)
        {
            s=(LinkList *)malloc(sizeof(LinkList));
            s->data=a[i];
            r->next=s;
            r=s;
        }
        r->next=NULL;
    }
    //求以h为头指针的单链表的节点个数
    int Number(LinkList *h)
    {
        if(h==NULL)
            return 0;
        else
            return 1+Number(h->next);
    }
    //反向显示以h为头指针的单链表的所有节点值
    void Display(LinkList *h)
    {
        if(h==NULL)
            return ;
        else
        {
            Display(h->next);
            cout<<h->data<<" ";
            //如果是正向显示的话，cout写在Display递归上面
        }
    }
    int main()
    {
        int a[10]= {0,1,2,3,4,5,6,7,8,9};//作为预设单链表中的data值
        Create(h,a,10);//尾插法将a数组中的值插入链表
        cout<<"以h为头指针的单链表的节点个数=";
        cout<<Number(h)<<endl;
        cout<<"反向显示以h为头指针的单链表的所有节点值"<<endl;
        Display(h);
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220724/57d2311f0b374f1498a344ad961f47d4.png