递归实现链表数据互换，纯不会，明天再说
1、链表实现以下功能
链表，创建链表，申请节点，判空，头插，遍历输出，通过位置查找节点，任意位置插入，头删，任意位置删除，安置查找返回位置，按位置进行修改，按值进行修改，翻转链表，释放链表，链表的排序，反转链表（递归实现）
//link_list.h
#ifndef LINK_LIST_H
#define LINK_LIST_H
#include <myhead.h>typedef int datatype;typedef struct Node
{union{int len;datatype data;};struct Node *next;
}Node,*NodePtr;//创建链表
NodePtr list_create();//申请结点封装数据的函数
NodePtr apply_node(datatype e);//链表判空
int list_empty(NodePtr L);//头插
int list_insert_head(NodePtr L,datatype e);//链表遍历函数
int list_show(NodePtr L);//通过位置查找结点
NodePtr list_search_pos(NodePtr L,int pos);//任意位置插入
int list_insert_pos(NodePtr L,int pos,datatype e);//链表头删
int list_delete_head(NodePtr L);//链表任意位置删除
int list_delete_pos(NodePtr L,int pos);//链表按值查找返回位置
int list_search_retval(NodePtr L,datatype e);//链表按位置进行修改
int list_updata_pos(NodePtr L,int pos,datatype e);//按值进行修改
int list_updata_data(NodePtr L,datatype old_e,datatype new_e);//将链表进行翻转
int list_reserve(NodePtr L);//释放链表
void list_destroy(NodePtr L);//链表的排序
int list_sort(NodePtr L);//链表的翻转（递归函数实现）
NodePtr list_reserve1(NodePtr L);#endif
//link_list.c
#include "link_list.h"//创建链表
NodePtr list_create()
{NodePtr L = (NodePtr)malloc(sizeof(Node));if(NULL == L){printf("链表创建失败\n");return NULL;}L->len = 0;L->next = NULL;printf("链表创建成功\n");return L;
}//申请结点封装数据的函数
NodePtr apply_node(datatype e)
{NodePtr p = (NodePtr)malloc(sizeof(Node));if(NULL == p){printf("创建结点失败\n");return NULL;}p->data = e;p->next = NULL;return p;}//链表判空
int list_empty(NodePtr L)
{return L->next == NULL;
}//头插
int list_insert_head(NodePtr L,datatype e)
{if(NULL == L){printf("头插失败\n");}NodePtr p = apply_node(e);p->next = L->next;L->next = p;L->len++;printf("头插成功\n");return 0;
}//链表遍历函数
int list_show(NodePtr L)
{if(NULL == L || list_empty(L)){printf("遍历失败\n");return -1;}printf("链表中的元素是:");NodePtr q = L->next;while(q){printf("%d->",q->data);q = q->next;}printf("NULL\n");
}//通过位置查找结点
NodePtr list_search_pos(NodePtr L,int pos)
{if(NULL == L || list_empty(L) || pos < 0 || pos > L->len){printf("查找失败\n");return NULL;}NodePtr q = L;for(int i = 0;i < pos;i++){q = q->next;}return q;
}//任意位置插入
int list_insert_pos(NodePtr L,int pos,datatype e)
{if(NULL == L || pos < 1 || pos > L->len+1){printf("插入失败\n");return -1;}NodePtr p = apply_node(e);if(p == NULL){return -1;}NodePtr q = list_search_pos(L,pos-1);p->next = q->next;q->next = p;L->len++;printf("插入成功\n");return 0;
}//链表头删
int list_delete_head(NodePtr L)
{if(NULL == L || list_empty(L)){printf("头删失败\n");return -1;}NodePtr q = L->next;L->next = q->next;free(q);q = NULL;L->len--;return 0;
}//链表任意位置删除
int list_delete_pos(NodePtr L,int pos)
{if(NULL == L || list_empty(L) || pos < 1 || pos > L->len){printf("删除失败\n");return -1;}NodePtr q = list_search_pos(L,pos-1);NodePtr p = q->next;q->next = p->next;free(p);p = NULL;L->len--;printf("成功删除第%d个元素\n",pos);return 0;
}//链表按值查找返回位置
int list_search_retval(NodePtr L,datatype e)
{if(NULL == L || list_empty(L)){printf("查找失败\n");return -1;}NodePtr q = L->next;for(int i = 1;i <= L->len;i++){if(q->data == e){return i;}q = q->next;}printf("没有找到该元素\n");return -1;
}//链表按位置进行修改
int list_updata_pos(NodePtr L,int pos,datatype e)
{if(NULL == L || list_empty(L) || pos < 1 || pos > L->len){printf("修改失败\n");return -1;}NodePtr q = list_search_pos(L,pos);q->data = e;printf("按位置修改成功\n");return 0;
}//按值进行修改
int list_updata_data(NodePtr L,datatype old_e,datatype new_e)
{if(NULL == L || list_empty(L)){printf("修改失败\n");return -1;}NodePtr q = L->next;while(q){if(q->data == old_e){q->data = new_e;return 0;}q = q->next;}printf("没有该元素\n");return -1;
}//将链表进行翻转
int list_reserve(NodePtr L)
{if(NULL == L || list_empty(L) || L->len == 1){printf("翻转失败\n");return 0;}NodePtr H = L->next;L->next = NULL;while(H){NodePtr q = H;H = H->next;q->next = L->next;L->next = q;}printf("翻转成功\n");return 0;
}//释放链表
void list_destroy(NodePtr L)
{if(NULL == L){return ;}while(!list_empty(L)){list_delete_head(L);}free(L);L = NULL;printf("释放链表成功\n");
}//链表的排序
int list_sort(NodePtr L)
{if(NULL == L || list_empty(L) || L->len ==1){printf("排序失败\n");return -1;}for (int i = 1; i < L->len; i++) {NodePtr p = L->next;for (int j = 0; j < L->len - i; j++) {if (p->data > p->next->data){int temp = p->data;p->data = p->next->data;p->next->data = temp;}p = p->next;}} printf("排序成功\n");return 0;
}//链表的翻转（递归函数实现）
NodePtr list_reserve1(NodePtr L)
{if(NULL == L || L->len == 1){printf("翻转失败\n");return L;}NodePtr q = list_reserve1(L->next);L->next->next = L;L->next = NULL;return q;
}//main.c
#include "link_list.h"int main(int argc, const char *argv[])
{NodePtr L = list_create();int retem = list_empty(L);list_insert_head(L,520);list_insert_head(L,1314);list_insert_head(L,123);list_insert_head(L,456);list_insert_head(L,789);list_show(L);list_insert_pos(L,2,200);list_show(L);list_delete_head(L);list_show(L);list_delete_pos(L,3);list_show(L);int retval = list_search_retval(L,200);if(retval != -1){printf("该元素在第%d个位置\n",retval);}retval = list_search_retval(L,232);list_updata_pos(L,3,520);list_show(L);list_updata_data(L,456,997);list_show(L);list_reserve(L);list_show(L);list_sort(L);list_show(L);NodePtr retPtr = list_reserve1(L);list_show(retPtr);list_destroy(L);L = NULL;list_show(L);return 0;
}
输出结果如下：
