优秀课件笔记之什么是数据结构

1、本文所以内容来自 著名高校课件和学生笔记（校园里面经常见到有人高价买笔记）
2、任课教师不会提供参考文献，所以只能对作者表示感谢，如果引用了您的作品，可以用回复方式补充参考文献。
3、我不对文章无关问题进行解答，文章内容也比较难，我也很难解答您遇到的问题，如果发现BUG可以用回复方式帮我修正。

第一章 绪 论
1.1 什么是数据结构
1.2 基本概念和术语
1.3 抽象数据类型的表示与实现
1.4 算法和算法分析
1.4.1 算法
1.4.2 算法设计的要求
1.4.3 算法效率的度量
1.4.4 算法的存储空间的需求
计算机的程序是对信息进行加工处理。信息的表
示和处理直接关系到程序的效率。在大多数情况下，
信息（数据）之间往往具有重要的结构关系，这就是
数据结构的内容。
 例1、电话号码查询系统：设有一个电话号码薄，它记
录了N个人的名字和其相应的电话号码，假定按如下形
式安排：(a1，b1) (a2，b2)…(an，bn)
其中ai，bi (i=1，2…n) 分别表示某人的名字和对应的
电话号码。要求设计算法：（1）当给定任何一个人的
名字时能够给出此人的电话号码；（2）加入一个新的
人的名字和其相应的电话号码；（3）删除一个不需要
的人的名字和其相应的电话号码。
1.1 什么是数据结构1.1 什么是数据结构
算法的设计，依赖于计算机如何存储人的名字和对应
的电话号码，或者说依赖于名字和其电话号码的结构。
数据结构就是研究数据的逻辑结构和物理结构以及它
们之间相互关系，并对这种结构定义相应的运算。
 数据结构的三个方面：
1 逻辑结构—数据之间的逻辑关系
2 物理结构—数据在计算机中如何表示
3 运算
 问题逻辑结构（模型）物理结构（存储）
运算（算法）
 数据(Data):是对信息的一种符号表示。在计算机科
学中是指所有能输入到计算机中并被计算机程序处理
的符号的总称。
 数据元素(Data Element):是数据的基本单位，在计算
机程序中通常作为一个整体进行考虑和处理。
一个数据元素可由若干个数据项组成。数据项是
数据的不可分割的最小单位。
 数据对象(Data Object)：是性质相同的数据元素的集
合。是数据的一个子集。
1.2 基本概念和术语
 数据结构(Data Structure)：是相互之间存在一种或多
种特定关系的数据元素的集合。数据之间的相互关系
称为逻辑结构。通常分为四类基本结构：
1、集合 数据元素除了同属于一种类型外，别无其它
关系。
2、线性结构 数据元素之间存在一对一的关系。
3、树型结构 数据元素之间存在一对多的关系。
4、图状结构 数据元素之间存在多对多的关系。
1.2 基本概念和术语
集合线性结构树形结构图状结构
数据结构的形式定义为：
Data-Structure=(D，S)
其中，D是数据元素的有限集，S是D上关系的有限集。
例： 复数的数据结构定义如下：
Complex=(C，R)
其中，C是含两个实数的集合﹛C1，C2﹜，分别表示
复数的实部和虚部。R={P}，P是定义在集合上的一种
关系{〈C1，C2〉}。
1.2 基本概念和术语
 数据结构在计算机中的表示称为数据的物理结构，又
称为存储结构。数据结构在计算机中有两种不同的表
示方法：
 顺序存储结构:用数据元素在存储器中的相对位置来
表示数据元素之间的逻辑关系。
 链式存储结构：在每一个数据元素中增加一个存放地
址的指针，用此指针来表示数据元素之间的逻辑关系。
1.2 基本概念和术语
 数据类型：在一种程序设计语言中，变量所具有的数
据种类。
例：C语言的数据类型：基本类型和构造类型
基本类型：整型、浮点型、字符型
构造类型：数组、结构、联合、指针等
 数据对象是某种数据类型元素的集合。
例：整数的数据对象是{…-2，-1，0，1，2，…}
英文字符类型的数据对象是{A，B，C，D，E，F，…}
 数据对象可以是有限的，也可以是无限的。
 数据结构不同于数据类型，也不同于数据对象，它不
仅要描述数据类型的数据对象，而且要描述数据对象
各元素之间的相互关系。
1.2 基本概念和术语
 抽象数据类型：一个数学模型以及定义在该模型上
的一组操作。
　　 抽象数据类型实际上就是对该数据结构的定义。
因为它定义了一个数据的逻辑结构以及在此结构上
的一组算法。
　　 用三元组描述如为：（Ｄ，Ｓ，Ｐ）
其中D是数据对象，S是D上的关系集，P是对D的基
本操作集。
1.2 基本概念和术语
 预定义常量和类型
 typedef
 算法用函数描述
 赋值语句
 选择语句
 循环语句
 结束语句
 输入输出语句
 注释
 基本函数
 逻辑运算
