备案控制台
探索云世界
开发者社区 云计算 文章 正文

＜单链表（含头结点）＞《数据结构(C语言版)》

2022-11-27 67
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜单链表（含头结点）＞《数据结构(C语言版)》

博文内容：

数据结构（C语言版）之单链表及其功能实现（增删查改）

博文作者：

新晓·故知

注：

★博文转载请注明出处。

★博文仅供学习交流，禁止用于商业用途。

目录

博文内容：

数据结构（C语言版）之单链表及其功能实现（增删查改）

博文作者：

新晓·故知

注：

★博文转载请注明出处。

★博文仅供学习交流，禁止用于商业用途。

《数据结构(C语言版)》实战项目之单链表（增删查改）功能实现

一、完整源码：

完整源码如下，欢迎复制测试指正！

单链表（增删查改）功能实现测试示例：

完整源码：

二、实现分析：

问题导引：

3.链表

3.1 链表的概念及结构

单链表尾插：

单链表头插：

单链表尾删：

单链表头删:

单链表查找（按值查找）:

单链表在指定数据位置（pos）插入数据：

单链表在指定数据位置（pos）后插：

单链表在指定数据位置（pos）删除：

单链表在指定数据位置（pos）后删：

单链表销毁：

单链表动态开辟新结点：

后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                              ——By 作者：新晓·故知

《数据结构(C语言版)》实战项目之单链表（增删查改）功能实现

一、完整源码：

完整源码如下，欢迎复制测试指正！

单链表（增删查改）功能实现测试示例：

image.gif编辑

完整源码：

Test.c:

#include "SList.h"
//单链表
//打印测试
void TestSList1()
{
  SListNode* slist = NULL;
  //malloc需要检查，防止开辟失败
  SListNode* n1 = malloc(sizeof(SListNode));
  SListNode* n2 = malloc(sizeof(SListNode));
  SListNode* n3 = malloc(sizeof(SListNode));
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n1->next = n3;
  n3->next = n2;
  n2->next = NULL;
  slist = n1;
  //SListNode* slist = NULL;
  //SListNode* n1 = malloc(sizeof(SListNode));
  //SListNode* n2 = malloc(sizeof(SListNode));
  //SListNode* n3 = malloc(sizeof(SListNode));
  //n1->data = 1;
  //n2->data = 2;
  //n3->data = 3;
  //n1->next = n2;
  //n2->next = n3;
  //n3->next = NULL;
  //slist = n1; 
  SListPrint(slist);
}
//尾插测试
void TestSList2()
{
  SListNode* slist = NULL; //空链表
  //一个一个创建
  /*SListPushBack(slist, 1);
  SListPushBack(slist, 2);
  SListPushBack(slist, 3);
  SListPushBack(slist, 4);*/
  //使用循环创建
  for (int i = 0; i < 4; ++i)
  {
    SListPushBack(&slist, i);
  }
  SListPrint(slist);
}
//头插测试
void TestSList3()
{
  SListNode* slist = NULL; //空链表
  //使用循环创建
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
}
//尾删测试
void TestSList4()
{
  SListNode* slist = NULL; //空链表
  //使用尾插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushBack(&slist, i);
  }
  SListPrint(slist);
  //尾删5次
  SListPopBack(&slist);
  SListPopBack(&slist);
  SListPopBack(&slist);
  SListPopBack(&slist);
  SListPopBack(&slist);
  SListPopBack(&slist);
  SListPrint(slist);
}
//头删测试
void TestSList5()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  //头删
  SListPopFront(&slist);
  SListPrint(slist);
  SListPopFront(&slist);
  SListPopFront(&slist);
  SListPrint(slist);
  SListPopFront(&slist);
  SListPrint(slist);
}
//查找（按值查找）测试
void TestSList6()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  //查找
  SListNode* pos = SListFind(slist, 2);
  if (pos)
  {
    printf("找到了:%p\n", pos);
    // 修改
    pos->data *= 10; //扩大10倍
  }
  SListPrint(slist);
}
//在指定数据（pos）位置插入数据测试
void TestSList7()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  //在指定数据（pos）位置插入数据
  //查找（按值查找）
  SListNode* pos = SListFind(slist, 3);
  if (pos)
  {
    SListInsert(&slist, pos, 30);
  }
  SListPrint(slist);
  //查找（按值查找）
  pos = SListFind(slist, 1);
  if (pos)
  {
    SListInsert(&slist, pos, 50);
  }
  SListPrint(slist);
}
// 在指定数据位置（pos）后插测试
void TestSList8()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  // 在指定数据位置（pos）后插
  //查找（按值查找）
  SListNode* pos = SListFind(slist, 2);
  if (pos)
  {
    SListInsertAfter(pos, 30);
  }
  SListPrint(slist);
}
// 在指定数据位置（pos）删除测试
void TestSList9()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  // 在指定数据位置（pos）删除
  //查找（按值查找）
  SListNode* pos = SListFind(slist, 2);
  if (pos)
  {
    SListErase(&slist, pos);
  }
  SListPrint(slist);
  //查找（按值查找）
  pos = SListFind(slist, 1);
  if (pos)
  {
    SListErase(&slist, pos);
  }
  SListPrint(slist);
}
// 在指定数据位置（pos）位置后删测试
void TestSList10()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  //在指定数据位置（pos）位置后删
  //查找（按值查找）
  SListNode* pos = SListFind(slist, 2);
  if (pos)
  {
    SListEraseAfter(pos);
  }
  SListPrint(slist);
  //查找（按值查找）
  pos = SListFind(slist, 3);
  if (pos)
  {
    SListEraseAfter(pos);
  }
  SListPrint(slist);
}
//销毁单链表测试
void TestSList11()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  //销毁单链表
  SListDestroy(&slist);
}
int main()
{
  TestSList1();
  TestSList2();
  TestSList3();
  TestSList4();
  TestSList5();
  TestSList6();
  TestSList7();
  TestSList8();
  TestSList9();
  TestSList10();
  TestSList11();
  return 0;
}
image.gif

