猿考研之数据结构篇一（复杂度，线性表）

• 1.数据
• 数据是信息的载体，是描述客观事物属性的数、字符以及所有能够输入到计算机中并被计算机程序识别和处理的符号的集合。
• 2.数据元素
• 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。
• 3.数据类型
• 数据类型是一个值的集合和定义在此集合上一组操作的总称。
  • 1）原子类型：其值不可再分的数据类型。
  • 2）结构类型：其值可以再分解为若干成分（分量）的数据类型。
  • 3）抽象数据类型：抽象数据组织和与之相关的操作。
    • 抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。通常用（数据对象、数据关系、基本操作集）这样的三元组来表示抽象数据类型。
  • 4）数据结构：
    • 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Structure)。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

数据结构

• 逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。
  • 数据的逻辑结构分为线性结构和非线性结构
    • 集合结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。类似于数学上的集合
  • 线性结构结构中的数据元素之间只存在一对一的关系。比如排队
  • 树形结构 结构中的数据元素之间存在一对多的关系。比如家族族谱
  • 图状结构或网状结构结构中的数据元素之间存在多对多的关系。比如地图

• 物理结构
  • 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构
• 主要有：顺序存储、链式存储、索引存储和散列存储。
• 顺序存储：存储的物理位置相邻。(p.s.物理位置即信息在计算机中的位置。)
• 链接存储：存储的物理位置未必相邻，通过记录相邻元素的物理位置来找到相邻元素。
• 索引存储：类似于目录
• 散列存储：通过关键字直接计算出元素的物理地址。

---

算法和算法的复杂度

算法是对问题求解步骤的描述，通过有限序列的指令来实现。

• 五大特征
• 1，有穷性：有限步之后结束不会出现无限循环
• 2，确定性：不存在二义性，算法的每个步骤被精确定义
• 3，可行性：比如受限于计算机的计算能力，有些算法虽然理论上可行，但实际上无法完成。
• 4，输入：能被计算机处理的各种类型数据，如数字，音频，图像等等。
• 5，输出：一至多个程序输出结果。

时间复杂度

• 它用来衡量算法随着问题规模增大，算法执行时间增长的快慢。
• 时间复杂度是问题规模的函数：记作T（n)，时间复杂度主要分析T（n)的数量级。
• T(n)=O(f(n)，大o记法，f(n）是算法中基本运算的频度，一般我们考虑最坏情况下的时间复杂度。
• 计算方法：取算法时间增长最快那个函数项，把它的系数改为1

空间复杂度

• 它用来衡量算法随着问题规模增大，算法所需空间的增长的快慢；
• 是问题规模的函数：S(n)=O(g(n))。
  

时间复杂度的计算

• 时间分析：
  • 该算法执行了3n+6个语句。
  • 假设每个语句执行时间一致，均为常数t。则总时间T=（3n+6）*t。
  • 随着问题规模n的增大，总时间的增长率与n的增长率一致，所以复杂度为o（n)。
• 结论：
  • 复杂度是关于增长率的，所以可以直接忽视常数项。
  • 一般可以直接关注循环段基本操作语句（示例中的sum=sum+i)的执行次数。

单循环体

直接关注循环体的执行次数，设为k

多循环体

两个运算规则：乘法，加法

空间复杂度的计算

