备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

数据结构之顺序表的实现（详解！附完整代码）

2024-03-25 37
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构之顺序表的实现（详解！附完整代码）

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构

常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表和链表的存储结构如下：

顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改

而顺序表又可以分为：

静态顺序表

使用定长数组存储元素：

也就是说，已经把数组的长度内定了，用宏定义了数组的长度

动态顺序表

使用动态开辟的数组存储：

用malloc函数开辟空间，当数组的存储空间不够可以用realloc扩容，在顺序表中我们用的更多的是动态的顺序表

顺序表的接口实现

这里我们只实现动态的顺序表，静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表

头文件如下：

#include<stdio.h>
#include<assert.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDateType;
typedef struct SeqList
{
  SLDateType* a;
  int size;
  int capacity;
}SL;
// 对数据的管理:增删查改 
void SeqListInit(SL* ps);
void SeqListDestroy(SL* ps);
void SeqListPrint(SL* ps);
void SeqListPushBack(SL* ps, SLDateType x);
void SeqListPushFront(SL* ps, SLDateType x);
void SeqListPopFront(SL* ps);
void SeqListPopBack(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);
//修改pos位置的值
void SeqListModify(SL* ps, int pos, SLDateType x);

首先为了方便顺序表的灵活运用，我们用typedef来在头文件中定义int为SLDateType，如果下次是字符型的数据，我们只需要在这里将int改为char，后续的代码就不用更改，其次我们定义一个结构体为顺序表

typedef int SLDateType;
typedef struct SeqList
{
  SLDateType* a;//数组，存放数据
  int size;//数组内存放有效数据的元素
  int capacity;//数组能够存储数据的容量
}SL;//将顺序表有typedef简化为SL，方便后面的代码撰写
初始化顺序表

我们在顺序表中创建一个表后，首先要做的就是初始化这个数据结构，在今后的学习中我们更是要养成一个初始化的习惯，不然很容易出现bug，有些编译器甚至会警告

我们在这里将初始化函数取名为SeqListInit，所需参数为结构体的地址

我们首先断言这个顺序表，防止为空，所以我们在头文件中直接写下assert.h

在这里我们要实现的是动态顺序表，所以我们用malloc动态开辟数组a的空间，记住，要判断动态开辟是否为空，不然部分的编译器会有警告

初始化我们直接将数组的size初始化为0，capacity我们初始化为4

这样我们初始化就完成了

void SeqListInit(SL* ps)
{
  assert(ps);
  ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
  if (ps->a == NULL)
  {
    perror("malloc");
    return;
  }
  ps->size = 0;
  ps->capacity = 4;
}
销毁顺序表

在函数完成后我们需要销毁顺序表，避免内存的浪费和野指针的出现，所以我们定义一个销毁顺序表的函数：

首先要做的还是断言

然后将数组的空间free掉，并将其置为空指针（防止出现野指针），最后将size和capacity都置为0，就完成了销毁

void SeqListDestroy(SL* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}
顺序表打印

我们增删查改后需要打印这个顺序表

打印函数和数组一样，不做过多的讲解

void SeqListPrint(SL* ps)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
顺序表数据的插入

凡是插入数据，咱们都要检查他的容量是否够，所以我们可以先写一个函数检查容量，如果数组已满，就扩容

当size和capacity相等的时候就是容量已满，我们就realloc开辟一个新的空间，大小为原先a数组的两倍，然后再将新的空间capacity给数组a，capacity变成原来的两倍

void CheckCapacity(SL* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
    SLDateType* temp = (SLDateType*)realloc(ps->a,ps->capacity*sizeof(SLDateType*) * 2);
    if (temp == NULL)
    {
      perror("realloc");
      return;
    }
    ps->a = temp;
    ps->capacity *= 2;
  }
}

数据的尾插：

尾插很容易，先检查容量

然后将数组的下标为size的位置插入数据x

同时size要++

void SeqListPushBack(SL* ps, SLDateType x)
{
  assert(ps);
  CheckCapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;
}

头插：

同样的我们首先检查容量，并且要将所有的数据后移一位，再将数据x插入数组下标为0的位置，同时size++

void SeqListPushFront(SL* ps, SLDateType x)
{
  assert(ps);
  CheckCapacity(ps);
  int end = ps->size - 1;
  while (end>=0)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[0] = x;
  ps->size++;
}
顺序表数据的删除

删除的时候一定要记得断言，因为空顺序表就删不了了

头删：

