【数据结构】线性表

一.线性表

1.定义:

n个同类型数据元素的有限序列,记为$L=(a_1,a_2,...,a _n)$

L为表名,i为数据元素在线性表中的位序,n为线性表的表长,n=0时称为空表。

2.数据元素之间的关系:

直接前驱和直接后继

3.抽象数据类型线性表的定义:

ADT List{

数据对象:

$D=\{a_i|a_i \in ElemSet,i=1,2,...,n,n\geq 0\}$

数据关系:

$R=\{<a_{i-1},a_i|a_{i-1},a_i \in D,i=2,...,n\}$

一个长度为n的线性表有n-1个数据关系

基本操作:

(1)结构初始化操作

(2)结构销毁操作

(3)访问型操作

(4)加工型操作
}ADTList

二.存储结构

1.顺序存储

以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>

最简单的一种顺序存储方式是:

令y的存储位置和x的存储位置相邻。

用一组地址连续的存储单元依次存放线性表中的数据元素

线性表的起始地址称为线性表的基地址

所有数据元素的存储位置均取决于第一个数据元素的存储位置

1.1 顺序表的定位查找

将顺序表中的元素逐个与给定值e相比较

时间复杂度为$O(ListLength)$

1.2 顺序表的插入操作

插入位置以及之后的元素后移

时间复杂度为$O(ListLength)$

1.3 顺序表的删除操作

删除该元素并且该元素之后的元素前移

时间复杂度为$O(ListLength)$

2.单链表

用一组地址任意的存储单元存放线性表中的数据。

结点(表示数据元素的存储)=元素+地址

结点的序列表示线性表——称作链表

2.1 头结点

为了操作方便,在第一个结点之前虚加一个“头结点”,以指向头结点的指针为链表的头指针。

2.2 访问第i个元素

p=p->next;

时间复杂度为$O(ListLength)$

2.3 在第i个位置插入元素

寻找第i-1个位置

再进行插入

时间复杂度为$O(ListLength)$

 2.4 在第i个位置删除元素

寻找第i-1个位置

再进行删除

时间复杂度为$O(ListLength)$

2.5 将单链表置为空表

时间复杂度为$O(ListLength)$

2.6 如何从线性表中得到单链表?

链表是一个动态的结构,它不需要预先分配空间,因此生成链表的过程是一个结点“逐个插入”的过程。

2.7 其他形式的链表

1)双向链表

有两个指针,一个指向前驱,一个指向后继。

2)循环链表

最后一个结点的指针域的指针又指回第一个结点的链表。

和单链表的差别仅在于:判别链表中最后一个结点的条件不再是“后继是否为空”,而是“后继是否为头结点”。

3)双向循环链表

2.8 双向链表的操作特点

“查询”和单链表相同

“插入”和“删除”时需要同时修改两个方向上的指针。

例如“插入”:

s->next=p->next;

p->next=s;

s->next->prior=s;

s->prior=p;

例如“删除”:

s=p->next;

p->next=p->next->next;

p->next->prior=p;

delete s;

 3.总结

顺序表适合查找操作,而链表适合插入和删除操作。

三.栈(操作受限的线性数据结构)

1.栈的抽象类型定义:

ADT Stack{

数据对象:

$D=\{a_i|a_i \in ElemSet,i=1,2,3,...,n,n\geq 0\}$

数据关系:

$R1=\{<a_{i-1},a_i>|a_{i-1},a_i \in D,i=2,...,n\}$

约定$a_n$端为栈顶,$a_1$端为栈底。

基本操作:


}ADTStack

2.顺序栈

指向表尾的指针可以作为栈顶指针

3.链栈

链栈中指针的方向是从栈顶元素往下指

4.栈的应用举例:

1)数制转换

void conversion(){

    stack <int> s;

    int N;

    cin>>N;

    while(N){

        s.push(N%8);//余数进栈

        N/=8;

    }

    while(!s.empty()){

        cout<<s.top();

        s.pop();

    }

    cout<<endl;

}

2)表达式求值

表达式由操作数、运算符、界限符组成。

操作数(operand):常数或变量

运算符(operator):算数、关系、逻辑等

