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

数据结构：顺序表详解

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

一、 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的。

线性表在物理上存储时，通常以数组和链式结构的形式.

二、 顺序表概念及结构

顺序表一般可以分为:

1. 静态顺序表：使用定长数组存储元素。

2. 动态顺序表：使用动态开辟的数组存储。

三、接口实现

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

基本增删查改接口

//对数据管理 --- 增删查改
void SLInit(SL* ps);      //初始化
void SLDestory(SL* ps);     //释放
void SLPrint(SL* ps);         //打印
void SLCheakCapacity(SL* ps); //检查容量 -- 扩容

//头插头删 尾插尾删
void SLPushBack(SL* ps, SLDateType x); //尾插
void SLPopBack(SL* ps);          //尾删
void SLPushFront(SL* ps, SLDateType x);//头插
void SLPopFront(SL* ps);         //头删

//返回下标，没找到返回-1
int SLFind(SL* ps, SLDateType);      //查找元素，返回下标

//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDateType x); //任意位置插入
//在pos位置删除x
void SLErase(SL* ps, int pos);          //任意位置删除

void SLModify(SL* ps, int pos, SLDateType x);//修改

1. 创建

由于在实际工程中，项目的实现都是采用模块化进行实现的。所以在此处博主也采用了模块化的方式进行实现。

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
  SLDateType* a;//指向动态开辟的数组
  int size; //有效数据的个数
  int capacity;//容量空间的大小
}SL;

为了后续好修改类型数据，在此采用typedef将结构体类型struct SeqList 重新命名为SL。

在实际开发过程中，为了开发人员更好的输入数据，一般我们会将输入数据的数据类型重命名为SLDateType。（在本篇博客中，采用typedef将其数据类型int重命名为SLDateType）

2. 初始化

初始化时，理论上我们只需要开辟一个空间并置为空指针，并将结构体中的数据全部初始化为0即可。

但在实际开发过程中，我们一般会开辟一定大小的空间（本篇博客开4个空间，但具体开多少，各位可自行选择）。

代码实现：

void SLInit(SL* ps)
{
  assert(ps);
  ps->a = (SLDateType*)malloc(4 * sizeof(SLDateType));//开辟4个空间
  if (ps->a == NULL)
  {
    perror("malloc");
    exit(-1);
  }
  //开辟成功
  ps->capacity = 4;//开辟多少空间，容量变为多少
  ps->size = 0;
}

3. 扩容

在后续我们插入数据时，已开辟容量可能已经无法满足需求了。这是就需要扩容。

那一次扩到多少呢？

在实际开发过程中我们一般是扩到原有空间的两倍。（当然你也可以开1000倍，只要后台空间足够大）

代码实现：

void SLCheakCapacity(SL* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
    //开辟空间X2
    SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * sizeof(SLDateType) * 2);
    if (tmp == NULL)
    {
      perror("realloc");
      exit(-1);
    }
    //开辟成功
    ps->a = tmp;
    ps->capacity *= 2;
  }
}

4. 打印

上述函数定义完成后，我们通常需要测试打印以下相关数据，来判断相关函数定义是否成功.

代码实现：

void SLPrint(SL* ps)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}

5. 销毁

由于上述空间是动态开辟的。所以当我们使用完时，要及时销毁，释放空间。

代码实现：

void SLDestory(SL* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->size = 0;
}

6. 尾插

尾插：在尾部插入一个数据。

但是在数据的尾部插入一个数据时，我们需要考虑一个问题：原有空间是否可以容纳新的数据，是否需要扩容。

所以我们在插入数据时，要先调用 SLCheakCapacity函数来检查是否需要扩容。

代码实现：

void SLPushBack(SL* ps, SLDateType x)
{
  assert(ps);
  SLCheakCapacity(ps);//检查是否需要扩容
  ps->a[ps->size] = x;
  ps->size++;
}

7. 尾删

尾删：删除尾部最后的一个元素。

但尾删同样也要考虑一个问题，空间中是否还有数据给我们删除。

所以在进行尾删时，我们可以采用assert函数断言空间中还有数据。

代码实现：

void SLPopBack(SL* ps)
{
  assert(ps);
  assert(ps->size >= 0);//断言空间中还有元素
  ps->size--;//下标减1
}

在删除数据时，我们不用将原有数据删除。只需要下标减1即可。

