24/11/29单向链表的操作

linklist.h

#ifndef LINKLIST_H
#define LINKLIST_H 
#include <myhead.h>

typedef char datatype;
typedef struct Node
{
	union
	{
		int len;
		datatype data;
	};
	struct Node *next;
}Node,*Node_ptr;

Node_ptr list_create();


//链表判空操作
int list_empty(Node_ptr L);


//定义申请节点封装数据函数
Node_ptr node_apply(datatype e);

//单向链表头插
int list_insert_head(Node_ptr L,datatype e);

//单向链表的按位置查找返回节点
Node_ptr list_find_node(Node_ptr L,int pos);

//单向链表的遍历
int list_show(Node_ptr L);

//单向链表任意位置插入
int list_insert_pos(Node_ptr L,int pos,datatype e);


//单向联系的头删
int list_delete_head(Node_ptr L);

//任意位置删除
int list_delete_pos(Node_ptr L,int pos);

//单向链表按位置修改
int list_update_pos(Node_ptr L,int pos,datatype e);


//单向链表的尾删
int list_delete_trail(Node_ptr L);

//单向列表按值查找返回位置
int list_findzhi_backweizhi(Node_ptr L,datatype e); 


//单向链表按值修改
int list_findzhi_change(Node_ptr L,datatype e);

//单向链翻转
int list_reverse(Node_ptr L);

//单向链表的排序
int list_paixu(Node_ptr L);

//单向链表的去重
int list_quchong(Node_ptr L);



//返回单链表的长度
int list_changduback(Node_ptr L);


//清空单向链表
int list_clear(Node_ptr L);


//单向链表的释放
void list_free(Node_ptr L);
#endif

linklist.c

#include "linklist.h"

Node_ptr list_create()
{
	Node_ptr L =(Node_ptr)malloc(sizeof(Node));
	if(NULL==L)
	{
		printf("链表创建失败\n");
		return NULL;
	}
	//程序执行至此，申请头结点成功
	//有了头结点就有了一条链表
	//初始化操作
	L->len=0;
	L->next=NULL;
	printf("创建成功\n");
	return L;
}
int list_empty(Node_ptr L)
{
	if(NULL==L)
	{
		printf("链表不合法\n");
		return -1;
	}

	return L->next==NULL?1:0;
	
}

Node_ptr node_apply(datatype e)
{
	Node_ptr p=(Node_ptr)malloc(sizeof(Node));
	if(NULL==p)
	{
		printf("节点申请失败\n");
		return NULL;
	}
	p->data=e;
	p->next=NULL;
	return p;
}
int list_insert_head(Node_ptr L,datatype e)
{
	//判断逻辑
	if(NULL==L)
	{
		printf("申请失败\n");
		return -1;
	}

	//申请节点封装数据
	Node_ptr p=node_apply(e);
	if(NULL==p)
	{
		return -1;
	}
	//头插逻辑变化
	p->next=L->next;
	L->next=p;
	//表长变化
    L->len++;
	printf("插入成功\n");
	return 0;
}
	
Node_ptr list_find_node(Node_ptr L,int pos)
{
	//判断逻辑
	if(NULL==L||pos<0||pos>L->len)
	{
		printf("查找失败\n");
		return NULL;
	}
	//查找逻辑
	Node_ptr q=L;//定义遍历指针
    for(int i=0;i<pos;i++)
	{
		//q++;   //向后偏移一个节点的大小
		q=q->next;//将指针偏移到下一个节点的位置
	}
	//返回节点
	return q;
}

int list_show(Node_ptr L)
{
	if(list_empty(L))
	{
		printf("遍历失败\n");
		return -1;
	}
	printf("链表中的元素分别是：");
/*	for(int i=0;i<L->len;i++)
	{
		Node_ptr p=list_find_node(L,i);
		printf("%c\t",p->data);
	}*/
	Node_ptr q=L->next;
	while(q)
	{
		printf("%c\t",q->data);
		q=q->next;
	}
	printf("\n");
	return 0; 
}

int list_insert_pos(Node_ptr L,int pos,datatype e)
{
	if(NULL==L||pos<1||pos>L->len+1)
	{
		printf("插入失败\n");
		return -1;
	}
	Node_ptr q=list_find_node(L,pos-1);
	Node_ptr p=node_apply(e);
	if(NULL==p)
	{
		return -1;
	}
    p->next=q->next;
	q->next=p;
     
	L->len++;
	printf("插入成功\n");
	return 0;
}

int list_delete_head(Node_ptr L)
{
	if(NULL==L||list_empty(L))
	{
		printf("删除失败\n");
		return -1;
	}
	Node_ptr p=L->next;
	L->next=p->next;
	free(p);
	p=NULL;
	L->len--;
	printf("删除成功\n");
	return 0;
}

int list_delete_pos(Node_ptr L,int pos)
{
	if(NULL==L||list_empty(L)||pos<1||pos>L->len)
	{
		printf("无法删除\n");
		return -1;
	}
	Node_ptr q=list_find_node(L,pos-1);
	Node_ptr p=q->next;  //标记要删除的节点
	q->next=p->next;    //孤立要删除的节点

	free(p);   // 释放要删除的节点
	p=NULL;
	printf("删除成功\n");
	L->len--;
	return 0;
}
	
int list_update_pos(Node_ptr L,int pos,datatype e)
{
	if(NULL==L||list_empty(L)||pos<1||pos>L->len)
	{
		printf("修改失败\n");
		return -1;
	}
	Node_ptr p=list_find_node(L,pos);

	//进行修改
	p->data=e;
	printf("修改成功\n");
	return 0;
}