界限符(delimiter):左右括号、表达式结束符#等

运算符优先表

算法思想:

使用两个栈,一个运算符栈(OPTR)一个操作数栈(OPND)

1)OPND置为空栈,将#放入OPTR栈

2)依次读入表达式中的每个字符

3)若是操作数,读入OPND栈,若是运算符,则和OPTR栈的栈顶元素进行优先级比较,若栈顶元素优先级高,则执行相应运算,结果存入OPND栈;若栈顶元素优先级低,则将该字符读入OPTR栈;若优先级相同,则做‘##’或‘()’处理。

4)重复上述操作,直到表达式求值完毕(读入的是‘#’,并且OPTR栈顶元素也为‘#’)

3)迷宫求解

回溯法:一种不断试探且及时纠正错误的搜索方法。

回溯法思想:从入口出发,按某一方向向前探索,若能走通(未走过),则到达新点,否则试探下一没有探索过的方向,若所有的方向均没有通路,则沿原点返回前一点,换下一个方向再继续试探,直到所有可能的通路都探索过,或找到一条通路,或无路可走又返回到入口点。

(1)表示迷宫的数据结构

#define M 6        //迷宫的实际行和列

#define N 8

int maze[M+2][N+2];

入口坐标为(1,1),出口坐标为(M,N)

(2)试探方向

每个点有8个方向可以试探,试探顺序规定为:从正东方向顺时针方向进行。

move数组定义

typedef struct{
int x,y;

}item;

item move[8];

x:行坐标增量

y:列坐标增量

(3)栈的设计

当到达了某点而无路可走时需要返回前一点,再从前一点开始向下一个方向继续试探。因此,压入栈中的不仅是顺序到达的各点的坐标,而且还要有从看一点到达本点的方向。

栈中元素是一个由行、列、方向组成的三元组。

typedef struct{
int x,y,direction;

}datatype;

栈的定义为:

stack <datatype> s;

(4)如何防止重复到达某点,以避免发生死循环?

当到达某点(i,j)时,将maze[i][j]置为-1

(5)迷宫求解算法思想

1.栈初始化

2.将入口点坐标以及到达该点的方向direction设置为-1,入栈。

3.while(栈不为空)

{

弹栈

求出下一个要试探的方向direction++

while(还有剩余试探方向时){

if(direction方向可走){

则{x,y,direction}入栈,求新点坐标(i,j)

将新点(i,j)切换为当前点(x,y)

if((x,y)==(M,N)){

结束

                }

else{

重制direction=0;

}

}

else

direction++;

}

}

四.队列

1.队列的抽象定义

ADT Queue{

数据对象:

$D=\{a_i|a_i \in ElemSet,i=1,2,...,n,n\geq 0\}$

数据关系:

$R1=\{<a_{i-1},a_i>|a_{i-1},a_i \in D,i=2,...,n\}$

约定:其中$a_1$端为队列头,$a_n$端为队列尾。

基本操作:


}ADT Queue

2.顺序队列

#define MAXQSIZE 100
typedef struct{
ElemType base[MAXQSIZE];
int front;//头指针,若队列不为空,指向队列头元素
int resr;//尾指针,若队列不为空,指向队列尾元素的下一个位置
}SqQueue;

2.1 "假溢出"

为了解决假溢出问题,采用循环队列

队满和队空时均有sq.front==sq.rear

无法判断队满还是队空。

1)方法一:

用一个计数变量来记录队列中元素的个数。

2)方法二:

设置一个标志位。

当有元素入队时,标志位为true;有元素出队时,标志位为false。

3)方法三:

牺牲一个元素空间,来区别队空或队满。 

队满:(sq.rear+1)%queue_length==sq.front

队空:sq.front==sq.rear

2.2 插入元素e为Q的新的队尾元素

1)判断队列是否满

2)满了,则error

3)没满,Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%queue_length;

2.3 出队

1)判断队列是否为空

2)空,返回error

3)非空,e=Q.base[Q.front];

Q.front=(Q.front+1)%queue_length;

2.4 队列长度 

return ((Q.rear-Q.front+queue_length)%queue_length);

3.链队列

