当前位置：首页 > article >正文

C语言单链表

article 2024/10/28 10:32:41

文章目录

- 链表的概念及结构
- 链表结构
- 链表分类
- 链表的操作

链表的概念及结构

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表结构

在这里插入图片描述
图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。
为什么还需要指针变量来保存下⼀个节点的位置？
链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。

链表分类

在这里插入图片描述

链表的操作

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
//节点的定义
typedef struct SListNode
{
 SLDataType data; //节点数据 
 struct SListNode* next; //指针保存下一个节点的地址 
}SLNode;
//创建节点 
SLNode* SLBuyNode(SLDataType x)
{
	SLNode* pur=(SLNode*)malloc(sizeof(SLDataType));
	if(pur==NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	pur->data=x;
	pur->next=NULL;
	return pur;
}
//遍历打印链表
void SLTPrint(SLNode* phead)
{
	SLNode* pur=phead;
	while(pur!=NULL)
	{
		printf("%d->",pur->data);
		pur=pur->next;
	}
	printf("NULL\n");
}
//链表尾插 
void SLTPushBcak(SLNode** pphead, SLDataType x)//用二级指针是为了传地址 
{
	assert(pphead != NULL);
	SLNode* pur=SLBuyNode(x);
	if(*pphead==NULL)//链表为空的时候 
	{
		*pphead=pur;
	}
	else//链表不为空，先找到尾节点 
	{
		SLNode* temp=*pphead;
		while(temp->next!=NULL)
		{
			temp=temp->next;
		}
		temp->next=pur; 
	} 
}
//链表头插 
void SLTPushFront(SLNode** pphead, SLDataType x)
{
	//assert(pphead!=NULL);
	SLNode* pur=SLBuyNode(x);
	pur->next=*pphead;
	*pphead=pur;
}
//链表尾删 
void SLTPopBack(SLNode** pphead)
{
	assert(pphead && *pphead);//判断链表不能为空和被删的节点也不能为空 
	//只有一个节点
	if ((*pphead)->next == NULL)//->优先级高于*
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* prev = *pphead;//倒数第二个节点 
		SLNode* ptail = *pphead;//最后一个节点 
		while (ptail->next!=NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}
//链表头删 
void SLTPopFront(SLNode** pphead)
{
	assert(pphead && *pphead);
	SLNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
	
}
//查找链表节点 
SLNode* SLFind(SLNode* head, SLDataType x)
{
     SLNode* pcur = head;
	 while (pcur != NULL)
	 {
	 	if (pcur->data == x)
	 	{
	 		return pcur;
	 	}
	 	pcur=pcur->next;
	 }
	 return NULL;
}
//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) {
	assert(pphead);
	//约定链表不能为空，pos也不能为空
	assert(pos);
	assert(*pphead);
	SLNode* node = SLBuyNode(x);
	//pos刚好是头结点，头插
	if (pos == *pphead) {
		node->next = *pphead;
		*pphead = node;
		return;
	}
	//找pos的前一个节点
	SLNode* prev = *pphead;
	while (prev->next != pos)//第一次循环的时候（缺少pos刚好是第一个节点的判断）
	{
		prev = prev->next;
	}
	node->next = pos;
	prev->next = node;
}
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x) {
	assert(pos);
	SLNode* node = SLBuyNode(x);
	//pos  node  pos->next
	node->next = pos->next;
	pos->next = node;
}
//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos) {
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (pos == *pphead) {
		*pphead = (*pphead)->next;
		free(pos);
		return;
	}
	//找pos的前一个节点
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}
//删除pos之后节点
void SLEraseAfter(SLNode* pos) {
	assert(pos && pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
}
//销毁链表
void SLDesTroy(SLNode** pphead) {
	assert(pphead);
	SLNode* pcur = *pphead;
	//循环删除
	while (pcur!=NULL)
	{
		SLNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}
int main()
{
	SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));
	node1->data = 1;
	SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));
	node2->data = 2;
	SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));
	node3->data = 3;
	SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));
	node4->data = 4;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLTPushBcak(&node1,7);
	SLTPushBcak(&node1,3);
	SLTPushBcak(&node1,3);
	SLTPushFront(&node1,5);
	SLTPrint(node1);
	printf("\n");
	SLTPopFront(&node1); 
    SLTPopBack(&node1);
    SLInsert(&node1,node3,10);
    SLTPrint(node1);
	return 0;
}