• 空间复杂度S（n)指算法运行过程中所使用的辅助空间的大小。
• 记为：S(n)=O(f(n))
• 辅助空间：除了存储算法本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。
• 算法原地工作是指算法所需的辅助空间是常量，即O(1）。

---

线性表

线性表的逻辑结构

• 线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列。
• 线性表中第一个元素称为表头元素；最后一个元素称为表尾元素。
• 除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继

顺序存储

• 线性表的顺序存储是用一组地址连续的存储单元（比如C语言里面的数组），依次存储线性表中的数据元素。顺序存储的线性表也叫顺序表。
• 存储器每个存储单元都有编号，这个编号就是地址
  
• 通过这个公式，可以计算出顺序表中任一个元素的位置，而且所需要的时间都是相同的，即时间复杂度为O（1），即随机存取

静态建表

管先我们要在存储器中“找块地”，而且是连续的，那么这块存储空间必然有首地址和大小；最后我们要将表中各个元素对号入座，那就要知道有多少元素，也就是表的长度。

• 顺序表需要的三个部分：
  • 1.存储空间的起始位置
  • 2.顺序表最大存储容量
  • 3.顺序表当前的长度
    
• 数组是静态分配的（大小固定）

动态建表

其实存储空间（数组）还可以动态分配，也就是存储数组的空间是在程序执行过程中通过动态分配语句来分配。

• 动态分配并不是链式存储，同样还是属于顺序存储结构，只是分配的空间大小可以在运行时决定

插入

• 算法流程：
  • 在顺序表L的第i（i<=L.length+1)个位置插入新元素e。
    • 如果i的输入不合法，则返回false，表示插入失败；
    • 否则，将顺序表的第i个元素以及其后的所有元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。
• 算法思路：
  • 1.判断i的值是否正确
  • 2.判断表长是否超过数组长度
  • 3.从后向前到第个位置，分别将这些元素都向后移动一位
  • 4.将该元素插入位置i并修改表长
    

删除

算法流程：删除顺序表L中第i（i<=L.length)个位置的元素，成功则返回true，并将被删除的元素用引用变量e返回，否则返回false。

• 算法思路：
  • 1.判断i的值是否正确
  • 2.取删除的元素
  • 3.将被删元素后面的所有元素都依次向前移动一位
  • 4.修改表长
    

顺序存储优缺点

• 优
  • 存储密度大：不需要为表中元素之间的逻辑关系增加额外存储空间。
  • 随机存取：可以快速存取表中任一位置的元素
• 缺
  • 插入和删除操作需要移动大量元素
  • 对存储空间要求高，会产生存储空间的“碎片”

链式存储

线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针。

• 因为每个结点只有一个指针指向下一个结点，故这种结点组成的线性表也叫单链表
• 通常用“头指针”来标识一个单链表，例如Linklist L，那么头指针L就代指一个单链表。
• 单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点。

P.S. 头结点和头指针的区别？
不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息，它是为了方便做的一种处理。

---

P.S. 为什么要设置头结点？
1.处理操作起来方便例如：对在第一元素结点前插入结点和删除第一结点操作与其它结点的操作就统一
2.无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

头插法建表

建立新的结点分配内存空间，将新结点插入到当前链表的表头
头插法建立单链表，读入数据的顺序与生成的链表中结点的顺序是相反的

尾插法建表

建立新的结点分配内存空间，将新结点插入到当前链表的表尾
头插法建立单链表，读入数据的顺序与生成的链表中结点的顺序是相同的

按序号查找节点

按值查找节点

插入&删除

双链表

插入&删除

循环链表

• 循环单链表：循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环
• 从任何一个结点出发都能访问到链表的每一个元素
  • 循环单链表的判空条件不是头结点的后继指针是否为空，而是它是否等于头指针
  • 有时对单链表常做的操作是在表头和表尾进行的，此时可对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高
• 循环双链表：类比循环单链表，循环双链表链表区别于双链表就是首尾结点构成环
  • 在循环双链表L中，尾结点的后继指针指向表头结点，头节点的前驱指针指向表尾结点。
  • 当循环双链表为空表时，其头结点的prior域和next域都等于L。
• 静态链表：静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称为游标。

• 数组第一个元素不存储数据，它的指针域存储第一个元素所在的数组下标。
• 链表最后一个元素的指针域值为-1。

栈

