AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构-顺序表（2）

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

1. 线性表

线性表是n个具有相同特性的数据元素的有限序列，


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


2. 顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。


2.1 动态顺序表

我们一般使用的都是动态的顺序表。


3. 接口实现

前期工作

在VS上建三个工程文件，


test.c用来测试顺序表；


SeqList.c用来实现接口；


SeqList.h用来包头文件，和创建动态顺序表的基本结构；


头文件如下：


#pragma once
#include 
#include 
#include 
#define INIT_CAPACITY 4
//选择需要的类型
typedef int SLDatatype;
//动态的顺序表
typedef struct SeqList
{
  SLDatatype* a;
  int size;   //有效的数据个数
  int capacity; //顺序表的空间容量
}SL;
//顺序表的增删查改:
//初始化顺序表
void SeqInit(SL* s);
//销毁顺序表
void SeqDestory(SL* s);
//打印顺序表
void SeqPrint(SL* s);
//检查容量
void CheckCapacity(SL* s);
//尾插
void SeqPushBack(SL* s, SLDatatype x);
//尾删
void SeqPopBack(SL* s);
//头插
void SeqPushFront(SL* s, SLDatatype x);
//头删
void SeqPopFront(SL* s);
//插入
void SeqInsert(SL* s, int pos, SLDatatype x);
//删除
void SeqErase(SL* s, int pos);


3.1 初始化、销毁与检查容量

接口如下：


3.1.1 初始化

//初始化顺序表
void SeqInit(SL* ps)
{
  //结构体指针不能为空
  assert(ps);
  //开辟空间
  ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * INIT_CAPACITY);
  //检查
  if (ps->a == NULL)
  {
  perror("malloc fail");
  }
  ps->size = 0;
  ps->capacity = INIT_CAPACITY;
}


3.1.2 销毁

//销毁顺序表
void SeqDestory(SL* ps)
{
  //结构体指针不能为空
  assert(ps);
  //释放并置空
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->size = 0;
}

3.1.3 检查容量

//检查容量
void CheckCapacity(SL* ps)
{
  //结构体指针不能为空
  assert(ps);
  if (ps->size == ps->capacity)
  {
  //增容（两倍）
  SLDatatype* tmp = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * ps->capacity * 2);
  //检查是否增容成功
  if (tmp == NULL)
  {
    perror("realloc fail");
    return;
  }
  ps->a = tmp;
  ps->capacity *= 2;
  }
}


3.2 尾插

//尾插
void SeqPushBack(SL* ps, SLDatatype x)
{
  //代码复用
  SeqInsert(ps, ps->size, x);
  /*单独实现
  //结构体指针不能为空
  assert(ps);
  //检查容量
  CheckCapacity(ps);
  //尾插
  ps->a[ps->size++] = x;
  */
}


3.3 尾删

//尾删
void SeqPopBack(SL* ps)
{
  //代码复用
  SeqErase(ps, ps->size - 1);
  /*单独实现
  //结构体指针不能为空
  assert(ps);
  //检查顺序表是否为空
  assert(ps->size);
  //尾删
  ps->size--;
  */
}


3.4 头插

