单链表（增删查改）

2023-06-12 115

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 单链表（增删查改）

一、什么是单链表？

单链表是一种链式存取的数据结构，，链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示的线性表称作线性链表（单链表），单链表是链式存取的结构。简单来说单链表就是一个一个的节点链接起来的链式结构，每个节点里面存储着一个数据和与它链接的下一个节点的（指针）地址。（注意，每一个节点都是同一种结构体类型）

二、单链表的增删查改

2.1 结构体变量的声明

typedef int SLTDataType;
typedef struct SLTNode
{
  SLTDataType data;
  struct SLTNode* next;
}SLTNode;

2.2 申请新结点

SLTNode* BuySListNode(SLTDataType x)
{
  SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newNode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  else
  {
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
  }
}

2.2 链表的头插

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newNode = BuySListNode(x);
  newNode->next = *pphead;
  *pphead = newNode;
}

2.3 链表的尾插

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newNode = BuySListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newNode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newNode;
  }
}

2.4 链表的头删

void SListPopFront(SLTNode** pphead)
{
  assert(pphead && *pphead);
  SLTNode* del = *pphead;
  *pphead = (*pphead)->next;
  free(del);
  del = NULL;
}

2.5 链表的尾删

void SListPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tailPrev = NULL;
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tailPrev = tail;
      tail = tail->next;
    }
    tailPrev->next = NULL;
    free(tail);
    tail = NULL;
  }
}

2.6 链表的查找

SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
  SLTNode* cur = pphead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  printf("找不到%d\n",x);
  return NULL;
}

2.7 链表的任意位置后面插入

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newNode = BuySListNode(x);
  SLTNode* posNext = pos->next;
  pos->next = newNode;
  newNode->next = posNext;
}

2.8 链表的任意位置后面删除

void SListEraseAfter(SLTNode* pos)
{
  assert(pos && pos->next);
  SLTNode* posNext = pos->next;
  pos->next = posNext->next;
  free(posNext);
  posNext = NULL;
}

2.9 链表的销毁

//建议传二级指针，因为销毁的话需要把这个指向链表的指针置空
//传一级指针无法把指向链表的指针置空
void SListDestroy(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* del = cur;
    cur = cur->next;
    free(del);
    del = NULL;
  }
  *pphead = NULL;
}

2.10 链表的打印

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

三、代码汇总

3.1 SLish.h

#pragma once
//SList.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLTDataType;
typedef struct SLTNode
{
  SLTDataType data;
  struct SLTNode* next;
}SLTNode;
// 动态申请一个节点
extern SLTNode* BuySListNode(SLTDataType x);
// 单链表打印
extern void SListPrint(SLTNode* phead);
// 单链表尾插
extern void SListPushBack(SLTNode** pphead, SLTDataType x);
// 单链表的头插
extern void SListPushFront(SLTNode** pphead, SLTDataType x);
// 单链表的尾删
extern void SListPopBack(SLTNode** pphead);
// 单链表头删
extern void SListPopFront(SLTNode** pphead);
// 单链表查找
extern SLTNode* SListFind(SLTNode* pphead, SLTDataType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
extern void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
extern void SListEraseAfter(SLTNode* pos);
// 单链表的销毁
extern void SListDestroy(SLTNode** pphead);

3.2 SLish.c

#define _CRT_SECURE_NO_WARNINGS 1
//Slist.c
#include "SList.h"
SLTNode* BuySListNode(SLTDataType x)
{
  SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newNode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  else
  {
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
  }
}
void SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newNode = BuySListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newNode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newNode;
  }
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newNode = BuySListNode(x);
  newNode->next = *pphead;
  *pphead = newNode;
}
void SListPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tailPrev = NULL;
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tailPrev = tail;
      tail = tail->next;
    }
    tailPrev->next = NULL;
    free(tail);
    tail = NULL;
  }
}
void SListPopFront(SLTNode** pphead)
{
  assert(pphead && *pphead);
  SLTNode* del = *pphead;
  *pphead = (*pphead)->next;
  free(del);
  del = NULL;
}
SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
  SLTNode* cur = pphead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  printf("找不到%d\n",x);
  return NULL;
}
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newNode = BuySListNode(x);
  SLTNode* posNext = pos->next;
  pos->next = newNode;
  newNode->next = posNext;
}
void SListEraseAfter(SLTNode* pos)
{
  assert(pos && pos->next);
  SLTNode* posNext = pos->next;
  pos->next = posNext->next;
  free(posNext);
  posNext = NULL;
}
void SListDestroy(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* del = cur;
    cur = cur->next;
    free(del);
    del = NULL;
  }
  *pphead = NULL;
}

3.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
//test.c
#include "SList.h"
void test_SListPushBack(void)
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 5);
  SListPrint(plist);
  SLTNode* ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListInsertAfter(ret, 6);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListInsertAfter(ret, 7);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListInsertAfter(ret, 8);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListInsertAfter(ret, 9);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListInsertAfter(ret, 10);
    SListPrint(plist);
  }
  /*SLTNode* ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListEraseAfter(ret);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListEraseAfter(ret);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListEraseAfter(ret);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListEraseAfter(ret);
    SListPrint(plist);
  }*/
  /*ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListEraseAfter(ret);
    SListPrint(plist);
  }*/
  //SListInsertAfter(ret, 8);
  /*SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist); 
  SListPopFront(&plist);
  SListPrint(plist); 
  SListPopFront(&plist);
  SListPrint(plist); 
  SListPopFront(&plist);
  SListPrint(plist);*/
}
void test_SListPushFront(void)
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  /*SListPopFront(&plist);
  SListPrint(plist);*/
  //SListDestroy(plist);
  //SListPrint(plist);
  /*SListPopBack(&plist);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPrint(plist);*/
}
int main()
{
  //test_SListPushBack();
  test_SListPushFront();
  return 0;
}

文章标签：

存储

单链表（增删查改）

一、什么是单链表？

二、单链表的增删查改

2.1 结构体变量的声明

2.2 申请新结点

2.2 链表的头插

2.3 链表的尾插

2.4 链表的头删

2.5 链表的尾删

2.6 链表的查找

2.7 链表的任意位置后面插入

2.8 链表的任意位置后面删除

2.9 链表的销毁

2.10 链表的打印

三、代码汇总

3.1 SLish.h

3.2 SLish.c

3.3 test.c

热门文章

最新文章

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

单链表（增删查改）

一、什么是单链表？

二、单链表的增删查改

2.1 结构体变量的声明

2.2 申请新结点

2.2 链表的头插

2.3 链表的尾插

2.4 链表的头删

2.5 链表的尾删

2.6 链表的查找

2.7 链表的任意位置后面插入

2.8 链表的任意位置后面删除

2.9 链表的销毁

2.10 链表的打印

三、代码汇总

3.1 SLish.h

3.2 SLish.c

3.3 test.c

热门文章

最新文章

相关电子书