【C语言】 作业11 链表+实现函数封装

 递归实现链表数据互换，纯不会，明天再说

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;
}

输出结果如下：