手撕单链表

简介: 手撕单链表

> 作者简介:დ旧言~,目前大一,现在学习Java,c,c++,Python等

> 座右铭:松树千年终是朽,槿花一日自为荣。

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言      

       前面我们已经学习了顺序表,顺序表可以存储动态的数据,但是一旦元素过少,而又要开辟空间,这样就造成空间的浪费,为了解决这类问题,人们发现了单链表,把一个一个元素以链子的形式存储,那单链表如何实现呢,今天咱们就实现一下--《单链表》。

🌙主体

咱们从三个方面实现单链表,动态管理,头插头删尾插尾删,增删查改。

在程序中为了实现顺序表,需要创建头文件Slist.h ,创建源文件Test.c,Slist.c。

🌠动态管理

💤初始化动态单链表

既然实现单链表,初始化动态的单链表必不可少,从两个方面实现初始化动态的单链表。

1.首先我们在Slist.h定义动态的单链表,省得我们再定义节点(单链表)。

//重匿名方法来定义数据类型
typedef int SLTDataType;
//定义动态的单链表
typedef struct SListNode
{
  //定义数据类型
  SLTDataType data;
  //指向下一个元素
  struct SListNode* next;
}SLTNode;

2.对单链表进行初始化。(这里和顺序表相似)

💦这里采用malloc开辟空间

💦采用预指令判断空间是否开辟完成(没有开辟空间返回-1)

💦之后就是简单的初始数据

💦记得返回值

//初始化
SLTNode* BuySListNode(SLTDataType x)
{
  //开辟空间
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  //判断开辟的空间是否为空
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  //初始化数据
  newnode->data = x;
  newnode->next = NULL;
  //返回数值
  return newnode;
}

💤释放单链表内存

这里就遍历一下单链表就行,没什么好说的

//销毁链表
void SLTDestory(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* cur = *pphead;
  //比cur->next!=NULL更好一些
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

🌠头插头删尾插尾删

💤打印元素

打印元素就太简单了,直接上代码

//打印数据
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    //找到下一个地址
    cur = cur->next;
  }
  printf("NULL\n");
}

💤头插

💦1.因为需要改变结构体的指针,因此需要二级指针来接收

💦2.因为头插是一个元素,因此需要初始化

💦3.指向开始

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  //初始化
  SLTNode* newnode = BuySListNode(x);
  //改变地址指向
  newnode->next = *pphead;
  //指向开始
  *pphead = newnode;
}

💤尾插(重点)

💦1.因为需要改变结构体的指针,因此需要二级指针来接收

💦2.因为尾插是一个元素,因此需要初始化

💦3.如果单链表没有元素,直接把头赋值给pphead

💦4.如果单链表有元素,就需要找到尾,再把开辟好的newnode赋值给tail->next

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  //初始化
  SLTNode* newnode = BuySListNode(x);
  //判断pphead == NULL
  if (*pphead == NULL)
  {
    //改变的结构体的指针,所以要用二级指针
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      //找到尾
      tail = tail->next;
    }
    //改变的结构体,用结构体的指针即可(指向空指针)
    tail->next = newnode;
  }
}

💤头删(重点)

头删还是比较简单的,这里就需要注意一点(单链表为空时,不为空时)

//头删
void SLTPopFront(SLTNode** pphead)
{
  //空时
  assert(*pphead);
  //非空时 指向下一个
  SLTNode* newhead = (*pphead)->next;
  //释放内存
    free(*pphead);
  *pphead = newhead;
}

💤尾删(重点)

💦1.一个节点(一个元素)直接把头指向空(NULL)

💦2.一个节点以上(一个元素以上),先找到尾,再释放内存,最后尾指向空(NULL)

//尾删
void SLTPopBack(SLTNode** pphead)
{
  //不能为空
  assert(*pphead);
  // 1、一个节点
  if ((*pphead)->next == NULL)
  {
    //释放空间
    free(*pphead);
    //指向空
    *pphead = NULL;
  }
  // 2、一个以上节点
  else
  {
    //找到尾
    SLTNode* tail = *pphead;
    while (tail->next->next)
    {
      tail = tail->next;
    }
    //释放空间
    free(tail->next);
    //指向空
    tail->next = NULL;
  }
}

 🌠增删查改

💤查找下标

这个函数是为了增删查改服务的函数,这个函数还是比较好实现的。

//查找下标 需要给尾phead参数
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

💤在pos之前插入x

💦1.因为需要改变结构体的指针,因此需要二级指针来接收

💦2.先断言(pphead和pos)

