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

【海贼王的数据航海】顺序表

2024-06-25 21
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
日志服务 SLS，月写入数据量 50GB 1个月
简介： 【海贼王的数据航海】顺序表

1 -> 线性表

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

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

2 -> 顺序表

2.1 -> 概念及结构

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

顺序表一般可以分为：

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

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

2.2 -> 接口声明

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

#pragma once
 
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
// 顺序表的动态存储
typedef int SLDateType;
 
typedef struct SeqList
{
  //  指向动态开辟的数组
  SLDateType* a;
  // 有效数据个数
  int size;
  // 容量空间大小
  int capacity;
}SL;
 
// 对数据的管理:增删查改 
 
// 顺序表初始化
void SLInit(SL* psl);
 
// 顺序表销毁
void SLDestroy(SL* psl);
 
// 顺序表检查,满则增容
void SLCheckCapacity(SL* psl);
 
// 顺序表打印
void SLPrint(SL* psl);
 
// 顺序表尾插
void SLPushBack(SL* psl, SLDateType x);
 
// 顺序表头插
void SLPushFront(SL* psl, SLDateType x);
 
// 顺序表尾删
void SLPopBack(SL* psl);
 
// 顺序表头删
void SLPopFront(SL* psl);
 
// 顺序表在pos位置插入x
void SLInsert(SL* psl, int pos, SLDateType x);
 
// 顺序表删除pos位置的值
void SLErase(SL* psl, int pos);
 
// 顺序表查找,找到返回下标,找不到返回-1
int SLFind(SL* psl, SLDateType x);
 
// 顺序表修改
void SLModify(SL* psl, int pos, SLDateType x);

2.3 -> 接口实现

2.3.1 -> 初始化

// 顺序表初始化
void SLInit(SL* psl)
{
  psl->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
  if (psl->a == NULL)
  {
    perror("malloc fail");
    return;
  }
 
  psl->capacity = 4;
  psl->size = 0;
}

2.3.2 -> 销毁

// 顺序表销毁
void SLDestroy(SL* psl)
{
  free(psl->a);
  psl->a = NULL;
  psl->capacity = 0;
  psl->size = 0;
}

2.3.3 -> 检查

// 顺序表检查,满则增容
void SLCheckCapacity(SL* psl)
{
  if (psl->size == psl->capacity)
  {
    SLDateType* tmp = (SLDateType*)realloc(psl->a, sizeof(SLDateType) * psl->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
 
    psl->a = tmp;
    psl->capacity *= 2;
  }
}

2.3.4 -> 打印

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

2.3.5 -> 尾插

// 顺序表尾插
void SLPushBack(SL* psl, SLDateType x)
{
  SLCheckCapacity(psl);
 
  psl->a[psl->size++] = x;
 
  //复用
  //SLInsert(psl, psl->size - 1, x);
}
// 尾插测试
void SLTest1()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushBack(&s, 5);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}

2.3.6 -> 头插

// 顺序表头插
void SLPushFront(SL* psl, SLDateType x)
{
  SLCheckCapacity(psl);
 
  int end = psl->size - 1;
  while (end >= 0)
  {
    psl->a[end + 1] = psl->a[end];
    --end;
  }
 
  psl->a[0] = x;
  psl->size++;
 
  //复用
  //SLInsert(psl, 0, x);
}
// 头插测试
void SLTest2()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushFront(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}

2.3.7 -> 尾删

// 顺序表尾删
void SLPopBack(SL* psl)
{
  // 暴力的检查
  assert(psl->size > 0);
 
  // 温柔的检查
  /*if (psl->size == 0)
    return;*/
 
  psl->size--;
 
  //复用
  //SLErase(psl, psl->size - 1);
}
// 尾删测试
void SLTest3()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushFront(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
 
  SLPrint(&s);
 
  SLPopBack(&s);
  SLPopBack(&s);
  SLPopBack(&s);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}

2.3.8 -> 头删

// 顺序表头删
void SLPopFront(SL* psl)
{
  assert(psl->size > 0);
 
  int start = 1;
  while (psl->a[start] < psl->size)
  {
    psl->a[start - 1] = psl->a[start];
    start++;
  }
 
  psl->size--;
 
  //复用
  //SLErase(psl, 0);
}


// 头删测试
void SLTest4()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushFront(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
 
  SLPrint(&s);
 
  SLPopFront(&s);
  SLPopFront(&s);
  SLPopFront(&s);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}