我们将下标为1的元素往前移动，然后size–就可以完成删除了，移动一次，begin++，同时begin是要小于size的，也就是可以等于size-1

void SeqListPopFront(SL* ps)
{
  assert(ps);
  int begin = 1;
  while (begin<ps->size)
  {
    ps->a[begin] = ps->a[begin - 1];
    begin++;
  }
  ps->size--;
}

尾删：

尾删我们直接将size-1下标的位置置为0，然后size–就可以了，当然，首先就得记得断言！

void SeqListPopBack(SL* ps)
{
  assert(ps);
  ps->a[ps->size - 1] = 0;
  ps->size--;
}
顺序表数据的查找

如果在顺序表中查找一个数据的位置，该怎么办呢？

很简单，我们可以遍历这个数组，然后返回下标就可以了，数据可以直接进行下标的访问，这就很舒服了，如果找不到，这里我就然他返回-1，因为-1是不可能为数组的下标的

int SeqListFind(SL* ps, SLDateType x)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == x)
    {
      return i;
    }
    return -1;
  }
}
顺序表pos位置的插入

在这里的插入数据，我们首先要将知道pos位置，而且pos位置要是大于等于0，小于等于size的，因为头插就是下标为0的位置，尾插就是下标为size的位置，之前的头插尾插我们可以直接用这个函数

插入数据我们先将pos位置以及后面的元素的值往后面移动，然后再直接将a[pos]赋值为x，

并且也要从最后一个位置开始往前移动，同时size++

void SeqListInsert(SL* ps, int pos, SLDateType x)
//先移动后插入
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  CheckCapacity(ps);
  int end = ps->size - 1;
  while (pos <= ps->size - 1)
  {
    ps->a[end+1] = ps->a[end];
    end++;
  }
  ps->a[pos] = x;
  ps->size++;
}
顺序表pos位置的删除

pos位置的删除我们可直接将pos+1位置的元素往前面移动，然后size–

void SeqListErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);
  int begin = pos + 1;
  while (begin < ps->size - 1 )//这里是<size-1的原因是因为begin=size-2，begin+1就是size-1了
  {
    ps->a[begin] = ps->a[begin + 1];
    begin++;
  }
  ps->size--;
}
顺序表pos位置的修改

修改也很容易，直接下标访问，赋值为x

void SeqListModify(SL* ps, int pos, SLDateType x)
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);
  ps->a[pos] = x;
}

到这里，顺序表的实习就完成了，完整代码如下：

头文件：

#include<stdio.h>
#include<assert.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDateType;
typedef struct SeqList
{
  SLDateType* a;
  int size;
  int capacity;
}SL;
// 对数据的管理:增删查改 
void SeqListInit(SL* ps);
void SeqListDestroy(SL* ps);
void SeqListPrint(SL* ps);
void SeqListPushBack(SL* ps, SLDateType x);
void SeqListPushFront(SL* ps, SLDateType x);
void SeqListPopFront(SL* ps);
void SeqListPopBack(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);
//修改pos位置的值
void SeqListModify(SL* ps, int pos, SLDateType x);

函数定义：

void SeqListInit(SL* ps)
{
  assert(ps);
  ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
  if (ps->a == NULL)
  {
    perror("malloc");
    return;
  }
  ps->size = 0;
  ps->capacity = 4;
}
void SeqListDestroy(SL* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}
void SeqListPrint(SL* ps)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
void CheckCapacity(SL* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
    SLDateType* temp = (SLDateType*)realloc(ps->a,ps->capacity*sizeof(SLDateType*) * 2);
    if (temp == NULL)
    {
      perror("realloc");
      return;
    }
    ps->a = temp;
    ps->capacity *= 2;
  }
}
//尾插
void SeqListPushBack(SL* ps, SLDateType x)
{
  assert(ps);
  CheckCapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;
}
//头插
void SeqListPushFront(SL* ps, SLDateType x)
{
  assert(ps);
  CheckCapacity(ps);
  int end = ps->size - 1;
  while (end>=0)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[0] = x;
  ps->size++;
}
//头删
void SeqListPopFront(SL* ps)
{
  assert(ps);
  int begin = 1;
  while (begin<ps->size)
  {
    ps->a[begin] = ps->a[begin - 1];
    begin++;
  }
  ps->size--;
  //可以用SeqListErase（ps, 0）
}
//尾删
void SeqListPopBack(SL* ps)
{
  assert(ps);
  ps->a[ps->size - 1] = 0;
  ps->size--;
  //可以用SeqListErase（ps,size-1）
}
// 顺序表查找
int SeqListFind(SL* ps, SLDateType x)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == x)
    {
      return i;
    }
    return -1;
  }
}
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDateType x)
//先移动后插入
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  CheckCapacity(ps);
  int end = ps->size - 1;
  while (pos <= ps->size - 1)
  {
    ps->a[end+1] = ps->a[end];
    end++;
  }
  ps->a[pos] = x;
  ps->size++;
}
void SeqListErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);
  int begin = pos + 1;
  while (begin < ps->size - 1)
  {
    ps->a[begin] = ps->a[begin + 1];
    begin++;
  }
  ps->size--;
}
void SeqListModify(SL* ps, int pos, SLDateType x)
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);
  ps->a[pos] = x;
}

