严密数据结构课件第一章资料
重电教务系统
湘潭大学信息工程学院
石跃祥教授
15367149988
助教：喃红娟18673238738
工学楼北栋307
现状目标正常
学习
加倍努力
学习兴趣
不浓
1.1数据结构讨论范畴
1.2基本概念
1.3算法和算法尺度
1.1数据结构讨论范畴
(数据结构在软件开发中的地位)
系统分析
系统设计
系统的实现
系统维护
Niklaus Wirth
algorithmdatastructures=programs
编程：
算法：
数据结构：
为计算机处理问题而编制
指令集
应对问题的战略
问题的数学模型
结构静力分析计算
例如：数值计算的编程问题
(线性代数方程
(环流模式方程
(球面坐标系)
全球天气预报
非数值计算的编程问题
例：求一组(n个)整数中的最大值
算法：
模特？
基本操作是“比较两个数的大小”
取决于整数值的范围
例2 :酒店客房管理
算法？
模特？
先进先出
队列
例3 :铺设城市煤气管道
算法？
模特？
如何规划总投资
费用最高吗？
照片
概括地说，
数据结构是“说明现实”的讨论
世界实体的数学模型(非数值计算) ) )。
和的操作在计算机中是如何表化的
“表示与实现”的学科。
1.2基本概念
一.数据和数据结构
二.数据类型
三.抽象数据类型
一.数据和数据结构
可以输入计算机，可以计算
机器处理的符号(数值、字符等)的集合。
数据：
是计算机操作对象的总称。
是计算机处理的信息的特定符号
号码表示形式。
数据(集合)中的“个”
“身体”在计算机中通常作为一个整体
进行方面的考虑和处理。 在数据结构中
讨论的基本单位。
数据要素：
例如：整数"5"、字符" n "等。
---不可分割的“原子”
每一笔钱都叫做“数据项”
这是在数据结构中讨论的最小单位
数据元素也可以由几个钱组成。
例如，描述某个学生的数据元素
称为组合项
年月日
姓名学号班号性别出生年月日入学成绩
原子项
数据结构：
结构化数据元素的集合
有具有相同特性的数据要素的集合，
如果数据元素之间有一种或多种类型
特定的关系称为数据结构。
指数据元素之间存在的关系
例如，在使用三个4位十进制数表示1的情况下
包含12位十进制数时，
314、6587、9345a1(3214 )、a2 ) 6587 )、a3 ) 9345 )
存在于数据要素a1、a2和a3之间
“顺序”关系a1、a2、a2、a3
3214、6587、93456587、3214和9345
例如：
a1 a2 a3 a2 a1 a3
另外，在2行3列二维排列中为6个要素
{a1，a2，a3，a4，a5，a6}
之间有两种关系：
行顺序关系：
row={，}
col={，}
a1 a2 a3
a4 a5 a6
列顺序关系：
在六个数据元素{a1、a2、a3、a4、a5、a6}中
之间有以下顺序关系：
{|I=1，2，3，4，5 }
数据结构相互之间有某种逻辑关系
的数据元素的集合。
这样，不同的“关系”构成了不同的“结构”
构成一维数组的定义。
从关系或结构上来看，数据结构可以归纳如下
以下4种：
线性结构
树结构
图表结构
集合结构
数据结构包括“逻辑结构”和“物理接合”
“结构”的两个方面(层次) :
逻辑结构是数据元素之间的逻辑关系
请参照的说明。 数据元素的集合和
定义并表示此集合上的几个关系；
物理结构是逻辑结构在计算机中的表示
为了实现，也称为“存储结构”。
数据结构的格式定义描述为：
数据结构是二维的组
Data_Structures=(D，s )
其中，D是数据元素的有限集合，
s是d上关系的有限集合。
例如，将：“班集体”定义为一个数据结构
类=(d，s ) )。
D={ a，b1，…，bn，c1，…cn，d1，…dn }
S={ R1，R2}
R1={，}
R2={，
| j=2，3，…，n }
数据的存储结构
——逻辑结构的内存中的映像
数据元素的图像？
“关系”的形象？
如何映射数据元素：
用二进制位的位串表示数据元素
(321 ) 10=) 501 )8=(10100001 ) 2
a=(101 )8=) 00100001 ) 2
的关系映射方法： (表示x，y的方法) )
顺序影像
在相对存储位置上显示后续关系
例如：命令y存储位置和x的存储位置的
有一个常数c的差
c是默认值，在整个存储结构中
包括数据要素本身的信息
x y
链图像
用追加信息(指针)表示继承关系
需要和x在一起的其他信息
指示y的存储位置
y x
在不同的编程环境中，
存储结构有不同的描述方法。
用高级编程语言进行编程时，
通常可以使用高级编程语言提供的数据
类型说明。
例如：
用有顺序关系的三个整数表示
长整数时，可以用c语言提及
的整数数组类型，
typedef int Long_int [3]
定义长度整数为：
typedef struct {
int y； //年号Year
int m； //月号Month
int d； //日号
} DateType； //日期类型
将日期定义为：
将“学生”定义为：
typedef struct {
char id[8]； //学号
char name[16]； //名称
char sex； //性别‘m/f’:男/女
DateType bdate； //生日
} Student； //学生类型
二.数据类型
在用高级程序语言编写的程序中，
对于程序中出现的每个变量，
常数或表达式。 明确表示它们在哪里
的数据类型。
例如，c语言提供的基本数据类型为：
整数int
浮点型浮点型
字符类型char
型bool(c语言) ) ) ) )。
双精度型双精度型
真实(c语言) )
数据类型是值的集合
以及为此集合定义的一组操作
的总称。
教育信息化促进教育公平研究
根据范围不同，可以进行的操作也不同。
例如整数
值的范围为- 32768到32767
操作为、*、/、%
各种高级编程语言都有“整数”
类型在不同的处理器上实现
方法不同，但对程序员来说是“一样的”
“因为数学特性一样。
从“数学抽象”的角度来看，它可以说是一个
个抽象数据类型。
三.抽象数据类型
(Abstract Data Type简称ADT )
是指数学模型和额定值
这个数学模型上的义群
操作
例如：
“整数”是抽象数据类型。
其数学特性和具体的计算机或语言
没关系。
“抽象”的意思是强调数据类型
的数学特性。
抽象数据类型还包括设计软件系统的用户
有时自己定义的数据类型。
在构建软件系统各个相对独立的模块时，
定义一组数据和应用于其上的一组数据
操作，在模块内部给出它们的表示和实
目前，在模块外部使用的只有抽象的数量
根据抽象的操作。
例如，定义抽象数据类型“多个”
数据对象：
D={e1，e2|e1，e2RealSet }
数据关系：
R1={ | e1是复数的实数部分，
| e2是复数的虚数部分}
ADT Complex {
基本操作：
assigncomplex(z，v1，v2 ) ) ) ) ) )。
操作结果：复数z，作实部和虚部
分别被赋予参数v1和v2的值。
EstroyComplex(z ) )。
操作结果：复数z被放弃。
获取真实(z，realPart ) )。
初始条件：已存在多个。
操作结果：在realPart中返回复数z的实部值。
getimag(z，ImagPart )。
初始条件：已存在多个。
操作结果：用ImagPart返回复数z的虚部值。
add(Z1，z2，sum ) )。
初始条件： z1、z2为多个。
操作结果：用sum计算两个复数z1，z2的
价格。
} ADT Complex
(8) (4)3) )。
(8) (4)3) )。
I
I
z
=
#包含
# include 'complex.h '
void main () )
{
}
… …
complex z1、z2、z3、z4、z；
float RealPart，ImagPart；
initcomplex(z1、8.0、6.0 )；
init complex (z2，4.0，3.0 )；
add(Z1、z2、z3 )；
多工(Z1，z2，z4 )；
if(division(Z4，z3，z ) ) }
获取真实(z，RealPart )；
getimag(z，ImagPart )；
}//if
ADT有两个重要特征：
在将数据抽象化并用ADT记述程序处理的实体时，
强调其本质特征、可以做到的事情
功能及其与外部用户的接口，即外部
使用它的方法)
数据封装实现实体的外部特性及其内部实现
详细信息将被分离，并对外部用户隐藏
全部实现的详细情况
抽象数据类型的描述方法
抽象数据类型可以用(d，s，p )三元组表示
其中，d是数据对象，
s是d上的关系集
p是对d的基本操作集。
ADT抽象数据类型名称{
数据对象：“定义数据对象”
数据关系：定义数据关系
基本操作：“基本操作定义”
} ADT抽象数据类型名称
其中，基本操作的定义格式为：
基本操作名称(参数表)
初始条件：“初始条件说明”
操作结果：“操作结果说明”
赋值参数只是为操作提供输入值；
除了可以在开头参照参数来指定输入值之外，
操作结果也将返回。
初始条件描述操作执行前的数据结构
参数应满足的条件，不满足时操作
失败，返回适当的错误消息。
操作结果，操作成功完成后，数量
取决于结构的变化情况和应该返回的结果。 如果
初始条件为空时省略。
抽象数据类型的表示和实现
抽象数据类型需要通过唯一的数据
类型(用高级编程语言实现的数据
类型)来实现。
例如，对于上面定义的复数
typedef struct {
浮动真实零件；
浮动图像零件；
}complex；
//-----存储结构定义
//-----基本操作的函数原型说明
voidassign(complexz，
float realval，float imagval；
//构成复数z，其实部和虚部分别被赋予参数
//realval和imagval的值
浮动获取真实(cpmplexz；
//返回复数z的实部值
floatgetimag(cpmplexz )；
//返回复数z的虚部的值
voidadd(complexZ1、complex z2、
complex sum；
//用sum返回两个复数z1，z2之和
//-----基本操作的实现
voidadd(complexZ1、complex z2、
complex sum ) {
//用sum返回两个复数z1，z2之和
sum.real part=Z1.real part z2.real part；
sum.imag part=Z1.imagpartz2. imag part；
}
{其他省略}
1.3算法和算法度量
一.算法
二.算法设计原则
三.算法效率的衡量方法和指南
四.算法存储空间需求
算法是为解决某类问题而规定的一种
有限长度的操作序列。 一个算法必须满
以下五个重要特征：
1 .有穷性2 .确定性3 .可行性
4 .有输入5 .有输出
一.算法
1 .为具有贫穷性的任意组合法输入值，然后在
有穷步必有终，即：
算法的各个步骤可以在有限时间内完成；
2 .每种情况下应切实执行的操作
制作，算法有准确的规定，算法的
执行者和观众都可以明确其含义和执行方法
是的。 而且在任何条件下算法都只有一个
执行路径；
3 .可行性算法的所有操作必须充分
基本上，可以通过已经实现的基本操作来搬运
以有限的次数实现
教务网教务系统
在算法运行过程中需要输入，取决于算法
表面上可以没有输入，实际上已经计算过了
法律中；
5 .有输出。 这是“输入”和
确实
决定关系大小的是基于算法的信息加法
工作后得到的结果是，这种确定关系即
是算法的功能。
二.算法设计原则
设计算法时，通常需要考虑实现以下目标：
1 .准确性
2 .可读性
3 .健壮性
4 .高效率和低存储需求
1 .准确性
首先，算法必须满足特定的“规范中说”
“明”方式的需求。
其次，我们可以理解算法是否“正确”
这四个级别包括：
a .程序不含语法错误
b .程序对一些输入数据
满足要求的结果；
c .程序经过仔细选择、典型、严格
刁难的一些输入数据是令人满意的
要求的结果；
通常，以第c层语义的正确性为平衡
衡量算法是否合格的标准。
d .程序可以对所有合法的输入数据获得
得出满足要求的结果
2 .可读性
算法主要是为了人的阅读和交流，
其次是为计算机执行。 所以算法应该很简单
人的理解； 另一方面，难以读取的程序
容易隐藏很多错误，调试很难
3 .健壮性
如果输入的数据不正确，算法必须合适
进行反映或者相应的处理，而不是生产
产生奇怪的输出。 然后进行处理
错误的方法不是中断程序的执行
返回错误或表示错误性质的值。
为了在更高的抽象水平上处理。
4 .高效率和低存储需求
通常，效率是指算法的执行
时间； 存储是算法的执行过程
所需的最大存储容量。 哪个都是
关系到问题的规模。
三.算法效率的
测量方法和指南
通常有两种测量算法效率的方法：
事后统计法
先验分析估计法
坏处： 1。 必须执行程序
2。 其他因素隐藏算法的本质
与算法执行时间相关的因素：
1 .算法选择的策略
2 .问题的规模
3 .编程语言
4 .编译器生成的机器代码质量
5 .计算机执行指令的速度
特定算法的“执行工作量”
的大小只取决于问题的规模
(通常用整数n表示)，或者，
那是问题规模的函数。
假设，随着问题规模n的增大，
算法执行时间的增长率和f(n )的增加
如果比率相同，可以写如下。
t(n )=o ) f ) n ) )
将t(n )称为算法的(渐近)时间复杂度
怎么估算
算法的时间复杂性？
算法=控制结构的原始操作
(固有数据类型操作)
算法的执行时间=
原始操作(I )的执行次数原始操作(I )的执行时间
算法的执行时间
与
与原始操作执行次数之和成比例
从算法中选出一个对研究的问题
问题是基本操作的原操作，这个
算法中重复执行基本操作的次数
作为算法执行时间的衡量标准。
范例
一
双脚
个
力矩
阵形
相
骑
voidmult(inta (，int b[] )，int c[] ) )。
//用2维排列收纳矩阵要素，设c为a和b的积
for(I=1； i=n； I )
for(j=1； j=n； j ) {
c[i，j]=0；
for(k=1； k=n； k )
c[i，j] =a[i，k]*b[k，j]；
} //for
} //mult基本操作：乘法操作
时间复杂度：o(n3 ) )。
范例
二
选择
选择
排队
序
voidselect_sort(inta[]，int n ) {
//A中的整数序列从小到大排列为整数序列。
} //select_sort
基本操作：
比较(数据元素)操作
时间复杂度：o(N2 ) ) )。
j=i；//选择第I个最小元素
for(k=I1； k n； k )
if(a ) k ) a ) j ) j=k；
for(I=0； i n-1； I ) {
if(j！=i ) a[j] a[i]
}
范例
三
起床
泡沫
排队
序
voidbubble_sort(inta[]，int n ) {
//A中的整数序列从小到大排列为整数序列。
for(I=n-1，change=TRUE； i1变更； -I )
} //bubble_sort
基本操作：代入操作
时间复杂度：o(N2 ) ) )。
{ change=FALSE； //change是交换元素的标志
for(j=0； j a[j 1] )
{ a[j] a[j 1]； 更改=真； }
() /一次起泡
四.算法存储空间需求
算法的空间复杂度被定义为：
随着问题规模n的增大，
运行算法所需的存储增长率
与g(n )的增长率相同。
s(n )=o ) g ) n ) )
算法的存储量为：
1 .输入数据所占的空间
2 .程序本身所占的空间
3 .辅助变量所占空间。
如果输入数据所占空间仅取决于问题
它本身与算法无关，只是分析和消除
输入和程序以外的辅助变量额外占
空间。
所需额外空间相对于输入数据量
在常数的情况下，这种算法称为原地功。
如果所需的内存量取决于特定输入，则为、
通常在最坏的情况下考虑。
1 .熟悉和掌握各名词、术语的含义
基本概念。
2 .理解算法五个元素的确切含义。
本章的学习要点
3 .掌握计算语句的频率和估计算法时
之间复杂性的方法。
1.1.4(1.8
1.6 1.19 1.20
本章的工作
((考试问题) ) ) ) ) ) ) )。