2.3.9 -> 在pos位置插入x

// 顺序表在pos位置插入x
// 头插、尾插可复用此
void SLInsert(SL* psl, int pos, SLDateType x)
{
  assert(0 <= pos && pos <= psl->size);
 
  SLCheckCapacity(psl);
 
  int end = psl->size - 1;
  while (end >= pos)
  {
    psl->a[end + 1] = psl->a[end];
    --end;
  }
 
  psl->a[pos] = x;
  psl->size++;
}


// 任意位置插入测试
void SLTest5()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushFront(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
 
  SLPrint(&s);
 
  SLInsert(&s, 1, 99);
  SLInsert(&s, 3, 22);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}

2.3.10 -> 删除pos位置的值

// 顺序表删除pos位置的值
// 头删、尾删可复用此
void SLErase(SL* psl, int pos)
{
  assert(0 <= pos && pos < psl->size);
  assert(psl->size > 0);
 
  int start = pos + 1;
  while (start < psl->size)
  {
    psl->a[start - 1] = psl->a[start];
    ++start;
  }
 
  psl->size--;
}
// 任意位置删除测试
void SLTest6()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushBack(&s, 5);
  SLPushBack(&s, 6);
 
  SLPrint(&s);
 
  SLErase(&s, 2);
  SLErase(&s, 4);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}

2.3.11 -> 查找

// 顺序表查找
int SLFind(SL* psl, SLDateType x)
{
  for (int i = 0; i < psl->size; i++)
  {
    if (psl->a[i] == x)
      return i;
  }
 
  return -1;
}
// 查找测试
void SLTest7()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushBack(&s, 5);
  SLPushBack(&s, 6);
 
  SLPrint(&s);
 
  int ans1 = SLFind(&s, 2);
  int ans2 = SLFind(&s, 6);
 
  printf("%d\n%d", ans1, ans2);
 
  SLDestroy(&s);
}

2.3.12 -> 修改

// 顺序表修改
void SLModify(SL* psl, int pos, SLDateType x)
{
  assert(0 <= pos && pos < psl->size);
 
  psl->a[pos] = x;
}


// 修改测试
void SLTest8()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushBack(&s, 5);
  SLPushBack(&s, 6);
 
  SLPrint(&s);
 
  SLModify(&s, 2, 99);
  SLModify(&s, 0, 11);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}

3 -> 完整代码

3.1 -> SeqList.h

#pragma once
 
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
// 顺序表的动态存储
typedef int SLDateType;
 
typedef struct SeqList
{
  //  指向动态开辟的数组
  SLDateType* a;
  // 有效数据个数
  int size;
  // 容量空间大小
  int capacity;
}SL;
 
// 对数据的管理:增删查改 
 
// 顺序表初始化
void SLInit(SL* psl);
 
// 顺序表销毁
void SLDestroy(SL* psl);
 
// 顺序表检查,满则增容
void SLCheckCapacity(SL* psl);
 
// 顺序表打印
void SLPrint(SL* psl);
 
// 顺序表尾插
void SLPushBack(SL* psl, SLDateType x);
 
// 顺序表头插
void SLPushFront(SL* psl, SLDateType x);
 
// 顺序表尾删
void SLPopBack(SL* psl);
 
// 顺序表头删
void SLPopFront(SL* psl);
 
// 顺序表在pos位置插入x
void SLInsert(SL* psl, int pos, SLDateType x);
 
// 顺序表删除pos位置的值
void SLErase(SL* psl, int pos);
 
// 顺序表查找,找到返回下标,找不到返回-1
int SLFind(SL* psl, SLDateType x);
 
// 顺序表修改
void SLModify(SL* psl, int pos, SLDateType x);

3.2 -> SeqList.c

#include "SeqList.h"
 
// 顺序表初始化
void SLInit(SL* psl)
{
  psl->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
  if (psl->a == NULL)
  {
    perror("malloc fail");
    return;
  }
 
  psl->capacity = 4;
  psl->size = 0;
}
 
// 顺序表销毁
void SLDestroy(SL* psl)
{
  free(psl->a);
  psl->a = NULL;
  psl->capacity = 0;
  psl->size = 0;
}
 
