数据结构介绍

  1. 数据 数据对<br />    数据结构=数据元素+关系

逻辑结构和物理结构

逻辑结构是面向问题的,物理结构是面向计算机的,其目标是将数据及其逻辑结构存储到计算机的内存中
逻辑结构：集合结构，线性结构，树形结构，图形结构
物理结构：顺序存储结构，链式存储结构

研究数据结构都要从逻辑结构和物理结构两方面学习。先直到各种数据结构的逻辑结构，再针对不同的问题考虑其存储到计算机中的物理结构

抽象数据类型
抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。把生活中的问题分解为多个规模小而且易于处理的问题，建立计算机可以处理的数据模型，把每个功能模块的实现细节作为独立的单元，从而使具体实现过程隐藏。

算法

算法的五个特性
算法设计的要求：正确性，算法的正确性大部分情况下都不可能用程序来证明，而是用数学方法证明

算法推导大O阶的方法

线性表

1、定义： 0个或多个元素的有限序列

2、数组长度和线性表长度：数组的长度是不变的，但是线性表的长度是可变的；静态数组在分配之初其长度就已经固定，是其存储空间的长度；线性表的长度是线性表中数据元素的个数，随着插入删除而变化。

3、线性表的逻辑结构和物理结构
线性表的逻辑结构：线性表的每一个元素至多有一个后继，这是线性表和树，图等数据结构的区别
线性表的存储结构有两种：1、顺序存储，2、链式存储；

4、头指针和头结点

栈

顺序栈和链栈的使用
时间复杂度相同，均为O（1）；对于空间性，顺序栈要实现确定长度，可能存在空间浪费，但是定位方便；链栈的指针域增加开销，但长度无限制；若元素变化范围不可预料最好用链栈，若变化范围可控用顺序栈

共享栈的出现和使用场景
由于顺序栈的长度固定的缺点，催生出一个新的数据结构：共享栈。头对头，共享双方的栈空间。使用场景如：股票的买入和卖出。两个栈的空间需求有相反的关系，一个栈在增长时，另一个在缩短。

为何要用栈？
    栈本身也是线性表，只不过栈只能在栈顶push和pop；只能操作一端。不管是顺序栈还是链栈都可以用顺序表和链表代替。但是定义出栈这一数据结构是为了划分关注层次，在针对使用栈这一数据结构的场景下，无需再关心数组内部下标增减的细节问题，更多精力放在栈的使用上。设计到封装的思想。

栈的应用
递归，四则运算表达式求值（后缀）

    栈的递归应用中涉及到溢出攻击；栈的求值涉及到中缀转后缀，再利用后缀和栈求值

递归和迭代的区别
迭代是循环，递归是选择。递归更简洁但是更耗时间内存

队列

循环队列的出现
    当之前插入的元素离开队列，之后的元素无法自动向前补齐，造成假溢出的情况；这就催生出循环队列。循环队列让首尾相接，当出现假溢出时候，新插入的元素将从头部开始插入。

    循环队列是顺序存储，若是使用链式存储则就不会事先固定存储空间大小，存储空间随使用情况而动态变化，也就不会出现假溢出的情况。

循环队列和链式队列的比较
时间上：O（1），循环队列事先申请好空间且无需释放，链式队列会动态申请和释放空间，但差距不大

空间上：循环队列长度固定，存在浪费问题，链式队列更灵活

总而言之：元素变化范围不可预料最好用链式队列，若变化范围可控用循环队列

串

串和线性表的不同
一种不同于线性表的新的数据结构；线性表更关注单个元素的操作，对单个元素的增删改查；而串更多是针对子串的操作，对子串的查找，替换。

串的朴素匹配
    大循环+小循环，时间复杂度：O（m+n）

串的KMP模式匹配
    快速从主串中找子串，比较指针无需回溯。需要使用next数组，且此数组由模式串的特点得出和主串无关。需要利用最长公共前后缀：1、找最长的公共前后缀。2、最长公共前后缀长度要小于比较指针左侧的子串长度。通过找最长公共前后缀得出next数组。由此减少比较次数，避免回溯。

    在java中可用：indexOf()方法 替代

树

结点的存储位置无法直接翻译出逻辑关系；

双亲表示法，孩子表示法，孩子兄弟表示法

双亲表示法：指针域存放双亲位置

图

图和线性表，树的区别
线性表只有一个前驱和一个后继，树打破了这一规则，存在一个前驱，多个后继。图不存在前驱和后继这一概念或者说图存在多个前驱和多个后继。

图的存储结构

为何要使用邻接矩阵，邻接表？
使用简单的顺序存储无法反应图中各结点的关系，只能反应前驱后继；若是使用多重链表，因为若各结点度数相差大则出现大量空指针浪费，若按照每个顶点度数设计又会出现操作不变？？？？？？

邻接矩阵
    用一维数组+二维数组来表示，一维数组来表示顶点，二维数组表示顶点之间的关系（是否连接或权值）

邻接表
    若是稀疏矩阵，则考虑到每个顶点情况的邻接矩阵存储结构就会造成资源浪费。因为邻接矩阵中的一维数组和二维数组都是静态数组，其存储空间都是由输入的顶点数和边数固定，且后续不再改变。

    如此就需要用数组+链表的方式（邻接表）进行存储。类似于树中的孩子表示法。具体做法是：用一维数组（或单链表）存储顶点，每个顶点包含一个数据域和一个指针域，用链表存储每个顶点的邻接点，因为每个顶点的邻接点不固定，遂用单链表存储。

    逆邻接表就把由原先的由出度构造改为由入度构造。

查找
排序