typedef struct QNode{
QelemType data;
struct QNode *next;

}*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

3.1 插入元素e为Q的队尾元素

p=new QNode;

p->data=e;

p->next=NULL;

Q.rear->next=p;

Q.rear=p; 

3.2 出队

if(Q.front==Q.rear)

        return error;

p=Q.front->next;

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)

        Q.rear=Q.front;//避免尾指针成为野指针

delete p;

3.3 构造函数

Q.front=Q.rear=new QNode;

Q.front->next=NULL;//带头结点

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/265814.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

PADS Layout安全间距检查报错

问题&#xff1a; 在Pads Layout完成layout后&#xff0c;进行工具-验证设计安全间距检查时&#xff0c;差分对BAK_FIXCLK_100M_P / BAK_FIXCLK_100M_N的安全间距检查报错&#xff0c;最小为3.94mil&#xff0c;但是应该大于等于5mil&#xff1b;如下两张图&#xff1a; 检查&…

SpringBoot的配置高级

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开心好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…

【JMeter】使用内网负载机(Linux)执行JMeter性能测试

一、背景 ​ 在我们工作中有时候会需要使用客户提供的内网负载机进行性能测试&#xff0c;一般在什么情况下我们需要要求客户提供内网负载机进行性能测试呢&#xff1f; 遇到公网环境下性能测试达到了带宽瓶颈。那么这时&#xff0c;我们就需要考虑在内网环境负载机下来执行我们…

使用C语言将ASCII明文编码为GSM短信体格式

一、背景介绍 GSM&#xff08;Global System for Mobile Communications&#xff09;是全球移动通信系统的简称&#xff0c;而GSM 03.38是GSM系统中用于短信编码的标准。GSM 03.38字符集采用7-bit编码&#xff0c;与ASCII的8-bit编码有所不同。为了将ASCII编码的文本转换为GSM…

【JavaWeb学习笔记】13 - JSP浏览器渲染技术

项目代码 https://github.com/yinhai1114/JavaWeb_LearningCode/tree/main/jsp JSP 一、JSP引入 1.JSP现状 1.目前主流的技术是前后端分离(比如: Spring Boot Vue/React),我们会讲的.[看一下] 2. JSP技术使用在逐渐减少&#xff0c;但使用少和没有使用是两个意思&#xff…

DB207S-ASEMI迷你贴片整流桥DB207S

编辑&#xff1a;ll DB207S-ASEMI迷你贴片整流桥DB207S 型号&#xff1a;DB207S 品牌&#xff1a;ASEMI 封装&#xff1a;DBS-4 最大平均正向电流&#xff1a;2A 最大重复峰值反向电压&#xff1a;1000V 产品引线数量&#xff1a;4 产品内部芯片个数&#xff1a;4 产品…

Spring security之授权

前言 本篇为大家带来Spring security的授权&#xff0c;首先要理解一些概念&#xff0c;有关于&#xff1a;权限、角色、安全上下文、访问控制表达式、方法级安全性、访问决策管理器 一.授权的基本介绍 Spring Security 中的授权分为两种类型&#xff1a; 基于角色的授权&…

2024最新苹果手机APP软件下架了,怎么安装?

如果你是一个iPhone用户&#xff0c;你可能会遇到这样的情况&#xff1a;你想下载或更新一个软件&#xff0c;但发现它已经从APP Store上消失了。这可能是因为软件违反了苹果的规则&#xff0c;或者开发者主动撤下了软件。那么&#xff0c;这种情况下&#xff0c;你还能安装或使…

OpenCV | 霍夫变换:以车道线检测为例

霍夫变换 霍夫变换只能灰度图&#xff0c;彩色图会报错 lines cv2.HoughLinesP(edge_img,1,np.pi/180,15,minLineLength40,maxLineGap20) 参数1&#xff1a;要检测的图片矩阵参数2&#xff1a;距离r的精度&#xff0c;值越大&#xff0c;考虑越多的线参数3&#xff1a;距离…

Unreal5.3 PCG 笔记