原因在于我们时根据下标来使用数据的，当下标减1后，尾部最后一个数据便无法进行访问。

Tips:

  • 越界是不一定报错的，系统对越界的检查是一种设岗抽查。
  • 以VS2022为例，微软公司在数据的开始前和结尾后的一小段空间设有一些特殊值。当程序结束或内存空间释放时，编译器就会检查这些值是否发生改变, 从而触发程序的保护机制。但如果这些值没有发生改变，即使发生越界访问，程序也不会报错。就像如果你酒驾，交警只在二环设关卡，但只要你不去二环，你就没事不会被发现。（每个编译器略有差异）

8. 头插

头插：在数据最开始地方插入数据。

同样，头插也要调用 SLCheakCapacity函数来检查空间是否足够，是否需要扩容。

代码实现：

void SLPushFront(SL* ps, SLDateType x)
{
  assert(ps);
  SLCheakCapacity(ps);//检查是否需要扩容

  //移动数据
  int i = ps->size-1;
  while (i >= 0)
  {
    ps->a[i + 1] = ps->a[i];
    i--;
  }
  //移动数据完成，插入元素。同时有效个数加1
  ps->a[0] = x;
  ps->size++;
}

9. 头删

头删：删除数据最开始的元素。

思路和头插类似，只要下标从1开始，所有数据依次向前移动1位，再把有限个数减1即可。

同时头删也需要使用assert函数断言原有空间中还有数据可以删除。

代码实现：

void SLPopFront(SL* ps)
{
  assert(ps);
  assert(ps->size >= 0);//空间中还有数据可以删除
  //移动数据
  for (int begin = 1; begin < ps->size; begin++)
  {
    ps->a[begin - 1] = ps->a[begin];
  }
  ps->size--;//有效个数减1
}

10. 插入任意位置数据

由于顺序表要求数据是连续存放的,所以我们只需要找到输入位置的下标pos即可。

【代码思路】：首先我们要检查输入下标是否合法，是有效下标；并检查是否有足够空间来容纳新数据，是否需要扩容。之后从输入的数据下标开始，所有元素向后移动一位，并把新数据插入到下标为pos处即可。

代码实现：

void SLInsert(SL* ps, int pos, SLDateType x)
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);//检查下标是否合法
  SLCheakCapacity(ps);  //检查空间是否足够
  //移动数据
  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;
}

11. 删除任意位置数据

【代码思路】：和插入任何位置数据思想类似。首先我们要检查输入下标pos是否合法。之后从输入下标开始，后一个元素拷贝到前一个元素空间。

代码实现：

void SLErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);//下标是否合法
  //移动数据
  int begin = pos+1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}

12. 查找

【代码思路】：要查找某个元素。由于这里只是最简单的查找，我们直接暴力查找，遍历整个数组返回下标即可。更为复杂的数据查找，会有更高阶的数据结构来实现。

代码实现：

int SLFind(SL* ps, SLDateType x)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    if (x == ps->a[i])
      return i;
  }
  return -1;
}

13. 修改

【代码思路】： 要实现修改数据，我们只需要先判断输入下标是否合法。在将对应下标数据进行修改即可。

代码实现：

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

四：所有代码

SeqList.h源文件

#include <assert.h>
#include <stdlib.h>


//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
  SLDateType* a;
  int size;
  int capacity;
}SL;


//对数据管理 --- 增删查改
void SLInit(SL* ps);
void SLDestory(SL* ps);
void SLPrint(SL* ps);
void SLCheakCapacity(SL* ps);

//头插头删 尾插尾删
void SLPushBack(SL* ps, SLDateType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDateType x);
void SLPopFront(SL* ps);


//返回下标，没找到返回-1
int SLFind(SL* ps, SLDateType);

//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDateType x);
//在pos位置删除x
void SLErase(SL* ps, int pos);


void SLModify(SL* ps, int pos, SLDateType x);

SeqList.c头文件

#define _CRT_SECURE_NO_WARNINGS

#include "SeqList.h"


void SLInit(SL* ps)
{
  assert(ps);
  ps->a = (SLDateType*)malloc(4 * sizeof(SLDateType));
  if (ps->a == NULL)
  {
    perror("malloc");
    exit(-1);
  }
  //开辟成功
  ps->capacity = 4;
  ps->size = 0;
}


void SLDestory(SL* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->size = 0;
}

