数据结构与算法之美08

数据结构与算法之美08

一、什么是栈?1.后进者先出,先进者后出,这就是典型的“栈”结构。2.从栈的操作特性来看,是一种“操作受限”的线性表,只允许在端插入和删除数据。二、为什么需要栈?1.栈是一种操作受限的数据结构,其操作特性用数组和链表均可实现。2.但,任何数据结构都是对特定应用场景的抽象,数组和链表虽然使用起来更加灵活,但却暴露了几乎所有的操作,难免会引发错误操作的风险。3.所以,当某个数据集合只涉及在某端插入和删除数据,且满足后进者先出,先进者后出的操作特性时,我们应该首选栈这种数据结构。三、如何实现栈?1.栈的APIpublic class Stack<Item> {//压栈public void push(Item item){}//弹栈public Item pop(){}//是否为空pu

数据结构与算法之美07

数据结构与算法之美07

链表(下):如何轻松写出正确的链表代码? 一、理解指针或引用的含义1.含义:将某个变量(对象)赋值给指针(引用),实际上就是就是将这个变量(对象)的地址赋值给指针(引用)。2.示例:p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。 二、警惕指针丢失和内存泄漏(单链表)1.插入节点在节点a和节点b之间插入节点x,b是a的下一节点,,p指针指向节点a,则造成指针丢失和内存泄漏的代码:p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。正确的写法是2句代码交换顺序,即:x—>next =

约瑟夫环问题

约瑟夫环问题

约瑟夫环问题,这是一个很经典算法,处理的关键是:伪链表 问题描述:N个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,报到m的人出圈;如此往复,直到所有人出圈。

数据结构与算法之美06

数据结构与算法之美06

链表(上):如何实现LRU缓存淘汰算法? 一、什么是链表?1.和数组一样,链表也是一种线性表。2.从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构。3.链表中的每一个内存块被称为节点Node。节点除了存储数据外,还需记录链上下一个节点的地址,即后继指针next。 二、为什么使用链表?即链表的特点1.插入、删除数据效率高O(1)级别(只需更改指针指向即可),随机访问效率低O(n)级别(需要从链头至链尾进行遍历)。2.和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。 三、常用链表:单链表、循环链表和双向链表1.单链表1)每个节点只包含一个

数据结构与算法之美05

数据结构与算法之美05

数组:为什么很多编程语言中数组都从0开始编号? 数组看起来简单基础,但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号,而不是从1开始的问题,进入主题。 1. 数组如何实现随机访问1) 数组是一种线性数据结构,用连续的存储空间存储相同类型数据I) 线性表:数组、链表、队列、栈 非线性表:树 图II) 连续的内存空间、相同的数据,所以数组可以随机访问,但对数组进行删除插入,为了保证数组的连续性,就要做大量的数据搬移工作a) 数组如何实现下标随机访问。引入数组再内存种的分配图,得出寻址公式b) 纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组,用二分查找,时间复杂度也是O(

数据结构与算法之美04

数据结构与算法之美04

复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度 一、复杂度分析的4个概念1.最坏情况时间复杂度:代码在最理想情况下执行的时间复杂度。2.最好情况时间复杂度:代码在最坏情况下执行的时间复杂度。3.平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示。4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。 二、为什么要引入这4个概念?1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。2.代码复

数据结构与算法之美03

数据结构与算法之美03

复杂度分析(上):如何分析、统计算法的执行效率和资源消耗? 一、什么是复杂度分析? 1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。 2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。 3.分别用时间复杂度和空间复杂度两个概念来描述性能问题,二者统称为复杂度。 4.复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。 一、什么是复杂度分析? 1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。 2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。 3.分别用时间复杂度和空间复杂度两个概念来描述性能问题,二者统称为复杂度。 4.复杂度描述

数据结构与算法之美02

数据结构与算法之美02

如何抓住重点,系统高效地学习数据结构与算法? 当我们要谈一个事物/概念的时候,需要问自己三个终极问题–是什么?为什么?怎么样? 什么是数据结构和算法 数据结构,就是一组数据的存储结构。 算法,就是操作数据的一组方法。 数据结构是为算法服务的,算法要作用在特定的数据结构之上。 为什么需要数据结构和算法 来谈谈应用层面的原因。在计算机科学和互联网迅猛发展下,需要计算的数据量越来越庞大。但是计算机的计算能力是有限的,这么大量的数据计算,需要越来越多的计算机,需要越来越长的计算时间,注重效率的我们需要尽可能的提高计算效率。其中重要的一项,就是使用合适的数据结构和算法。选用合适的数据结构和算法,特别是在

数据结构与算法之美01

数据结构与算法之美01

为什么要学习数据结构和算法? 为什么学习数据结构和算法?我认为有3点比较重要 1.直接好处是能够有写出性能更优的代码。 2.算法,是一种解决问题的思路和方法,有机会应用到生活和事业的其他方面。 3.长期来看,大脑思考能力是个人最重要的核心竞争力,而算法是为数不多的能够有效训练大脑思考能力的途径之一。