目录 ElectricDreams场景功能移动中间山体向周围随机生成倒下的树干树干上随机生成的植被 ElectricDreams场景功能 移动中间山体向周围随机生成倒下的树干 配置内容 中心山体Spline周围沟渠Spline&#xff08;土堆&#xff09;PCG规则 主要功能节点 SplineSample&#xff08;…

基于Java web的住院管理系统论文

目 录 目 录 I 摘 要 III ABSTRACT IV 1 绪论 1 1.1 课题背景 1 1.2 研究现状 1 1.3 研究内容 2 2 系统开发环境 3 2.1 vue技术 3 2.2 JAVA技术 3 2.3 MYSQL数据库 3 2.4 B/S结构 4 2.5 SSM框架技术 4 3 系统分析 5 3.1 可行性分析 5 3.1.1 技术可行性 5 3.1.2 操作可行性 5 3…

Linux 操作系统(用户注册、删除、权限修改等)

添加用户 格式&#xff1a;useradd 用户名 ( 添加用户 ) passwd 用户名 (给用户设置密码) Linux 用户切换原则&#xff1a; 高权限向低权限切换无需输入密码 低权限向高权限或同级用户切换需要输入密码 用户切换&#xff1a;su su – 用户名 &#xff08;用户切换&#x…

【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推荐--…

蓝牙技术在物联网中的应用

随着蓝牙技术的不断演进和发展&#xff0c;蓝牙已经从单一的传统蓝牙技术发展成集传统蓝牙。高速蓝牙和低耗能蓝牙于一体的综合技术&#xff0c;不同的应用标准更是超过40个越来越广的技术领域和越来越多的应用场景&#xff0c;使得目前的蓝牙技术成为包含传感器技术、识别技术…

DRF从入门到精通三(反序列化数据校验源码分析、断言Assert、DRF之请求、响应)

文章目录 一、反序列化数据校验源码分析二、断言Assert三、DRF之请求、响应Request类和Response类请求中的Request 能够解析前端传入的编码格式响应中的Response能够响应的编码格式 一、反序列化数据校验源码分析 反序列化数据校验&#xff0c;校验顺序为&#xff1a;先校验字段…

懂机器学习?先来回答这三个问题 >>

机器学习是一种数据分析技术&#xff0c;让计算机学习人类和动物与生俱来的能力&#xff1a;从经验中学习。 机器学习算法使用计算方法直接从数据中“学习”信息&#xff0c;而不依赖于预定方程作为模型。 随着可用于学习的样本数量的增加&#xff0c;算法也会相应地提高性能。…

探索栈数据结构:深入了解其实用与实现(c语言实现栈)

上次结束了链表部分的内容&#xff1a;链接未来&#xff1a;深入理解链表数据结构&#xff08;二.c语言实现带头双向循环链表&#xff09; 然而&#xff0c;当我们涉及特定问题时&#xff0c;另一个非常有用的数据结构也开始显得至关重要——栈 栈与链表有着截然不同的特性&a…

MySQL数据库基础和基本的增删改查操作

目录 前瞻 数据库的基本概念 数据库管理系统&#xff08;DBMS&#xff09; 数据库系统(DBS) 数据库类型和常用数据库 关系型数据库 SQL 非关系型数据库 NoSQL SQL语句 简介 SQL语句分类 常用的数据类型 MySQL的六大约束特性 SQL语句的使用 创建及删除数据库和表 …

H5小游戏加固方案

今年的中国游戏产业年会上&#xff0c;小游戏成了万众瞩目的行业新风口。据伽马数据统计&#xff1a;2023年小游戏市场规模可达200亿元&#xff0c;同比增长300% 。 小游戏有着分发更精准、用户转化率更高、研发成本更低、场景适用性更强等优势&#xff0c;具备巨大的市场潜力…

openGauss学习笔记-171 openGauss 数据库运维-备份与恢复-导入数据-深层复制

文章目录 openGauss学习笔记-171 openGauss 数据库运维-备份与恢复-导入数据-深层复制171.1 使用CREATE TABLE执行深层复制171.1.1 操作步骤 171.2 使用CREATE TABLE LIKE执行深层复制171.2.1 操作步骤 171.3 通过创建临时表并截断原始表来执行深层复制171.3.1 操作步骤 openGa…