AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】实现顺序表的增删查改

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

一.顺序表介绍

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


(1)静态顺序表：使用定长数组存储，适用于确定知道需要存多少数据的场景


#define N 100
typedef int SeqListDataType;
typedef struct SeqList
{
SLDataType array[N]; // 定长数组
size_t size; // 有效数据的个数
}SeqList;


(2)动态顺序表：使用动态开辟的数组存储，可根据需要动态的分配空间大小。


typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t size ; // 有效数据个数
size_t capicity ; // 容量空间的大小
}SeqList;


二.动态顺序表增删查功能实现

现在Seqlist.h里对相关功能的函数，结构体进行声明，和类型的重定义


#pragma once
//C库函数的头文件声明
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//自定义顺序表元素的类型
typedef int SeqListDateType;
//顺序表的结构体
typedef struct SeqList
{
  SeqListDateType* data;
  size_t size;
  size_t capacity;
}SL;
//基本的增删查改接口
//顺序表的初始化
void SeqListInit(SL* ps);
//顺序表销毁
void SqeListDestory(SL* ps);
//顺序表打印
void SeqListPrint(SL* ps);
//顺序表在pos位置插入x
void SeqListInsert(SL* ps, size_t pos, SeqListDateType x);
//顺序表删除pos位置的值
void SeqListErase(SL* ps, size_t pos);
//顺序表尾插
void SeqListPushBack(SL* ps, SeqListDateType x);
//顺序表尾删
void SeqListPopBack(SL* ps);
//顺序表头插
void SeqListPushFront(SL* ps, SeqListDateType x);
//顺序表头删
void SeqListPopFront(SL* ps);
//顺序表查找(找到了返回下标，找不到返回-1)
int SeqListFind(SL* ps, SeqListDateType x);



（1）顺序表的初始化:对数组开辟4个容量的空间，有效数据为0，容量为4


void SeqListInit(SL* ps)
{
  assert(ps);
  ps->data = (SeqListDateType*)malloc(4 * sizeof(SeqListDateType));
  if (ps->data == NULL)
  {
  printf("申请内存失败\n");
  exit(-1);
  }
  ps->size = 0;
  ps->capacity = 4;
}


（2）对开辟后的空间销毁


void SqeListDestory(SL* ps)
{
    //断言，保证指针的有效性，防止野指针
  assert(ps);
  free(ps->data);
  ps->data = NULL;
}


（3）打印顺序表的内容


void SeqListPrint(SL* ps)
{
    //断言，保证指针的有效性，防止野指针
  assert(ps);
  for (size_t i = 0; i < ps->size; i++)
  {
  printf("%d ", ps->data[i]);
  }
}


（4）检查空间，如果满了，进行原来空间1倍的增容；没满就啥都不干（这个函数只在SeqList.c内部使用，使用static修饰，SeqList.h也不用声明这个函数）


