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

顺序表——“数据结构与算法”

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

各位CSDN的uu们你们好呀，今天小雅兰的内容是数据结构与算法里面的顺序表啦，在我看来，数据结构总体上是一个抽象的东西，关键还是要多写代码，下面，就让我们进入顺序表的世界吧


线性表


顺序表


线性表


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

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

2d605a9168ce40949ed7c88b999924be.png 顺序表


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


顺序表就是数组，但是在数组的基础上，它还要求数据是从头开始连续存储的，不能跳跃间隔


顺序表一般可以分为：


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

#define _CRT_SECURE_NO_WARNINGS 1
#define N 7
#include"SeqList.h"
typedef int SLDateType;
typedef struct SeqList
{
  SLDateType arr[N];//定长数组
  size_t size;//表示数组中存储了多少数据
}SL;

e65c3291fd6c45a19ef60880cf973e47.png

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

#define _CRT_SECURE_NO_WARNINGS 1
#define N 7
#include"SeqList.h"
typedef int SLDateType;
typedef struct SeqList
{
  SLDateType* arr;//指向动态开辟的数组
  size_t size;//表示数组中存储了多少数据
  size_t capicity;//数组实际能存储数据的空间容量是多大
}SL;

b6df47eff9474289860198bd2c117ca6.png

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


在这里，所有函数命名风格都是跟着STL走的，方便小雅兰日后的学习！！！


顺序表的初始化：

void SeqListInit(SL* ps)//顺序表的初始化
{
  ps->arr = NULL;
  ps->size = ps->capacity = 0;
}

注意：在这里，不可以使用传值调用的方式，只能使用传址调用的方式

void SeqListInit(SL ps)//顺序表的初始化
{
  ps.arr = NULL;
  ps.size = ps.capacity = 0;
}

万万不能使用这样的方式初始化，因为：在函数传参的时候，形参是实参的一份临时拷贝，对形参的修改并不会影响实参

顺序表的打印：

void SeqListPrint(SL* ps)//顺序表的打印
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->arr[i]);
  }
  printf("\n");
}

扩容：

void SeqListCheckCapacity(SL* ps)//检查空间，如果满了，进行扩容
{
  //如果没有空间或者空间不足，那么我们就扩容
  if (ps->size == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SLDateType* tmp = (SLDateType*)realloc(ps->arr, newcapacity * sizeof(SLDateType));
    if (tmp == NULL)
    {
      printf("realloc fail!\n");
      exit(-1);
    }
    ps->arr = tmp;
    ps->capacity = newcapacity;
  }
}

顺序表销毁：

void SeqListDestroy(SL* ps)//顺序表销毁
{
  free(ps->arr);
  ps->arr = NULL;
  ps->capacity = ps->size = 0;
}

尾插：

void SeqListPushBack(SL* ps, SLDateType x)//尾插
{
  SeqListCheckCapacity(ps);
  ps->arr[ps->size] = x;
  ps->size++;
}

尾删：

void SeqListPopBack(SL* ps)//尾删
{
  assert(ps->size > 0);
  ps->size--;
}

头插：

void SeqListPushFront(SL* ps, SLDateType x)//头插
{
  SeqListCheckCapacity(ps);
  //挪动数据
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->arr[end + 1] = ps->arr[end];
    end--;
  }
  ps->arr[0] = x;
  ps->size++;
}

efc186b6f851460cbd26a105b72c341a.png

b5405af5a9c84dd480b74f03bbc7ff8d.png

头删：

void SeqListPopFront(SL* ps)//头删
{
  assert(ps->size > 0);
  //挪动数据
  int begin = 0;
  while (begin < ps->size-1)
  {
    ps->arr[begin] = ps->arr[begin+1];
    ++begin;
  }
  ps->size--;
}

另一种写法：

void SeqListPopFront(SL* ps)//头删
{
  assert(ps->size > 0);
  //挪动数据
  int begin = 1;
  while (begin < ps->size)
  {
    ps->arr[begin - 1] = ps->arr[begin];
    ++begin;
  }
  ps->size--;
}

顺序表查找：

//顺序表查找
//找到了返回x位置的下标，没有找到返回-1
int SeqListFind(SL* ps, SLDateType x)
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->arr[i] == x)
    {
      return i;
    }
  }
  return -1;
}

指定pos下标位置插入：

// 顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x)
{
  温柔的写法
  //if (pos > ps->size || pos < 0)
  //{
  //  printf("pos invalid!\n");
  //}
  //粗暴的写法
  assert(pos <= ps->size || pos >= 0);
  SeqListCheckCapacity(ps);
  //挪动数据
  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->arr[end + 1] = ps->arr[end];
    end--;
  }
  ps->arr[pos] = x;
  ps->size++;
}

然后，写出了这个函数的功能之后，我们发现：可以对之前写的头插和尾插搞一些事情，下面，我们开始搞事情！！！

头插和尾插：

