单链表的实现-阿里云开发者社区

单链表的定义

由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

单链表的实现

初始化

我们要先定义一个单链表的结构体，单链表需要一个链表的指针，链表中数据的个数，链表的空间大小，

typedef int SQDatatype;
typedef struct SeqList
{
  SQDatatype* ps;
  int size;
  int capacity;
}SL;

初始化链表时链表指针指向空，链表内元素个数为0，链表空间为0；

//初始化
void SLInit(SL* s1)
{
  assert(s1);
  s1->ps = NULL;
  s1->size = 0;//链表内数据个数
  s1->capacity = 0;//链表空间
}

检查扩容

每次插入数据时我们都要检查一下链表的空间是否足够，因此可以专门下一个检查扩容的函数；

void SLCheckCapacity(SL* s1)
{
  assert(s1);
  //链表内个数和链表空间相等时需要扩容
  if (s1->size == s1->capacity)
  {
    int newcapacity = s1->capacity == 0 ? 4 : s1->capacity * 2;
    SQDatatype* tem = (SQDatatype*)realloc(s1->ps, newcapacity * sizeof(SQDatatype));
    if (tem == NULL)
    {
      perror("realloc fail");
      return;
    }
    s1->ps = tem;
    s1->capacity = newcapacity;
  }
}

注意扩容时要用realloc而不是malloc，malloc是重新开辟空间，会覆盖之前的数据，（因为我之前写的时候，就写错成了malloc，检查了老半天）；

头插

//头插
void SLPushFront(SL* s1, SQDatatype x)
{
  assert(s1);
  SLCheckCapacity(s1);
  for (int i = s1->size; i > 0; i--)
  {
    s1->ps[i] = s1->ps[i - 1];
  }
  s1->ps[0] = x;
  s1->size++;
}

头插时把原来的元素一个个往后移，然后头插入新的元素，记得s1->size++ ,注意细节；

尾插

//尾插
void SLPushBack(SL* s1, SQDatatype x)
{
  assert(s1);
  SLCheckCapacity(s1);
  s1->ps[s1->size] = x;
  s1->size++;
}

头删

删除数据时链表不能为空；

//头删
void SLPopFront(SL* s1)
{
  assert(s1);
  assert(s1->size != 0);
  for (int i = 0; i < s1->size - 1; i++)
  {
    s1->ps[i] = s1->ps[i + 1];
  }
  s1->size--;
}

尾删

删除数据时链表不能为空；

//尾删
void SLPopBack(SL* s1)
{
  assert(s1);
  assert(s1->size != 0);
  s1->size--;
}

指定位置插入

注意判断pos的值，如果pos不在0到size中，会直接报错，所以要加个断言

//指定位置插入
void SLInsert(SL* s1, int pos, SQDatatype x)
{
  assert(s1);
  assert(pos >= 0 && pos <= s1->size);
  SLCheckCapacity(s1);
  for (int i = s1->size; i > pos; i--)
  {
    s1->ps[i] = s1->ps[i - 1];
  }
  s1->ps[pos] = x;
  s1->size++;
 
}

指定位置删除

注意判断pos的值，如果pos不在0到size中，会直接报错，所以要加个断言

//指定位置删除
void SLErase(SL* s1, int pos)
{
  assert(s1);
  assert(pos >= 0 && pos <= s1->size);
  for (int i = pos; i < s1->size - 1; i++)
  {
    s1->ps[i] = s1->ps[i + 1];
  }
  s1->size--;
}

