nets:[[../else/数据结构]] 课程笔记

1.1 数据结构讨论的范畴

程序设计：为计算机处理问题编制一组指令集
算法：处理问题的策略
数据结构：问题的数学模型

以上几个例子可见，描述这类非数值计算问题的数学模型不耳是数学方程，而是用表、树和图之类的数据结构，这正是数据结构要讨论的问题。
概括地说，数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算)及其上的操作在计算机中如何表示和实现”的学科。

1.2 基本概念

一、数据与数据结构

数据：

所有能被输入到计算机中，且能被计算机处理的符号的集合。
是计算机操作的对象的总称。
是计算机处理的信息的某种特定的符号表示形式。

数据元素：

数据元素：是数据（集合）中的一个“个体”
是数据结构中讨论的基本单位

数据项：

是数据结构中讨论的最小单位
数据元素可以是数据项的集合

数据项：一个数据元素由若干数据项组成
数据元素：组成数据对象的基本单位
数据对象：性质相同的数据元素的集合（类似于数组一般)

数据结构：

带结构的数据元素的集合。或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。

数据结构的形式定义为：

数据结构是一个二元组：Data Structures=(D,S)
其中：D是数据元素的有限集，S是D上关系的有限集。

集合结构

特点：集合结构中的数据元素除了同属于一个集合外，它们之间无其他关系。

树形结构

结点之间关系：一对多。
特点：开始结点惟一，终端结，点不惟一。除终端结点以外，每个结点有一个或多个后继结点；除开始结点外，每个结点有且仅有一个前驱结点。

线性结构

结点之间关系：一对一
特点：开始结，点和终端结点都是惟一的，除了开始结点和终端结点以外，其余结点都有且仅有一个前驱结点，有且仅有一个后继结点。

图状结构

结点之间关系：多对多。
特点：没有开始结点和终端结点，所有结点都可能有多个前驱结点和多个后继结点。

数据的存储结构

一逻辑结构在存储器中的映象
“数据元素”的映象？
数据元素的映象方法：
用二进制位(bit)的位串表示数据元素
(321)10=(501)8=(101000001)2
A=(101)=(001000001)2
“关系”的映象？
顺序映像：以相对的储存位置位置表示后记关系
链式映像：以附加信息（指针）表示后记关系

二、数据类型

数据类型是一个值的集合和定义在此集合上的的一组操作的总称。

抽象数据类型

是一个数学模型以及定义在此数学模型的一组操作

抽象数据类型的描述方法

抽象数据类型可用(D,S,P)三元组表示。
其中：D是数据对象；
S是D上的关系集；
P是对D的基本操作集。

ADT抽象数据类型名{
数据对象：〈数据对象的定义〉
数据关系：〈数据关系的定义》
基本操作：〈基本操作的定义〉》
}ADT抽象数据类型名

其中基本操作的定义格式为：基本操作名（参数表）
初始条件：〈初始条件描述)
操作结果：〈操作结果描述》

赋值参数只为操作提供输入值。
引用参数以&打头，除可提供输入值外，还将返回操作结果。
初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。
操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之

抽象数据类型的表示和实现

抽象数据类型需要通过固有数据类型（高级编程语言中
已实现的数据类型)来实现。

1.3 算法和算法的量度

一、算法

算法是为了解决某类问题而规定的一个有限长的操作序列。

算法必须满足的几个特性

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

二、算法设计的原则

设计算法时，通常应考虑达到以下目标：

正确性
可读性
鲁棒性
高效率与低存储量需求

三、算法设计的衡量方法和准则

通常有两种衡量算法效率的方法：

事后统计法
缺点：

必须执行程序
其它因素掩盖算法本质

事前分析估算法

和算法执行时间相关的因素：

算法选用的策略
问题的规模
编写程序的语言
编译程序产生的机器代码的质量
计算机执行指令的速度

一个特定算法的运行工作量的大小，只依赖于问题的规模(通常用整数量表示)，或者说，它是问题规模的函数，即T(n)=O(f(n))

四、算法的储存空间需求

算法的空间复杂度定义为：
S(n)=O(g(n))
表示随着问题规模的增大，算法运行所需存储
量的增长率与g(n)的增长率相同。

算法的存储量包括：
1.输入数据所占空间
2.程序本身所占空间
3.辅助变量所占空间

总结

数据结构的基本概念
四大逻辑结构
两大物理结构（存储结构）
数据类型
抽象数据类型
算法
算法设计的原则
算法效率的衡量方法
算法的存储空间需求

数据结构第一讲课程笔记——绪论