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

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);//&plistassert(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);
}