数据结构第01章概论

数据结构与算法谢颂华whxiesonghua@163.com12数据结构课程的地位——针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。——是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。关系对象关系操作数学软件硬件对象关系操作Data_Structure=（D,R）3学时数：40学分：

2.5

教材：

严蔚敏等，数据结构（C语言版），清华大学出版社（配题集）

参考书：[1]（美）霍罗维兹等，《数据结构基础（C语言版）》，清华大学出版社，2009[2]严蔚敏等，《数据结构(C语言版)》，人民邮电出版社，2011[3]殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社，2002教材与参考书4内容安排章内容学时章内容学时1绪论37图52线性表48动态存储管理略3栈和队列39查找44串210内部排序55数组和广义表211外部排序略6树和二叉树612文件略5第1章绪论第2章线性表第3章栈和队列

第4章串第5章数组和广义表第6章树和二叉树

第7章图第9章查找第10章排序目录6第1章绪论讨论5个问题：1.1什么是数据结构1.2学习数据结构的意义1.3数据结构涵盖的主要内容1.4什么是抽象数据类型1.5算法效率的度量71.1什么是数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,R）——是指同一数据元素类型中各元素之间存在的关系。元素有限集关系有限集8数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。三者之间的关系：数据>数据元素>数据项例：班级通讯录>个人记录>姓名、年龄……数据、数据元素和数据项术语简介：91.2学习数据结构的意义计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。程序设计＝好算法＋好数据结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。101.3数据结构涵盖的内容11集合结构：仅同属一个集合线性结构:一对一（1:1)

树结构:一对多（1:n)

图结构:多对多(m:n)非线性线性逻辑结构可细分为4类：答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。解释1：什么叫数据的逻辑结构？12数据的逻辑结构分类线性结构（反映一对一的逻辑关系）逻辑特征：有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。实现：线性表非线性结构（反映一对多或多对多的逻辑关系）逻辑特征：一个结点可能有多个直接前趋和直接后继。实现：树、图（或网络）13学生成绩表结点数据结构bindevetclibuser线性结构142114131211234678910315871011998745662313155树形结构

树二叉树二叉排序树15文件系统结构图/rootbinlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp16例如:在迷宫问题中,计算机之间所以能够找到迷宫的出口,是因为人们已将搜索出口的策略事先存入计算机中.在迷宫中,每走到一处,接下来可走的通路有三条,如图:计算机处理的这类对象之间通常不存在线性关系,若将从迷宫入口处到出口的过程中所有可能的通路都画出来,则可以得到一棵倒长的”树”.”树根”是迷宫入口,”树叶”是出口或死路.”树”可以是某些非数值计算问题的数学模型.如下图：现实中的问题：迷宫17入口死路死路死路死路死路死路死路死路死路死路出口死路死路死路死路18现实中的问题：计算机和人的对弈井字棋的一个格局19125643125436113318146651921

图结构

网络结构20现实中的问题：多叉路口交通灯的管理

在多叉路口需设几种颜色的交通灯才能既使车辆之间不碰撞，又能达到车辆的最大流通呢？ABCDEC，E为单行道可同时通行：A->BE->C不能同时通行：E->BA->D21101582552175081092010现实中的问题：在N个城市之间建立通信网络问题：如何使该网络造价最低？22在应用程序中涉及到各种各样的数据，如何在计算机中组织、存储、传递数据，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，依此实现软件功能。综上，描述这类非数值计算问题的数学模型不是数学方程，而是树、表和图之类的数据结构。因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。23（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。24d1d5d2d4d3该结构是非线性的。解：上述表达式可用图形表示为：（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}25答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：例：复数3.0－2.3i的两种存储方式：顺序、链式、索引、散列－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节解释2：什么叫数据的物理结构？26存储结构的描述虽然存储结构涉及数据元素及其关系在存储器中的物理位置，但我们是在高级语言的层次上讨论数据结构的操作。因此我们不用具体的内存地址来描述存储结构，而是借助于高级语言中提供的“数据类型”来描述。27答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序解释3：什么是数据的运算？281.4什么是抽象数据类型1.4.1数据类型与抽象数据类型的区别？1.4.2抽象数据类型如何定义？1.4.3抽象数据类型如何表示和实现？

讨论：抽象数据类型和伪码是学习数据结构的工具291.4.1数据类型与抽象数据类型的区别数据类型：是一个值的集合和定义在该值上的一组操作的总称。变量的数据类型决定了如何将代表这些值的位存储到计算机的内存中。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）301.4.2抽象数据类型如何定义抽象数据类型可以用以下的三元组来表示：

ADT=（D，R，P）ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名ADT常用定义格式数据对象D上的关系集D上的操作集31例：给出自然数(NaturalNumber

)的抽象数据类型定义。ADT

Natural_Number

isobjects:

一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数(MAXINT)functions:

对于所有的x,yNatural_Number；TRUE,FALSEBoolean；+,-,<,==,=等都是可用的服务。Zero()：NaturalNumber返回0IsZero(x)：Booleanif(x==0)返回TRUE

else返回FALSEAdd(x,y)：NaturalNumber

if(x+y<=MAXINT)返回x+yelse返回MAXINTSubtract(x,y):NaturalNumber