void SeqListPushBack(SL* ps, SLDateType x)//尾插
{
  SeqListInsert(ps, ps->size, x);
}
void SeqListPushFront(SL* ps, SLDateType x)//头插
{
  SeqListInsert(ps, 0, x);
}

删除pos位置的数据：

//顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos)
{
  assert(pos < ps->size || pos >= 0);
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->arr[begin - 1] = ps->arr[begin];
    ++begin;
  }
  ps->size--;
}
void SeqListErase(SL* ps, size_t pos)
{
  assert(pos < ps->size || pos >= 0);
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->arr[begin - 1] = ps->arr[begin];
    ++begin;
  }
  ps->size--;
}

写出这个函数的功能之后，我们又可以搞事情啦！！！

头删和尾删：

void SeqListPopBack(SL* ps)//尾删
{
  SeqListErase(ps, 0);
}
void SeqListPopFront(SL* ps)//头删
{
  SeqListErase(ps, ps->size - 1);
}

菜单：

void menu()
{
  printf("#############################################\n");
  printf("\n");
  printf("###################1.头插#####################\n");
  printf("\n");
  printf("###################2.头删#####################\n");
  printf("\n");
  printf("###################3.尾插######################\n");
  printf("\n");
  printf("###################4.尾删######################\n");
  printf("\n");
  printf("###################5.打印#####################\n");
  printf("\n");
  printf("###################0.exit#####################\n");
  printf("\n");
  printf("##############################################\n");
}

其实，最好不要一上来就写菜单，先写单元测试，菜单不方便调试

测试菜单函数：

void MenuTest()
{
  SL s1;
  SeqListInit(&s1);
  int input = 0;
  int x;
  while (input != -1)
  {
    menu();
    scanf("%d", &input);
    switch (input)
    {
    case 1:
      printf("请输入你要头插的数据，以-1结束：");
      while (x != -1)
      {
        SeqListPushFront(&s1, x);
        scanf("%d", &x);
      }
      break;
    case 2:
      SeqListPopFront(&s1);
      break;
    case 3:
      printf("请输入你要尾插的数据，以-1结束：");
      while (x != -1)
      {
        SeqListPushBack(&s1, x);
        scanf("%d", &x);
      }
      break;
    case 4:
      SeqListPopBack(&s1);
      break;
    case 5:
      SeqListPrint(&s1);
      break;
    case 0:
      printf("退出程序\n");
      break;
    default:
      printf("输入错误，请重新输入\n");
    }
  }
}

源代码如下：

SeqList.h的内容：

#pragma once
#include<stdio.h>
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<assert.h>
#define N 7
typedef int SLDateType;
//顺序表的动态存储
typedef struct SeqList
{
  SLDateType* arr;//指向动态开辟的数组
  size_t size;//表示数组中存储了多少数据
  size_t capacity;//数组实际能存储数据的空间容量是多大
}SL;
//基本增删查改接口
void SeqListInit(SL* ps);//顺序表的初始化
void SeqListPrint(SL* ps);//顺序表的打印
void SeqListCheckCapacity(SL* ps);//检查空间，如果满了，进行扩容
void SeqListDestroy(SL* ps);//顺序表销毁
void SeqListPushBack(SL* ps, SLDateType x);//尾插
void SeqListPopBack(SL* ps);//尾删
void SeqListPushFront(SL* ps, SLDateType x);//头插
void SeqListPopFront(SL* ps);//头删
//顺序表查找
//找到了返回x位置的下标，没有找到返回-1
int SeqListFind(SL* ps, SLDateType x);
//顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x);
//顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos);

SeqList.c的内容：

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListInit(SL* ps)//顺序表的初始化
{
  ps->arr = NULL;
  ps->size = ps->capacity = 0;
}
void SeqListPrint(SL* ps)//顺序表的打印
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->arr[i]);
  }
  printf("\n");
}
void SeqListCheckCapacity(SL* ps)//检查空间，如果满了，进行扩容
{
  //如果没有空间或者空间不足，那么我们就扩容
  if (ps->size == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SLDateType* tmp = (SLDateType*)realloc(ps->arr, newcapacity * sizeof(SLDateType));
    if (tmp == NULL)
    {
      printf("realloc fail!\n");
      exit(-1);
    }
    ps->arr = tmp;
    ps->capacity = newcapacity;
  }
}
void SeqListDestroy(SL* ps)//顺序表销毁
{
  free(ps->arr);
  ps->arr = NULL;
  ps->capacity = ps->size = 0;
}
void SeqListPushBack(SL* ps, SLDateType x)//尾插
{
  SeqListCheckCapacity(ps);
  ps->arr[ps->size] = x;
  ps->size++;
}
void SeqListPopBack(SL* ps)//尾删
{
  assert(ps->size > 0);
  ps->size--;
}
void SeqListPushFront(SL* ps, SLDateType x)//头插
{
  SeqListCheckCapacity(ps);
  //挪动数据
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->arr[end + 1] = ps->arr[end];
    end--;
  }
  ps->arr[0] = x;
  ps->size++;
}
void SeqListPopFront(SL* ps)//头删
{
  assert(ps->size > 0);
  //挪动数据
  int begin = 1;
  while (begin < ps->size)
  {
    ps->arr[begin - 1] = ps->arr[begin];
    ++begin;
  }
  ps->size--;
}
//顺序表查找
//找到了返回x位置的下标，没有找到返回-1
int SeqListFind(SL* ps, SLDateType x)
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->arr[i] == x)
    {
      return i;
    }
  }
  return -1;
}
// 顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x)
{
  温柔的写法
  //if (pos > ps->size || pos < 0)
  //{
  //  printf("pos invalid!\n");
  //}
  //粗暴的写法
  assert(pos <= ps->size || pos >= 0);
  SeqListCheckCapacity(ps);
  //挪动数据
  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->arr[end + 1] = ps->arr[end];
    end--;
  }
  ps->arr[pos] = x;
  ps->size++;
}
//顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos)
{
  assert(pos < ps->size || pos >= 0);
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->arr[begin - 1] = ps->arr[begin];
    ++begin;
  }
  ps->size--;
}