// 顺序表检查,满则增容
void SLCheckCapacity(SL* psl)
{
  if (psl->size == psl->capacity)
  {
    SLDateType* tmp = (SLDateType*)realloc(psl->a, sizeof(SLDateType) * psl->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
 
    psl->a = tmp;
    psl->capacity *= 2;
  }
}
 
// 顺序表打印
void SLPrint(SL* psl)
{
  for (int i = 0; i < psl->size; i++)
  {
    printf("%d ", psl->a[i]);
  }
 
  printf("\n");
}
 
// 顺序表尾插
void SLPushBack(SL* psl, SLDateType x)
{
  SLCheckCapacity(psl);
 
  psl->a[psl->size++] = x;
 
  //复用
  //SLInsert(psl, psl->size - 1, x);
}
 
// 顺序表头插
void SLPushFront(SL* psl, SLDateType x)
{
  SLCheckCapacity(psl);
 
  int end = psl->size - 1;
  while (end >= 0)
  {
    psl->a[end + 1] = psl->a[end];
    --end;
  }
 
  psl->a[0] = x;
  psl->size++;
 
  //复用
  //SLInsert(psl, 0, x);
}
 
// 顺序表尾删
void SLPopBack(SL* psl)
{
  // 暴力的检查
  assert(psl->size > 0);
 
  // 温柔的检查
  /*if (psl->size == 0)
    return;*/
 
  psl->size--;
 
  //复用
  //SLErase(psl, psl->size - 1);
}
 
// 顺序表头删
void SLPopFront(SL* psl)
{
  assert(psl->size > 0);
 
  int start = 1;
  while (psl->a[start] < psl->size)
  {
    psl->a[start - 1] = psl->a[start];
    start++;
  }
 
  psl->size--;
 
  //复用
  //SLErase(psl, 0);
}
 
// 顺序表在pos位置插入x
// 头插、尾插可复用此
void SLInsert(SL* psl, int pos, SLDateType x)
{
  assert(0 <= pos && pos <= psl->size);
 
  SLCheckCapacity(psl);
 
  int end = psl->size - 1;
  while (end >= pos)
  {
    psl->a[end + 1] = psl->a[end];
    --end;
  }
 
  psl->a[pos] = x;
  psl->size++;
}
 
// 顺序表删除pos位置的值
// 头删、尾删可复用此
void SLErase(SL* psl, int pos)
{
  assert(0 <= pos && pos < psl->size);
  assert(psl->size > 0);
 
  int start = pos + 1;
  while (start < psl->size)
  {
    psl->a[start - 1] = psl->a[start];
    ++start;
  }
 
  psl->size--;
}
 
// 顺序表查找
int SLFind(SL* psl, SLDateType x)
{
  for (int i = 0; i < psl->size; i++)
  {
    if (psl->a[i] == x)
      return i;
  }
 
  return -1;
}
 
// 顺序表修改
void SLModify(SL* psl, int pos, SLDateType x)
{
  assert(0 <= pos && pos < psl->size);
 
  psl->a[pos] = x;
}

3.3 -> Test.c

#include "SeqList.h"
 
// 尾插测试
void SLTest1()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushBack(&s, 5);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}
 
// 头插测试
void SLTest2()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushFront(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}
 
// 尾删测试
void SLTest3()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushFront(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
 
  SLPrint(&s);
 
  SLPopBack(&s);
  SLPopBack(&s);
  SLPopBack(&s);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}
 
// 头删测试
void SLTest4()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushFront(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
 
  SLPrint(&s);
 
  SLPopFront(&s);
  SLPopFront(&s);
  SLPopFront(&s);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}
 
// 任意位置插入测试
void SLTest5()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushFront(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
 
  SLPrint(&s);
 
  SLInsert(&s, 1, 99);
  SLInsert(&s, 3, 22);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}
 
// 任意位置删除测试
void SLTest6()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushBack(&s, 5);
  SLPushBack(&s, 6);
 
  SLPrint(&s);
 
  SLErase(&s, 2);
  SLErase(&s, 4);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}
 
// 查找测试
void SLTest7()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushBack(&s, 5);
  SLPushBack(&s, 6);
 
  SLPrint(&s);
 
  int ans1 = SLFind(&s, 2);
  int ans2 = SLFind(&s, 6);
 
  printf("%d\n%d", ans1, ans2);
 
  SLDestroy(&s);
}
 
