导图社区 《数据结构》第一章-绪论
《数据结构》第一章-绪论知识梳理，包括数据结构的基本概念、算法和算法评价两部分内容。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
绪论
数据结构的基本概念
1. 基本概念和术语
数据
信息的载体，描述客观事物属性的数
数据元素
数据的基本单元，由若干数据项组成
数据项：构成数据元素的最小单位
数据对象
具有相同性质的数据元素的集合
数据类型
原子类型
结构类型
抽象数据类型
抽象数据组织及与之相关的操作
数据结构
相互之间存在一种或多种特定关系的数据元素的集合
2. 数据结构的三要素
逻辑结构：数据元素之间的逻辑关系
线性结构
集合
树形结构
图状结构（网状结构）
存储结构：数据结构在计算机中的表示（又称映像），又称物理结构
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
优点：可以实现随机存取，占用存储空间少
缺点：只能使用相邻的一整块存储单元，可能产生外碎片
链式存储：借助指示元素存储地址的指针来表示元素之间的逻辑关系
优点：不会出现碎片，充分利用所有存储单元
缺点：指针占用额外空间，且只能实现顺序存取
索引存储：在存储元素信息的同时，还建立附加的索引表
优点：检索速度快
缺点：索引表占用额外空间；增删数据时需修改索引表，更费时
散列存储（哈希存储）：根据元素的关键词直接计算出该元素的存储地址
优点：检索、增删结点操作都很快
缺点：若散列函数不好，则可能出现元素存储单元冲突，造成额外的时空开销
数据的运算
运算的定义
针对逻辑结构，指出运算的功能
运算的实现
针对存储结构，指出运算的具体操作步骤
算法和算法评价
概念
定义：算法是对特定问题求解步骤的一种描述，是指令的有限序列
特征
有穷性
确定性
可行性
输入
输出
目标
正确性
可读性
健壮性
效率与低存储量需求
算法效率的度量
时间复杂度
基本公式：
T(n)——算法中所有语句的频度之和
f(n)——算法中基本运算的频度
O——数量级
公式定义：若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和n0，使得当n>=n0时，都满足0=<T(n)=<Cf(n)
分类
最坏时间复杂度
平均时间复杂度
最好时间复杂度
运算规则
a. 加法规则
b. 乘法规则
常见的渐进时间复杂度
空间复杂度
定义：算法耗费的存储空间
公式：
算法原地工作是指算法所需的辅助空间为常量，即O(1)