总结(废话）

单链表是动态的顺序表，对于初学者可以锻炼自己的代码能力，当你熟悉之后就会发现很简单，难点就是初学时不清楚细节，还是要多多练习;

一起加油！

完整代码

#pragma once
 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SQDatatype;
typedef struct SeqList
{
  SQDatatype* ps;
  int size;
  int capacity;
}SL;
//初始化
void SLInit(SL* s1);
//检查扩容
void SLCheckCapacity(SL* s1);
//头插
void SLPushFront(SL* s1, SQDatatype x);
//尾插
void SLPushBack(SL* s1, SQDatatype x);
//头删
void SLPopFront(SL* s1);
//尾删
void SLPopBack(SL* s1);
//指定位置插入
void SLInsert(SL* s1, int pos, SQDatatype x);
//指定位置删除
void SLErase(SL* s1, int pos);
//查找数据
void SLFind(SL* s1, SQDatatype x);
//修改数据
void SLModity(SL* s1, int pos, SQDatatype x);
//打印链表
void SLPrintf(SL* s1);
//销毁链表
void SLDestroy(SL* s1);

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
 
void SLInit(SL* s1)
{
  assert(s1);
  s1->ps = NULL;
  s1->size = 0;//链表内数据个数
  s1->capacity = 0;//链表空间
}
 
void SLCheckCapacity(SL* s1)
{
  assert(s1);
  //链表内个数和链表空间相等时需要扩容
  if (s1->size == s1->capacity)
  {
    int newcapacity = s1->capacity == 0 ? 4 : s1->capacity * 2;
    SQDatatype* tem = (SQDatatype*)realloc(s1->ps, newcapacity * sizeof(SQDatatype));
    if (tem == NULL)
    {
      perror("realloc fail");
      return;
    }
    s1->ps = tem;
    s1->capacity = newcapacity;
  }
}
//头插
void SLPushFront(SL* s1, SQDatatype x)
{
  assert(s1);
  SLCheckCapacity(s1);
  for (int i = s1->size; i > 0; i--)
  {
    s1->ps[i] = s1->ps[i - 1];
  }
  s1->ps[0] = x;
  s1->size++;
}
//尾插
void SLPushBack(SL* s1, SQDatatype x)
{
  assert(s1);
  SLCheckCapacity(s1);
  s1->ps[s1->size] = x;
  s1->size++;
}
 
//头删
void SLPopFront(SL* s1)
{
  assert(s1);
  assert(s1->size != 0);
  for (int i = 0; i < s1->size - 1; i++)
  {
    s1->ps[i] = s1->ps[i + 1];
  }
  s1->size--;
}
//尾删
void SLPopBack(SL* s1)
{
  assert(s1);
  assert(s1->size != 0);
  s1->size--;
}
//指定位置插入
void SLInsert(SL* s1, int pos, SQDatatype x)
{
  assert(s1);
  assert(pos >= 0 && pos <= s1->size);
  SLCheckCapacity(s1);
  for (int i = s1->size; i > pos; i--)
  {
    s1->ps[i] = s1->ps[i - 1];
  }
  s1->ps[pos] = x;
  s1->size++;
 
}
//指定位置删除
void SLErase(SL* s1, int pos)
{
  assert(s1);
  assert(pos >= 0 && pos <= s1->size);
  for (int i = pos; i < s1->size - 1; i++)
  {
    s1->ps[i] = s1->ps[i + 1];
  }
  s1->size--;
}
//查找数据
void SLFind(SL* s1, SQDatatype x)
{
  assert(s1);
  int flag = 0;
  for (int i = 0; i < s1->size; i++)
  {
    if (s1->ps[i] == x)
    {
      flag = 1;
      printf("找到了，在下表为%d的位置\n", i);
 
    }
  }
  if(flag==0)
  printf("该数据不存在\n");
}
 
//修改数据
void SLModity(SL* s1, int pos, SQDatatype x)
{
  assert(s1);
  assert(pos >= 0 && pos <= s1->size);
  s1->ps[pos] = x;
}
//打印链表
void SLPrintf(SL* s1)
{
  assert(s1);
  for (int i = 0; i < s1->size; i++)
  {
    printf("%d ", s1->ps[i]);
  }
  printf("\n");
}
//销毁链表
void SLDestroy(SL* s1)
{
  assert(s1);
  free(s1->ps);
  SLInit(s1);
}

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
int main()
{
  SL s1;
  SLInit(&s1);
  SLPushFront(&s1, 1);
  SLPushFront(&s1, 2);
  SLPushFront(&s1, 3);
  SLPushFront(&s1, 4);
  SLPushFront(&s1, 5);
  SLPushBack(&s1, 100);
  SLPushBack(&s1, 200);
  SLPushBack(&s1, 300);
  SLPushBack(&s1, 400);
  SLPushBack(&s1, 500);
  /*SLPopBack(&s1);
  SLPopBack(&s1);
  SLPopBack(&s1);
  SLPopBack(&s1);*/
  /*SLErase(&s1, 2);*/
  SLModity(&s1, 3, 5000);
  SLFind(&s1, 5000);
  SLPrintf(&s1);
  SLDestroy(&s1);
  return 0;
}

单链表的实现

单链表的定义