if(x<y)返回0else返回x-yEqual(x,y):Boolean if(x==y)返回TRUEelse返回FALSESuccessor(x):NaturalNumber

if(x==MAXINT)返回xelse返回x+1end

Natural_Number

321.4.3抽象数据类型如何表示和实现抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注1：它有些类似C语言中的结构体（struct)类型，但增加了相关的操作。注2：教材中用类C语言（介于伪码和C语言之间）作为描述工具。其描述语法汇总在教材P10-11上。但上机时要用具体语言实现，如C或C++等33提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请自己先试读一遍。当课程内容学习到50%以后，你再回头看这个例子，会发现自己已能完全看懂了！341.5算法效率的度量1.5.1什么是算法？如何评判算法的好坏？1.5.2时间复杂度和空间复杂度如何表示？1.5.3计算举例讨论：351.5.1什么是算法？如何评判一个算法的好坏？常用时间复杂度来衡量算法的基本特性：算法评价指标：有穷性、确定性、可行性、必有输出正确性、可读性、健壮性、效率与低存储量需求常用空间复杂度来衡量程序设计的实质：好算法＋好数据结构

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。4个层次36算法分析定义：为了解决某类问题而规定的一个有限长的操作序列。特性：有穷性执行有穷步，有穷时间内完成确定性每条指令的含义都必须明确,无歧义可行性算法中描述的操作都是可以通过已经实现的基本运算执行有限次实现输入有0个或多个输入输出有一个或多个输出37例子：选择排序问题：递增排序解决方案：逐个选择最小数据算法框架：

for(inti=0;i<n-1;i++){//n-1趟 从a[i]检查到a[n-1];

若最小整数在a[k],交换a[i]与a[k];}细化：SelectSort算法设计38voidselectSort(inta[],intn){//对n个整数a[0],a[1],…,a[n-1]按递增顺序排序inti,j,k,temp;for(i=0;i<n;i++) {k=i;//从a[i]查到a[n-1],找最小整数,在a[k]for(j=i+1;j<n;j++) if(a[j]<a[k])k=j; //记录最小整数的下标k if(k!=i)//交换,最小整数移至本轮最前{temp=a[i];a[i]=a[k];a[k]=temp;}}} 39性能分析与度量算法的性能标准正确性：包括不含语法错误对几组数据运行正确对典型、苛刻的数据运行正确；对所有数据运行正确可读性效率：高效、低存储需要（算法执行时间短，同时所占用的存储空间小）。健壮性：当输入非法数据时，算法也能作出适当反应，而不会出现莫名其妙的输出结果。40算法的事前估计(1)空间复杂度度量存储空间的固定部分

程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间可变部分

尺寸与实例特性有关的成分变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间1.5.2时间复杂度和空间复杂度如何表示？41(2)时间复杂度度量运行时间=算法中每条语句执行时间之和。每条语句执行时间=

该语句的执行次数（频度）*语句执行一次所需时间语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。42一、时间复杂度:算法中语句重复执行次数的数量级就是时间复杂度。二、表示方法：T(n)=O(f(n))f(n)表示基本操作重复执行的次数，是n的某个函数，随问题规模n的增大，算法执行时间的增长率和f(n)的增长率属于同一数量级；O表示f(n)和T(n)只相差一个常数倍。T(n)称做渐进时间复杂度，简称时间复杂度。时间复杂度433n+2=O(n)因为3n+24nforn26*2n+n2=O(2n)因为6*2n+n27*2nforn4例：渐进符号（O）的定义：当且仅当存在一个正的常数C，使得对所有的

nn0，有f(n)Cg(n)，则：f(n)=O(g(n))44几种时间复杂度O(1):常数时间O(log2n)：对数时间O(n)：线性时间O(nlog2n)：线性对数时间O(n2):平方时间O(n3):立方时间O(2n):指数时间上述的时间复杂度的优劣次序如下（n>=16):O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)45算法的存储空间需求算法的空间复杂度定义为:

表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。S(n)=O(g(n))46算法的存储量包括:1．输入数据所占空间2．程序本身所占空间3．辅助变量所占空间若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。47如何估算算法的时间复杂度？1.5.3计算举例算法=控制结构+原操作（固有数据类型的操作）算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间算法的执行时间

与

原操作执行次数之和

成正比

48从算法中选取一种对于所研究的问题来说是

基本操作

的原操作，以该基本操作

在算法中重复执行的次数

作为算法运行时间的衡量准则。49例一两个矩阵相乘voidmult(inta[],intb[],int&c[]){

//以二维数组存储矩阵元素，c为a和b的乘积for(i=0;i<n;++i)

for(j=0;j<n;++j){c[i,j]=0;for(k=0;k<n;++k)c[i,j]+=a[i,k]*b[k,j];}//for}//mult基本操作:

乘法操作时间复杂度:

O(n3)50例二选择排序voidselect_sort(int&a[],intn){

//将a中整数序列重新排列成自小至大有序的整数序列。

}//select_sort基本操作:

比较(数据元素)操作时间复杂度:

O(n2)j=i;//选择第i个最小元素for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;for(i=0;i<n-1;++i