数据结构——单链表

前言

1. 什么是链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。与顺序表不同，链表的存储数据在内存是随机分布的。

2. 链表的分类

链表的种类多种多样，其中最常见的有八种，它们大致可以分为三类：

1 单向和双向

2 带头和不带头

3 循环和不循环

本章将对单向不带头不循环链表进行详细讲解

单向不带头不循环链表

1. 单链表的功能

单链表的主要功能有以下几个：

1. 打印单链表
2. 头插
3. 头删
4. 尾插
5. 尾删
6. 查找

7. 在指定节点之前插入数据

8. 在指定节点之后插入数据
9. 删除指定节点数据
10. 删除指定节点之后的数据
11. 销毁单链表

2. 单链表的定义

一个结构体中包含两个成员。一个是存储数据，一个存放下一个结点的地址（当下一个节点为空时保存的地址为NULL)

typedef int SLTDataType;//将int类型命名为SLTDataType，便于后续更改
typedef struct SListNode
{SLTDataType data; //存储数据struct SListNode* next; //存储下一个节点地址
}SListNode;

3. 单链表功能实现

创建新节点

缩减代码，避免代码冗余

SLTNode* BuyNode(SLTDataType x) {SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//如果创建失败if (node == NULL) {perror("malloc fail!\n");exit(1);}node->data = x;node->next = NULL;return node;//返回该节点
}

1. 打印单链表

void SLTPrint(SLTNode* phead) {SLTNode* cur = phead;while (cur) {printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

2. 头插

void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* node = BuyNode(x);//创建新节点node->next = *pphead;//头插*pphead = node;//将头插进来的节点作为头节点
}

3. 头删

void SLTPopFront(SLTNode** pphead) {assert(pphead);assert(*pphead);//链表不为空SLTNode* first = *pphead;*pphead = (*pphead)->next;//头删free(first);//释放头节点first = NULL;
}

4. 尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);//pphead不为空SLTNode* node = BuyNode(x);//创建新节点//如果链表为空if (*pphead == NULL) {*pphead = node;//新节点为头节点return;}//找尾SLTNode* cur = *pphead;while (cur->next) {cur = cur->next;}cur->next = node;//将新节点进行尾插
}

5. 尾删

void SLTPopBack(SLTNode** pphead) {assert(pphead);assert(*pphead);//链表不为空//如果链表只有一个节点if ((*pphead)->next == NULL) {free(*pphead);//释放头节点*pphead = NULL;//将头节点位置置为空return;}//找尾
//    SLTNode *cur = *pphead;
//    SLTNode *prev = NULL;
//    while(cur->next){
//        prev = cur;
//        cur = cur->next;
//    }
//    prev->next = NULL;
//    free(cur);
//    cur = NULL;SLTNode* tail = *pphead;//寻找尾节点的前一个节点while (tail->next->next) {tail = tail->next;}free(tail->next);//释放尾节点tail->next = NULL;
}

6. 查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {assert(phead);SLTNode* cur = phead;while (cur) {//如果找到该节点，返回该节点if (cur->data == x) {return cur;}cur = cur->next;}return NULL;//否则返回空
}

7. 在指定节点之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//检测pos节点不为空，如果pos节点不为空，那么该链表也不为空SLTNode* node = BuyNode(x);//如果pos==头节点if (*pphead == pos) {//        node->next = pos;//        *pphead = node;SLTPushFront(pphead, x);//头插return;}//找pos的前一个节点SLTNode* prev = *pphead;while (prev->next) {if (prev->next == pos) {break;}prev = prev->next;}//插入pos节点之前node->next = pos;prev->next = node;
}

8. 在指定节点之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* node = BuyNode(x);//创建新节点//插入pos节点之后node->next = pos->next;pos->next = node;
}

9. 删除指定节点数据

void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(pos);//检测pos节点不为空，如果pos节点不为空，那么该链表也不为空//如果pos==头节点if (*pphead == pos) {//        SLTNode *del = *pphead;//        *pphead = (*pphead)->next;//        free(del);//        del = NULL;SLTPopFront(pphead);//头删return;}//找pos的前一个节点SLTNode* prev = *pphead;while (prev->next) {if (prev->next == pos) {break;}prev = prev->next;}prev->next = pos->next;//删除pos节点free(pos);//释放pos节点//    pos = NULL;//没有存在的必要
}

10. 删除指定节点之后的数据

void SLTEraseAfter(SLTNode* pos) {assert(pos);assert(pos->next);//删除pos之后的节点SLTNode* del = pos->next;pos->next = del->next;free(del);//释放该节点del = NULL;
}

