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

【数据结构】顺序表

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

只有毅力才会使我们成功，而毅力的来源又在于毫不动摇，坚决采取为达到成功所需要的手段。                                                                                                       ——车尔尼雪夫斯基

18f1d19c5bfd74345ed49b9fe151eb85_e63838ad4434432d8fb594ab04060122.jpeg

目录


前言：


参数部分：


函数功能：


初始化Seqlist:


销毁Seqlist：


打印Seqlist：


扩容Seqlist：


尾插：


尾删：


头插：


头删：


在任意位置上插入：


删除任意位置：


查找任意位置：


完整代码：


Seqlist.h:


Seqlist.c:


Text.c:


前言：

顺序表：

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

顺序表一般可以分为：

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

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

注：本章讲解动态顺序表

参数部分：

首先是连续存放的数据，我们会想到数组，但是我们的个数不能改变，所以我们需要一个指针a指向malloc开辟一段连续的空间。

然后当我们需要改变这个空间的大小，我们还需要一个变量来表示已有空间容量的大小capacity。

我们如何判断什么时候需要扩容呢？需要一个计算多少个有效数据的个数变量size来判断等于已有空间的大小来决定是否扩容。  

定义结构体 ：

typedef int SLDataType;
typedef struct SeqList
{
  SLDataType* a;   //动态数组
  int size;       // 记录存储多少个有效数据
  int capacity;   // 空间容量大小 
}SL;

在这里我分为了三个部分来实现：

  • SeqList.h文件中进行函数声明。
  • SeqList.c函数进行各个函数的实现。
  • Test.c函数进行函数的测试。

函数功能：

初始化Seqlist:

//初始化
void SLInit(SL* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = ps->size = 0;
}

销毁Seqlist：

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

打印Seqlist：

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

扩容Seqlist：

SLCheckCapacity(SL* ps)
{
  //扩容
  assert(ps);
  if (ps->size == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
    if (tmp == NULL)
    {
      perror("realloc fail :");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
}

尾插：

//尾插
void SLPushBack(SL* ps,SLDataType x)
{
//扩容
  SLCheckCapacity(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, ps->size - 1);
}

头插：

//头插
void SLPushFront(SL* ps, SLDataType x)
{
  SLCheckCapacity(ps);
  //挪动数据
  int end = ps->size - 1;
  while (end>=0)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[0] = x;
  ps->size++;
  //SLInsert(ps, 0, x);
}

头删：

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

在任意位置上插入：

//从中间位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
  assert(ps);
  assert(pos >= 0);
  assert(pos <= ps->size);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (pos <= end)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;
}

删除任意位置：

// 删除pos位置数据
void SLErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0);
  assert(pos < ps->size);
  int begin = pos;
  int end = ps->size - 1;
  while (begin <= end)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}

查找任意位置：

// begin查找x的起始位置
int SLFind(SL* ps, SLDataType x, int begin)
{
  assert(ps);
  for (int i=0 ; i < ps->size; i++)
  {
    if (x == ps->a[i])
    {
      printf("%d\n", i);
      return i;
    }
  }
  return -1;
}

完整代码：

Seqlist.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
  SLDataType* a;
  int size;       // 记录存储多少个有效数据
  int capacity;   // 空间容量大小 
}SL;
//初始化
void SLInit(SL* ps);
//尾插尾删
void SLPushBack(SL* ps,SLDataType x);
void SLPopBack(SL* ps);
//销毁
void SLDestory(SL* ps);
//初始化
void SLPrint(SL* ps);
//头插头删
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
// 中间插入删除
// 在pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
// 删除pos位置数据
void SLErase(SL* ps, int pos);
//int SLFind(SL* ps, SLDataType x);
// begin查找x的起始位置
int SLFind(SL* ps, SLDataType x, int begin);

Seqlist.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"
SLCheckCapacity(SL* ps)
{
  //扩容
  assert(ps);
  if (ps->size == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
    if (tmp == NULL)
    {
      perror("realloc fail :");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
}
//尾插
void SLPushBack(SL* ps,SLDataType x)
{/*
  SLCheckCapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;*/
  SLInsert(ps, ps->size,x);
}
//打印
void SLPrint(SL* ps)
{
  assert(ps);
  for (int i = 0; i < ps->size; ++i)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
//初始化
void SLInit(SL* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = ps->size = 0;
}
//销毁
void SLDestory(SL* ps)
{
  assert(ps);
  if (ps->a)
  {
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->size = 0;
  }
}
//尾删
void SLPopBack(SL* ps)
{
  /*assert(ps);
  assert(ps->size > 0);
  ps->size--;*/
  SLErase(ps, ps->size - 1);
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
  //SLCheckCapacity(ps);
  挪动数据
  //int end = ps->size - 1;
  //while (end>=0)
  //{
  //  ps->a[end + 1] = ps->a[end];
  //  end--;
  //}
  //ps->a[0] = x;
  //ps->size++;
  SLInsert(ps, 0, x);
}
void SLPopFront(SL* ps)
{
  //assert(ps);
  //assert(ps->size > 0);
  //int begin = 1;
  //while (begin<ps->size)
  //{
  //  ps->a[begin - 1] = ps->a[begin];
  //  begin++;
  //}
  //ps->size--;
  SLErase(ps, 0);
}
//从中间位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
  assert(ps);
  assert(pos >= 0);
  assert(pos <= ps->size);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (pos <= end)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;
}
// 删除pos位置数据
void SLErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0);
  assert(pos < ps->size);
  int begin = pos;
  int end = ps->size - 1;
  while (begin <= end)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}
