《算法学习与数据结构》part1 算法分析与数据结构之表、栈和队列

2023-12-20 08:18

本文主要是介绍《算法学习与数据结构》part1 算法分析与数据结构之表、栈和队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

part1 算法分析与数据结构之表、栈和队列

1、分治策略:其想法是把问题分成两个大致相等的子问题,然后递归地对它们求解,这是“分”部分。“治”阶段将两个子问题的解合并到一起并可能再做些少量的附加工作,最后得到整个问题的解。

2、联机算法:主存中不必存储数组的任何部分,不仅如此,在任意时刻,算法都能对它已经读入的数据给出子序列问题的正确答案,具有这种特性的算法叫做联机算法。仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法。

3、分析算法最混乱的方面大概集中在对数上面。我们已经看到,某些分治算法将以O(NlogN)时间运行。处分治算法外,可将对数最常出现的规律概括为下列一般法则:如果一个算法用常数时间(O(1))将问题的大小削减为其一部分(通常是1/2),那么该算法就是O(logN)。另一方面,如果使用常数时间只是把问题减少一个常数(如果将问题减少1),那么这种算法就是O(N)的。

4、线性表是存在一段连续的存储空间中的,那么L.listsize是这段空间的大小。由于我们允许对表进行插入操作,所以表会变大,所以L.listsize会比实际表中数据元素大点,而L.length是表中实际数据元素的个数。

5、线性表

(1)线性表的特点:线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中的任一元素,它的存储位置可用一个简单直观的公式来表示。

(2)线性表的弱点:在作插入或删除操作时,需移动大量元素。

6、线性链表:线性链表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

7、结点(node):它包括两个域,其中存储数据元素信息的域称为数据域,存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n个结点(ai(1<=i<=n)的存储映像)链结成一个链表,即为线性表的链式存储结构。又由于此链表的每个结点中只包含一个指针域,故又称作线性链表或单链表。

8、关于线性表的一个简单总结:

一、线性结构特点

在数据元素的非空有限集中,(1)存在唯一的一个被称做“第一个”的数据元素;(2)存在唯一的一个被称做“最后一个”的数据元素;(3)除了第一个之外,集合中的每个数据元素均只有一个前驱;(4)除了最后一个之外,集合中每个元素均只有一个后继。

二、线性表的种类主要有以下4种:

(1)线性表:最常用且最简单的一种数据结构,除了头结点外其他结点都有前驱,除了尾结点外其他结点都有后继。最显著的特点是前驱与后继

(2)线性链表(单链表):用一组任意的存储单元存储线性表的数据元素这组存储单元可以是连续的,也可以是不连续的)。此链表的每一个结点中只包含一个指针域,故又称线性链表单链表

注:在使用时,常常使用单链表这一叫法。

(3)循环链表(Circular linked list):是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。

(4)双向链表(Double linked list):若要寻查结点的直接前驱,则需从表头指针出发。换句话说,在单链表中,NextElem的执行时间为O(1),而PriorElem的执行时间为O(n)。为客服单链表这种单向性的缺点,可利用双向链表(Double linked list)。顾名思义,在双向链表的结点中有两个指针域,其一指向直接后继,另一个指向直接前驱

9、栈(stack):是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端有其特殊含义,称为栈顶(top),相应地,表头端称为栈底(bottom)不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的原则进行的。因此,栈又称为后进先出(last in first out)的线性表(简称LIFO结构)

栈的数据类型在应用程序内定义,并称插入元素的操作为入栈删除栈顶元素的操作为出栈

和线性表类似,栈也有两种存储表示方法。顺序栈链栈

1)顺序栈:即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。一般来说,在初始化设空栈时不应限定栈的最大容量。通常合理的做法是:先为栈分配一个基本容量,然后再应用过程中,当栈的空间不够使用时再逐段扩大。为此,可以设定两个常量:STACK_INIT_SIZE(存储空间初始分配量)和STACKINCREAMENT(存储空间分配增量),并以下述类型说明作为顺序栈的定义。

typedef struct{SElemType *base;SElemType *top;int   stacksize;
}SqStack;
其中,stacksize指示栈的当前可使用的最大容量。栈的初始化操作为:按设定的初始分配量进行第一次存储分配,base可称为栈底指针,在顺序栈中,它始终指向栈底的位置,若base的值为NULL,则表明栈结构不存在。称top为栈顶指针,其初始值指向栈底,即top=base可作为栈空的标记,每当插入新的栈顶元素时,指针top增1;删除栈顶元素时,指针top减1,因此,非空栈中的栈顶指针始终在栈顶元素的下一个位置上。

2)链栈:栈的链式存储结构称为链栈。
在算法中要用到多个栈时,最好用链表作为栈的存储结构,即用指针来实现栈。用这种方式实现的栈也称为链栈。由于栈的插人和删除操作只在表头进行,因此用指针实现栈时没有必要像单链表那样设置一个表头单元。

栈的链式存贮结构,也称为链栈,它是一种限制运算的链表,即规定链表中的插入和删除运算只能在链表开头进行。链栈结构见图。


在链栈中,只会出现栈空和非空两种状态:当栈为空时,有top=null;当栈非空时, top指向链表的第一个结点(栈顶)。

10、一个简单的行编辑程序的功能是:接收用户从终端输入的程序或数据,并存入用户的数据区。

11、OP:我们把运算符和界限符统称为算符,它们构成的集合命名为OP。

OPTR:为实现算符优先算法,可以使用有两个工作栈。一个称作OPTR,用以寄存运算符。

OPND:另一个称作OPND,用以寄存操作数或运算结果。

12、递归函数:一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称作递归函数。

递归是程序设计中一个强有力的工具。其一,有很多数学函数是递归定义的,如大家熟悉的阶乘函数、二阶Fibonacci数列和Ackerman函数等;其二,有的数据结构,如二叉树、广义表等,由于结构本身固有的递归特性,则他们的操作可递归地描述;其三,还有一类问题,虽然问题本身没有明显的递归结构,但用递归求解比迭代求解更简单,如八皇后问题、Hanoi塔问题等。

这篇关于《算法学习与数据结构》part1 算法分析与数据结构之表、栈和队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n