王道408数据结构——第一章 绪论

一、概念

数据结构研究内容

数据结构是一门研究在非数值计算中，计算机的操作对象、对象间关系以及施加于对象的操作的学科。

• 数据元素
  数据的基本单位，可由若干数据项构成。
• 数据项（属性）
  构成数据元素的不可分割的最小单位。
• 数据对象
  具有相同性质的数据元素的集合，是数据的一个子集。
• 数据类型
  值的集合以及对应操作。
  • 原子类型：不可再分
  • 结构类型：可以分解为若干分量
  • 抽象数据类型：抽象数据组织及与之相关的操作。
• 数据结构
  互相之间存在一种或多种特定关系的数据元素的集合。
  • 结构：数据元素之间的关系称为结构，分为逻辑结构、储存结构和运算。
  • 算法的设计取决于逻辑结构，算法的实现取决于存储结构。
• 算法：算法是对待定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。此外，算法还具有有穷性、确定性、可行性、输入和输出五个基本特点。

二、数据三要素

逻辑结构

指数据元素之间的逻辑关系，独立于计算机，与数据元素本身的形式、内容、相对位置、个数无关。分为线性结构和非线性结构。

数据的逻辑结构
线性结构				非线性结构
一般线性表	受限线性表		线性表推广	集合	树形结构		图状结构
	栈和队列	串	数组		一般树	二叉树	有向图	无向图

• 集合:结构中的元素除"同属一个集合外"再无其他关系.
• 线性结构:集合中的元素只存在一对一的关系.
• 树形结构:集合中的元素存在一对多的关系.
• 图(网)状结构:集合中的元素存在多对多的关系.

储存结构（物理结构）

指数据结构在计算机中的表示（映像），依赖于计算机语言，分为顺序存储、链式存储、索引存储和散列存储。

• 顺序存储：
  把逻辑上相邻的元素储存在物理位置也相邻的储存单元中。优点是可以随机存取、每个元素可以占用最少的空间；缺点是可能产生较多的外部碎片。
• 链式存储
  借助指示元素存储地址的指针来表示元素的逻辑关系。优点是不会产生碎片，充分利用储存单元；缺点是指针会占用额外空间、且只能顺序存取。
• 索引存储
  建立附加的索引表，表中每项称为索引项。优点是检索速度快；缺点是索引表占用额外空间、增删数据也要修改索引表，花费较多时间。
• 散列储存（哈希存储）
  根据元素的关键字直接计算出该元素的储存地址。优点是检索、增删元素快；缺点是若散列函数不好，会出现散列冲突

文件的物理记录和逻辑记录间可以存在三种关系：

• 一个物理记录存放一个逻辑记录
• 一个物理记录存放多个逻辑记录
• 多个物理记录存放一个逻辑记录

运算

施加在数据上的运算包括运算的定义和实现。
运算的定义针对逻辑结构，指出运算的功能；运算的实现针对物理结构，针对运算的具体操作步骤。

三、算法和算法评价

算法是对特定问题求解步骤的一种描述，是指令的有限序列。具有以下个重要特性：

1. 有穷性
2. 确定性
3. 可行性
4. 输入
5. 输出

好的算法还要考虑一下目标：

1. 正确性
2. 可读性
3. 健壮性
4. 时空效率

时间复杂度

语句的频度是指起在算法中被执行的次数，算法中所有语句的频度之和记为T(n)，它是算法问题规模n的函数。时间复杂度用于衡量T(n)的数量级。
也指在最坏情况下，估算算法执行时间的一个上界。

算法的时间复杂度不仅依赖于问题的规模，也依赖于待输入数据的性质。一般总是考虑算法在最坏情况下的复杂度。

空间复杂度

该算法耗费的储存空间，是问题规模n的函数S(n)。
算法原地工作是指算法所需的辅助空间为常量。

四、数字相关汇总

算法性能

算法	最好情况	最坏情况	平均情况	占用空间	稳定性
顺序表的插入	$O(1)$	$O(n)$	$\frac{1}{n}$/$O(n)$
顺序表的删除

二叉树相关

图相关

矩阵相关