💦3.如果只有一个元就头插

💦4.再找到pos之前的地址

💦5.初始化插入的元素

💦6.改变元素的地址

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  //断言
  assert(pphead);
  assert(pos);
  //如果只有一个元素就头插
  if (pos == *pphead)
  {
    SLTPushFront(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    //初始化
    SLTNode* newnode = BuySListNode(x);
    //前一个元素地址指向插入的元素
    prev->next = newnode;
    //插入的元素指向后一个元素
    newnode->next = pos;
  }
}

💤在pos之后插入x

这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点

//在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  //断言
  assert(pos);
  //初始化
  SLTNode* newnode = BuySListNode(x);
  pos->next = newnode;
  newnode->next = pos->next;
}

💤删除pos位置

💦1.因为需要改变结构体的指针,因此需要二级指针来接收

💦2.先断言(pphead和pos)

💦3.如果只有一个元就头删

💦4.再找到pos的地址

💦5.修改pos的地址

💦6.释放内存

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  //断言
  assert(pphead);
  assert(pos);
  //如果只有一个元素就头删
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
  }
  else
  {
        //找删除的地址
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    //指向后一元素
    prev->next = pos->next;
    //释放内存
    free(pos);
  }
}

💤删除pos的后一个位置

这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
  //断言
  assert(pos);
  //检查pos是否是尾节点
  assert(pos->next);
  //改变地址
    SLTNode* posNext = pos->next;
  pos->next = posNext->next;
  //释放内存
    free(posNext);
  posNext = NULL;
}

💤单链表结点修改

      其实这个函数也没啥技术含量, 这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点

// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur != pos)
  {
    cur = cur->next;
    assert(cur);
  }
  pos->data = x;
}

🌙代码总结

🌠主函数

//包含头文件
#include"Slist.h"
void TestSList1()
{
  int n;
  printf("请输入链表的长度:");
  scanf("%d", &n);
  printf("\n请依次输入每个节点的值:");
  SLTNode* plist = NULL;
  for (size_t i = 0; i < n; i++)
  {
    int val;
    scanf("%d", &val);
    SLTNode* newnode = BuySListNode(val);
    //头插
    newnode->next = plist;
    //指向头 
    plist = newnode;
  }
  //打印数据
  SLTPrint(plist);
  //这里头插本质相似
  //SLTPushBack(&plist, 10000);
  //打印数据
  SLTPrint(plist);
}
void TestSList2()
{
  //初始化
  SLTNode* plist = NULL;
  //头插
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPushBack(&plist, 5);
  //打印数据
  SLTPrint(plist);
  SLTPushFront(&plist, 10);
  SLTPushFront(&plist, 20);
  SLTPushFront(&plist, 30);
  SLTPushFront(&plist, 40);
  //打印数据
  SLTPrint(plist);
}
void TestSList3()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPushBack(&plist, 5);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  //SLTPopBack(&plist);
  //SLTPrint(plist);
}
void TestSList4()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPushBack(&plist, 5);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  //SLTPopFront(&plist);
  SLTPrint(plist);
}
void TestSList5()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPushBack(&plist, 5);
  SLTPrint(plist);
  SLTNode* pos = SLTFind(plist, 40);
  if (pos)
  {
    pos->data *= 10;
  }
  SLTPrint(plist);
  int x;
  scanf("%d", &x);
  pos = SLTFind(plist, x);
  if (pos)
  {
    SLTInsert(&plist, pos, x * 10);
  }
  SLTPrint(plist);
}
void TestSList6()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPushBack(&plist, 5);
  SLTPrint(plist);
  int x;
  scanf("%d", &x);
  SLTNode* pos = SLTFind(plist, x);
  if (pos)
  {
    //SLTInsertAfter(pos, x * 10);
  }
  SLTPrint(plist);
}
void TestSList7()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPushBack(&plist, 5);
  SLTPrint(plist);
  int x;
  scanf("%d", &x);
  SLTNode* pos = SLTFind(plist, x);
  if (pos)
  {
    //SLTErase(&plist, pos);
    //SLTEraseAfter(pos);
    pos = NULL;
  }
  SLTPrint(plist);
  //SLTPopFront(&plist);
  //SLTPrint(plist);
  //SLTPopFront(&plist);
  //SLTPrint(plist);
  //SLTPopFront(&plist);
  //SLTPrint(plist);
  //SLTPopFront(&plist);
  //SLTPrint(plist);
}
int main()
{
  TestSList7();
  return 0;
}

🌠SqList.h头文件

