数据结构--单链表详解（附代码

1：链表的概念及结构

2：实现单链表

3：常见疑问解答（看到最后！！）

一：链表的概念及结构

1.1 概念：

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

1.2 结构：

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。

---在链表里，每节“车厢”是什么样的呢？

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”

节点的组成主要有两个部分：

当前节点要保存的数据和下⼀个节点的地址(指针变量）

注意：链表中的最后一个节点的next指向空指针(next=NULL)

图中指针变量 plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，链表中的每个节点都是独立申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。

结合前面学到的结构体知识，我们可以给出每个节点对应的结构体代码：

假设当前保存的节点为整型：

struct SListNode
{
 int data;    //节点数据
 struct SListNode* next; //指向下⼀个节点的指针
};

二：实现单链表

单链表英文名——single linked list，我们简写为SL

1.1创建

为了养成模块化好习惯，我们把代码分开来写

1.2 链表的功能

1.3链表的实现

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义节点的结构
//数据 + 指向下一个节点的指针
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);//打印
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead);//头删
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

SList.c

#include"SList.h"

void SLTPrint(SLTNode* phead)//打印
{
	SLTNode* pcur = phead;
	while (pcur)//pcur!=NULL
	{
		printf("%d->",pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if(newnode==NULL)
	{
		perror("newnode fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
                                               //一级指针的地址用      
void SLTPushBack(SLTNode** pphead, SLTDataType x)//二级指针来接收
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//空链表 与 非空链表
	if (*pphead == NULL)//*pphead就是指向第一个节点的指针
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;//先找到尾节点
		while (ptail->next)//!=NULL
		{
			ptail = ptail->next;
		}//ptail指向的就是尾节点
		ptail->next = newnode;

	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)//尾删
{
	assert(*pphead && pphead);
	//一个节点
	if ((*pphead)->next == NULL)// ->的优先级高于*
	{
		free(*pphead);
		*pphead = NULL;
	}
	//多个节点
	else
	{
		SLTNode* ptail = *pphead;
		SLTNode* prev = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}
void SLTPopFront(SLTNode** pphead)//头删
{
	assert(*pphead && pphead);
	SLTNode* next = (*pphead)->next;// ->的优先级高于*
	free(*pphead);
	*pphead = next;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur)//pcur!=NULL
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(*pphead && pphead);
	assert(pos);//还要判断能不能在链表中找到pos这个地址
	SLTNode* newnode = SLTBuyNode(x);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	
	}
}
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);
	SLTNode* next = pos->next;
	newnode->next = next;
	pos->next = newnode;

}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos&&pos->next);//pos->next也要断言，因为当cur->next为NULL时，
//说明整个链表的节点都排查完了，最后还是没有找到地址为pos的结点，证明pos传值有误。

	SLTNode* after = pos->next;
	pos->next = after->next;
	free(after);
	after = NULL;

}

//销毁链表
//因为链表在物理结构上是不连续存储的，销毁链表必须要一个结点一个结点去销毁
void SListDesTroy(SLTNode** pphead)
{
	assert(*pphead && pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;//不要忘记把phead置为NULL。
}

test.c