单链表的概念，结构和优缺点

1. 概念

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

2. 单链表的结构

单链表是由一系列节点组成的线性结构，每个结点包含两个域。：数据域和指针域。

数据域用来存储数据，指针域用来存储下一个结点的指针。单链表的头结点指向第一个结点，最后一个结点的指针域为空。

一个结点的结构：

逻辑结构：为了方便形象理解，想象出来的。

物理结构：实际内存中，真实的样子。

1.3 单链表的优缺点

优点：

1. 插入和删除操作效率高（只需修改指针的指向）

2. 空间利用率高（不需要预先分配空间）

3. 长度可变

缺点：

1. 随机访问效率低（只能挨个遍历）

2. 存储空间浪费（每个结点包含数据和指针）

3. 链接信息的丢失 （无法访问前一个节点）

2. 单链表的实现

单链表各接口函数

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;//这样做的目的是为了增加代码的可读性和可维护性，以及提高代码的可移植性，
//因为如果将来需要更改 SLTDataType 的类型，只需要在 typedef 语句中修改一处即可，
// 如果我们在程序的其他地方需要修改 SLTDataType 的类型，
//只需在 typedef 语句中修改 int 为其他类型即可，不需要修改其他代码。
//typedef int SLTADataType;
 
typedef struct SListNode //--single Linked List
{
	SLTDataType data;//成员变量
	struct SListNode* next;
}SLTNode;
 
void SLTPrint(SLTNode* phead);
void SLPushFront(SLTNode** pphead, SLTDataType x);//头部插入
void SLPushBack(SLTNode** pphead, SLTDataType x);//尾部插入
 
void SLPopFront(SLTNode** pphead);//头部删除
void SLPopBack(SLTNode** pphead);//尾部删除
 
//单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x);
 
//单链表pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//单链表pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);
//单链表pos位置删除
void SLErase(SLTNode** pphead, SLTNode* pos);
//单链表pos之后删除
void SLEraseAfter(SLTNode* phead);

2.1 结点的定义

单链表的英文为:Single linked list --简写为SL

而顺序表的英文是:Sequence table -- 简写为Seq

结点的英文为:node

typedef int SLTDataType;
typedef struct SListNode //--single Linked List
{
	SLTDataType data;//成员变量
	struct SListNode* next;
}SLTNode;

2.2 链表的打印

//函数的作用是遍历单链表，并将每个节点的数据元素打印到屏幕上。
void SLTPrint(SLTNode* phead)//参数是一个指向 SLTNode 类型的指针 phead，表示单链表的头节点。
{
	SLTNode* cur = phead;//头结点存储的地址给cur指针。
	while (cur != NULL)//使用一个while循环对单链表进行遍历，循环条件为 cur 不为 NULL。
	{    		
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

2.3 创建一个新节点

SLTNode* BuyLTNode(SLTDataType x)//表示要创建的节点的数据元素。
//函数的作用是创建一个新的单链表节点，并将其初始化为包含数据元素 x 的节点。
{ 
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	
	newnode->data = x;
	newnode->next = NULL;
	return newnode;//返回的是一个结点的地址
}

2.4 单链表尾插

void SLPushBack(SLTNode** pphead, SLTDataType x)//尾插的本质是让上一个结点链接下一个结点
{
	SLTNode* newnode = BuyLTNode(x);
	// 1、空链表
	// 2、非空链表
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		    tail->next = newnode;
	}
 
}

2.5 单链表头插

void SLPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuyLTNode(x);
 
	newnode->next = *pphead;
	*pphead = newnode;
}

2.6 单链表头删

void SPopFront(SLTNode** pphead)
{
	//没有节点
	//暴力检查
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//多个节点
	else
	{
		SLTNode* del = *pphead;//相当于一个标记,删掉的标记
		//写法一
		//*pphead = del->next;
		//写法二 
		*pphead = (*pphead)->next;
		free(del);
	}
 
 
 
}

2.7 单链表尾删

void SLPopBack(SLTNode** pphead)
{
	//没有节点(空链表)
	//暴力检查
	assert(*pphead);
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}//多个节点
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		//找尾
		//方法一
		/*while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;*/
 
		//方法二
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
 
		free(tail->next);
		tail->next = NULL;
	}
}

2.8 单链表查找/修改某个值

SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
	//assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

2.9 单链表在pos之前插入

void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);//&plist
	assert(pos);
	//assert(*pphead);
	//一个节点
	if (*pphead == NULL)
	{
		SLPushFront(pphead, x);
	}
	else//多个节点
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuyLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.10 单链表在pos之后插入

void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
 
	SLTNode* newnode = BuyLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

2.11 单链表删除pos的值

void SLErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
 
	if (pos == *pphead)
	{
		SLPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next!=pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

2.12 单链表删除pos之后的值

void SLEraseAfter(SLTNode* pos)
{
	assert(pos);
	SLTNode* next= pos->next;
	pos->next = next->next;
	free(next);
}