文章目录

    • 0. 前言
    • 1.链表的概念及结构
    • 2. 单链表概念
    • 3.单链表接口声明
    • 4. 接口实现
      • 4.1 尾插与尾删
      • 4.2 头插与头删
      • 4.3 查找与修改
      • 4.4 pos位置前(后)插入
      • 4.5 pos位置(后面)删除
      • 4.6 关于断言的使用
    • 5. 接口测试

0. 前言

  • 我们需要在程序中存储一系列的数据，这些数据不是一成不变的，需要满足随时的动态增删查改。
  • 顺序表，虽然能满足这些要求，可是顺序表在头插或者中间插入数据时，需要将数据一个一个挪动，效率较低；而且需要频繁的扩容，扩容也是需要付出一定的代价。
  • 为有效解决这些问题，数据结构中有一种链式存储，它不要求逻辑上相邻的元素在物理上也相邻，由此解决了顺序表的缺陷，但同时也失去了顺序表可随机存取的优点。

1.链表的概念及结构

链表由一些节点组成，节点包含两个部分：数据域和指针域。

  • 数据域： 用来存储节点的数据。
  • 指针域： 指向下一个节点的地址。

链表可以分为单向链表、双向链表和循环链表等类型。本篇文章讲解的是单链表的实现。

2. 单链表概念

单链表：每个节点只有一个指针域，指向下一个节点。链表的头结点是第一个节点，尾节点是最后一个节点，其指针域指向 NULL。

3.单链表接口声明

#pragma once#include#include#includetypedef int SLTDateType;typedef struct SListNode{SLTDateType data;//存储的数据struct SListNode* next;//指向下一个节点}SLTNode; //单链表打印void SLTPrint(SLTNode* phead);//尾插void SLTPushBcak(SLTNode** pphead, SLTDateType x);//头插void SLTPushFront(SLTNode** pphead, SLTDateType x);//尾删void SLTPopBack(SLTNode** pphead);//头删void SLTPopFront(SLTNode** pphead);//查找SLTNode* SLTFind(SLTNode* phead, SLTDateType x);//pos之前插入void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);//pos位置删除void SLTErase(SLTNode** pphead, SLTNode* pos);//pos之后插入void SLTInsertAfter(SLTNode* pos, SLTDateType x);//pos位置后面删除void SLTEraseAfter(SLTNode* pos);

4. 接口实现

4.1 尾插与尾删

//买节点SLTNode* BuySLTNode(SLTDateType x){SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;}//尾插void SLTPushBcak(SLTNode** pphead, SLTDateType x){assert(pphead);//买SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}//尾删void SLTPopBack(SLTNode** pphead){assert(pphead);assert(*pphead);//只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//多个节点SLTNode* prev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}}

小贴士：

  • 这里在插入或删除数据的时候，防止第一个数据是空，所以传过来的是二级指针。第一个数据为空，我们需要改变的是结构体指针，更改指针，需要二级指针；如果不为空，我们只需改变结构体的内容，这里只是更改内容，所以用一级指针即可。
  • 尾删时，如果链表本身就为空，那么无法继续删除，所以需要使用断言判断；
    另外，prev是用来保存尾节点的前一个节点的指针，因为在删除尾节点之前需要找到尾节点的前一个节点，将其next指针置为NULL。如果不保存prev指针，将无法将尾节点的前一个节点的next指针置为NULL，从而导致删除操作失败或出现错误的节点连接。

4.2 头插与头删

//头插void SLTPushFront(SLTNode** pphead, SLTDateType x){assert(pphead);SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;}//头删void SLTPopFront(SLTNode** pphead){assert(pphead);assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;}

4.3 查找与修改

查找其实就意味着修改，既然能找到这个值，那也就代表着可以将其内容修改。

//查找or修改SLTNode* SLTFind(SLTNode* phead, SLTDateType x){SLTNode* cur = phead;while (cur){if (cur->data == x)return cur;cur = cur->next;}return NULL;}

4.4 pos位置前(后)插入

//pos之前插入void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x){assert(pos);assert(pphead);if (pos == *pphead){//头插SLTPushFront(&pos, x);}else{//找pos前一个位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}}//pos之后插入void SLTInsertAfter(SLTNode* pos, SLTDateType x){assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;}

4.5 pos位置(后面)删除

//pos位置删除void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead);assert(pos);assert(*pphead);if (pos == *pphead){SLTPopFront(&pos);}else{//找pos前一个位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);//形参改变不影响实参//pos = NULL;}}//pos位置后面删除void SLTEraseAfter(SLTNode* pos){assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;}

4.6 关于断言的使用

我们发现有些位置断言有些位置不用，这其实很好理解：

  1. 打印或者查找链表时，不管是不是空链表，都可以进行，所以不需要断言。
  2. 进行插入的时候，空链表也是可以的；但是链表的地址，必定不能为空，所以这里必定不能为空，这防止我们在传入的时候出错。
  3. 删除也同理，空链表是不能进行删除的，所以需要对链表断言判断是否为空。

5. 接口测试

#define _CRT_SECURE_NO_WARNINGS 1#pragma warning(disable:6031)#include"SList.h"void TestSList1(){//尾插测试//SLTNode s = { 1,NULL };//SLTNode* plist = &s;SLTPushBcak(&plist, 1);plist->data = 1;plist->next = NULL;//SLTPushBcak(plist, 2);//SLTPushBcak(plist, 3);//SLTPushBcak(plist, 4);//SLTPrint(plist);SLTNode* plist = NULL;SLTPushBcak(&plist, 1);SLTPushBcak(&plist, 2);SLTPushBcak(&plist, 3);SLTPushBcak(&plist, 4);SLTPrint(plist);//头插测试/*SLTPushFront(&plist, 4);SLTPushFront(&plist, 3);SLTPushFront(&plist, 2);SLTPushFront(&plist, 1);SLTPrint(plist);*///尾删测试/*SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);*///头删测试/*SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);*///查找测试SLTNode* ret = SLTFind(plist, 2);ret->data *= 2;SLTPrint(plist);//pos前插入测试SLTInsert(&plist, ret, 9);SLTPrint(plist);//pos位置删除测试/*SLTErase(&plist, ret);ret = NULL;SLTPrint(plist);*///pos位置之后插入测试SLTInsertAfter(ret, 10);SLTPrint(plist);//pos位置后面删除SLTNode* a = ret->next;SLTEraseAfter(ret);SLTPrint(plist);}int main(){TestSList1();return 0;}