0%
数据结构基本概念
基本概念和术语
- 数据：信息的载体，描述客观事物属性，如数字、字符、所有能输入计算机中识别处理的符号集合
- 数据元素：数据基本单位（数据表中的一行），由数据项组成
- 数据项：数据元素不可分割的最小单位（理解成属性）
- 数据对象：数据元素的集合，数据的子集
- 数据类型：值的集合和定义在此集合上的一组操作的总称
- 原子类型：值不可再分
- 结构类型：值可以再分
- 抽象数据类型：抽象数据组织和操作（即结构和运算）
- 数据结构：存在关系的数据元素的集合
- 数据指数据元素
- 结构指数据元素之间的关系
- 定义数据结构需要数据对象、结构关系、操作运算
数据结构的三要素
- 逻辑结构：独立于计算机（物理存储），从逻辑上描述数据的关系，分为线性结构和非线性结构
- 线性结构（一对一的关系）
- 一般线性表
- 受限线性表：栈、队列、串
- 线性表推广：数组
- 非线性结构
- 集合（属于同集合的关系）
- 树形结构（一对多的关系）：一般树、二叉树
- 图状结构（多对多的关系）：有向图、无向图
- 存储结构：计算机中对数据和关系的表示
- 顺序存储：逻辑相邻的元素在物理上也相邻存储
- 优点：可随机存取、节约空间
- 缺点：只能使用相邻的整块存储单元，容易产生碎片
- 链式存储：逻辑相邻的元素在物理上可不相邻
- 优点：不会出现碎片，充分利用所有存储单元
- 缺点：引入额外指针空间开销、只能顺序存取
- 索引存储：存储信息的同时，维护一个索引表（表的每个索引项包含关键字和地址）
- 优点：搜索速度快
- 缺点：索引表占用额外的存储空间，增删元素时维护索引表需要额外的开销
- 散列存储：根据关键字直接算出存储地址，又叫哈希(Hash)存储
- 优点：检索增删操作快
- 缺点：如果散列函数不好，可能出现大量的冲突，从而增加时间空间开销
- 数据元素：包括运算定义和运算实现
- 定义：针对逻辑结构，指出运算的功能效果
- 实现：针对存储结构，指出运算的操作步骤
算法和算法评价
算法基本概念
- 定义：问题求解步骤的描述，指令的有限序列，指令由若干操作组成
- 特性：
- 有穷性：算法在有穷步结束，每一步在有穷时间完成
- 确定性：相同输入得到相同输入
- 可行性：算法的操作可以通过已有的基本运算执行有穷次实现
- 输入：零个或多个
- 输出：一个或多个
- 目标：
算法效率的度量
- 时间复杂度：假设为问题规模，为频度，则时间复杂度定义为
- 最坏时间复杂度：最坏输入情况下的时间复杂度
- 平均时间复杂度：给定每种输入的概率后算出的时间复杂度期望
- 最好时间复杂度：最好输入情况下的时间复杂度
- 期望时间复杂度：针对随机算法，最坏输入情况下的期望随机复杂度。
- 空间复杂度：定义为算法所耗费的存储空间
- 一般认为输入的空间取决于问题，与算法无关
- 只考虑额外空间即可
- 原地工作算法指额外空间开销为
程序时间复杂度分析技巧
- 循环体变量参与循环条件判断：考虑该变量和循环次数的关系，用循环次数参与循环条件判断
- 循环体变量不参与循环条件判断：数学归纳法或者直接累计
微信支付