• 栈（Stack)：只允许在一端进行插入或删除操作的线性表。
• 栈顶（Top)：栈中允许进行插入和删除的那一端。
• 栈底（Bottom)：固定的，不允许进行插入和删除的另一端。
• 1.栈是受限的线性表，所以自然具有性关系。
• 2.栈中元素后进去的必然先出来，即后进先出LIFO(Last In First Out)
• 由于栈是受限的线性表，所以顺序栈需要在顺序表的基础上做点修改。
• Top值不能超过MaxSize
• 空栈的判定条件通常定为top==-1，满栈的判定条件通常为top==MaxSize-1,栈中数据元素个数为top+1

共享栈

• 顺序栈的存储空间大小需要事先开辟好，很多时候对每个栈各自单独开辟存储空间的利用率不如将各个栈的存储空间共享
• 栈满的条件：指针top1和top2只相差1，即top1+1==top2

链式栈

• 栈是线性表的特例，线性表的存储结构还有链式存储结构，所以也可以用链表的方式来实现栈。栈的链式存储结构也叫作链栈。
• 每个单链表都有头指针，对于栈来说，栈顶指针也是必须的。
  • 所以可以将头指针当做栈顶指针，所以栈顶放在单链表的头部。
• 1.链栈一般不存在栈满的情况。
• 2.空栈的判定条件通常定为top==NULL；
  

队列

• 队列是只允许在一端进行插入，而在另一端进行删除的线性表
• 队头（Front)：允许删除的一端，又称为队首。
• 队尾（Rear)：允许插入的一端。
• 先进入队列的元素必然先离开队列，
• 即先进先出（First In First Out)简称FIFO

顺序队列

P.S. 实际有空间，但是无法利用的情况被称为假溢出。所以我们可以使用循环队列

• 存在假溢出的问题，使用循环队列解决

循环队列

把数组“掰弯”，形成一个环。Rear指针到了下标为4的位置还能继续指回到下标为0的地方。这样首尾相连的顺序存储的队列就叫循环队列

• 入队：rear=(rear+1)%MaxSize
• 出队：front=（front+1)%MaxSize

此时出现了新的问题，rear和front指针值相同，空队列时front等于rear，现在队列满了也是front等于rear，那如何分辨队列是空还是满呢？

• 方法一：设置标志位flag，当flag=0且rear等于front时为队列空，当flag=1且rear等于front时为队列满。
• 方法二：我们把front=rear仅作为队空的判定条件。当队列满的时候，令数组中仍然保留一个空余单元。我们认为这种情况就是队列满了。
  • 队列满，(rear+1)%Maxsize==front
  • 队列中元素个数：(rear-front+MaxSize)% MaxSize
    

链式队列

• 队列的链式存储结构，其实就是线性表的单链表，只不过需要加点限制，只能表尾插入元素，表头删除元素。

双端队列

• 封闭一端 栈
• 两端各去掉一项操作 队列
• 一端只能删除，另一端可以删除可以插入 输入受限的双端队列
• 一端只能插入，另一端可以删除可以插入 输入受限的双端队列

栈的应用

• 括号匹配
  • 算法思想若是左括号，入栈；若是右括号，出栈一个左括号判断是否与之匹配；检验到字符串尾，还要检查栈是否为空。只有栈空，整个字符串才是括号匹配的。
• 表达式求值
• 规则：从左到右扫描表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈然后跟这个符号进行运算，最后将运算结果进栈，直到最终获得结果。
• 将中缀表达式转换成后缀表达式
  • 1.按运算符优先级对所有运算符和它的运算数加括号。（原本的括号不用加）
  • 2.把运算符移到对应的括号后。
  • 3.去掉括号。
• 前缀表达式其实将运算符提到括号前面，其他都一样
• 递归
  • 如果在一个函数、过程或数据结构的定义中又应用了它自身，那么这个函数、过程或数据结构称为是递归定义的，简称递归。递归最重要的是递归式和递归边界。
  • 使用递归求解n的阶乘 n!=12…*n

• 求斐波那契数列的第N项