顺序表的实现（迈入数据结构的大门）（1）-阿里云开发者社区

顺序表的实现（迈入数据结构的大门）（1）

2024-05-16 13

版权

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

简介： 顺序表的实现（迈入数据结构的大门）（1）

上一节我们认识到了什么是数据结构

这一节我们就来实现第一个数据结构的实现

思考一个问题：

假定一个数组，空间为10，已经使用了5个，向其中插入数据的步骤：

1.插入数据，我们先要求数组长度，其中有效数据的个数，判断空余空间的大小，向下标中放入有效数据；（这里需要判断数组是否太满了，剩余空间是否还足够）；

2.如果数据量庞大，我们就要频繁获取数组有限个数，就会影响程序运行速率；

这时候我们就要利用其余数据结构（顺序表、链表、二叉树；更甚至红黑树、B树等更为高级的数据结构）；

那我们就进入，顺序表的学习吧；

顺序表

顺序表是一种线性表

线性表（List）：零个或多个数据元素的有限序列。线性表的数据集合为{a1,a2,…,an}，假设每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件

顺序表（对数组的封装）的分类

静态顺序表

顾名思义：即是使用定长数组来储存元素

typedef int SLdataTapy;
#define N  10   //数组的大小由N决定
 
typedef struct seqlist {
  SLdataTapy arr[N];//定长数组
  int size;//有效数组个数
}SL;

注意：这就会出现：空间小了不够用，空间大了，空间浪费。

想一想呢，根据之前的学习，是什么可以动态增删内存呢

没错，就是利用malloc、relloc、calloc内存函数了

（忘记的小朋友可以回顾一下往期的博客，动态内存的管理（内存储存的god）-CSDN博客）

动态顺序表

typedef int SLdataTapy;
 
typedef struct seqlist {
  SLdataTapy* a;//用来开辟动态内存
  int size;//有效数组个数
  int capacity;//剩余容量；判断是否需要新添加内存
}SL;

顺序表的实现

#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
 SLDataType* a;
 int size; // 有效数据个数
 int capacity; // 空间容量
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插⼊删除 / 尾部插⼊删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插⼊/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

以上则是我们需要实现顺序表的作用

顺序表的初始化

将其中的数组置为NULL；其余置为0；

void SLInit(SL* ps) {
  ps->a = NULL;//置为NULL,以防野指针的出现
  ps->size = ps->capacity = 0;
}

有初始化就有销毁

销毁则是需要将数组重新置为NULL；其余置为0；

void SLDestroy(SL* ps) {
  if (ps->a) {//判断数组中是否为空
    free(ps->a);//因为动态顺序表需要使用malloc开辟内存，所以需要注意释放内存
  }
  ps->a = NULL;
  ps->size = ps->capacity = 0;
}

当我们设置好一切后，就要对数组进行扩容

//扩容
void SLCheckCapacity(SL* ps) {
  //先要判断内存够不够
  if (ps->size == ps->capacity) {
    //使用malloc relloc celloc
    int newcappacity = ps->capacity * 2;//一般增容原来内存的二到三倍；
    SLDataType*tmp = (SLDataType*)relloc(ps->a,newcappacity * sizeof(SLDataType));
    //注：这里没有直接使用ps->a直接申请，是为了防止内存申请失败；防止数据丢失
    if (tmp == NULL) {
        //也可以使用assert直接终止程序；需要使用aseert.h的头文件
      perror("relloc fail");
      exit(1);
        //直接退出程序；也可使用return；
    }
    //空间增容成功
    ps->a = tmp;
    ps->capacity = newcappacity;
  }
}

其中出现了一点小问题，是否发现了呢；

果然聪明的你一眼就发现问题了呢；

int newcappacity = ps->capacity * 2;//一般增容原来内存的二到三倍；
SLDataType*tmp = (SLDataType*)relloc(ps->a,newcappacity * sizeof(SLDataType));

在使用这句的前提是capacity为0；就会导致开辟为0的空间，就会出现错误；

就可以利用到三目操作符，使其完成扩容：如以下代码

int newcappacity = ps->capacity == 0 ? 4 :ps->capacity*2

ps->capacity是否为0；如果是则为4；否则乘以2；

总结：

//初始化和销毁
void SLInit(SL* ps) {
  ps->a = NULL;
  ps->size = ps->capacity = 0;
}
 
void SLDestroy(SL* ps) {
  if (ps->a) {//判断数组中是否为空
    free(ps->a);//因为需要使用malloc，所以需要注意释放内存
  }
  ps->a = NULL;
  ps->size = ps->capacity = 0;
}
 
//扩容
void SLCheckCapacity(SL* ps) {
  //先要判断内存够不够
  if (ps->size == ps->capacity) {
    //使用malloc relloc celloc
    int newcappacity = ps->capacity == 0 ? 4 :ps->capacity*2;//一般增容原来内存的二到三倍；
    SLDataType*tmp = (SLDataType*)relloc(ps->a,newcappacity * sizeof(SLDataType));
    //注：这里没有直接使用ps->a直接申请，是为了防止内存申请失败；防止数据丢失
    if (tmp == NULL) {//也可以使用assert直接终止程序；需要使用aseert.h的头文件
      perror("relloc fail");
      exit(1);//直接退出程序；也可使用return；
    }
    //空间增容成功
    ps->a = tmp;
    ps->capacity = newcappacity;
  }
}

我们已经完成了初始化，销毁与扩容，你可以尝试剩余代码的编写；

点关注，不迷路，up将会在接下来揭晓如何编写！！！