SList.c:

#include "SList.h"
//单链表
//打印
void SListPrint(SListNode* phead)
{    //Print不需要改变什么
  //assert(phead);  //没必要暴力终止程序,空链表也可打印
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//动态开辟新结点
SListNode* BuySListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  //检查是否开辟成功
  if (newnode == NULL)
  {
    printf("malloc fail！\n");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  return newnode;
}
//头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
  assert(pphead);
  //根据需要动态开辟新结点
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
  assert(pphead);
  //根据需要动态开辟新结点
  SListNode* newnode = BuySListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    // 找尾-需要从头遍历
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
////尾插-传参有误
//void SListPushBack(SListNode* phead, SLTDataType x)
//{  
//  //根据需要动态开辟新结点
//  SListNode* newnode = BuySListNode(x);
//  if (phead == NULL)
//  {
//    phead = newnode;
//  }
//  else
//  {
//    // 找尾-需要从头遍历
//    SListNode* tail = phead;
//    while (tail->next != NULL)
//    {
//      tail = tail->next;
//    }
//    tail->next = newnode;
//  }
//}
//尾删
void SListPopBack(SListNode** pphead)
{
  assert(pphead);
  // 也可以暴力检查为空的情况
  //assert(*pphead != NULL);
  // 1、空
  // 2、一个节点
  // 3、多个节点
  if (*pphead == NULL)  // 温柔检查
  {
    return;
  }
  else if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    //写法1——使用双指针
    /*SListNode* prev = NULL;
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
    prev = tail;
    tail = tail->next;
    }
    free(tail);
    tail = NULL;
    prev->next = NULL;*/
    //写法2——提前控制指针
    SListNode* tail = *pphead;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
//头删
void SListPopFront(SListNode** pphead)
{
  assert(pphead);
  // 1、空
  // 2、非空
  if (*pphead == NULL)
  {
    return;
  }
  else
  {
    SListNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
  }
}
//查找（按值查找）
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
  SListNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
// 在指定位置（pos）位置插入数据
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  // 1、pos是第一个节点
  // 2、pos不是第一个节点
  if (pos == *pphead)
  {
    SListPushFront(pphead, x);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    //根据需要动态开辟新结点
    SListNode* newnode = BuySListNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
// 在指定位置（pos）位置后插
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
  assert(pos);
  SListNode* next = pos->next;
  ////写法1
  ////根据需要动态开辟新结点
  //SListNode* newnode = BuySListNode(x);
  ////改动顺序随意
  //pos->next = newnode;
  //newnode->next = next;
  //写法2
  //根据需要动态开辟新结点
  SListNode* newnode = BuySListNode(x);
  //改动顺序指定
  newnode->next = pos->next;
  pos->next = newnode;
}
// 在指定位置（pos）位置删除
void SListErase(SListNode** pphead, SListNode* pos)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    SListPopFront(pphead);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
// 在指定位置（pos）位置后删
void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  //注：这个不会是头删
  SListNode* next = pos->next;
  if (next)
  {
    pos->next = next->next;
    free(next);
    next = NULL;
  }
}
//销毁单链表
void SListDestroy(SListNode** pphead)
{
  assert(pphead);
  SListNode* cur = *pphead;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}
image.gif

SList.h:

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;  //以后可以更改int为char或者double等
typedef struct SListNode
{
  SLTDataType data; // val
  struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SListNode** pphead);
//头删
void SListPopFront(SListNode** pphead);
//查找（按值查找）
//查找可以传二级指针，但没必要，因为不会改变数据，只是进行查找
SListNode* SListFind(SListNode* phead, SLTDataType x);
// 在指定位置（pos）位置前插
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
// 在指定位置（pos）位置删除
void SListErase(SListNode** pphead, SListNode* pos);
// 在指定位置（pos）位置后插
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 在指定位置（pos）位置后删
void SListEraseAfter(SListNode* pos);
//销毁单链表
void SListDestroy(SListNode** pphead);
image.gif

二、实现分析：

问题导引：

顺序表的问题及思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们

再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

3.链表

3.1 链表的概念及结构

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

image.gif编辑

image.gif编辑

也可以这样：

image.gif编辑

单链表实现测试：

测试示例：image.gif编辑 Test.c：

#include "SList.h"
void TestSList1()
{
  SListNode* slist = NULL;
  SListNode* n1 = malloc(sizeof(SListNode));
  SListNode* n2 = malloc(sizeof(SListNode));
  SListNode* n3 = malloc(sizeof(SListNode));
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n1->next = n3;
  n3->next = n2;
  n2->next = NULL;
  slist = n1;
  SListPrint(slist);
}
int main()
{
  TestSList1();
  return 0;
}
image.gif

SList.c:

#include "SList.h"
void SListPrint(SListNode* phead)
{
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
image.gif

SList.h:

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data; // val
  struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
image.gif

单链表不需要初始化，即使最初为空，也是一个空指针，而顺序表最初为空是一个结构体！

image.gif编辑image.gif编辑

image.gif编辑image.gif编辑

image.gif编辑image.gif编辑

举例传参分析：

1.image.gif编辑image.gif编辑

2.image.gif编辑image.gif编辑

image.gif编辑

image.gif编辑

单链表尾插：

测试示例：image.gif编辑

Test.c:

#include "SList.h"
//单链表尾插数据测试
void TestSList2()
{
  SListNode* slist = NULL; //空链表
  //一个一个创建
  /*SListPushBack(slist, 1);
  SListPushBack(slist, 2);
  SListPushBack(slist, 3);
  SListPushBack(slist, 4);*/
  //使用循环创建
  for (int i = 0; i < 4; ++i)
  {
    SListPushBack(&slist, i);
  }
  SListPrint(slist);
}
int main()
{
  TestSList2();
  return 0;
}
image.gif

SList.c:

#include "SList.h"
//单链表打印
void SListPrint(SListNode* phead)
{    //Print不需要改变什么
  //assert(phead);  //不需要暴力终止程序,空链表也可打印
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//单链表动态开辟新结点
SListNode* BuySListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  //检查是否开辟成功
  if (newnode == NULL)
  {
    printf("malloc fail！\n");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  return newnode;
}
//单链表尾插数据
void SListPushBack(SListNode** pphead, SLTDataType x)
{
  //根据需要动态开辟新结点
  SListNode* newnode = BuySListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    // 找尾-需要从头遍历
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
image.gif

SList.h:

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;  //以后可以更改int为char或者double等
typedef struct SListNode
{
  SLTDataType data; // val
  struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);
image.gif

单链表头插：

测试示例：image.gif编辑

Test.c:

#include "SList.h"
//单链表头插数据测试
void TestSList3()
{
  SListNode* slist = NULL; //空链表
  //使用循环创建
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
}
int main()
{
  TestSList3();
  return 0;
}
image.gif

SList.c:

#include "SList.h"
//单链表打印
void SListPrint(SListNode* phead)
{    //Print不需要改变什么
  //assert(phead);  //不需要暴力终止程序,空链表也可打印
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//单链表动态开辟新结点
SListNode* BuySListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  //检查是否开辟成功
  if (newnode == NULL)
  {
    printf("malloc fail！\n");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  return newnode;
}
//单链表头插数据
void SListPushFront(SListNode** pphead, SLTDataType x)
{
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
image.gif

SList.h:

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;  //以后可以更改int为char或者double等
typedef struct SListNode
{
  SLTDataType data; // val
  struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);
image.gif

单链表尾删：

image.gif编辑

image.gif编辑image.gif编辑

单链表头删:image.gif编辑

单链表查找（按值查找）:image.gif编辑

单链表在指定数据位置（pos）插入数据：image.gif编辑

单链表在指定数据位置（pos）后插：image.gif编辑

单链表在指定数据位置（pos）删除：image.gif编辑

单链表在指定数据位置（pos）后删：image.gif编辑

单链表销毁：image.gif编辑

单链表动态开辟新结点：image.gif编辑

image.gif编辑

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                   ——By 作者：新晓·故知

文章标签：
存储
关键词：
C语言单链表
C语言数据结构
数据结构c语言
单链表数据结构
数据结构单链表
新晓故知
目录
相关文章
yma16
|
6天前
|
C语言
C语言用头插法建立单链表
C语言用头插法建立单链表
yma16
4 0
颦颦Admin@123
|
6天前
|
存储 算法 C语言
C语言进阶：顺序表（数据结构基础） （以通讯录项目为代码练习）
C语言进阶：顺序表（数据结构基础） （以通讯录项目为代码练习）
颦颦Admin@123
8 0
yma16
|
6天前
|
C语言
数据结构中顺序栈的进栈和出栈用C语言表示
数据结构中顺序栈的进栈和出栈用C语言表示
yma16
14 1
认真学习的小雅兰.
|
14天前
|
存储 算法
单链表——“数据结构与算法”
单链表——“数据结构与算法”
认真学习的小雅兰.
13 0
ForcibleBugMaker
|
22天前
|
存储 缓存 程序员
初阶数据结构之---顺序表和链表（C语言）
初阶数据结构之---顺序表和链表（C语言）
ForcibleBugMaker
54 1
ForcibleBugMaker
|
22天前
|
机器学习/深度学习 存储 算法
初阶数据结构之---导论，算法时间复杂度和空间复杂度（C语言）
初阶数据结构之---导论，算法时间复杂度和空间复杂度（C语言）
ForcibleBugMaker
16 1
阿森要自信
|
28天前
|
算法 C语言
【算法与数据结构】 C语言实现单链表队列详解2
【算法与数据结构】 C语言实现单链表队列详解
阿森要自信
12 1
阿森要自信
|
28天前
|
存储 算法 C语言
【算法与数据结构】 C语言实现单链表队列详解1
【算法与数据结构】 C语言实现单链表队列详解
阿森要自信
22 0
Kevin_17
|
23天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列（二）：队列
深入理解栈和队列（二）：队列
Kevin_17
36 0
张继群
|
2月前
|
存储 开发工具
栈存储结构详解
栈存储结构详解
张继群
42 7