// begin查找x的起始位置
int SLFind(SL* ps, SLDataType x, int begin)
{
  assert(ps);
  for (int i=0 ; i < ps->size; i++)
  {
    if (x == ps->a[i])
    {
      printf("%d\n", i);
      return i;
    }
  }
  return -1;
}

Text.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"
TextSeqList1()
{
  SL sl;
  SLInit(&sl);
  SLPushBack(&sl, 1);
  SLPushBack(&sl, 2);
  SLPushBack(&sl, 3);
  SLPushBack(&sl, 4);
  SLPrint(&sl);
  SLDestory(&sl);
}
TextSeqList2()
{
  SL sl;
  SLInit(&sl);
  SLPushFront(&sl, 1);
  SLPushFront(&sl, 2);
  SLPushFront(&sl, 3);
  SLPushFront(&sl, 4);
  SLPushFront(&sl, 5);
  SLPushFront(&sl, 6);
  SLPushFront(&sl, 7);
  SLPrint(&sl);
  SLPopFront(&sl);
  SLPopFront(&sl);
  SLPopFront(&sl);
  SLPopFront(&sl);
  SLPrint(&sl);
  SLDestory(&sl);
}
TextSeqList3()
{
  SL sl;
  SLInit(&sl);
  SLPushFront(&sl, 1);
  SLPushFront(&sl, 2);
  SLPushFront(&sl, 3);
  SLPushFront(&sl, 4);
  SLPushFront(&sl, 5);
  SLPrint(&sl);
  SLInsert(&sl, 3, 100);
  SLPrint(&sl);
   SLFind(&sl, 100, 0);
  /*if (pos != -1)
  {
    SLErase(&sl, pos);
  }*/
   SLErase(&sl,2);
   SLPrint(&sl);
  SLDestory(&sl);
}
int main()
{
  TextSeqList3();
  return 0;
}








文章标签：
存储
关键词：
数据结构顺序表
日出等日落
目录
相关文章
悲伤小伞
|
29天前
|
存储
数据结构链表详解(不仅顺序表可以，我链表也可以)
数据结构链表详解(不仅顺序表可以，我链表也可以)
悲伤小伞
20 0
sky_qiyi
|
8天前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表（双向带头循环链表）的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表（双向带头循环链表）的优缺点、CPU高速缓存命中率
sky_qiyi
11 0
TU^
|
22天前
|
存储 索引
数据结构~~顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存 储。在数组上完成数据的增删查改。
TU^
22 0
小李很执着
|
23天前
|
存储 缓存
[数据结构]——顺序表和链表
[数据结构]——顺序表和链表（下）：https://developer.aliyun.com/article/1515507
小李很执着
31 0
就学呗
|
3天前
数据结构初阶 顺序表的补充
数据结构初阶 顺序表的补充
就学呗
5 0
就学呗
|
3天前
|
存储
数据结构初阶 顺序表的讲解
数据结构初阶 顺序表的讲解
就学呗
7 0
sky_qiyi
|
8天前
|
算法
数据结构和算法学习记录——复习静态顺序表的两个接口函数（在指定位置插入数据，在指定位置删除数据）
数据结构和算法学习记录——复习静态顺序表的两个接口函数（在指定位置插入数据，在指定位置删除数据）
sky_qiyi
6 0
sky_qiyi
|
8天前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数（顺序表缺陷、单链表优点、链表打印）
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数（顺序表缺陷、单链表优点、链表打印）
sky_qiyi
8 0
sky_qiyi
|
8天前
|
存储 算法
数据结构和算法学习记录——线性表之顺序表(顺序表概念、结构、顺序表接口函数-头插头删、尾插尾删)
数据结构和算法学习记录——线性表之顺序表(顺序表概念、结构、顺序表接口函数-头插头删、尾插尾删)
sky_qiyi
8 0
7fa6b5ui5pmtk
|
9天前
|
存储 C语言
数据结构——顺序表（C语言版）
数据结构——顺序表（C语言版）
7fa6b5ui5pmtk
10 5

热门文章

最新文章

  • 1
    java进阶-常用数据结构以及算法思想
  • 2
    数据结构概述
  • 3
    数据结构（三）：二叉树遍历
  • 4
    基于OHCI的USB主机 —— UFI数据结构3
  • 5
    【Java数据结构的实现】之系列二栈的介绍
  • 6
    《数据结构与抽象：Java语言描述（原书第4版）》一2.1.6　实现更多的方法
  • 7
    1531 山峰 【栈的应用】
  • 8
    Struts中自定义标签中获取值栈valuestack
  • 9
    数据结构之栈与队列
  • 10
    OSPF协议栈的perl 脚本实现！
  • 1
    Golang 数据结构：图
    48
  • 2
    C/C++ 数据结构设计与应用（三）：运算符重载的策略与实践 (Operator Overloading Strategies and Practices)
    26
  • 3
    C/C++ 数据结构设计与应用（二）：自定义数据结构的设计 (Design of Custom Data Structures)
    67
  • 4
    C/C++ 数据结构设计与应用（一）： 数据结构的选择与应用 (Data Structure Selection and Application)
    45
  • 5
    【手撕数据结构】二分查找(好多细节)
    19
  • 6
    【排序算法】数据结构排序详解
    58
  • 7
    【链式二叉树】数据结构链式二叉树的（万字详解）
    50
  • 8
    【堆】数据结构堆的实现（万字详解）
    61
  • 9
    【树和二叉树】数据结构二叉树和树的概念认识
    35
  • 10
    【双向链表】数据结构双向链表的实现
    24

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考