1.3 抽象数据类型的表示和实现
1.4.1 算法
 算法：一个有穷的指令集，这些指令为解决某一特定
任务规定了一个运算序列。
 算法的特性：
（1）有穷性 算法应在执行有穷步后结束
（2）确定性 每步定义都是确切、无歧义的
（3）可行性 算法由可实现的基本运算构成
（4）输入 有0个或多个输入
（5）输出 有一个或多个输出(处理结果)
1.4 算法和算法分析
1.4.2 算法设计的要求
(1) 正确性(Correctness ) 算法应满足具体问题的
需求。
(2) 可读性(Readability) 算法应该好读。以有利于
阅读者对程序的理解。
(3) 健壮性(Robustness) 算法应具有容错处理。当
输入非法数据时，算法应对其作出反应，而不是产
生莫名其妙的输出结果。
(4) 效率与存储量需求 效率指的是算法执行的时
间；存储量需求指算法执行过程中所需要的最大存
储空间。这两者与问题的规模有关。
1.4 算法和算法分析
1.4.3 算法效率的度量
 事后测试 采用时间函数计算此算法的执行时间。
 事先分析 算法的运行时间通常取决于以下因素：
a. 算法选用的策略
b. 问题的规模
c. 使用的程序语言
d. 编译程序所产生的机器代码的质量
e. 机器执行指令的速度
1.4 算法和算法分析
 定义：如果存在两个正常数c和n0，对于所有的
n≧n0，有|f(n)|≦ c|g(n)|︳
则记作 f(n)=O(g(n))　　
一般情况下，算法中基本操作重复执行的次数
是问题规模n的某个函数，算法的时间量度记作
T(n)=O(f(n))，称作算法的渐近时间复杂度。
 例1 {++x;s=0;} 将x自增看成是基本操作，则语
句频度为１，即时间复杂度为Ｏ(1)。如果将s=0也
看成是基本操作，则语句频度为２，其时间复杂度
仍为Ｏ(1)，即常量阶。
1.4 算法和算法分析
 例2 for(i=1;i<=n;++i)
{++x;s+=x;}
语句频度为2n，其时间复杂度为O(n)，即线性阶。
 例3 for(i=1;i<=n;++i)
　　　　 for(j=1;j<=n;++j)
{++x;s+=x;}
语句频度为：2n2，其时间复杂度为：O(n2)。
即时间复杂度为平方阶。
 定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一
个m次多项式，则A(n)=O(n m)　证略。
1.4 算法和算法分析
 例4 for(i=2;i<=n;++i)
for(j=2;j<=i-1;++j)
{++x;a[i][j]=x;}
语句频度为：1+2+3+…+n-2=(1+n-2) ×(n-2)/2
=(n-1)(n-2)/2 = n2-3n+2
∴时间复杂度为O(n2)
即此算法的时间复杂度为平方阶.
一个算法时间为O(1)的算法，它的基本运算执行的
次数是固定的。因此，总的时间由一个常数（即零次多
项式）来限界。而一个时间为O(n2)的算法则由一个二
次多项式来限界。
1.4 算法和算法分析
 以下是最常用的计算算法时间的多项式，其关系为：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<
O(2n)<O(n!)<O(nn)
0
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
0 1 0 2 0 3 0 4 0
系列1
系列2
系列3
系列4
系列5
2n 2 5n2
100n
200log2n
n3
1.4 算法和算法分析
 有的情况下，算法中基本操作重复执行的次数还随
问题的输入数据集不同而不同。例如：
void bubble-sort(int a[]，int n)
{ for(i=n-1;change=TURE;i>1 && change;--i)
{ change=false;
for(j=0;j<i;++j)
if (a[j]>a[j+1])
{ a[j] ←→a[j+1]; change=TURE}
}
}
 最好情况：0次
 最坏情况：1+2+3+…+n-1=n(n-1)/2
 平均时间复杂度为:O(n2)
1.4 算法和算法分析
1.4.4 算法的存储空间需求
空间复杂度:算法所需存储空间的度量，记作:
S(n)=O(f(n))
其中n为问题的规模(或大小)。
例：数组逆序问题。
算法1：for(i=0; i<n; i++) b[n-i-1]=a[i];
for(i=0; i<n; i++) a[i]=b[i];
该算法需额外使用n个存储单元，S(n)=O(n)
算法2：for(i=0; i<n/2; i++)
{ x=a[i]; a[i]=a[n-i-1]; a[n-i-1]=x; }
该算法需额外使用1个存储单元，S(n)=O(1)