《算法学习与数据结构》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

相关文章

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory