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

1、单向链表基本操作的递归实现这几天正在复习一些基本的算法和实现，今天看了看递 归的基本原理，发现自己对递归还不是特别清楚，特别 是不清楚递归的思想，不能很准确的把握先分解成小事 件，在合并的思想，其实也是数学归纳法的程序体现， 其实数学归纳法是一种强大的方法，记得高中的时候最 喜欢做的题目就是数学归纳方面的证明，现在想过来好 多问题我不能采用这种方式思考，可见知识真的是有联 系的，只是我们没有找到联系的方式而已。为了熟悉递归的思想，我尝试了采用递归的方式实现单 向链表的基本操作。单向的链表是 C 语言课程中接触到 的中比较复杂的数据结构，但是他确实其他数据结构的 基础，在一般情况下都是采用迭代的

2、形式实现，迭代的 形式相比递归要节省时间和空间，但是代码相对来说要 复杂，递归往往只是简单的几句代码，我主要是为了熟 悉迭代，并不在性能上进行分析。 基本的实现如下所示：#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;count_listnode(head->next); return count;/* 顺

3、序打印 */void fdprint_listnode(List *head) if(NULL != head)printf("%dt",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("%dt&

4、quot;,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;elsetemp = head->next;if(temp != NULL)temp = delete_node(temp,d);head->next = temp;return head;/* 删除所有 va

5、l = 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;/* 将得到的链表连接到检测的区域 */head->n

6、ext = 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;elsetemp = max_list(head->next);max = (head->val > temp ? head->val : temp); re

7、turn 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 ;val : temp); return min;/* 创建链表 */List* create_

8、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 = va

9、l;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*ra

10、nd()/(RAND_MAX + 1.0); head = insert_listnode(head, n);fdprint_listnode(head); printf(&quot;n&quot;); bkprint_listnode(head); printf(&quot;n%dn&quot;, count_listnode(head);printf(&quot;n&quot;);#if 10head = delete_node(head, 10);fdprint_listnode(head);printf(&quot;n&q

11、uot;);bkprint_listnode(head);printf(&quot;n&quot;);#endif#if 10head = delete_allnode(head, 10);fdprint_listnode(head);printf(&quot;n&quot;);bkprint_listnode(head);#endifprintf(&quot;max= %dn&quot;,max_list(head);printf(&quot;max= %dn&quot;,min_list(head);delete_list(h

12、ead); head = NULL; if(head = NULL)printf(&quot;ERROR:null pointer!.n&quot;);return 0;递归中需要注意的思想我任务就是为了解决当前的问 题，我完成最简单的一部操作，其他的由别人去完成， 比如汉诺塔中的第一个和尚让第二个和尚把前 63 个金盘 放在B处，而他自己只需要完成从 A到C的搬运，实质上 他自己完成的只有一部最简答的，但是搬运这种动作有 存在非常大的相似性。因此为了解决当前的问题 f(n), 就需要解决问题 f(n-1), 而 f(n-1) 的解决就需要解决 f(n-2) ，这样逐层的分解， 分解成很多相似的小事件，当最小的事件解决完成以后， 就能解决高层次的事件，这种逐层分解，逐层合并的方 式就构成了递归的思想，最主要的要找到递归的出口和 递归的方式，搞清楚了这两个，实现一个递归问题相对 来说就比较简单