链表的基础

目录

顺序表

链表

需要注意的 

链表的优势 

 单链表的实现

1.单链表的准备

2.单链表的结构体的创建

 3.单链表的准备

 4.前插

5.后插

 6.后删

7.前删

8.任意位置前插

9.任意位置后插

 10.删除

11.修改

12.打印

13.释放链表

 总说链表难，但我感觉只要认真听讲，再加上自己敲敲代码，也不是很难，毕竟后面还有更难的算法  哈哈

顺序表

想要了解什么是链表，我们要先知道什么是顺序表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储

 这一点在通讯录的实现给出了充足的运用，然后向更深的探索，也就慢慢产生了链表

链表

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

这就好比火车一样，每个车间都装着东西，然而车间与车间之间并不是向顺序表一样直接加加向后，而是每个车间是通过中间车钩连接起来的，

 在数据结构上的链表也是同样道理，在一个结构体内，有一部分装着必要的信息，而另一部分又有指针，该指针存放着下一个结构体的地址，使得两个结构体如果火车一样连接在一起；

文字表示固然不清楚，我们展示图形：

此处只展示单链表，单链表会的话，双链表也是同样道理，可以自己实现 

需要注意的 

我们的链表最后一个节点的指针部分，必须存放的是NULL这里我们需要自己写代码让其为NULL要不然没有这一步，我们不知道结束的判断是什么 

链表的优势 

这里是摘自别人的博客 

 链表基础知识详解（非常详细简单易懂）-CSDN博客

人家写的比我写的详细多了，还讲解了双链表，值得学习 

   链表是通过节点把离散的数据链接成一个表，通过对节点的插入和删除操作从而实现 对数据的存取。而数组是通过开辟一段连续的内存来存储数据，这是数组和链表最大的区 别。数组的每个成员对应链表的节点，成员和节点的数据类型可以是标准的 C 类型或者是 用户自定义的结构体。数组有起始地址和结束地址，而链表是一个圈，没有头和尾之分， 但是为了方便节点的插入和删除操作会人为的规定一个根节点。
————————————————

                            版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
                        
原文链接：https://blog.csdn.net/qq_61672347/article/details/125701955

 单链表的实现

1.单链表的准备

我们先写出需要用到的头文件 

#include <stdio.h>
#include <string.h>
#include<malloc.h>
#include<stdlib.h>
#include<assert.h>
#include<errno.h>

typedef int SLDataType;

这里的重命名是为了方便以后修改

2.单链表的结构体的创建

一部分存放需要存的信息，一部分为指针存放下一个结构体的地址

typedef int SLDataType;

typedef struct SLList
{
    SLDataType x;
    struct SLList* next;
}SL;

 3.单链表的准备

int main()
{
	SL* SLList=NULL;
	return 0;
}

 4.前插

前插需要考虑的就是如果单链表本来就没有节点 

大致图：

需要注意的是我们传的是指针的地址，我们需要用二级指针接收，才可以改变一级指针指向的内容

	SLPushFront(&SLList, 5);

    void SLPushFront(SL** pphead, SLDataType x)
{
	assert(pphead);
	SL* newcode = (SL*)malloc(sizeof(SL));
	if (newcode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newcode->next = *pphead;
	newcode->x = x;
	*pphead = newcode;
}

5.后插

 后插跟前插同样的道理

 同样需要考虑的是没有节点的问题与只有一个节点

void SLPushback(SL** pphead,SLDataType x)
{
	assert(pphead);
	SL* newcode = (SL*)malloc(sizeof(SL));
	if (*pphead == NULL)
	{
		*pphead = newcode;
		(*pphead)->x = x;
		(*pphead)->next = NULL;
		return;
	}
	SL* tail = *pphead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	tail->next = newcode;
	tail = tail->next;
	tail->x = x;
	tail->next = NULL;
}

 6.后删

后删同样需要考虑没有节点，没有节点当然删不了啊，还有只有一个节点，我们需要直接将这个节点直接释放，然后等于NULL

void SLPopBack(SL** pphead)
{
	assert(pphead);
	assert(*pphead);
	SL* tail = *pphead;
	//一个也没有
	assert(*pphead);
	//一个节点
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点
	while (tail->next->next != NULL)
	{
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;
}

7.前删

void SLPopFront(SL** pphead)
{
	assert(pphead);
	assert(*pphead);
	SL* tail = *pphead;
	*pphead = (*pphead)->next;
	free(tail);//tail是SL* tail=&SLList;
}

8.任意位置前插

 我们需要先找到该位置，然后在与前面前插后插同样方法进行插入

	SL* pos = SLFind(SLList,2);
	SLInsert(&SLList,pos,20);//前插
	SLPrint(SLList);

SL* SLFind(SL* pphead, SLDataType x)
{
	assert(pphead);
	SL* tail = pphead;
	while (tail->x != x)
	{
		tail = tail->next;
	}
	return tail;
}

void SLInsert(SL** pphead, SL* pos, SLDataType x)
{
	assert(pphead);
	assert(pos);
	SL* tail = *pphead;
	SL* newcode = (SL*)malloc(sizeof(SL));
	if (newcode == NULL)
	{
		perror("SLInsert fail");
	}
	while (tail->next != pos)
	{
		tail = tail->next;
	}
	newcode->next = tail->next;
	newcode->x = x;
	tail->next = newcode;
}

9.任意位置后插

	SL* pos = SLFind(SLList,2);
    SLInsertBack(&SLList, pos, 30);//后插
	SLPrint(SLList);

void SLInsertBack(SL** pphead, SL* pos, SLDataType x)
{
	assert(pphead);
	assert(pos);
	SL* tail = *pphead;
	SL* newcode = (SL*)malloc(sizeof(SL));
	if (newcode == NULL)
	{
		perror("SLInsertBack fail");
	}
	while (tail != pos)
	{
		tail = tail->next;
	}
	newcode->next = tail->next;
	newcode->x = x;
	tail->next = newcode;
}

 10.删除

	SL* pos = SLFind(SLList,2)；

	SLErase(&SLList, pos);
	SLPrint(SLList);

void SLErase(SL** pphead, SL* pos)
{
	assert(pphead);
	assert(pos);
	SL* tail = *pphead;
	if (pos == *pphead)
	{
		SLPopFront(pphead);
		return;
	}
	while (tail->next != pos)
	{
		tail = tail->next;
	}
	tail->next = pos->next;
	free(pos);
}

11.修改

	pos= SLFind(SLList, 3);
	SLModify(&SLList, pos, 50);
	SLPrint(SLList);

void SLModify(SL** pphead, SL* pos, SLDataType x)
{
	assert(pphead);
	assert(pos);
	SL* tail = *pphead;
	while (tail != pos)
	{
		tail = tail->next;
	}
	tail->x = x;
}

12.打印

void SLPrint(SL* pphead)
{
	SL* tail = pphead;
	while (tail != NULL)
	{
		printf("%d->", tail->x);
		tail = tail->next;
	}
	printf("NULL\n");
}

13.释放链表

void SLList_free(SL** pphead)
{
	//定义一个指针变量保存头结点的地址
	SL* pb = *pphead;
	while (*pphead != NULL)
	{
		//先保存p_head指向的结点的地址
		pb = *pphead;
		//p_head保存下一个结点地址
		*pphead = (*pphead)->next;
		free(pb);
		pb = NULL;
	}
}