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

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

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

基本的实现如下所示：

#include
#include

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 ",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 ",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)
{
returnhead->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;

returnhead;
}

/*删除链表*/
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("");

bkprint_listnode(head);

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

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

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

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

printf("");

bkprint_listnode(head);
#endif

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

head = NULL;

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