数据结构课件:第1章 绪论_第1页
数据结构课件:第1章 绪论_第2页
数据结构课件:第1章 绪论_第3页
数据结构课件:第1章 绪论_第4页
数据结构课件:第1章 绪论_第5页
已阅读5页,还剩44页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构总学时:36(考试课)

教材:《数据结构(C语言版)》严蔚敏、吴伟民编著

清华大学出版社

课程安排教学内容第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章排序考查方式20%作业70%考试10%考勤第1章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型1.4算法和算法分析“数据结构”学科形成和发展背景1946年第一台计算机问世,计算机产业的飞速发展,深入到人类社会的各个领域。计算机的应用已不再局限于科学计算,而更多地用于控制、管理及数据处理等非数值计算的处理工作。计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据,这就给程序设计带来一些新的问题。为了编写一些“好”的程序,必须分析待处理对象的特性以及各处理对象间的关系。这就是“数据结构”这门学科形成和发展的背景。1.1什么是数据结构数值计算解决问题的一般步骤:数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是:如何得出数学模型(方程)?程序设计人员比较关注程序设计的技巧。非数值计算问题中,数据元素之间的相互关系一般无法用数学方程加以描述。8例1-1

书目自动检索系统登录号:书名:作者名:分类号:出版单位:出版时间:价格:书目卡片书目文件按书名按作者名按分类号索引表线性表树……..……..…...…...…...…...例1-2

井字棋例1-3多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图综上三个例子可见,描述这类非数值计算问题的数学模型不再是数学方程,而是诸如表、树和图之类的数据结构。因此,简单说来,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。形成阶段:60年代初期,“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年,“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段:数据结构的概念不断扩充,包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期,我国高校陆续开设该课程。数据结构课程的形成和发展数据结构所处的地位数据(Data):对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数值型数据:整数、实数等;非数值型数据:图像、声音等。1.2基本概念和术语数据元素(DataElement):数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

一个数据元素可由若干个数据项(dataitem)组成。数据项是数据的不可分割的最小标识单位。1.2基本概念和术语数据对象(DataObject):性质相同的数据元素的集合。是数据的一个子集。整数数据对象N={0,1,2,…}字母字符数据对象

C={‘A’,‘B’,‘C’,…‘Z’}1.2基本概念和术语定义1----数据结构是相互之间存在一种或多种特定关系的数据元素的集合。定义2----按某种逻辑关系组织起来的一批数据(或称带结构的数据元素的集合)应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中,并在其上定义了一个运算的集合。数据结构数据元素间的四类基本结构:集合:结构中的数据元素除了同属于一种类型外,别无其它关系。线性结构:结构中的数据元素之间存在一对一的关系,如线性表、栈、队列。树形结构:结构中的数据元素之间存在一对多的关系,如树。图状结构或网状结构:结构中的数据元素之间存在多对多的关系。数据结构的形式定义为:数据结构是一个二元组

Data__Structure(D,S)其中:D是数据元素的有限集

S是D上关系的有限集例1-4:在计算机科学中,复数可取如下定义:复数是是一种数据结构Complex=(C,R)其中:C是含两个实数的集合<c1,c2>,R={P},P是定义在集合C上的一种关系{<c1,c2>},其中<c1,c2>表示c1是复数的实部,c2是复数的虚部。例1-5:假设我们需要编制一个事务管理的程序,管理学校科学研究课题小组的各项事务,则首先要为程序的操作对象——课题小组设计一个数据结构。假设每个小组由1位教师、1~3名研究生及1~6本科生组成,小组成员之间的关系是:教师指导研究生,而由每位研究生指导一至两名本科生。则可以如下定义数据结构:Group=(P,R)其中:P={T,G1,……,Gn,S11…Snm}1≦n≦3,1≦m≦2,R={R1,R2}R1={〈T,Gi〉∣1≦i≦n,1≦n≦3}R2={〈Gi,Sij〉

∣1≦i≦n,1≦j≦m,1≦n≦3,1≦m≦2}课堂练习:画出下列数据结构所对应的结构示意图:(1)数据结构structure1=(D,R)D={1,2,3,4,5,6}R={r}r={<1,2>,<2,5>,<5,3>,<3,6>,<6,4>}(2)数据结构structure2=(D,R)D={1,2,3,4,5,6}R={r}r={<1,2>,<1,3>,<1,4>,<2,5>,<2,6>}(3)数据结构structure3=(D,R)D={1,2,3,4,5,6}R={r}r={<1,6>,<2,6>,<6,4>,<6,5>,<4,5>}课堂练习:(4)数据结构structure4=(D,R)D={a,b,c,d,e,f}R={r1,r2}r1={<c,b>,<c,e>,<b,a>,<e,d>,<e,f>}r2={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>}逻辑结构---数据元素间抽象化的相互关系(简称为数据结构)。与数据的存储无关,独立于计算机,它是从具体问题抽象出来的数学模型。存储结构(物理结构)----数据元素及其关系在计算机存储器中的存储方式。是逻辑结构用计算机语言的实现,它依赖于计算机语言。1.2基本概念和术语数据元素之间的关系在计算机中有两种不同的表示方法:顺序映象和非顺序映象,并由此得到两种不同的存储:顺序存储结构和链式存储结构。顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。链式存储结构:在每一个数据元素中增加一个存放另一个元素地址的指针(pointer),用该指针来表示数据元素之间的逻辑结构(关系)。数据的逻辑结构和物理结构是密切相关的两个方面,任何一个算法的设计取决于选定的逻辑结构,而算法的实现依赖于采用的存储结构。数据类型:是和数据结构密切相关的一个概念,它最早出现在高级程序语言中,用以刻画(程序)操作对象的特性。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。按“值”的不同特性,高级程序语言中的数据类型可分为两类:一类是非结构的原子类型。原子类型的值是不可分解的。另一类是结构类型。结构类型的值是由若干成分按某种结构组成的,因此是可以分解的,并且它的成分可以是非结构的,也可以是结构的。1.3抽象数据类型抽象数据类型(AbstractDataType,简称ADT):是指一个数学模型以及定义在该模型上的一组操作。

