递归方法建立链表

beyes

代码：

#include <stdio.h>
#include <stdlib.h>

struct list {
    int data;
    struct list *next;
};

typedef struct list node;
typedef node *link;

void printf_list (link ptr)
{
    if (ptr != NULL) {
        printf ("[%d]", ptr->data);
        /*递归链表输出函数调用*/
        printf_list (ptr->next);
    }
}

/*----------------------------*/
/*递归链表创建函数            */
/*----------------------------*/
link create_list (int *array, int len, int pos)
{
    link head;        /*链表结点指针*/
   
    if (pos == len)        /*终止条件*/
        return NULL;
    else {
        /*创建结点内存*/
        head = (link)malloc (sizeof (node));
        if (!head)
            return NULL;
        head->data = array [pos];    /*创建结点内容*/
        head->next = create_list (array, len, pos + 1);
        return head;
    }
}

int main ()
{
    int list [6] = {1, 2, 3, 4, 5, 6 };
    link head;

    head = create_list (list, 6, 0);
    if (!head) {
        printf ("内存分配失败!\n");
        exit (1);
    }
    printf ("链表内容:\n");
    printf_list (head);
    printf ("\n"):

    return (0);
}

运行与输出：

beyes@linux-beyes:~/C/structer/recursion> ./link_recur.exe
链表内容:
[1][2][3][4][5][6]

原理如下图所示：

beyes

#include <stdio.h>
#include <stdlib.h>

struct list {
    int data;
    struct list *next;
};

typedef struct list node;
typedef node *link;

void printf_list (link ptr)
{
    if (ptr != NULL) {
        printf ("[%d] ", ptr->data);
        /*递归链表输出函数调用*/
        printf_list (ptr->next);
    }
}

/*----------------------------*/
/*递归链表创建函数            */
/*----------------------------*/
link create_list (int *array, int len, int pos)
{
    link head;        /*链表结点指针*/
   
    if (pos == len)        /*终止条件*/
        return NULL;
    else {
        /*创建结点内存*/
        head = (link)malloc (sizeof (node));
        if (!head)
            return NULL;
        head->data = array [pos];    /*创建结点内容*/
        head->next = create_list (array, len, pos + 1);
        return head;
    }
}

/*----------------------------*/
/*递归反向输出-1              */
/*----------------------------*/
int printf_list_invert_1 (link p)
{
    int data;
    if (p->next == NULL)
        return (p->data);   
    else {
        data = printf_list_invert_1 (p->next);
        printf ("[%d] ", data);
        return (p->data);
    }
}       

/*----------------------------*/
/*递归反向输出-2              */
/*----------------------------*/
void printf_list_invert_2 (link p)
{
    if (p != NULL) {
        printf_list_invert_2 (p->next);
        printf ("[%d] ", p->data);
    }
}

int main ()
{
    int list [6] = {1, 2, 3, 4, 5, 6 };
    link head;

    head = create_list (list, 6, 0);
    if (!head) {
        printf ("内存分配失败!\\n");
        exit (1);
    }
    printf ("链表内容:\\n");
    printf_list (head);
    printf ("\\n");

    printf ("反转后输出-1: \\n");   
    printf ("[%d] ", printf_list_invert_1 (head));
    printf ("\\n");

    printf ("反转后输出-2: \\n");   
    printf_list_invert_2 (head);
    printf ("\\n");
   
    return (0);
}

运行与输出：

beyes@linux-beyes:~/C/structer/recursion> ./link_recur2.exe
链表内容:
[1] [2] [3] [4] [5] [6]
反转后输出-1:
[6] [5] [4] [3] [2] [1]
反转后输出-2:
[6] [5] [4] [3] [2] [1]