数据结构

计算机网络的坑还没有填完，于是我决定开个新坑。

二刷完了数据结构，来一个粗暴的整理。

高能慎入，只是简单的总结，并没有复杂的推导过程和代码。

数据结构

程序设计 = 算法 + 数据结构。

数据 ：描述事物的符号，可以输出计算机并处理。

数据元素 ：组成数据的有意义的基本单位。人群中的数据元素就是人。

数据项 ：描述数据元素的最小单位，不可切分。

数据对象 ：性质相同的数据元素的结合，是数据的子集。

数据结构 ：相互之间存在一种或多种特定关系的数据元素的集合。

数据类型 ：性质相同的值的集合及定义在上面的操作。

抽象数据类型 ：一个数学模型及在上面的操作。

逻辑结构面向问题，物理结构面向计算机

逻辑结构

图、树、集合、线性结构。线性结构中常用的为：队列、栈、线性表。

物理结构

顺序存储 ：如数组，逻辑关系和物理关系对应。

链式存储 ：逻辑关系和物理关系无关，逻辑相邻，物理不相邻。靠存储单元中的指针指向下一个地址。

算法

算法的特性

输入输出 ：可以没有输入，但至少有一个输出

有穷性 ：可接受的时间内求解

确定性 ：对于任何输入或相同输入，得到唯一确定的解

可行性 ：有限步骤内求解问题

算法的目标

正确性 ：算法的输出是正确的，通常用数学的方法证明

可读性 ：通俗易懂

健壮性 ：面临任何极端输入，都能得到确定的输出

时间存储 ：算法执行时间快，需要的存储空间少

时间复杂度

算法的渐进增长取决于最高项，执行次数$T(n)$是关于问题规模$n$的函数，$T(n)=O(f(n))$，增长率和$f(n)$相同，称为渐进时间复杂度，也叫时间复杂度，只保留最高项，出去常熟和系数。

最坏情况的时间复杂度是算法的保证，代码中辅助存储空间的空间复杂度一律为$O(1)$。

线性表

零个或多个相同类型的数据元素组成的有限序列（一个数据元素可以包括多个数据项）。

顺序结构 ：存取为$O(1)$，不能为逻辑关系的增加设置额外的存储空间。插入与删除为$O(n)$，主要是元素的移动。难以确定容量，可能会造成内存空间的碎片。

链式结构 ：头指针指向下一个元素，最后节点的指针为空。存取的复杂度为$O(n)$，并不知道元素的位置在哪里，插入删除的时间复杂都为$O(1)$。整表的删除与创建，头插入，尾插入，需要借助两个指针。

静态链表 ：数组表示链式线性表。使用数组式结构体，每个数组有两个值，一个表示本节点的值，一个表示下一个节点在数组中的位置。

循环链表 ：尾指针指向头指针。

双向链表 ：节点加入前驱后继。

栈

也属于线性表，只能在表尾进行插入和删除，表尾也是栈顶。顺序存储使用数组，链式存储使用指针，结构体存储指向自己的指针和值。

两栈共享空间，当两个栈顶指针重合时栈溢出。

栈的应用，递归。递归易懂，但是迭代不用占用额外的存储空间。

递归 , 每次递归都会产生调用栈，不在可执行文件中，在执行时创建。调用栈所在的段为 堆栈段 ，有自己的大小不能越界访问，否则为段错误。每次递归会在 调用栈 里增加一个栈帧，越界后的错误为栈溢出。

后缀表达式的应用 ：也称为逆波兰表达式，Reverse Polish Notation。无括号表达式。数字压栈，遇到操作符取出来，后者操作前者。

中缀表达式转后缀 ：是正常的小学算术的四则运算。1.数字直接输出。2.遇到 ) ，输出遇到第一个 ( 之间所有的符号。3. ( 直接压栈。4.后来者优先级高则压栈，优先级低，弹两个。完成转后缀表达式。

队列

一端进，一端出，先进先出。如操作系统的任务序列，键盘输入到记事本的显示同样为队列。简单的顺序存储会造成存储资源的浪费，循环队列可以对空白位置利用。位置计算 (rear+1)%QueueSize==front 。链式结构同样，先进先出，包括了指针与值。

串

零个字符或多个字符组成的有限序列，序列表明了元素的前驱后继的关系。

子串的位置 ：子串对应到主串中，第一个字符的位置。

顺序存储 ：”\0”表示结束，不计入长度。

链式存储 ：一个节点可以存储多个字符。

朴素匹配 ：最好的复杂度为$O(1)$，平均复杂度为$O(m+n)$，最坏为$O((n-m+1)\cdot m)$

KMP匹配 ：