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

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); }