第一章绪论

绪论

学习资源

101什么是数据结构.pdf

102初识算法.pdf

103算法效率的衡量和评价.pdf

学习笔记

1.1什么是数据结构

例子:

图书馆的书目检索系统自动化问题
计算机和人对弈问题
多叉路口交通灯的管理问题

算法 + 数据结构 = 程序
Alogorithm + DataStructures = Programs

1.2 基本概念和术语

数据：是对客观事物的符号表示
- 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。
- 是计算机操作的对象的总称。
- 是计算机处理的信息的某种特定的符号表示形式。
数据元素：
- 是数据的基本单位
- 是数据（集合）中的一个"个体"
数据项：数据项是构成数据元素的不可分割的最小单位
- 一个数据元素可以由若干个数据项组成
- 是组成数据元素的、具有独立含义的、不可分割的最小单位
数据对象：是性质相同的数据元素的集合，是数据的一个子集
数据结构：
- 数据结构是一门讨论"描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现"的学科。->[概括的说]
- 是带结构的数据元素的集合
- 是相互之间存在一种或多种特定关系的数据元素的集合
- 是一个二元组 -> [形式定义]
  - eg： Data_Structure = ( D , S )
    D ：是数据元素的有限集丨 S ：是D上关系的有限集
- 是从操作对象抽象出来的数学模型 -> [数学描述]
数据类型：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称。
- 原子类型：其值不可再分的数据类型 -> 值的集合+操作 [ int , char , float , etc . ]
- 结构类型：其值可以再分解为若干成分（分量）的数据类型 -> 结构集合+操作 [list , map , etc . ]
- 抽象数据类型：抽象数据组织及与之相关的操作 -> 数据对象 + 数据关系 + 操作

逻辑结构

'Logical Structure & Storage Structure'

                ┌ 集合
	┌ 逻辑结构  —— 线性结构
	|		    ├ 树形结构
	|           └ 图状结构 / 网状结构
DS -|
	|
	|		  	┌ 顺序
	└ 物理结构  ·
			  	└ 链式

 	          ┌ 一般线性表
			  |				┌ 栈和队列
	┌ 线性结构—— 受限线性表  ·
	|		  |		        └ 串
	|		  |
	|		  |			  ┌ 数组
	|         └ 线性表推广 ·
	|					  └ 广义表
DS -|
	|
	|		    ┌ 集合
	|		    |
	|		    |		  ┌ 一般树
	└ 非线性结构——树形结构 ·
				|		  └ 二叉树
				|
				|		   ┌ 有向图
				└ 图状结构 ·
				   		   └ 无向图
						 
Note:
[1] 线性结构: 有且只有一个开始与结束和一个终端结点
[2] 非线性结构: 一个结点，可能有多个直接前驱和直接后继

[逻辑结构] -> [算法设计]
 映 ☟ 射		  ☟
[存储结构] -> [算法实践]

存储结构

顺序映像：

以相对的存储位置表示后继关系

链式映像：

以附加信息(指针)表示后继关系

表头	顺序存储结构	链式存储结构
优点	存储密度大（＝1）存储空间利用率高	插入或删除元素时很方便使用灵活
缺点	插入或删除元素时不方便	存储密度小（<1）存储空间利用率低
不同	顺序存储结构的内存地址一定是连续的	链表存储结构的内存地址不一定是连续的
相同

适用情况

顺序表适宜于做查找这样的静态操作；
链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

抽象数据类型

原子类型
固定聚合类型
可变聚合类型

抽象数据类型可用（D, S, P）三元组表示。

D : 是数据对象；
S : 是 D 上的关系集；
P : 是对 D 的基本操作集。

抽象数据类型定义

抽象数据类型的定义格式:
ADT 抽象数据类型名 {
	数据对象: <数据对象的定义>
	数据关系: <数据关系的定义>
	基本操作: <基本操作的定义>
} ADT 抽象数据类型名 

---------------------

数据对象和数据关系的定义用伪代码描述

