数据结构——单链表专题

1. 链表的概念及结构

在顺序表中存在一定的问题：

1. 顺序表的中间/头部插入、删除需要挪动数据
2. 扩容存在性能的消耗
3. 会有空间的浪费

而链表是独立的节点组成

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

链表、顺序表都是线性表

逻辑结构一定是线性的
物理结构不一定是线性的

图中指针变量plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希望plist“指向第二个节点时，只需要修改plist保存的内容为0x0012FFA0

为什么还需要指针变量来保存下一个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

链表是由一个一个的节点组成的
一个节点由两部分组成：要存储的数据+指针

int a = 1;
int* pa = &a;

节点结构的定义

struct SListNode{
int data;
struct SListNode* next;
}

链表结构体的打印方式：

补充说明：

1. 链式机构在逻辑上是连续的，在物理结构上不一定连续
2. 节点一般是从堆上申请的
3. 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

2. 实现单链表

初始化

typedef int SLTDataType;
//链表是由节点组成的
typedef struct SListNode
{SLTDataType data;//节点数据struct SListNode* next;//指针变量保存下一个节点的地址
}SLTNode;

尾插

//公共部分，开辟一个新的节点
SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL){*pphead = newnode;return;}//链表不为空，找尾结点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptril就是尾结点,将尾结点指向newnodeptail->next = newnode;
}

头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//newnode  *ppheadnewnode->next = *pphead;*pphead = newnode;
}

尾删

void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//指向第一个节点的地址//链表不为空//链表只有一个节点/多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;
}

头删

void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点称为新的头SLTNode* next = (*pphead)->next;//->优先级高于*//把旧的头节点释放掉free(*pphead);*pphead = next;
}

查找

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(*pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到当前数据return NULL;
}

在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//链表不能为空assert(*pphead);//pos刚好是头结点if (pos == *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* newnode = SLBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//找到了prev->next = newnode;newnode->next = pos;
}

在指定位置之后插入数据

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

删除指定位之前的节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos){//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}

删除指定位置之后pos节点

//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}}

销毁链表

//销毁链表
void SListDesTory(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

3. 完整代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
#include <stdio.h>//void SlistTest1()
//{
//	//一般不会这样去创建链表，这里只是为了给大家展示链表的打印
//	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
//	node1->data = 1;
//	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
//	node2->data = 2;
//	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
//	node3->data = 3;
//	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
//	node4->data = 4;
//
//	node1->next = node2;
//	node2->next = node3;
//	node3->next = node4;
//	node4->next = NULL;
//
//	SLTNode* plist = node1;//定一个指针指向第一个节点
//	SLTPrint(plist);
//}void SlistTest2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 0);SLTPrint(plist);//SLTPushFront(&plist, 2);//SLTPushFront(&plist, 3);//SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);
}void SlistTest3()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 0);SLTPrint(plist);//头删SLTPopFront(&plist);SLTPrint(plist);//查找SLTNode* FindRet = SLTFind(&plist, 0);if (FindRet){printf("找到了\n");}else {printf("未找到\n");}SLTInsert(&plist, FindRet, 100);SLTPrint(plist);SLTInsertAfter(FindRet, 200);SLTPrint(plist);//删除指定位置的节点SLTErase(&plist, FindRet);SLTPrint(plist);//销毁节点SListDesTory(&plist);
}int main()
{SlistTest3();//SlistTest2();//SlistTest1();return 0;
}

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
#include <assert.h>//链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL){*pphead = newnode;return;}//链表不为空，找尾结点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptril就是尾结点,将尾结点指向newnodeptail->next = newnode;
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//newnode  *ppheadnewnode->next = *pphead;*pphead = newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//指向第一个节点的地址//链表不为空//链表只有一个节点/多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点称为新的头SLTNode* next = (*pphead)->next;//->优先级高于*//把旧的头节点释放掉free(*pphead);*pphead = next;
}//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(*pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到当前数据return NULL;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//链表不能为空assert(*pphead);//pos刚好是头结点if (pos == *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* newnode = SLBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//找到了prev->next = newnode;newnode->next = pos;
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//删除指定位之前的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos){//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}//销毁链表
void SListDesTory(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

SList.h

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdlib.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** pphead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除指定位置之前pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);//销毁链表
void SListDesTory(SLTNode** pphead);

4. 链表的分类

链表的结构非常多样，一下情况组合组合起来就有8种链表结构：

链表说明：

在单链表中，“头结点”的“头”和“带头”链表是两个概念
单链表中提到的“头结点”指的是第一个有效的节点
“带头”链表里的“头”指的是无效的节点

虽然链表的种类非常之多，但是使用比较多的只有两种：单链表（不带头单向不循环链表）和双向链表（带头双向循环链表）