int list_reverse(Node_ptr L)
{
	if(NULL==L||list_empty(L)||L->len==1)
	{
		printf("翻转失败\n");
		return -1;
	}
	Node_ptr H=L->next;
	L->next=NULL;
	while(H!=NULL) 
	{
		Node_ptr p=H;
		H=H->next;
		p->next=L->next;
		L->next=p;
	}
	printf("翻转成功\n");
	return 0;
}

int list_delete_trail(Node_ptr L)
{
	if(NULL==L||list_empty(L))
	{
		printf("尾删失败\n");
		return -1;
	}
    Node_ptr p=L;
	for(int i=0;i<L->len-1;i++)
	{
		p=p->next;
	} 
	Node_ptr Q=p->next;
	p->next=NULL;
	L->len--;
	free(Q);
	Q=NULL;
	printf("尾删成功\n");
	return 0;
}
    
int list_findzhi_backweizhi(Node_ptr L,datatype e) 
{
	if(NULL==L||list_empty(L))
	{
		printf("找位置失败\n");
		return -1;
	}
	int pos=-1;
	Node_ptr p=L->next;
	for(int i=0;i<L->len;i++)
	{ 
		if(p->data==e)
		{
			pos=i;
			break;
		}
		p->next;
	}
	if(pos!=-1)
	{
		printf("该值的位置是%d\n",pos);
	}
	else
	{
		printf("未找到该值\n");
	}
	return 0;
}


 int list_findzhi_change(Node_ptr L,datatype e)
{
	if(NULL==L||list_empty(L))
	{
		printf("按找值修改失败\n");
		return -1;
	}
	Node_ptr p=L->next;
	for(int i=0;i<L->len;i++)
	{
		if(p->data==e)
		{
			printf("请输入要修改的值：");
			datatype new_e;
			scanf("%c",&new_e);
			p->data=new_e;
			printf("修改值成功\n");
			return 0;
		}
		p=p->next;

	}
	printf("未找到该值\n");
	return -1;
}

int list_paixu(Node_ptr L)
{
	if(NULL==L||list_empty(L))
	{
		printf("排序失败\n");
		return -1;
	}
	for(int i=0;i<L->len-1;i++)
	{
		Node_ptr p=L->next;
		Node_ptr q=p->next;
		for(int j=0;j<L->len-i-1;j++)
		{
			if(p->data>q->data)
			{
				datatype t=p->data;
				p->data=q->data;
				q->data=t;
			}
			p=q;
			q=q->next;
		}
	}
	printf("排序成功\n");
	return 0;
}
		
int list_quchong(Node_ptr L)
{
	if(NULL==L||list_empty(L))
	{
		printf("去重失败\n");
		return -1;
	}
	Node_ptr p=L->next;
	while(p!=NULL)
	{
		Node_ptr q=p;
		Node_ptr Q=p;
		while(q->next!=NULL)
		{
			if(q->next->data==p->data)
			{
				Node_ptr t=q->next;
				q->next=q->next->next;
				free(t);
				L->len--;
			}
			else
			{
				q=q->next;
			}
		}
		p=p->next;
	}
	
	printf("去重成功\n");
	return 0;
}


int list_changduback(Node_ptr L)
{
	if(NULL==L||list_empty(L))
	{
		printf("返回长度失败\n");
		return -1;
	}
	Node_ptr p=L->next;
	int flag=0;
	for(int i=0;i<L->len;i++)
	{
		p=p->next;
		flag++;
	}
	printf("单链表的长度为%d\t",flag);
	return 0;
}

int list_clear(Node_ptr L)
{
	if(NULL==L||list_empty(L))
	{
		printf("清空失败\n");
		return -1;
	}
	Node_ptr p=L->next;
	Node_ptr temp;
	while(p!=NULL)
	{
		temp=p;
		p=p->next;
		free(temp);
	}
	L->next=NULL;
	L->len=0;
	printf("清空成功\n");
	return 0;
}

	 

void list_free(Node_ptr L)
{
	if(NULL==L)
	{
		printf("销毁失败\n");
		return;
	}
	while(!list_empty(L))
	{
		list_delete_head(L);
	}
	free(L);
	L=NULL;
	printf("销毁成功\n");
}

main.c

#include"linklist.h"

int main(int argc, const char *argv[])
{
	Node_ptr L=list_create();
	if(NULL==L)
	{
		return -1;
	}


	list_insert_head(L,'o');
	list_insert_head(L,'H');
	list_insert_head(L,'J');
	list_insert_head(L,'L');

	list_show(L);

	list_insert_pos(L,1,'D');
	list_show(L);

	list_insert_pos(L,L->len,'A');
	list_show(L);
	list_delete_head(L);
	list_show(L);
	list_delete_pos(L,1);
	list_show(L);
	list_update_pos(L,2,'h');
	list_show(L);

	list_reverse(L);
	list_show(L);
	list_delete_trail(L);
	list_show(L);
	list_findzhi_backweizhi(L,'A');
	list_show(L);
	list_findzhi_change(L,'A');
	list_show(L);
    list_paixu(L);
	list_show(L);
    list_quchong(L);
	list_show(L);
    list_changduback(L);
	list_show(L);
    list_clear(L);
	list_show(L);
	list_free(L);
	list_show(L);
	return 0;
}