Day02 顺序表

2024-06-14 09:04
文章标签 顺序 day02

本文主要是介绍Day02 顺序表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1、顺序表

2、随机访问&顺序访问

3、思考

4、顺序表的封装


1、顺序表

        数组在数据结构中是属于线性表的一种,线性表是由一组具有n个相同类型的数据元素组成的。线性表中的任何一个数据元素

  • 有且只有一个直接前驱
  • 有且只有一个直接后继
  • 首元素是没有前驱的
  • 尾元素是没有后继的

  • 某个元素的左侧相邻元素被称为“直接前驱”,
  • 元素左侧所有的数据元素被称为“前驱元素”。
  • 某个元素的右侧相邻元素被称为“直接后继”,
  • 元素右侧所有的数据元素被称为“后继元素”。

        满足这种数学关系的一组元素,逻辑关系就是线性结构,并且逻辑关系是一对一的,比如一个教室学生的学号、一个排队的队伍、一摞堆好的盘子.....都属于线性结构,当然线性结构和存储方式是无关的,简单理解:只有逻辑关系是一对一的,就是线性结构。

所以,根据数据的存储方式可以把线性表分为两种

  • 顺序存储的线性表
  • 链式存储的线性表。

        顺序表指的是使用一组内存地址连续的内存单元来依次存储线性表中的数据元素,使用这种存储结构的线性表就被称为顺序表。

简单理解:数据存储在一块连续的内存中,在C语言中可以具名的数组,也可以使用匿名的数组(堆内存)。

顺序表的特点:数据元素之间的逻辑关系是相邻的,并且内存地址也是相邻的,所以只要知道存储线性表的第一个数据元素的内存地址,就可以对线性表中的任意一个元素进行随机访问。通常用户使用动态分配的数组来实现顺序表,也就是使用堆内存实现。

2、随机访问&顺序访问

        随机访问指的是在同等时间内具有访问任意元素的能力

  • 随机访问相对立的就是顺序访问
  • 顺序访问花费的时间要高于随机访问

比如卷轴(顺序)和书籍(随机)、磁带(顺序)和唱片(随机)。

3、思考

思考:既然数组可以作为线性表来使用,请问如何对数组中的元素进行增加和删除以及访问?

回答:如果打算使用数组实现线性表的特性,需要知道三个条件:

  1. 数组首元素地址address;
  2. 数组元素的容量size;
  3. 数组中元素的个数count。

4、顺序表的封装

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//设计数据元素类型
typedef int ElemType;// 设计一个顺序表节点结构体
struct Sqlist
{ElemType *data; // 保存数据首地址int count;      // 保存存储的数据个数int size;       // 保存容量
};// 创建一个顺序表
struct Sqlist *createSq(int size);
// 销毁顺序表
void destroySq(struct Sqlist *sq);
// 在指定位置插入数据
bool insertSq(struct Sqlist *sq, ElemType data, int pos);
// 查询数据--返回数据位置,没找到返回-1
int indexSq(struct Sqlist *sq, ElemType data);
// 删除数据
bool deleteSq(struct Sqlist *sq, ElemType data);
// 遍历显示
void displaySq(struct Sqlist *sq);// 创建一个顺序表
struct Sqlist *createSq(int size)
{// 1.申请结构体空间struct Sqlist *sq = (struct Sqlist *)malloc(sizeof(struct Sqlist));if (sq == NULL){return NULL;}// 2.初始化结构体成员,sq->size = size;sq->count = 0;// 3.申请数据空间sq->data = malloc(sizeof(ElemType)*(sq->size));if (sq->data == NULL){// 数据空间申请失败,则将其结构体空间释放free(sq);return NULL;}// 4.返回结构体指针return sq;
}// 销毁顺序表
void destroySq(struct Sqlist *sq)
{if (sq == NULL){return;}// 1.释放数据空间free(sq->data);// 2.释放结构体空间free(sq);
}// 在指定位置插入数据
bool insertSq(struct Sqlist *sq, ElemType data, int pos)
{// 1.判断sq是否为空,count与size是否相等(满)if (sq == NULL){perror("顺序表为NULL");return false;}if (sq->count == sq->size || pos < 0){perror("顺序表满");return false;}// 2.判断pos是否在0-count中间,那么就要进行挪位,如果不在0-count中间就直接插入末尾if (pos >= sq->count){sq->data[sq->count] = data;sq->count++;}else{for (int i = sq->count; i > pos; i--){sq->data[i] = sq->data[i - 1];}// 3.把数据放在pos位置sq->data[pos] = data;// 4.count++sq->count++;}return true;
}
// 查询数据--返回数据位置,没找到返回-1
int indexSq(struct Sqlist *sq, ElemType data)
{// 遍历数组, 查到就返回数组下标if (sq == NULL){return -1;}for (int i = 0; i < sq->count; i++){if (sq->data[i] == data){return i;}}return -1;
}
// 删除数据
bool deleteSq(struct Sqlist *sq, ElemType data)
{// 1.调用indexSq查询int pos = indexSq(sq, data);if (pos == -1){return false;}// 2.挪位删除for (int i = pos; i < sq->count - 1; i++){sq->data[i] = sq->data[i + 1];}// 3.count--sq->count--;return true;
}// 遍历显示
void displaySq(struct Sqlist *sq)
{// 遍历数组输出if (sq == NULL){return;}for (int i = 0; i < sq->count; i++){printf("%d ", sq->data[i]);}printf("\n");
}int main(void)
{// 创建顺序表struct Sqlist *sq = createSq(10);// 插入数据for (int i = 0; i < 11; i++){int data = random() % 100;insertSq(sq, data, i);}// 显示displaySq(sq);// 销毁destroySq(sq);
}