11. 销毁单链表

void SListDesTroy(SLTNode** pphead) {SLTNode* pointer = NULL;while (*pphead) {pointer = *pphead;*pphead = (*pphead)->next;free(pointer);pointer = NULL;}
}

4. 完整代码

1. SList.h


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType val;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);

2. SList.c


#include "SList.h"
//创建节点
SLTNode* BuyNode(SLTDataType x) {SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//如果创建失败if (node == NULL) {perror("malloc fail!\n");exit(1);}node->data = x;node->next = NULL;return node;//返回该节点
}
//打印链表
void SLTPrint(SLTNode* phead) {SLTNode* cur = phead;while (cur) {printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);//pphead不为空SLTNode* node = BuyNode(x);//创建新节点//如果链表为空if (*pphead == NULL) {*pphead = node;//新节点为头节点return;}//找尾SLTNode* cur = *pphead;while (cur->next) {cur = cur->next;}cur->next = node;//将新节点进行尾插
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* node = BuyNode(x);//创建新节点node->next = *pphead;//头插*pphead = node;//将头插进来的节点作为头节点
}
//尾删
void SLTPopBack(SLTNode** pphead) {assert(pphead);assert(*pphead);//链表不为空//如果链表只有一个节点if ((*pphead)->next == NULL) {free(*pphead);//释放头节点*pphead = NULL;//将头节点位置置为空return;}//找尾
//    SLTNode *cur = *pphead;
//    SLTNode *prev = NULL;
//    while(cur->next){
//        prev = cur;
//        cur = cur->next;
//    }
//    prev->next = NULL;
//    free(cur);
//    cur = NULL;SLTNode* tail = *pphead;//寻找尾节点的前一个节点while (tail->next->next) {tail = tail->next;}free(tail->next);//释放尾节点tail->next = NULL;
}
//头删
void SLTPopFront(SLTNode** pphead) {assert(pphead);assert(*pphead);//链表不为空SLTNode* first = *pphead;*pphead = (*pphead)->next;//头删free(first);//释放头节点first = NULL;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {assert(phead);SLTNode* cur = phead;while (cur) {//如果找到该节点，返回该节点if (cur->data == x) {return cur;}cur = cur->next;}return NULL;//否则返回空
}
/** 在pos之前插入*/
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//检测pos节点不为空，如果pos节点不为空，那么该链表也不为空SLTNode* node = BuyNode(x);//如果pos==头节点if (*pphead == pos) {//        node->next = pos;//        *pphead = node;SLTPushFront(pphead, x);//头插return;}//找pos的前一个节点SLTNode* prev = *pphead;while (prev->next) {if (prev->next == pos) {break;}prev = prev->next;}//插入pos节点之前node->next = pos;prev->next = node;
}
/** 删除pos*/
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(pos);//检测pos节点不为空，如果pos节点不为空，那么该链表也不为空//如果pos==头节点if (*pphead == pos) {//        SLTNode *del = *pphead;//        *pphead = (*pphead)->next;//        free(del);//        del = NULL;SLTPopFront(pphead);//头删return;}//找pos的前一个节点SLTNode* prev = *pphead;while (prev->next) {if (prev->next == pos) {break;}prev = prev->next;}prev->next = pos->next;//删除pos节点free(pos);//释放pos节点//    pos = NULL;//没有存在的必要
}
//插入pos节点之后
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* node = BuyNode(x);//创建新节点//插入pos节点之后node->next = pos->next;pos->next = node;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos);assert(pos->next);//删除pos之后的节点SLTNode* del = pos->next;pos->next = del->next;free(del);//释放该节点del = NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead) {SLTNode* pointer = NULL;while (*pphead) {pointer = *pphead;*pphead = (*pphead)->next;free(pointer);pointer = NULL;}
}

3. text.c

#include "SList.h"
void Relization(void) {SLTNode* phead = NULL;SLTPushBack(&phead, 5);SLTPushBack(&phead, 2);SLTPushFront(&phead, 3);SLTPushFront(&phead, 4);SLTPopBack(&phead);SLTPopFront(&phead);SLTNode* node = SLTFind(phead, 3);if(node) {printf("找到了\n");}else {printf("没找到\n");}SLTInsert(&phead, phead->next, 7);SLTInsertAfter(phead->next, 6);SLTErase(&phead, NULL);SLTEraseAfter(phead->next->next->next);SLTPrint(phead);SListDesTroy(&phead);SLTPrint(phead);
}
int main() {Relization();return 0;
}