今天的分享到这里就结束了，谢谢大家的支持！

文章标签：
存储
编译器
关键词：
数据结构代码
数据结构顺序表
数据结构顺序表代码
只是雪豹
目录
相关文章
修修修也
|
28天前
|
存储 编译器 C语言
【数据结构】C语言实现链队列(附完整运行代码)
【数据结构】C语言实现链队列(附完整运行代码)
修修修也
36 0
修修修也
|
28天前
|
存储 算法 程序员
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
修修修也
39 0
是小宇吖
|
30天前
|
存储 编译器
数据结构：顺序表详解
数据结构：顺序表详解
是小宇吖
37 0
诡异森林。
|
存储 索引
数据结构--动态顺序表
数据结构--动态顺序表
诡异森林。
36 0
颦颦Admin@123
|
3天前
|
存储 算法 C语言
C语言进阶：顺序表（数据结构基础） （以通讯录项目为代码练习）
C语言进阶：顺序表（数据结构基础） （以通讯录项目为代码练习）
颦颦Admin@123
7 0
鼠鼠我呀
|
1月前
|
机器学习/深度学习 存储 Java
揭秘数组：数据结构的基石与代码实践解析
揭秘数组：数据结构的基石与代码实践解析
鼠鼠我呀
9 0
只是雪豹
|
1月前
栈和队列的实现（详解+图解！文末附完整代码）
栈和队列的实现（详解+图解！文末附完整代码）
只是雪豹
78 2
67vpym2vvkfhs
|
1月前
|
存储 机器学习/深度学习 算法
C语言代码实现数据结构与算法
以上代码中，哈希表使用链表解决哈希冲突，每个链表节点包含一个键值对。hash函数用于计算键值对应的哈希值，insert函数用于向哈希表中插入一个键值对，若当前位置为空，则直接插入；否则，将新节点插入到链表末尾。search函数用于在哈希表中查找指定键值的值，若存在则返回其值，否则返回-1。
67vpym2vvkfhs
32 1
起飞的风筝
|
1月前
|
存储
【数据结构——顺序表的实现】
【数据结构——顺序表的实现】
起飞的风筝
26 0
小王又困了
|
1月前
|
存储
【数据结构】顺序表
【数据结构】顺序表
小王又困了
28 0

热门文章

最新文章

  • 1
    数据结构期末复习（fengkao课堂）
  • 2
    【C/C++ 数据结构 】从零开始实现哈希表：C++实践指南
  • 3
    Java数据结构与算法-java数据结构与算法（二）
  • 4
    【数据结构】【版本2.0】【树形深渊】——二叉树入侵
  • 5
    【C/C++ 数据结构 树】探索C/C++中的二叉树：从理论到实践
  • 6
    【C/C++ 数据结构 线性表】深入理解与实现栈：从基础到应用的全面探索
  • 7
    数据结构-概念版（七）
  • 8
    Java数据结构与算法-java数据结构与算法（五）
  • 9
    【C/C++ 数据结构】深入探索数据结构中算法复杂度：从C++和数学的视角
  • 10
    python学习-函数模块，数据结构，字符串和列表（下）
  • 1
    【手撕数据结构】二分查找(好多细节)
    16
  • 2
    【数据结构与算法】—— 手撕红黑树
    37
  • 3
    【排序算法】数据结构排序详解
    42
  • 4
    【链式二叉树】数据结构链式二叉树的（万字详解）
    43
  • 5
    【堆】数据结构堆的实现（万字详解）
    52
  • 6
    【树和二叉树】数据结构二叉树和树的概念认识
    25
  • 7
    【双向链表】数据结构双向链表的实现
    21
  • 8
    数据结构——单链表的基本操作
    11
  • 9
    数据结构——排序算法之快速排序
    34
  • 10
    数据结构——二叉树的链式结构
    36

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）