数据结构-单链表

1个月前发布

对于顺序表来说，我要一次性的申请一块内存空间，但有时候用户并不确定要多大的内存空间!有时候可能会向里边添加元素，但是受限于申请的内存大小，导致加入元素的时候并不方便，而且顺序表的插入和删除相对复杂，需要设计元素的移动。基于顺序表的缺陷，引入链表，在创建链表的时候，我只需要申请一个头结点，存储链表的头，当需要添加元素的时候，我就申请一块内存，将链表头的下一个节点的指针，指向该地址空间九就可以完成链表结点的插入，可以方便的实现增删等功能。

创建链表的头

typedef struct LinkedList
{
	DataType_t  		 data; //结点的数据域
	struct LinkedList	*next; //结点的指针域

}LList_t;

创建一个空链表

LList_t * LList_Create(void)
{
	//1.创建一个头结点并对头结点申请内存
	LList_t *Head = (LList_t *)calloc(1,sizeof(LList_t));
	if (NULL == Head)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

	//2.对头结点进行初始化，头结点是不存储有效内容的！！！
	Head->next = NULL;

	//3.把头结点的地址返回即可
	return Head;
}

创建新结点


//func：创建新结点，并初始化
//argc：要添加的新结点的元素的值
//ret：新结点结构体的地址

LList_t * LList_NewNode(DataType_t data)
{
	//1.创建一个新结点并对新结点申请内存
	LList_t *New = (LList_t *)calloc(1,sizeof(LList_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}
	//2.对新结点的数据域和指针域进行初始化
	New->data = data;
	New->next = NULL;

	return New;
}

头部插入元素

bool LList_HeadInsert(LList_t *Head,DataType_t data)
{
	//1.创建新的结点，并对新结点进行初始化
	LList_t *New = LList_NewNode(data);
	if (NULL == New)
	{
		printf("can not insert new node\n");
		return false;
	}

	//2.判断链表是否为空，如果为空，则直接插入即可
	if (NULL == Head->next)
	{
		Head->next = New;
		return true;
	}

	//3.如果链表为非空，则把新结点插入到链表的头部
	New->next  = Head->next;
	Head->next = New;

	return true;
}

尾部插入元素

bool LList_TailInsert(LList_t *Head,DataType_t data)
{
	LList_t *Phead=Head;
	//1.创建新的结点，并对新结点进行初始化
	LList_t *New = LList_NewNode(data);
	if (NULL == New)
	{
		printf("can not insert new node\n");
		return false;
	}
	while(Phead->next != NULL){
		Phead = Phead->next;
	}
	Phead->next = New;
	return true;
}

指定元素后边插入

bool LList_DestInsert(LList_t *Head,DataType_t dest,DataType_t data)
{
	//定义两个指针用于遍历
	LList_t *Pphead;
	
	Pphead = Head->next;
	LList_t *New = LList_NewNode(data);
	if (NULL == New)
	{
		printf("can not insert new node\n");
		return false;
	}
	if(Head->next == NULL){
		printf("this is a void list\n");
		return false;
	}
	while(Pphead->data != dest){
		if(Pphead->next == NULL ){
			printf("NO value\n");
			return false;
		}
		else{
			Pphead = Pphead->next ;
		}
	}
	New->next =Pphead->next;
	Pphead->next= New;
	return true;

}

首删

bool LList_HeadDel(CircLList_t *Head)
{
	//对单向循环链表的头尾结点的地址进行备份
	CircLList_t *Phead = Head->next;
	CircLList_t *Pphead = Head->next;
	//判断当前链表是否为空，为空则直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		return false;
	}
	if(Head->next->next == Head->next){
		Head->next->next =NULL;
		free(Head->next);
		Head->next = Head;
		return true;
	}
	//遍历链表找到尾结点
	while(Phead->next != Head->next){
		Phead = Phead->next;
	}
	//进行删除操作，重新连接
	Phead->next = Pphead->next;
	Head->next = Pphead->next;
	Pphead->next = NULL;
	free(Pphead);
	return true;

	
}

指定元素删除

bool LList_DestDel(LList_t *Head,DataType_t dest)
{
	LList_t *Phead = Head;
	LList_t *Pphead = Head->next;
	//1.判断链表是否为空，如果为空，则直接退出 
	if (NULL == Head->next)
	{
		return false;
	}
	//循环查找目标节点
	while(Pphead->data != dest){
		if(Pphead->next == NULL){
			printf("not exit this node\n");
			return false;
		}
		Phead = Pphead;
		Pphead = Pphead->next;
	}
	Phead->next = Pphead->next;
	Pphead->next = NULL;
	free(Pphead);
	return true;

}

尾部删除

bool LList_TailDel(LList_t *Head)
{
	LList_t *Phead = Head;
	LList_t *Pphead = Head->next;
	//判断链表是否为空
	if(Head->next == NULL){
		printf("this is a void list，do not del \n");
		return false;
	}
	//循环找到链表的最后一个节点和倒数第二个节点
	while(Pphead->next != NULL){
		Phead = Pphead;
		Pphead = Pphead->next;
	}
	//删除尾节点
	Phead->next = NULL;
	free(Pphead);
	return true;

}

删除链表中最小的结点

bool LList_MinDel(LList_t *Head)
{
	LList_t *Phead = Head->next;
	DataType_t min = Phead->data;
	LList_t *Pphead = Head->next;
	//判断链表是否为空
	if(Head->next == NULL){
		printf("this is a void list，do not del \n");
		return false;
	}
	//循环找到最小的节点（循环的时候比较不了最后一个元素)
	while(Pphead->next != NULL){
		
		if(Pphead->data < min){
			min = Pphead->data;
			Phead = Pphead;
		}
		Pphead = Pphead->next;

	}
	 //比较最后一个元素是否是最小的
	if(Pphead->data < min){
		min = Pphead->data;
		Phead = Pphead;
	}
	if(Phead->next == NULL){
		LList_TailDel(Head);
	}
	else{
		LList_DestDel(Head,min);
	}
	
	return true;
	
}

删除链表中倒数k个元素

DataType_t LList_FindnLast(LList_t *Head,unsigned int n)
{
	LList_t *Pphead = Head;
	LList_t *Phead = Head;
	//判断链表是否为空
	if(Head->next == NULL){
		printf("this is a void list，do not del \n");
		return false;
	}
	for(int i=1;i<n;i++){
		Pphead = Pphead->next;
	}
	while(Pphead->next != NULL){
		Pphead = Pphead->next;
		Phead = Phead->next;
	}
	return Phead->data;
}

遍历链表并打印

void LList_Print(LList_t *Head)
{
	//对链表的头文件的地址进行备份
	LList_t *Phead = Head;
	
	//首结点
	while(Phead->next)
	{
		//把头的直接后继作为新的头结点
		Phead = Phead->next;

		//输出头结点的直接后继的数据域
		printf("data = %d\n",Phead->data);
	}

}

来源链接：https://www.cnblogs.com/lradian/p/18801079

评分

欢迎为Ta评分