//头插
void SeqPushFront(SL* ps, SLDatatype x)
{
  //代码复用
  SeqInsert(ps, 0, 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++;
  */
}

3.5 头删

//头删
void SeqPopFront(SL* ps)
{
  //代码复用
  SeqErase(ps, 0);
  /*单独实现
  //结构体指针不能为空
  assert(ps);
  //当顺序表为零时就不能删了
  assert(ps->size);
  //将数据往前覆盖
  int begin = 1;
  while (begin < ps->size)
  {
  ps->a[begin - 1] = ps->a[begin];
  begin++;
  }
  ps->size--;
  */
}

/

3.6 插入

//插入
void SeqInsert(SL* ps, int pos, SLDatatype x)
{
  //结构体指针不能为空
  assert(ps);
  //pos需要在有数据的区间
  assert(pos >= 0 && pos <= ps->size);
  //检查容量
  CheckCapacity(ps);
  //往后挪动数据
  int end = ps->size - 1;
  while (end >= pos)
  {
  ps->a[end + 1] = ps->a[end];
  end--;
  }
  //插入数据
  ps->a[pos] = x;
  ps->size++;
}


3.7 删除

//删除
void SeqErase(SL* ps, int pos)
{
  //结构体指针不能为空
  assert(ps);
  //pos需要在有数据的区间
  assert(pos >= 0 && pos < ps->size);
  //挪动数据
  int begin = pos + 1;
  while (begin < ps->size)
  {
  ps->a[begin - 1] = ps->a[begin];
  begin++;
  }
  ps->size--;
}

我们发现，


其实顺序表核心的功能就是插入和删除，


只要我们完成这两个接口，


其他的接口的实现都是大同小异。


顺序表源码

SeqList.h
#pragma once
#include 
#include 
#include 
#define INIT_CAPACITY 4
//选择需要的类型
typedef int SLDatatype;
//动态的顺序表
typedef struct SeqList
{
  SLDatatype* a;
  int size;   //有效的数据个数
  int capacity; //顺序表的空间容量
}SL;
//顺序表的增删查改:
//初始化顺序表
void SeqInit(SL* s);
//销毁顺序表
void SeqDestory(SL* s);
//打印顺序表
void SeqPrint(SL* s);
//检查容量
void CheckCapacity(SL* s);
//尾插
void SeqPushBack(SL* s, SLDatatype x);
//尾删
void SeqPopBack(SL* s);
//头插
void SeqPushFront(SL* s, SLDatatype x);
//头删
void SeqPopFront(SL* s);
//插入
void SeqInsert(SL* s, int pos, SLDatatype x);
//删除
void SeqErase(SL* s, int pos);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
//初始化顺序表
void SeqInit(SL* ps)
{
  //结构体指针不能为空
  assert(ps);
  //开辟空间
  ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * INIT_CAPACITY);
  //检查
  if (ps->a == NULL)
  {
  perror("malloc fail");
  }
  ps->size = 0;
  ps->capacity = INIT_CAPACITY;
}
//销毁顺序表
void SeqDestory(SL* ps)
{
  //结构体指针不能为空
  assert(ps);
  //释放并置空
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->size = 0;
}
//打印
void SeqPrint(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)
  {
  //增容（两倍）
  SLDatatype* tmp = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * ps->capacity * 2);
  //检查是否增容成功
  if (tmp == NULL)
  {
    perror("realloc fail");
    return;
  }
  ps->a = tmp;
  ps->capacity *= 2;
  }
}
//尾插
void SeqPushBack(SL* ps, SLDatatype x)
{
  //代码复用
  SeqInsert(ps, ps->size, x);
  /*单独实现
  //结构体指针不能为空
  assert(ps);
  //检查容量
  CheckCapacity(ps);
  //尾插
  ps->a[ps->size++] = x;
  */
}
//尾删
void SeqPopBack(SL* ps)
{
  //代码复用
  SeqErase(ps, ps->size - 1);
  /*单独实现
  * 
  //结构体指针不能为空
  assert(ps);
  //检查顺序表是否为空
  assert(ps->size);
  //尾删
  ps->size--;
  */
}
//头插
void SeqPushFront(SL* ps, SLDatatype x)
{
  //代码复用
  SeqInsert(ps, 0, 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 SeqPopFront(SL* ps)
{
  //代码复用
  SeqErase(ps, 0);
  /*单独实现
  //结构体指针不能为空
  assert(ps);
  //当顺序表为零时就不能删了
  assert(ps->size);
  //将数据往前覆盖
  int begin = 1;
  while (begin < ps->size)
  {
  ps->a[begin - 1] = ps->a[begin];
  begin++;
  }
  ps->size--;
  */
}
//插入
void SeqInsert(SL* ps, int pos, SLDatatype x)
{
  //结构体指针不能为空
  assert(ps);
  //pos需要在有数据的区间
  assert(pos >= 0 && pos <= ps->size);
  //检查容量
  CheckCapacity(ps);
  //往后挪动数据
  int end = ps->size - 1;
  while (end >= pos)
  {
  ps->a[end + 1] = ps->a[end];
  end--;
  }
  //插入数据
  ps->a[pos] = x;
  ps->size++;
}
//删除
void SeqErase(SL* ps, int pos)
{
  //结构体指针不能为空
  assert(ps);
  //pos需要在有数据的区间
  assert(pos >= 0 && pos < ps->size);
  //挪动数据
  int begin = pos + 1;
  while (begin < ps->size)
  {
  ps->a[begin - 1] = ps->a[begin];
  begin++;
  }
  ps->size--;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
//测试接口
void SLTest()
{
  SL s;
  SeqInit(&s);
  SeqPushBack(&s, 1);
  SeqPushBack(&s, 2);
  SeqPushBack(&s, 3);
  SeqPushBack(&s, 4);
  SeqPushBack(&s, 5);
  SeqPushBack(&s, 6);
  SeqPrint(&s);
  SeqPopBack(&s);
  SeqPopBack(&s);
  SeqPrint(&s);
  SeqPushFront(&s, 10);
  SeqPushFront(&s, 50);
  SeqPrint(&s);
  SeqPopFront(&s);
  SeqPopFront(&s);
  SeqPopFront(&s);
  SeqPrint(&s);
  SeqDestory(&s);
}
int main()
{
  SLTest();
  return 0;
}


测试结果无误。


写在最后：

以上就是本篇文章的内容了，感谢你的阅读。


如果喜欢本文的话，欢迎点赞和评论，写下你的见解。


如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。


之后我还会输出更多高质量内容，欢迎收看。


文章标签：
C++
存储
关键词：
数据结构顺序表
戊子仲秋
目录
相关文章
是基德吖
|
3月前
|
存储 C语言
【数据结构】顺序表
数据结构中的动态顺序表
是基德吖
40 3
【数据结构】顺序表
秋刀鱼不做梦
|
4月前
|
存储
数据结构—顺序表（如果想知道顺序表的全部基础知识点，那么只看这一篇就足够了！）
数据结构—顺序表（如果想知道顺序表的全部基础知识点，那么只看这一篇就足够了！）
秋刀鱼不做梦
53 1
2的n次方_
|
23天前
|
存储 Java 程序员
【数据结构】初识集合&深入剖析顺序表（Arraylist）
Java集合框架主要由接口、实现类及迭代器组成，包括Collection和Map两大类。Collection涵盖List（有序、可重复）、Set（无序、不可重复），Map则由键值对构成。集合通过接口定义基本操作，具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复，Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现，各有适用场景。其中ArrayList实现了动态数组功能，可根据需求自动调整大小。
2的n次方_
31 11
平凡程序猿~
|
1天前
|
存储 C语言 索引
数据结构--顺序表
数据结构--顺序表
平凡程序猿~
9 0
dream_ready
|
2天前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表，包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类，包括插入、删除、获取数据元素、求数据个数等功能，并对顺序表进行了测试，最后还提及了Java中自带的顺序表实现类ArrayList。
dream_ready
5 0
是店小二呀
|
2天前
|
存储 缓存
【初阶数据结构】深入解析顺序表:探索底层逻辑
【初阶数据结构】深入解析顺序表:探索底层逻辑
是店小二呀
10 0
小徐在进步
|
1月前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表：顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表，使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作，并提供了具体代码示例。静态分配方式下顺序表的长度固定，而动态分配则可根据需求调整大小。此外，还总结了顺序表的优点，如随机访问效率高、存储密度大，以及缺点，如扩展不便和插入删除操作成本高等特点。
小徐在进步
99 5
小徐在进步
|
1月前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现，涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例，展示了如何高效地处理顺序表数据结构的各种问题。
小徐在进步
24 1
国中之林
|
2月前
|
存储 算法
【数据结构与算法】顺序表
【数据结构与算法】顺序表
国中之林
17 0
【数据结构与算法】顺序表
Hoshiᅟᅠ
|
2月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
Hoshiᅟᅠ
20 0