好啦，小雅兰今天的内容就到这里啦，数据结构的的确确是一个麻烦的东西，还要加油呀！！！176a57e48a65486d8904289f5b9ff3ab.jpg


文章标签：
C++
测试技术
算法
存储
关键词：
顺序表数据结构
认真学习的小雅兰.
目录
相关文章
禁默
|
4月前
|
存储 编译器 C语言
数据结构-顺序表详解（看这篇就足够了，哈哈哈）
数据结构-顺序表详解（看这篇就足够了，哈哈哈）
禁默
83 2
RossyYan
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算（头歌实践教学平台习题）【合集】
本文档介绍了线性表的基本运算任务，涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法，并提供了测试说明和通关代码。 主要内容包括： - **任务描述**：实现顺序表的基本运算。 - **相关知识**：介绍线性表的基本概念及操作，如初始化、销毁、判定是否为空表等。 - **具体操作**：详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法，并附有代码示例。 - **测试说明**：提供测试输入和预期输出，确保代码正确性。 - **通关代码**：给出完整的C++代码实现，帮助完成任务。 文档
RossyYan
41 5
三三是该溜子
|
2月前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
55 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
肾透侧视攻城狮
|
3月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找等具体详解步骤以及举例说明
肾透侧视攻城狮
45 3
ephemerals__
|
3月前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
110 3
肾透侧视攻城狮
|
3月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找习题精讲等具体详解步骤以及举例说明
肾透侧视攻城狮
37 1
小强在此
|
4月前
|
存储 Java
数据结构第二篇【关于java线性表（顺序表）的基本操作】
数据结构第二篇【关于java线性表（顺序表）的基本操作】
小强在此
66 6
GuGuStudy
|
4月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
GuGuStudy
36 3
GuGuStudy
|
4月前
|
存储 C语言
探索C语言数据结构：利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录，包括初始化、添加、删除、查找和保存联系人信息的操作，以及自定义结构体用于存储联系人详细信息。
GuGuStudy
56 2
椰椰椰耶
|
4月前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
椰椰椰耶
40 1

热门文章

最新文章

  • 1
    C 408—《数据结构》易错考点200题（含解析）
  • 2
    C 408—《数据结构》图、查找、排序专题考点（含解析）
  • 3
    数据结构（C语言）之对归并排序的介绍与理解
  • 4
    图解前向、反向传播算法，一看就懂！
  • 5
    利用SVM(支持向量机)分类算法对鸢尾花数据集进行分类
  • 6
    通过算法备案之后就万事大吉了么？
  • 7
    算法备案全流程攻略：保姆级教程
  • 8
    C 408—《数据结构》算法题基础篇—链表（下）
  • 9
    使用贪心算法解决最小生成树问题
  • 10
    C 408—《数据结构》算法题基础篇—链表（上）
  • 1
    C语言数据结构算法，常用10种排序实战
    91
  • 2
    用伪代码表示算法
    138
  • 3
    AES算法逆向实战--某思路
    166
  • 4
    【优选算法】——滑动窗口——1004. 最大连续1的个数 III
    62
  • 5
    【优选算法】——滑动窗口——3. 无重复字符的最长子串
    60
  • 6
    [优选算法]------滑动窗⼝——209. 长度最小的子数组
    64
  • 7
    【优选算法】——双指针——18. 四数之和
    58
  • 8
    【优选算法】——双指针——15. 三数之和
    52
  • 9
    【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品
    75
  • 10
    【优选算法】——Leetcode——611. 有效三角形的个数
    66

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    PAI Model Gallery 支持云上一键部署 DeepSeek-V3、DeepSeek-R1 系列模型