ADT的定义仅是一组逻辑特性描述,与其在计算机内的表示和实现无关。因此,不论ADT的内部结构如何变化,只要其数学特性不变,都不影响其外部使用。

ADT的形式化定义是三元组:

ADT=(D,S,P)其中:D是数据对象,S是D上的关系集,P是对D的基本操作集。ADT的一般定义形式是:ADT<抽象数据类型名>{数据对象:<数据对象的定义>数据关系:<数据关系的定义>基本操作:<基本操作的定义>}ADT<抽象数据类型名>其中数据对象和数据关系的定义用伪码描述。基本操作的定义是:<基本操作名>(<参数表>)初始条件:<初始条件描述>操作结果:<操作结果描述>1.4.1算法什么是算法?算法(Algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。一个算法必须满足以下五个重要特性:1.4算法和算法分析一个算法必须满足以下五个准则:(1)有穷性(2)确定性(3)可行性(4)输入(5)输出1.4.1算法1、有穷性:对于任何合法的输入值,在执行有穷步骤之后一定能结束,即:算法中的每个步骤都能在有限时间内完成;2、确定性:对于每种情况下所应执行的操作,在算法中都有确切的规定,使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下,算法都只有一条执行路径;3、可行性:算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之;五个准则:4、输入:一个算法有零个或多个输入,有些输入量需要在算法执行过程中输入,而有的算法表面上可以没有输入,实际上已被嵌入算法之中;5、输出:它是一组与“输入”有着确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能。五个准则:一个算法可以用多种方法描述,主要有:使用自然语言描述;使用形式语言描述;使用计算机程序设计语言描述。算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。1.4.2算法设计的要求设计一个“好”的算法时,通常应考虑达到以下目标:1、正确性2、可读性3、健壮性4、效率与低存储量需求1、正确性(correctness)算法应当满足具体问题的需求。算法是否“正确”的理解可以有以下四个层次:A.程序中不含语法错误;B.程序对于几组输入数据能够得出满足要求的结果;C.程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果;D.程序对于一切合法输入数据都能够产生满足要求的结果。通常以第C层意义的正确性作为衡量一个算法是否合格的标准。2、可读性(readability)算法主要是为了人的阅读与交流,其次才是为计算机执行。因此算法应该易于人的理解;另一方面,晦涩难读的程序易于隐藏较多错误而难以调试和修改。3.健壮性(robustness)当输入的数据非法时,算法应当恰当地作出反映或进行相应处理,而不是产生莫名奇妙的输出结果。并且,处理出错的方法不应是中断程序的执行,而应是返回一个表示错误或错误性质的值,以便在更高的抽象层次上进行处理。4、效率与低存储量需求通常,效率指的是算法执行时间;对于同一个问题,如果有多种算法可以解决,执行时间短的算法效率高。存储量指的是算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。1.4.3算法效率的衡量算法执行时间通常有两种衡量的方法:(1)事后统计法缺点:1.必须执行程序;2.其它因素(计算机硬件、软件等)掩盖算法本身的优劣。(2)事前分析估算法算法执行时间取决于下列因素:1.算法选用的策略;2.问题的规模;3.编写程序的语言;4.编译程序产生的机器代码的质量;5.计算机执行指令的速度。撇开软硬件等有关部门因素,可以认为一个特定算法“运行工作量”的大小,只依赖于问题的规模(通常用整数量n表示),或者说,它是问题规模的函数。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量可记作:T(n)=O(f(n))它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作渐进时间复杂度,简称时间复杂度。1.4.3算法效率的衡量一般地,常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。“O”的定义:若f(n)是正整数n的一个函数,则O(f(n))表示M≥0,使得当n≥n0时,|f(n)|≤M

|f(n0)|。表示时间复杂度的阶有:O(1):常量时间阶O(㏒n):对数时间阶O(n):线性时间阶O(n㏒n):线性对数时间阶O(n2):平方时间阶O(nk):k≥2,k次方时间阶1.4.3算法效率的衡量

以下六种计算算法时间的多项式是最常用的。其关系为:

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)

指数时间的关系为:

O(2n)<O(n!)<O(nn)当n取得很大时,指数时间算法和多项式时间算法在所需时间上非常悬殊。因此,只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法,那就取得了一个伟大的成就。例1

{++x;s=0;}将x自增看成是基本操作,则语句频度为1,即时间复杂度为O(1)。如果将s=0也看成是基本操作,则语句频度为2,其时间复杂度仍为O(1),即常量阶。例2两个n阶方阵的乘法

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];}由于是一个三重循环,每个循环从1到n,则总次数为:n×n×n=n3时间复杂度为T(n)=O(n3)例3for(i=1;i<=n;++i){++x;s+=x;}语句频度为:2n,其时间复杂度为:O(n),即为线性阶。例4for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}语句频度为:2n2,其时间复杂度为:O(n2),即为平方阶。定理:若A(n)=amnm

+am-1nm-1+…+a1n+a0是一个m次多项式,则A(n)=O(n

m)例5for(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),即此算法的时间复杂度为平方阶。例6冒泡排序法。Voidbubble_sort(inta[],intn){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.4算法的存储空间需求类似于算法的

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论