基本操作的定义格式:	
基本操作名(参数表)
	初始条件: <初始条件描述>
	操作结果: <操作结果描述>

ADT：两个重要特点

数据抽象：
用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
数据封装：
将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

1.3 抽象数据类型的表示与实现

[C/C++]

1.4 算法和算法分析

1.4.1 算法

算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

算法特征:

有穷性：一个算法必须总是（对任何合法的输入值）执行有穷步之后结束，且每一步都可以在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义，算法只有唯一的一条执行路径。
可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
输入与输出

1.4.2 算法设计的要求

正确性："正确"一词的含义在通常的用法中有很大的差别，大体上可分为以下4个层次：
1. 程序不含语法错误。
2. 程序对于几组输入数据得出满足规格说明要求的结果。
3. 程序对于精心选择的典型、苛刻而带有发难性的几组输入数据能够得出满足规格说明要求的结果。
4. 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。

显然，达到第 4 层意义下的正确是极为困难的，所有不同输入数据的数量大得惊人，逐一验证的方法是不现实的。对于大型软件需要进行专业测试，而一般情况下，通常以第 3 层意义的正确性作为衡量一个程序是否合格的标准。

可读性

算法主要是为了人的阅读与交流，其次才是机器执行。
可读性好有助于人对算法牟理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。

健壮性

当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生黄晓明其妙的输出结果。例如，一个求凸多边形面积的算法，是采用求各三角形面积之和的策略来解决问题的。当输入的坐标集合表示的是一个凹多边形时，不应继续计算，而应报告输入出错。并且处理出错的方法应是返回一个表示错误或错误性质的值，而不是打印错误信息或异常，并中止程序的执行，以便在更高的抽象层次上进行处理。

效率与低存储量需求

通俗地说，效率指的是算法执行的时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求算法执行过程中所需要的最大存储空间。效率与低存储量需求这两者都与问题的规模有关。求 100 个人的平均分与求 1000 个人的平均分所花的执行时间或运行空间显然有一空差别。

1.4.3算法效率的度量

事后统计法：

依据算法编写出程序，不同算法的程序可通过一组或若干组相同的测试数据，利用计算机内部的计时功能来分辨其优劣。
缺陷:
- 必须依据算法实现编制好测试程序
- 不同测试环境差别不是一般的大

事前分析估算法：

通过对算法本身的分析，计算出算法的时间性能。
消耗的时间取决于下列因素：

算法采用的策略和方案
编译产生的代码质量
问题的输入规模
机器执行指令的速度

1.4.4 算法的存储空间需求

一个算法的存储量包括形参所占空间和临时变量所占空间。
在对算法进行存储空间分析时，只考察临时变量所占空间。

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

补充

数据结构中，一组数据中的每个个体被称为"数据元素"（简称"元素"）。

另外，对于具有"一对一"逻辑关系的数据，我们一直在用"某一元素的左侧（前边）或右侧（后边）"这样不专业的词，其实线性表中有更准确的术语：

某一元素的左侧相邻元素称为直接前驱，位于此元素左侧的所有元素都统称为前驱元素;
某一元素的右侧相邻元素称为直接后继，位于此元素右侧的所有元素都统称为后继元素;

课后练习

以下属于逻辑结构的是（）.

A：顺序表

B：哈希表

C：有序表

D：单链表
以下与数据的存储结构无关的术语是（）.

A：循环队列

B：链表

C：哈希表

D：栈
以下关于数据结构的说法中，正确的是（）.

A：数据的逻辑结构独立于其存储结构

B：数据的存储结构独立于其逻辑结构

C：数据的逻辑结构唯一决定了其存储结构

D：数据结构仅由其逻辑结构和存储结构决定
链式存储设计时，结点内的存储单元地址（）.

A：一定连续

B：一定不连续

C：不一定连续

D：部分连续，部分不连续
与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）.

A：存储结构

B：存储实现

C：逻辑结构

D：运算实现