三要素
逻辑结构
数据元素之间的逻辑关系。
线性结构
一般线性表
受限线性表(栈和队、串)
线性表推广（数组、广义表）
非线性结构
集合
树形结构（一般树、二叉树）
图状结构（有向图、无向图）
归结为四类
集合：结构中的数据元素之间除了“同属于一个集合”的关系之外，别无其他关系
线性结构：结构中的数据元素之间存在一个对一个的关系
树形结构：结构中的数据元素之间存在一个对多个的关系
图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系
存储结构
数据结构在计算机中的表示（又称映像），也称物理结构
顺序存储
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里。优点是可以实现随机存取（可以直接根据下标找到），每个元素占用最少的存储单元，缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
链接存储
不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系，指针就是下一个元素的地址。优点是不会出现碎片现象，充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存储（只能顺序从第一个开始查找指定元素）
索引存储
在存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：关键字：地址。优点是索引速度快；缺点是增加了附加的索引表，会占用较多的存储空间。另外，在增加和删除数据时要修改索引表，会花费较多的时间
散列存储
根据元素的关键字直接计算出该元素的存储地址，又称hash存储。优点是索引、增加和删除节点的操作都很快；缺点是如果散列函数不好可能会出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
运算
包括插入、删除、修改、查找、排序运算
算法和算法分析
算法
是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
五个重要特性
有穷性
对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即算法中的每个步骤都能在有限时间内完成
确定性
在算法中每一条指令都有确切的含义，不能产生二义性，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。相同的输入之恩呢得到相同的结果
可行性
算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算来有限次实现
有输入
一个算法有零个或多个输入，作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上没有输入，实际上已被嵌入算法之中
可输出
一个算法有零个或多个输出，它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。
时间复杂度
对于输入数据，所执行的基本操作次数最多的情况，为最坏情况，如果没有特殊说明我们要求的都是最坏情况。
含有控制语句函数的时间复杂度分析
一次循环运行时间是循环内语句的运行时间乘以循环次数
嵌套循环运行时间为最内层语句执行次数乘以总循环次数
并列的两个循环运行时间与执行次数数量级大的那个相同
递归函数时间复杂度分析
线性表
基本概念
线性表的逻辑结构
线性表的顺序表示和实现
顺序存储结构-顺序映象
逻辑上两个元素的关系，在物理存储上也要保持
用一组地址连续的存储单元依次存放线性表中的数据元素
所有数据元素的存储位置均取决于第一个数据 元素的存储位置
特点：
表中相邻的两个元素其物理存储位置也相邻；只要确定起始位置，线性表中的任一数据元素都可随机存取。顺序存储结构是一种随机存取的存储结构。
线性表的基本操作在顺序表中的实现
InitList(&L) //结构初始化
LocateElem(L,e,compare()) //查找
ListInsert(&L,i,e) //插入元素
ListDelete(&L,i) //删除元素
