数据结构：

　　数据元素的集合（数据对象）及元素间的相互关系（逻辑结构）、构造方法

　　目标：学会从问题出发，分析、研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构、相应的操作方法，为提高用计算机解决问题的效率服务。

　　是算法设计的基础。

　　按逻辑关系分类：线性结构、非线性结构（树结构、图结构）　　

1.线性结构

　　对客观世界中具有单一的前驱、后继的数据关系进行描述

　　特点：数据元素之间呈现一种线性关系，即元素"一个接一个地排列"

　　存储方法：

　　　　1.顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素

　　　　

　　　　插入时移动的概率：

　　　　删除时移动的概率：

　　　　2.链式存储：用节点来存储数据元素

　　　　节点：。数据域：存储数据元素的值；指针域：指针，链。存储直接前驱、直接后继的信息

　　　　不能对数据随机访问，但是插入、删除不需要移动元素

　　　　分类：线性链表、双向链表、循环链表、静态链表

　　　　线性链表：单链表。节点中只有一个指针域

　　　　添加、删除：

 　　　  示例：

　　　　

　　　　

　　　　

　　　　

　　　　

　　栈：“后进先出”。只能通过访问它的一端（栈顶）来实现数据存储、检索的一种线性数据结构

　　　　相关概念：栈底、空栈

　　　　存储结构：

　　　　1.顺序存储：预先定义，容量有限，插入需判断是否栈满

　　　　2.链式存储：不必设置头节点，链表的头指针就是栈顶指针

　　　　

　　队列：“先进先出”。只允许在表的一端（队尾）插入元素，另一端（队首）删除元素

 　　　 存储结构：

　　　　1.顺序存储：预先定义，容量有限，插入需判断队尾指针是否到达上限。

　　　　　　队列空、满，队头、队尾都指向相同的位置，区分？：1.设置标志位，指示队列空？满？2.牺牲一个存储单元，约定以“队尾指针所指的位置的下一个位置是队头指针”，表示队满

　　　　

　　　　

　　　　2.链式存储：链队添加一个头节点，并另头指针指向队头

　　　　　　队列空、满，队头、队尾都指向相同的位置，区分？：头指针和尾指针的值相同，且均被头节点指向，则为空

　　　　

　　　　示例：

　　　　

　　　　

 

 　　串（字符串）：一种特殊的线性列表，数据元素为字符。

　　　　仅由字符构成的有序序列，是取值范围受限的线性表

　　　　相关概念：空串、空格串、字串、串相等、串比较（ASCII码值比较，第一个值开始比较，相等则继续比较第二个值）

　　　　存储结构：

　　　　1.定长存储：静态存储、顺序存储。可事先定义存储空间，也可根据串长的需要动态申请字符串的空间

　　　　2.链式存储：每个节点可以存储一个字符、多个字符。节点大小决定对串的处理效率

　　　　匹配模式：子串的定位操作

　　　　1.朴素的模式匹配算法：布鲁特-福斯算法。从第一个位置比较，相等，则逐字对后续字符比较。不等，则从第二个位置比较。

　　　　

　　　　最好情况下匹配：，时间复杂度 O(m+n)

　　　　最坏情况下匹配：，时间复杂度 O(m*n),因为n>>m

　　　　2.改进的模式匹配算法：KMP算法。匹配结果不相等，不需要回溯主串的字符位置指针，而是利用已经得到的“部分匹配”结果，将其向右“滑动”尽可能远的距离，再继续进行比较 

　　　　原理：一句模式串的next函数值实现子串的滑动。若next[j]=k,表示当模式串中的Pj与主串中相应的字符不想等时令模式串的Pk与主串的相应字符进行比较。

　　　　

　　　　示例：

　　　　？？？？

　　　　

　　　　

 

2.数组、矩阵、广义表

数组：定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。n维数组是一种“同构”的数据结构，其每个数据元素类型相同，结构一致

　　特点：

　　1.数目固定，一旦定义了一个数组结构，就不再有元素个数的增减变化。

　　2.数据元素具有相同的类型

　　3.数据元素的下标关系具有上下界的约束且下标有序

　　存储：顺序存储

　　　　why：数组一般不做插入、删除运算，一旦定义，数据个数、元素间关系不再发生变动。

　　　　how：计算机内存结构是一维线性的，因此多维数组必须今年习惯降维处理，将数组元素排列成一个线性序列

　　　　　　一旦确定了维数、各维长度，便可为它分配存储空间

　　　　　　存储结构：以行为主序，以列为主序

　　　　　　

　　　　　　a[m,n]的存储地址计算：或

矩阵：

　　为了节省存储空间，可以对矩阵进行压缩：多个值相同的元素只分配一个存储单元，对0不分配存储单元

　　分类：

　　1.特殊矩阵：矩阵中元素的分布有一定的规律。

　　包括：对称矩阵、三角矩阵、对角矩阵……

　　n阶对称矩阵：n²个元素存放在 n（n+1）/2 个元素udall存储空间中

　　　　（1<=k<=n(n+1)/2）

　　对角矩阵：所有非0元素都集中在以主对角线为中心的带状区域中，其余元素都为0

　　　　   (1<=k<=3n-2)  ？？？

　　2.稀疏矩阵:非0元素的的个数远远少于0元素的个数，且非0元素的分布没有规律

　　　　常用的顺序存储结构：三元组顺序表

　　　　常用的链式存储结构：十字链表

　　　　

　　　　三元组表：

广义表：由0个或多个单元素或子表组成的有限序列。是线性表的推广

　　表头：非空表的第一个元素

　　表尾：除表头外，其余元素构成的表

　　特点：

　　1.多层次结构。元素的可以是子表，子表的元素还可以是子表

　　2.可被其他广义表共享。元素可以是已经定义的广义表的名字

　　3.一个递归的表。元素可以是本广义表的名字

　　存储结构：链式存储结构

　　　　why：元素本身又可以具有结构，是一种带有层次的非线性结构

　　　　

树：非线性结构

　　递归的（元素可由子树构成，子树又更小的子树构成）

　　元素间有明显的层次关系

　　凡是分等级的分类方案都可以用具有严格层次关系的树结构来描述。

　　

　　二叉树：树节点最大度为2。要区分左子树、右子树

　　　　

　　　　

　　　　存储结构：

　　　　1.顺序存储：多用于完全二叉树。

　　　　一般二叉树也要完全按照完全二叉树的形式存储，因此要添加许多并不存在的“虚结点”，造成空间浪费

　　　　

　　　　2.链式存储：三叉链表、二叉链表

　　　　

　　　　遍历：先序、中序、后序。

　　　　　　树中每个节点，且仅访问一次。

　　　　　　对一个非线性结构进行线性化的过程

　　　　

　　　　

　　　　时间复杂度O（n）

　　　　借助一个栈，可将二叉树的递归遍历算法转换为非递归算法

　　　　

　　　　

　　　　层序遍历

　　　　

　　线索二叉树：在每个节点中增加两个指针来存放前驱、后继信息。缺点：降低存储空间的利用率

　　　　why：二叉链表存储结构中，只能找到一个节点的左、右孩子，不能直接得到节点在任一遍历序列中的前驱、后继，这些信息只有在遍历的动态过程中才可以得到。

 

 

　　　　

 

 

 

 

 

　　　　

 

 

　　　　

 

　　　　

 

 

 

 

 

 

 

 

 

　　　　　　

　　

3.树

4.图

5.查找

6.排序