void SLPrint(SL* ps)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}

void SLCheakCapacity(SL* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
    SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * sizeof(SLDateType) * 2);
    if (tmp == NULL)
    {
      perror("realloc");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
}


void SLPushBack(SL* ps, SLDateType x)
{
  assert(ps);
  /*SLCheakCapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;*/

  SLInsert(ps, ps->size, x);
}


void SLPopBack(SL* ps)
{
  assert(ps);
  assert(ps->size >= 0);
  /*ps->size--;*/
  SLErase(ps, 0);
}


void SLPushFront(SL* ps, SLDateType x)
{
  assert(ps);
  SLCheakCapacity(ps);

  //移动数据
  /*int i = ps->size-1;
  while (i >= 0)
  {
    ps->a[i + 1] = ps->a[i];
    i--;
  }
  ps->a[0] = x;
  ps->size++;*/
  SLInsert(ps, 0, x);
}


void SLPopFront(SL* ps)
{
  assert(ps);
  assert(ps->size >= 0);
  /*for (int begin = 1; begin < ps->size; begin++)
  {
    ps->a[begin - 1] = ps->a[begin];
  }
  ps->size--;*/
  SLErase(ps, 0);
}


int SLFind(SL* ps, SLDateType x)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    if (x == ps->a[i])
      return i;
  }
  return -1;
}


void SLInsert(SL* ps, int pos, SLDateType x)
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  SLCheakCapacity(ps);

  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;

}



void SLErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);

  int begin = pos+1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}



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


文章标签：
存储
编译器
关键词：
数据结构顺序表
是小宇吖
目录
相关文章
修修修也
|
27天前
|
存储 算法 程序员
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
修修修也
39 0
诡异森林。
|
存储 索引
数据结构--动态顺序表
数据结构--动态顺序表
诡异森林。
36 0
鲜于言悠
|
1月前
|
存储 消息中间件 算法
数据结构从入门到精通——顺序表
顺序表是一种常见的线性数据结构，它使用一段连续的存储单元依次存储数据元素。这种数据结构的特点是逻辑上相邻的元素在物理存储位置上也相邻，因此可以快速地访问表中的任意元素。 顺序表的实现通常依赖于数组，数组是一种静态的数据结构，一旦创建，其大小就是固定的。这意味着在顺序表中插入或删除元素可能会导致空间的浪费或不足。例如，如果在一个已经满了的顺序表中插入一个新元素，就需要重新分配更大的数组空间，并将原有元素复制到新数组中，这是一个相对耗时的操作。
鲜于言悠
54 0
仍在探索未知中
|
3月前
|
存储 算法 C语言
数据结构 | 顺序表专题
数据结构 | 顺序表专题
仍在探索未知中
41 0
颦颦Admin@123
|
2天前
|
存储 算法 C语言
C语言进阶：顺序表（数据结构基础） （以通讯录项目为代码练习）
C语言进阶：顺序表（数据结构基础） （以通讯录项目为代码练习）
颦颦Admin@123
4 0
只是雪豹
|
1月前
|
存储 编译器
数据结构之顺序表的实现（详解！附完整代码）
数据结构之顺序表的实现（详解！附完整代码）
只是雪豹
37 1
起飞的风筝
|
1月前
|
存储
【数据结构——顺序表的实现】
【数据结构——顺序表的实现】
起飞的风筝
26 0
小王又困了
|
1月前
|
存储
【数据结构】顺序表
【数据结构】顺序表
小王又困了
28 0
卫卫周大胖
|
1月前
|
存储 C语言
【数据结构】顺序表的学习
【数据结构】顺序表的学习
卫卫周大胖
30 3
秋风起，再归来～
|
1月前
|
存储
数据结构之顺序表及其实现！
数据结构之顺序表及其实现！
秋风起，再归来～
48 1

热门文章

最新文章

  • 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
    【链式二叉树】数据结构链式二叉树的（万字详解）
    42
  • 5
    【堆】数据结构堆的实现（万字详解）
    52
  • 6
    【树和二叉树】数据结构二叉树和树的概念认识
    25
  • 7
    【双向链表】数据结构双向链表的实现
    21
  • 8
    数据结构——单链表的基本操作
    11
  • 9
    数据结构——排序算法之快速排序
    34
  • 10
    数据结构——二叉树的链式结构
    36

    • 相关课程

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

    • 相关电子书

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