单向链表基本操作的递归实现

这几天正在复习一些基本的算法和实现，今天看了看递归的基本原理，发现自己对递归还不是特别清楚，特别是不清楚递归的思想，不能很准确的把握先分解成小事件，在合并的思想，其实也是数学归纳法的程序体现，其实数学归纳法是一种强大的方法，记得高中的时候最喜欢做的题目就是数学归纳方面的证明，现在想过来好多问题我不能采用这种方式思考，可见知识真的是有联系的，只是我们没有找到联系的方式而已。

 

为了熟悉递归的思想，我尝试了采用递归的方式实现单向链表的基本操作。单向的链表是C语言课程中接触到的中比较复杂的数据结构，但是他确实其他数据结构的基础，在一般情况下都是采用迭代的形式实现，迭代的形式相比递归要节省时间和空间，但是代码相对来说要复杂，递归往往只是简单的几句代码，我主要是为了熟悉迭代，并不在性能上进行分析。

 

基本的实现如下所示：

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

typedef struct listnode
{
        int val;
        struct listnode *next;
}List;

/*统计节点个数*/
int count_listnode(List *head)
{
        static int count = 0;

        if(NULL != head)
        {
                count += 1;
                if(head->next != NULL)
                {
                        count_listnode(head->next);
                }

                return count;
        }
}

/*顺序打印*/
void fdprint_listnode(List *head)
{
        if(NULL != head)
        {
                printf("%d\t",head->val);
                if(head->next != NULL)
                {
                        fdprint_listnode(head->next);
                }
        }
}
/*反向打印*/
void bkprint_listnode(List *head)
{
        if(head != NULL)
        {
                if(head->next != NULL)
                {
                        bkprint_listnode(head->next);
                }

                printf("%d\t",head->val);
        }
}
/*删除一个节点的数据为d的节点*/
List *delete_node(List * head, int d)
{
        List *temp = head;

        if(head != NULL)
        {
                if(head->val == d)
                {
                        temp = head;
                        head = head->next;
                        free(temp);
                        temp = NULL;
                }
                else
                {
                        temp = head->next;
                        if(temp != NULL)
                        {
                                temp = delete_node(temp,d);
                                head->next = temp;
                        }
                }
        }

        return head;
}

/*删除所有val = d的节点*/
List* delete_allnode(List *head, int d)
{
        List *temp = head, *cur = head;
        if(head != NULL)
        {
                /*如果第一个就是需要删除的对象*/
                if(cur->val == d)
                {
                        temp = cur;
                        cur = cur->next;
                        free(temp);
                        temp = NULL;
                        temp = delete_allnode(cur, d);
                        head = temp;
                }
                else /*不是删除的对象*/
                {
                        cur = head->next;
                        temp = delete_allnode(cur, d);
                        /*将得到的链表连接到检测的区域*/
                        head->next = temp;
                }
        }
        return head;
}
/*最大值*/
int max_list(List *head)
{
        int max = 0;
        int temp;
        if(NULL == head)
        {
                printf("Error: NULL pointer...");
        }

        if(NULL != head && head->next == NULL)
        {
                return head->val;
        }

        else
        {
                temp = max_list(head->next);

                max = (head->val > temp ? head->val : temp);

                return max;
        }
}

/*最小值*/
int min_list(List *head)
{
        int min = 0;
        int temp;

        if(NULL == head)
        {
                printf("Error: NULL pointer...");
        }

        if(NULL != head && head->next == NULL)
        {
                return head->val;
        }

        else
        {
               temp = min_list(head->next);

                min = (head->val < temp ? head->val : temp);

                return min;
        }
}

/*创建链表*/
List* create_list(int val)
{
        List *head = (List *)malloc(sizeof(List)/sizeof(char));

        if(NULL == head)
        {
                return NULL;
        }

        head->val = val;

        head->next = NULL;

        return head;
}

/*插入节点*/
List* insert_listnode(List *head, int val)
{
        List *temp;
        if(NULL == head)
        {
                return NULL;
        }

        temp = (List *)malloc(sizeof(List)/sizeof(char));
        temp->val = val;
        temp->next = head;
        head = temp;

        return head;
}

/*删除链表*/
void delete_list(List *head)
{
        List *temp = NULL;
        if(head != NULL)
        {
                temp = head;
                head = head->next;
                free(temp);
                temp = NULL;

                delete_list(head);
        }
}

int main()
{
        int n = 0;
        int i = 0;
        List * head = create_list(10);

        for(i = 0; i < 10; ++ i)
        {
                n = 1 + (int)(10.0*rand()/(RAND_MAX + 1.0));

                head = insert_listnode(head, n);
        }

        fdprint_listnode(head);

        printf("\n");

        bkprint_listnode(head);

        printf("\n%d\n", count_listnode(head));

        printf("\n");
#if 10
        head = delete_node(head, 10);
        fdprint_listnode(head);
       printf("\n");

        bkprint_listnode(head);
        printf("\n");
#endif

#if 10
        head = delete_allnode(head, 10);
        fdprint_listnode(head);

        printf("\n");

        bkprint_listnode(head);
#endif

        printf("max = %d\n",max_list(head));
        printf("max = %d\n",min_list(head));
        delete_list(head);

        head = NULL;

        if(head == NULL)
        {
                printf("ERROR:null pointer!...\n");
        }
        return 0;
}

递归中需要注意的思想我任务就是为了解决当前的问题，我完成最简单的一部操作，其他的由别人去完成，比如汉诺塔中的第一个和尚让第二个和尚把前63个金盘放在B处，而他自己只需要完成从A到C的搬运，实质上他自己完成的只有一部最简答的，但是搬运这种动作有存在非常大的相似性。

 

因此为了解决当前的问题f(n),就需要解决问题f(n-1),而f(n-1)的解决就需要解决f(n-2)，这样逐层的分解，分解成很多相似的小事件，当最小的事件解决完成以后，就能解决高层次的事件，这种逐层分解，逐层合并的方式就构成了递归的思想，最主要的要找到递归的出口和递归的方式，搞清楚了这两个，实现一个递归问题相对来说就比较简单啦。

 

但是递归也存在问题，特别是深层次的递归可能导致栈空间的溢出，因为堆栈空间的大小并不是无限大的，特别当递归中数据量特别大的情况下，递归很有可能导致栈空间的溢出，因此递归并不是万能的，但是递归确实是一种思考问题的方式，一种反向思考的形式，从结果到具体的小过程。当然具体的问题就要具体分析啦。

 

用一句简单的话记住递归就是：我完成最简单的那一步，其他的复杂的相似问题都找别人去做吧。