static void CheckCapacity(SL* ps)
{
    //断言，保证指针的有效性，防止野指针
  assert(ps);
  if (ps->size == ps->capacity)
  {
  ps->capacity *= 2;
  ps->data = (SeqListDateType*)realloc(ps->data, ps->capacity * sizeof(SeqListDateType));
  if (ps->data == NULL)
  {
    printf("增容失败\n");
    exit(-1);
  }
  }


（5）任意位置（position）插入数据


void SeqListInsert(SL* ps, size_t pos, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针，和保证输入的位置正确
  assert(ps&& pos <= ps->size);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //把pos位置后面的数据往后移动
  int end = (int)ps->size - 1;
  while ((int)pos <= end)
  {
  ps->data[end + 1] = ps->data[end];
  end--;
  }
  //在pos上插入数据
  ps->data[pos] = x;
  //插入之后有效数据加一
  ps->size++;
}



（6）任意位置（position）删除数据


void SeqListErase(SL* ps, size_t pos)
{
  //断言，保证指针的有效性，防止野指针，和保证输入的位置正确
  assert(ps&&pos < ps->size);
  //把pos位置后面的数据往前移动
  size_t start = pos;
  while ((int)start <= (int)ps->size - 2)
  {
  ps->data[start] = ps->data[start + 1];
  start++;
  }
  //删除之后有效数据减一
  ps->size--;
}


（7）尾部插入一个数据


void SeqListPushBack(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //直接在最后一个位置插入数据
  ps->data[ps->size] = x;
  //插入之后有效数据加一
  ps->size++;
}


（8）尾部删除一个数据


void SeqListPopBack(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //直接有效数据减一，不会打印出来最后一个数据
  ps->size--;
}


（9）头部插入一个数据


void SeqListPushFront(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //把原来的所有数据往后移动，腾出第一个位置来
  size_t end = ps->size - 1;
  while ((int)end >= 0)
  {
  ps->data[end + 1] = ps->data[end];
  end--;
  }
  //头插
  ps->data[0] = x;
  //有效数据加一
  ps->size++;
}


（10）头部删除一个数据


void SeqListPopFront(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //把第二个数据开始所有的数据往前移动
  for (size_t i = 0; i < ps->size - 1; i++)
  {
  ps->data[i] = ps ->data[i + 1];
  }
  //有效数据减一
  ps->size--;
}


（11）查找数据（找到了返回下标，找不到返回-1）


int SeqListFind(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //根据下标遍历所有数据来查找
  for (size_t i = 0; i < ps->size; i++)
  {
  if (ps->data[i] == x)
  {
    //找到了就返回下标
    return i;
  }
  }
  //没找到就返回-1
  return -1;
}


三.完整代码

ps:完整代码包含在三个文件里

（1）SeqList.h


#pragma once
//C库函数的头文件声明
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//自定义顺序表元素的类型
typedef int SeqListDateType;
//顺序表的结构体
typedef struct SeqList
{
  SeqListDateType* data;
  size_t size;
  size_t capacity;
}SL;
//基本的增删查改接口
//顺序表的初始化
void SeqListInit(SL* ps);
//顺序表销毁
void SqeListDestory(SL* ps);
//顺序表打印
void SeqListPrint(SL* ps);
//顺序表在pos位置插入x
void SeqListInsert(SL* ps, size_t pos, SeqListDateType x);
//顺序表删除pos位置的值
void SeqListErase(SL* ps, size_t pos);
//顺序表尾插
void SeqListPushBack(SL* ps, SeqListDateType x);
//顺序表尾删
void SeqListPopBack(SL* ps);
//顺序表头插
void SeqListPushFront(SL* ps, SeqListDateType x);
//顺序表头删
void SeqListPopFront(SL* ps);
//顺序表查找(找到了返回下标，找不到返回-1)
int SeqListFind(SL* ps, SeqListDateType x);


（2）SeqList.c


#include"SeqList.h"
void SeqListInit(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  ps->data = (SeqListDateType*)malloc(4 * sizeof(SeqListDateType));
  if (ps->data == NULL)
  {
  printf("申请内存失败\n");
  exit(-1);
  }
  ps->size = 0;
  ps->capacity = 4;
}
void SqeListDestory(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  free(ps->data);
  ps->data = NULL;
}
void SeqListPrint(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  for (size_t i = 0; i < ps->size; i++)
  {
  printf("%d ", ps->data[i]);
  }
}
//检查空间，如果满了，进行增容
static void CheckCapacity(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  if (ps->size == ps->capacity)
  {
  ps->capacity *= 2;
  ps->data = (SeqListDateType*)realloc(ps->data, ps->capacity * sizeof(SeqListDateType));
  if (ps->data == NULL)
  {
    printf("增容失败\n");
    exit(-1);
  }
  }
}
void SeqListInsert(SL* ps, size_t pos, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针，和保证输入的位置正确
  assert(ps&& pos <= ps->size);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //把pos位置后面的数据往后移动
  int end = (int)ps->size - 1;
  while ((int)pos <= end)
  {
  ps->data[end + 1] = ps->data[end];
  end--;
  }
  //在pos上插入数据
  ps->data[pos] = x;
  //插入之后有效数据加一
  ps->size++;
}
void SeqListErase(SL* ps, size_t pos)
{
  //断言，保证指针的有效性，防止野指针，和保证输入的位置正确
  assert(ps&&pos < ps->size);
  //把pos位置后面的数据往前移动
  size_t start = pos;
  while ((int)start <= (int)ps->size - 2)
  {
  ps->data[start] = ps->data[start + 1];
  start++;
  }
  //删除之后有效数据减一
  ps->size--;
}
void SeqListPushBack(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //直接在最后一个位置插入数据
  ps->data[ps->size] = x;
  //插入之后有效数据加一
  ps->size++;
}
void SeqListPopBack(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //直接有效数据减一，不会打印出来最后一个数据
  ps->size--;
}
void SeqListPushFront(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //把原来的所有数据往后移动，腾出第一个位置来
  size_t end = ps->size - 1;
  while ((int)end >= 0)
  {
  ps->data[end + 1] = ps->data[end];
  end--;
  }
  //头插
  ps->data[0] = x;
  //有效数据加一
  ps->size++;
}
void SeqListPopFront(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //把第二个数据开始所有的数据往前移动
  for (size_t i = 0; i < ps->size - 1; i++)
  {
  ps->data[i] = ps ->data[i + 1];
  }
  //有效数据减一
  ps->size--;
}
int SeqListFind(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //根据下标遍历所有数据来查找
  for (size_t i = 0; i < ps->size; i++)
  {
  if (ps->data[i] == x)
  {
    //找到了就返回下标
    return i;
  }
  }
  //没找到就返回-1
  return -1;
}


（3）test.c(对顺序表进行测试)


#include"SeqList.h"
int main()
{
  //定义一个顺序表变量s
  SL s = { 0 };
  //顺序表接口功能的测试
  SeqListInit(&s);
  SeqListInsert(&s,0,1);
  SeqListInsert(&s, 1, 2);
  SeqListInsert(&s, 2, 3);
  SeqListErase(&s, 1);
  SeqListPrint(&s);
  printf("\n");
  return 0;
}


四.动态顺序表总结

1.可动态增长的数组

2.数据在数组中存储时必须是连续的


缺点：

1.中间或头部的插入删除很慢，需要挪动数据。时间复杂度为O（N）

2.空间不够时，增容会有一定的时间消耗和空间浪费


优点：

1.可以随机访问数据

2.cpu在缓存中拿数据时命中率高


文章标签：
缓存
存储
关键词：
数据结构顺序表
数据结构增删查改
数据结构顺序表增删查改
游客6nmtzqmqofvbk
目录
相关文章
是基德吖
|
3月前
|
存储 C语言
【数据结构】顺序表
数据结构中的动态顺序表
是基德吖
39 3
【数据结构】顺序表
2的n次方_
|
16天前
|
存储 Java 程序员
【数据结构】初识集合&深入剖析顺序表（Arraylist）
Java集合框架主要由接口、实现类及迭代器组成，包括Collection和Map两大类。Collection涵盖List（有序、可重复）、Set（无序、不可重复），Map则由键值对构成。集合通过接口定义基本操作，具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复，Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现，各有适用场景。其中ArrayList实现了动态数组功能，可根据需求自动调整大小。
2的n次方_
28 11
小徐在进步
|
24天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表：顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表，使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作，并提供了具体代码示例。静态分配方式下顺序表的长度固定，而动态分配则可根据需求调整大小。此外，还总结了顺序表的优点，如随机访问效率高、存储密度大，以及缺点，如扩展不便和插入删除操作成本高等特点。
小徐在进步
68 5
小徐在进步
|
24天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现，涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例，展示了如何高效地处理顺序表数据结构的各种问题。
小徐在进步
20 1
国中之林
|
2月前
|
存储 算法
【数据结构与算法】顺序表
【数据结构与算法】顺序表
国中之林
17 0
【数据结构与算法】顺序表
aliyun6365824167
|
2月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
19 0
aliyun6365824167
|
2月前
|
存储 测试技术
【初阶数据结构篇】顺序表的实现（赋源码）
线性表（linearlist）是n个具有相同特性的数据元素的有限序列。
aliyun6365824167
21 0
睡觉待开机
|
2月前
|
存储 编译器
【数据结构】顺序表(长期维护)
【数据结构】顺序表(长期维护)
睡觉待开机
18 0
大柏怎么被偷了
|
2月前
|
存储 缓存
【数据结构】——顺序表与链表
【数据结构】——顺序表与链表
大柏怎么被偷了
17 0
写代码的大学生
|
4月前
|
存储 C语言
顺序表（数据结构）
顺序表（数据结构）
写代码的大学生
39 1