数据结构概述

基本概念

数据

信息载体

数据元素、数据项

对象与属性的关系

数据对象、数据结构

数据对象 是相同性质的 数据元素的集合数据结构 是具有特定关系的 数据元素的集合

数据类型、抽象数据类型(ADT)

抽象数据类型是抽象 数据组织 及与之相关的 操作ADT定义数据逻辑结构、定义运算，也就是定义了一个数据结构ADT=（数据对象，数据关系，基本操作集）

三要素

逻辑结构

1. 元素之间是一对一、一对多、多对多的关系 2. 与数据存储无关 集合线性结构树形结构图状结构

物理结构

1. 数据结构在计算机中的表示/映像 2. 包括数据元素的表示、关系的表示 3. 确定了存储结构，也就确定了逻辑结构 顺序存储链式存储索引存储散列存储

数据运算

运算定义

针对逻辑结构

运算实现

针对物理结构

算法

算法特性

有穷性确定性可行性输入输出

“好”算法

正确性健壮性可读性效率高与低存储

度量

时间复杂度

O(1) < O(logn) < O(n )< O(nlogn) < O(n^2) < O(n^3) < O(2^n )< O(n!) < O(n^n)乘法规则：*O(mn)=O(m)O(n)加法规则：O(m+n)=O(m)+O(n)=max{O(m),O(n)}

空间复杂度

原地工作，是指算法所需的辅助空间为常量，即O(1)