//使用一些头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//重匿名方法来定义数据类型
typedef int SLTDataType;
//定义动态的单链表
typedef struct SListNode
{
  //定义数据类型
  SLTDataType data;
  //指向下一个元素
  struct SListNode* next;
}SLTNode;
//初始化
SLTNode* BuySListNode(SLTDataType x);
//打印数据
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);
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个位置
void SLTInsertAfter(SLTNode* pos);
//销毁链表
void SLTDestory(SLTNode** pphead);
// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x);

🌠SqList.c源文件

#define _CRT_SECURE_NO_WARNINGS 1
//包含头文件
#include"Slist.h"
//初始化
SLTNode* BuySListNode(SLTDataType x)
{
  //开辟空间
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  //判断开辟的空间是否为空
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  //初始化数据
  newnode->data = x;
  newnode->next = NULL;
  //返回数值
  return newnode;
}
//打印数据
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    //找到下一个地址
    cur = cur->next;
  }
  printf("NULL\n");
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  //初始化
  SLTNode* newnode = BuySListNode(x);
  //改变地址指向
  newnode->next = *pphead;
  //指向开始
  *pphead = newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  //初始化
  SLTNode* newnode = BuySListNode(x);
  //判断pphead == NULL
  if (*pphead == NULL)
  {
    //改变的结构体的指针,所以要用二级指针
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      //找到尾
      tail = tail->next;
    }
    //改变的结构体,用结构体的指针即可(指向空指针)
    tail->next = newnode;
  }
}
//头删
void SLTPopFront(SLTNode** pphead)
{
  //空时
  assert(*pphead);
  //非空时
  SLTNode* newhead = (*pphead)->next;
  free(*pphead);
  *pphead = newhead;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
  //不能为空
  assert(*pphead);
  // 1、一个节点
  if ((*pphead)->next == NULL)
  {
    //释放空间
    free(*pphead);
    //指向空
    *pphead = NULL;
  }
  // 2、一个以上节点
  else
  {
    //找到尾
    SLTNode* tail = *pphead;
    while (tail->next->next)
    {
      tail = tail->next;
    }
    //释放空间
    free(tail->next);
    //指向空
    tail->next = NULL;
  }
}
//查找下标 需要给尾phead参数
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  //断言
  assert(pphead);
  assert(pos);
  //如果只有一个元素就头插
  if (pos == *pphead)
  {
    SLTPushFront(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    //初始化
    SLTNode* newnode = BuySListNode(x);
    //前一个元素地址指向插入的元素
    prev->next = newnode;
    //插入的元素指向后一个元素
    newnode->next = pos;
  }
}
//在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  //断言
  assert(pos);
  //初始化
  SLTNode* newnode = BuySListNode(x);
  pos->next = newnode;
  newnode->next = pos->next;
}
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  //断言
  assert(pphead);
  assert(pos);
  //如果只有一个元素就头删
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
  }
  else
  {
    //找删除的地址
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    //指向后一元素
    prev->next = pos->next;
    //释放内存
    free(pos);
  }
}
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
  //断言
  assert(pos);
  //检查pos是否是尾节点
  assert(pos->next);
  SLTNode* posNext = pos->next;
  pos->next = posNext->next;
  free(posNext);
  posNext = NULL;
}
// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur != pos)
  {
    cur = cur->next;
    assert(cur);
  }
  pos->data = x;
}
//销毁链表
void SLTDestory(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* cur = *pphead;
  //比cur->next!=NULL更好一些
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

🌟结束语

      今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小说手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。

目录
相关文章
|
6月前
|
算法 C++
【数据结构与算法】—— 手撕红黑树
【数据结构与算法】—— 手撕红黑树
|
4月前
|
Java C++ Python
【C++】手撕红黑树
【C++】手撕红黑树
27 1
|
5月前
|
存储 算法 C++
【数据结构与算法】:带你手搓顺序表(C/C++篇)
【数据结构与算法】:带你手搓顺序表(C/C++篇)
|
6月前
|
存储 算法 Java
手撕Java集合——链表
手撕Java集合——链表
【手撕红黑树】
【手撕红黑树】
126 0
手撕红黑树
手撕红黑树
75 0
|
6月前
|
存储 Java C++
手撕双链表
手撕双链表
49 0
|
6月前
|
Java C++ Python
手撕顺序表
手撕顺序表
59 0
|
6月前
|
存储 缓存 算法
手撕无头单链表
手撕无头单链表
35 0
|
6月前
|
搜索推荐
手撕各种排序(中)
手撕各种排序(中)
65 0