// 修改测试
void SLTest8()
{
  SL s;
  SLInit(&s);
 
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushBack(&s, 5);
  SLPushBack(&s, 6);
 
  SLPrint(&s);
 
  SLModify(&s, 2, 99);
  SLModify(&s, 0, 11);
 
  SLPrint(&s);
 
  SLDestroy(&s);
}
 
int main()
{
 
  return 0;
}

感谢各位大佬支持！！！

互三啦！！！



文章标签：
日志服务
存储
相关实践学习
日志服务之使用Nginx模式采集日志
本文介绍如何通过日志服务控制台创建Nginx模式的Logtail配置快速采集Nginx日志并进行多维度分析。
枫叶丹4
目录
相关文章
枫叶丹4
|
3月前
【海贼王的数据航海】栈和队列
【海贼王的数据航海】栈和队列
枫叶丹4
23 0
枫叶丹4
|
3月前
|
存储
【海贼王的数据航海】链表—单链表
【海贼王的数据航海】链表—单链表
枫叶丹4
26 0
枫叶丹4
|
3月前
|
存储 缓存
【海贼王的数据航海】链表—双向链表
【海贼王的数据航海】链表—双向链表
枫叶丹4
19 0
快乐的流畅
|
4月前
|
存储 C++
【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）
【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）
快乐的流畅
43 2
周周的奇妙编程
|
对象存储
七夕快到了，来创造一副浪漫的鹊桥插画吧
本次通过加载和推理SD模型对象存储OSS Bucket，挂载到PAI-EAS服务，实现模型部署，加载和推理SD模型，制作属于自己的七夕画作。
周周的奇妙编程
111 2
许思王
|
算法
回溯算法——我欲修仙（功法篇）
回溯算法——我欲修仙（功法篇）
许思王
90 0
许思王
|
算法 搜索推荐 C语言
堆排序——我欲修仙（功法篇）
堆排序——我欲修仙（功法篇）
许思王
117 0
堆排序——我欲修仙（功法篇）
许思王
|
算法 搜索推荐
三大基础排序算法——我欲修仙（功法篇）
三大基础排序算法——我欲修仙（功法篇）
许思王
151 0
许思王
|
算法 C语言
二分查找——我欲修仙(功法篇)
二分查找——我欲修仙(功法篇)
许思王
81 0
LightOf
|
机器人
UPC—— 最勇敢的机器人（并查集+分组背包）
UPC—— 最勇敢的机器人（并查集+分组背包）
LightOf
74 0

热门文章

最新文章

  • 1
    python 中 print 函数用法大全
  • 2
    [Phoenix] 二、数据类型
  • 3
    IDEA 运行junit单元测试方法
  • 4
    Maven之阿里云镜像仓库配置--详解
  • 5
    交易系统架构
  • 6
    应用架构之道：分离业务逻辑和技术细节
  • 7
    产品更新｜宜搭AI 两大功能：智能应用、智能公式已上线
  • 8
    openresty capture
  • 9
    PLSQL的DBMS_GETLINE
  • 10
    Maestro的最近进展
  • 1
    谁动了我的选择器？深入理解CSS选择器优先级
    40
  • 2
    消费kafka不需要设置 压缩协议吗 假如生产者压缩协议是lz4
    27
  • 3
    module declares its path as: github.com/IBM/sarama but was required as: gith
    29
  • 4
    使用Python发送包含复杂JSON结构的POST请求
    28
  • 5
    你可能对position和z-index有一些误解
    34
  • 6
    mutex := rs.NewMutex(mutexname) // 对key进行 if err := mutex.Lock(); err != nil { pani
    11
  • 7
    Traceback(most recent call last):File "main.py", line 4l,in<module>alueError: sleep length must be n
    11
  • 8
    File "site-packages\pandas\core\indexing.py", line File "site-packages\pandas\core\indexing.py", l
    10
  • 9
    这个字段，我想看看报错吗
    8
  • 10
    手写一个简易bundler打包工具带你了解Webpack原理
    11

    • 相关课程

    更多
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 【新人赛】工业蒸汽量预测建模算法代码开源分享合集

    • 相关电子书

    更多
  • 《长安十二时辰》
  • 工业互联网为智能机床插上翅膀
  • 分身大师那些事儿

    • 相关实验场景

    更多
  • 在PAI ArtLab一键实现欧洲杯粉丝专属贴纸制作
  • 基于阿里云DeepGPU实例，用AI画唯美国风少女
    • 下一篇
    使用OSS上传下载文件