数据结构课件Ch1PPT课件下载推荐.ppt
- 文档编号:7781252
- 上传时间:2023-05-09
- 格式:PPT
- 页数:83
- 大小:1.66MB
数据结构课件Ch1PPT课件下载推荐.ppt
《数据结构课件Ch1PPT课件下载推荐.ppt》由会员分享,可在线阅读,更多相关《数据结构课件Ch1PPT课件下载推荐.ppt(83页珍藏版)》请在冰点文库上搜索。
数据的基本单位,在计算机程序中常常作为一个整体进行考虑和处理。
eg.每一行代表一本书,作为一个基本单位,即每一行为一个数据元素,上述表格数据由n个数据元素组成。
数据项DataItem:
一个数据元素由若干个数据项组成。
数据项是数据的不可分割的最小单位。
eg.上述一个数据元素由5个数据项组成。
13,数据对象DataObject:
性质相同的数据元素的集合,是数据的一个子集。
eg.整数的数据对象是,-3,-2,-1,0,1,2,3,英文字符类型的数据对象是A,B,C,D,E,F,,14,数据结构DataStructure:
是相互之间存在一种或多种特定关系的数据元素的集合。
数据元素之间不是相互独立的,他们之间有某种特定的关系,这种数据元素之间的关系,称为“结构”Structure。
15,四种基本结构(逻辑结构)p5集合:
元素仅属于同一个集体,没有其他关系。
eg.同班关系线性结构:
存在一对一关系,序列相邻,次序关系。
eg.大小关系树型结构:
存在一对多关系,层次关系。
eg.家族关系图状结构(网状结构):
存在多对多关系,任意性eg.交通图,16,数据结构的形式定义:
数据结构是一个二元组:
Data-Structure=(D,S)其中:
D是数据元素的有限集,S是D上关系的有限集。
数学描述,即数学模型eg.复数的数据结构定义如下:
Complex=(C,R)其中:
C是含两个实数的集合C1,C2,分别表示复数的实部和虚部。
R=P,P是定义在集合上的一种关系。
17,结构中描述的关系是数据元素之间的逻辑关系,因此又称为数据的逻辑结构.数据的逻辑结构又分为线型结构和非线性结构两大类.线性结构数据的逻辑结构非线性结构,18,对于任意一个逻辑结构S=(D,R),若aD,bD,(a,b)R,则称a是b的前驱,b是a的后继;
若某结点没有前驱,则称该结点为开始结点;
若某结点没有后继,则称该结点为终端结点。
序偶(),19,1,2,3,4,5,在线性结构中,除了开始结点和终端结点外,其余结点有且仅有一个前驱,有且仅有一个后继.eg.图示法,20,非线性结构分为树形结构和图状结构.树形结构非线性结构图状结构在树形结构中,每个结点最多只有一个前驱,但可以有多个后继,可以有多个终端结点.在图状结构中,每个结点的前驱和后继的数目可以是任意的,因此,可能没有开始结点和终端结点,也可能有多个开始结点和终端结点。
21,a,b,c,d,e,a,b,c,d,e,eg.树形结构图状结构,22,user,线性结构,树形结构树二叉树二叉排序树,Eg.,23,堆结构,12,3,5,4,8,7,11,10,2,9,1,6,图结构网络结构,24,数据的逻辑结构从逻辑关系上描述数据,与数据的存储无关;
从具体问题抽象出来的数据模型;
与数据元素本身的形式、内容无关;
与数据元素的相对位置无关。
25,讨论数据结构的目的是为了在计算机中实现对它的操作,因此还需研究如何在计算机中表示它。
数据结构在计算机中的表示称为数据的物理结构(又称映像或存储结构),即逻辑结构到存储器的一个映射。
它包括数据元素的表示和关系的表示。
数据元素的表示物理结构关系的表示,26,计算机使用0和1两个二进制数字,表示信息的最小单位是二进制的一位,叫做位Bit。
计算机的信息单位还有字节和字。
一个字节由8位二进制信息组成,一个字至少由一个以上的字节组成。
位信息单位字节字,27,在计算机中,用一个若干位组合起来形成的一个位串表示一个数据元素,通常称这个位串为元素Element或结点Node。
当数据元素由若干数据项组成时,位串中对于各个数据项的子位串成为数据域DataField。
逻辑结构:
数据元素数据项|物理结构:
元素/结点数据域,28,数据元素之间的关系在计算机中有两种不同的表示方法:
顺序映像和非顺序映像|顺序存储结构链式存储结构数据元素的表示物理结构关系的表示,29,1.顺序映像特点:
借助元素在存储器中的相对位置来表示元素之间的逻辑关系。
以x和y存储位置的相对关系表示有序对最简单的方法就是使y和x的存储位置之间差一个常量C,而C是一个隐含值,整个存储结构中只含数据元素本身的信息。
30,Eg.线性结构list:
设每个结点占用一个存储单元,数据从200号单元开始从低地址向高地址存放.存储结构如图所示:
1,2,3,4,5,1,2,3,4,5,200,201,202,203,204,31,设每个结点占用两个存储单元,数据从200号单元开始从低地址向高地址存放.存储结构如图所示:
200,201,202,203,204,206,207,208,209,210,1,2,3,4,5,32,2.非顺序映像特点:
借助指示元素存储地址的指针Pointer表示元素之间的逻辑关系.,x和y的存储位置随意,则需要用一个和x在一起的附加信息指示y的存储位置,这个附加信息和x绑定在一起,此时,两者合在一起作为x的存储映象。
33,Eg.每个结点占用两个单元,一个存放结点的数值,另一个存放后继结点的地址.存储结构如图所示:
1236,3308,5,2202,4214,209,202,214,236,308,结点的数值,后继结点的地址,34,存储密度紧凑结构:
所有的空间都存储数据元素非紧凑结构:
有附加的信息附加的信息会带来其他的优势,选择数据的存储结构数据操作花费的时间少占用的存储空间小一般情况,时间优于空间,35,数据类型DataType是一个值的集合和定义在这个值集上的一组操作的总称。
原子类型数据类型结构类型,36,数据类型,基本类型,构造类型,整型,字符型,实型(浮点型),枚举类型,指针类型,空类型,单精度型,双精度型,数组类型,结构体类型,共用体类型,C语言中的数据类型:
37,抽象数据类型AbstractDataType,简称ADT,是指一个数据模型和定义在该模型上的一组操作。
每一个操作由它的输入和输出定义。
抽象的与具体的相对应。
eg.inta,b;
则a和b可以进行+、-、*、/的运算,-2,-1,0,1,2,则是具体的int型数据例如:
矩阵+(求转置、加、乘、求逆、求特征值)构成一个矩阵的抽象数据类型数据结构+定义在此数据结构上的一组操作=抽象数据类型,38,原子类型抽象数据类型固定聚合类型结构类型可变聚合类型,39,抽象数据类型可用(D,S,P)三元组表示其中,D是数据对象,S是D上的关系集,P是对D的基本操作集。
ADT抽象数据类型名数据对象:
数据对象的定义数据关系:
数据关系的定义基本操作:
基本操作的定义ADT抽象数据类型名其中,数据对象和数据关系的定义用伪码描述,40,基本操作的定义格式为基本操作名(参数表)初始条件:
初始条件描述操作结果:
操作结果描述基本操作有两种参数:
赋值参数只为操作提供输入值;
引用参数以&
打头,除可提供输入值外,还将返回操作结果。
“初始条件”描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息。
“操作结果”说明了操作正常完成之后,数据结构的变化状况和应返回的结果。
若初始条件为空,则省略之。
41,数据结构的划分,
(1)按数据结构的性质划分数据的逻辑结构数据元素之间的逻辑关系(设计算法数学模型)数据的物理结构数据结构在计算机中的映像(存储结构,算法的实现),42,
(2)按数据结构在计算机内的存储方式来划分顺序存储结构借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。
链式存储结构借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
索引存储方法:
在存储结点的同时,还建立附加的索引表,索引表中的每一项称为索引项,形式为:
关键字,地址。
散列存储方法:
根据结点的关键字直接计算出该结点的存储地址。
说明:
四种存储方法可结合起来对数据结构进行存储映像。
43,(3)按数据结构的操作来划分静态结构经过操作后,数据的结构特征保持不变(如数组)。
半静态结构经过操作后,数据的结构特性只允许很小变迁(如栈、队列)。
动态结构经过操作后,数据的结构特性变化比较灵活,可随机地重新组织结构(如指针)。
44,1.3抽象数据类型的表示与实现,用来写算法的方式有好几种:
1.条例式的步骤2.流程图FlowChar3.伪码PseudoCode学习数据结构必须与实际应用相结合,使用伪代码讲授可能增加了学生上机实践的难度。
4.程序语句本书讨论的数据结构及其算法采用介于伪码和C语言之间的类C语言作为描述工具。
45,例、求两个整数m、n(mn)的最大公因子,46,开始,输入m、n,整除m/n,求余数r,r=0?
打印n,结束,mnnr,是,否,流程图,47,【求余数】以n除m,并令r为余数(0rn);
余数是否为0若r=O则结束算法,n就是最大公因子;
替换并返回a若r0则mn,nr返回a。
条例式的步骤,48,程序语句,intmaxcommonfactor(intm,intn)intr;
r=m%n;
while(r!
=O)m=n;
n=r;
r=mn;
returnn;
49,P16P23,50,1预定义常量和类型:
#defineTRUE1;
#defineFALSE-1;
#defineERRORNULL;
51,2函数的形式数据类型函数名(形式参数)形式参数说明;
内部数据说明;
执行语句组;
/*函数名*/函数的定义主要由函数名和函数体组成,函数体用花括号“”和“”括起来。
函数中用方括号括起来的部分为可选项,函数名之间的圆括号不可省略。
函数的结果可由指针或别的方式传递到函数之外。
执行语句可由各种类型的语句所组成,两个语句之间用“;
”号分隔。
可将函数中的表达式的值通过return语句返回给调用它的函数。
最后的花括号“”之后的/*函数名*/为注释部分,可舍。
52,3赋值语句简单赋值:
=,它表示将表达式的值赋给左边的变量;
+,它表示变量加1后赋值给变量;
-,它表示变量减1后赋值给变量;
53,成组赋值:
1.(,,)=(,);
2.下标1下标2=下标1下标2,54,串联赋值:
=;
条件赋值:
=?
:
;
交换赋值:
,表示变量1和变量2互换;
55,4条件选择语句if()语句;
if()语句1;
else语句2;
情况语句switch()case判断值1;
语句组1;
break;
case判断值2;
语句组2;
case判断值n;
语句组n;
break;
default:
语句组;
注意:
switchcase语句是先计算表达式的值,然后用其值与判断值相比较,若它们相一致时,就执行相应的case下的语句组;
若不一致,则执行default下的语句组;
其中的方括号代表可选项。
56,5循环语句for语句for(;
)循环体语句;
首先计算表达式1的值,然后求表达式2的值,若结果非零则执行循环体语句,最后对表达式3运算,如此循环,直到表达式2的值为零时止。
57,while语句while()循环体语句;
while循环首先计算条件表达式的值,若条件表达式的值非零,则执行循环体语句,然后再次计算条件表达式,重复执行,直到条件表达式的值为假时退出循环,执行该循环之后的语句。
58,do-while语句do循环体语句while()该循环语句首先执行循环体语句。
然后再计算条件表达式的值,若条件表达式成立,则再次执行循环体,再计算条件表达式的值,直到条件表达式的值为零,即条件不成立时结束循环。
59,6输入、输出语句输入语句:
用函数scanf实现,特别当数据为字符时,用getchar函数实现。
输出语句:
用printf函数实现,当要输出字符数据时,用putchar函数实现。
60,7其他一些语句
(1)return表达式或return:
用于函数结束。
(2)break语句:
可用在循环语句或case语句中结束循环过程或跳出情况语句。
(3)exit语句:
表示出现异常情况时,控制退出语句。
8注释形式可用/*字符串*/或者单行注释或/文字序列。
61,9一些基本的函数如:
max函数,用于求一个或几个表达式中的最大值;
min函数,用于求一个或几个表达式中的最小值;
abs函数,用于求表达式的绝对值;
eof函数,用于判定文件是否结束;
eoln函数,用于判断文本行是否结束。
62,例.计算f=1!
+2!
+3!
+n!
,用C语言描述。
voidfactorsum(intn)inti,j;
intf,w;
f=0;
for(i=1;
i=n;
i+)w=1;
for(j=1;
j=i;
j+)w=w*j;
f=f+w;
return;
上述算法所用到的运算有乘法、加法、赋值和比较,其基本运算为乘法操作。
在上述算法的执行过程中,对外循环变量i的每次取值,内循环变量j循环i次。
因为内循环每执行一次,内循环体语句w=w*j只作一次乘法操作,即当内循环变量j循环i次时,内循环体的语句w=w*j作i次乘法。
所以,整个算法所作的乘法操作总数是:
f(n)=1+2+3+n=n(n+1)/2。
63,1.4算法和算法分析,1.4.1算法Algorithmp13算法指一系列确定的而且是在有限步骤内能完成的操作。
算法的重要特性P13
(1)有穷性Finiteness:
能执行结束,对于任意一组合法输入值,在执行有穷步骤之后一定能结束,即:
算法中的每个步骤都能在有限时间内完成;
64,
(2)确定性Definiteness:
对于每种情况下所应执行的操作,在算法中都有确切的规定,使算法的执行者或阅读者都能明确其含义及如何执行。
并且在任何条件下,算法都只有一条执行路径;
每一条指令不会产生二义性对于相同的输入执行相同的路径(3)可行性(有效性)Effectiveness:
算法中的所有操作都必须足够基本,都可以通过已经实现的基本操作运算有限次实现之;
65,(4)输入Input:
0至多个输入作为算法加工对象的量值,通常体现为算法中的一组变量。
有些输入量需要在算法执行过程中输入,而有的算法表面上可以没有输入,实际上已被嵌入算法之中;
(5)输出Output:
1至多个输出它是一组与“输入”与确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能,66,问题:
操作系统程序是不是算法?
如操作系统,只要系统不遭破坏,它就永远不会停止,即使没有作业要处理,仍处于一个等待循环中,等待新作业的进入。
因此操作系统程序不是一个算法。
67,1.4.2算法设计的要求p13p14,
(1)正确性Correctness算法应满足具体问题的需求。
首先,算法应当满足以特定的“规格说明”方式给出的需求。
68,其次,对算法是否“正确”的理解可以有以下四个层次:
a程序中不含语法错误;
b程序对于几组输入数据能够得出满足要求的结果;
c程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果;
d程序对于一切合法的输入数据都能得出满足要求的结果;
通常以第c层意义的正确性作为衡量一个算法是否合格的标准。
69,
(2)可读性Readability算法首先是给人读,然后才是机器执行。
算法应该好读,以有利于阅读者对程序的理解。
(3)健壮性Robustness/容错性算法应具有容错处理。
当输入非法数据时,算法应对其作出反应,而不是产年莫名其妙的输出结果。
并且,处理出错的方法不应是中断程序的执行,而应是返回一个表示错误或错误性质的值,以便在更高的抽象层次上进行处理。
70,
(1),71,(4)效率与低存储量需求效率指的是算法的执行时间。
计算机的资源,最重要的是运算所需的时间和存储程序和数据所需的空间资源。
一个“好”的算法,运行时间较短,占用较少的存储空间。
一般,这两者与问题的规模有关。
72,1.4.3算法效率的度量,一个算法如果能在所要求的资源限制内将问题解决好,则称这个算法是有效率的。
对一个算法要作出全面的分析可分成两个阶段进行,即事先分析和事后测试p141)事前分析估算法(事先分析)2)事后统计法(事后测试),73,1)事前分析估算法(事先分析)和算法执行时间相关的因素:
1算法选用的策略2问题的规模3编写程序的语言4编译程序产生的机器代码的质量5计算机执行指令的速度,2)事后统计法(事后测试)缺点:
1.必须执行程序2.其它因素掩盖算法本质收集此算法的执行时间和实际占用空间的统计资料。
74,算法的执行时间等于算法中各个语句执行时间的总和。
运行时间=算法中每条语句执行时间之和某个语句的执行时间等于该语句执行一次所需时间与执行次数的乘积。
每条语句执行时间=该语句的执行次数(频度)*语句执行一次所需时间语句的频度:
该语句重复执行的次数。
75,语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量,很难确定在大多数情况下,精确统计算法中每个语句的执行次数与执行一次所需的时间都是非常困难的。
设每条语句执行一次所需时间为单位时间,则一个算法的运行时间就是该算法中所有语句的频度之和。
为了分析的方便,只选取一个基本操作(或原操作)的频度作为算法执行时间的度量。
基本操作一般指最深层循环内的语句。
例:
(a)+x;
s=0;
+x的频度为(b)for(i=1;
i=n;
+i)+x;
s+=x;
+x的频度为(c)for(j=1;
j=n;
+j)for(k=1;
k=n;
+k)f(n)=an2+bn+c+x;
+x的频度为,1,n,n2,n+1,n,n(n+1),n2,n2,1,n,n2,77,for(i=2;
i+)for(j=2;
j=i-1;
j+)+x;
aij=x;
i=2;
i=3,j=2;
i=4,j=2,3;
i=n,j=2,3,n-1频度之和:
an2+bn+can2n2,1次,n次,n-1次,1+2+(n-2)=(n-1)(n-2)/2次,1+2+(n-2)=(n-1)(n-2)/2次,78,时间复杂度定义:
一般情况下,算法中基本操作重复执行的时间是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n)它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。
79,main()inti,j,temp;
inta10;
for(i=0;
iai+1)temp=ai;
ai=ai+1;
ai+1=temp;
for(i=1;
i11;
i+)printf(%5d,ai);
printf(n);
80,有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。
例如:
voidbubble-sort(inta,intn)for(i=n-1;
change=TURE;
i1最好情况:
0次最坏情况:
1+2+3+n-1=n(n-1)/2平均时间复杂度为:
O(n2),81,结论,
(1)当f(n)为对数函数、幂函数、或它们的乘积时,算法的运行时间是可以接受的,称这些算法是有效算法;
当f(n)为指数函数或阶乘函数时,算法的运行时间是不可接受的,称这些算法是无效的算法。
(2)随着n值的增大,增长速度各不相同,n足够大时,存在下列关系:
对数函数幂函数指数函数,82,常见函数的增长率,O
(1)常量阶,与n无关O(logn)logn阶O(n)n阶O(nlogn)nlogn阶O(n2)平方阶O(n3)立方阶O(2n)指数阶增长率由慢到快图示见p16图1-7尽量少用指数阶的算法说明:
教材p17第2行除特别指明外,均指最坏情况下的时间复杂度,83,1.4.4空间复杂度,
(1)存储算法本身所占用的空间
(2)算法的输入/输出数据占用的空间(3)算法在运行过程中临时占用的辅助空间原地工作:
若辅助空间相对于输入数据量是常数,则称此算法是原地工作。
若所占空间量依赖于特定的输入,按最坏情况来分析。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件 Ch1