这篇关于Day02 顺序表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1059962

相关文章

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中,location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求,NGINX 提供了多种匹

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表,允许插入的一端叫做队尾(rear),允许删除的一端叫做队首(front)。 队列具有FIFO的性质 队列的存储表示也有两种方式:基于数组的,基于列表的。基于数组的叫做顺序队列,基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示:只提供了接口和显式的默认构造函数和析构函数,在派生类中调用。 #i

[数据结构]栈之顺序栈的类模板实现

栈的数组实现形式,采用动态分配数组,不够时可以调整栈的大小。 Stack.h文件:主要定义栈的抽象基类,提供公共的接口函数。 #ifndef STACK#define STACK//栈的抽象基类template<class T>class Stack{public:Stack(){}~Stack(){}virtual void Push(const T& x)=0;virt

C++中类的构造函数调用顺序

当建立一个对象时,首先调用基类的构造函数,然后调用下一个派生类的 构造函数,依次类推,直至到达派生类次数最多的派生次数最多的类的构造函数为止。 简而言之,对象是由“底层向上”开始构造的。因为,构造函数一开始构造时,总是 要调用它的基类的构造函数,然后才开始执行其构造函数体,调用直接基类构造函数时, 如果无专门说明,就调用直接基类的默认构造函数。在对象析构时,其顺序正好相反。

七、Maven继承和聚合关系、及Maven的仓库及查找顺序

1.继承   2.聚合   3.Maven的仓库及查找顺序

线性表中顺序表的合并

对两个顺序表进行合并,算法的复杂度为O(La.size+Lb.size)。 已知: 顺序线性表La和Lb的元素按值非递减排列 归并La和Lb得到的顺序线性表Lc,Lc的元素也按值非递减排列。 代码定义: void mergeList(SeqList *La,SeqList *Lb,SeqList *Lc){Lc->capacity = La->size + Lb->size;Lc->b

理解C++全局对象析构顺序与 IPC 资源管理:避免 coredump

文章目录 0. 概述1. 问题背景2. 问题分析3. 解决方案:手动释放资源4. 深入剖析:为什么手动调用 `reset()` 有效?5. 延伸思考:如何避免全局对象带来的问题?6. 总结 0. 概述 在编写 C++ 程序时,使用全局或静态对象有时可能会导致不可预期的崩溃(如 coredump)。这类崩溃通常源于对象的析构顺序、资源的管理方式,以及底层资源(如 IPC 通道或共

逆序和顺序创建单链表

单链表是一种顺序的存储方式,数据结构学的不好,考研又是必考内容,只好从头开始学习,相信不断地积累会有更好的爆发! 首先单链表的创建,单链表是建立在结构体的基础上,要创建单链表首先要建立起一个储存数据的结构体: struct node{int elem;node *next;};elem是数据域,用来存放你要输入的数据,next是指向下个存放数据节点的指针同为node 类型; 下面是

程序存储器编址及程序执行顺序

对于内部有ROM的芯片,根据情况也可以扩展外部ROM,虽然内、外程序存储器总容量可以超过64KB,但其有效存储空间只有64KB,内、外程序存储器逻辑上将共用64K存储空间。片内程序存储器地址空间和片外程序存储器的低地址空间重叠。51子系列重叠区域为0000H~0FFFH,52子系列重叠区域为0000H~1FFFH。        单片机在执行指令时,对于低地址部分,是从片内程序存