顺序表的实现(迈入数据结构的大门)(1)

简介: 顺序表的实现(迈入数据结构的大门)(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将会在接下来揭晓如何编写!!!


相关文章
|
30天前
|
存储 编译器 C语言
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
48 2
|
11天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
11天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
38 3
|
11天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
24天前
|
存储
数据结构(顺序表)
数据结构(顺序表)
22 0
|
25天前
|
存储 算法
【数据结构】新篇章 -- 顺序表
【数据结构】新篇章 -- 顺序表
13 0
|
30天前
|
存储 测试技术
探索数据结构:顺序表的实现与应用
探索数据结构:顺序表的实现与应用
|
8天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
75 9
|
2天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
5天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
下一篇
无影云桌面