• / 35
  • 下载费用:10 金币  

实用数据结构基础(中国铁道出版社 第三版)第1章 绪论.ppt

关 键 词:
实用数据结构基础(中国铁道出版社 第三版)第1章 绪论.ppt
资源描述:
第1章 绪论,2011年5月11日星期三,1,第1章 绪论,知 识 点数据结构中常用的基本概念和术语 算法描述和分析方法 难 点 算法时间复杂度 要 求 了解数据的逻辑结构和物理结构;了解算法对于程序设计的重要性 ;掌握算法时间复杂度的分析方法 。,目 录,1-1 什么是数据结构 1-2 数据的逻辑结构 1-3 数据的存储结构1-4 算法和算法分析 小 结 实验1习题1,1-1 什么是数据结构1-1-1 从数据结构实验演示认识数据结构《数据结构实验演示》1-1-2 数据结构研究的内容用计算机解决具体问题需要经过的步骤: (1)从具体问题抽象出适当的数学模型; (2)设计解数学模型的算法; (3)编制程序、运行并调试程序,直到解决实际问 题。,【例1-1】学生入学情况登记问题表1-1 学生入学情况简表,【例1-2】井字棋对奕问题,,【例1-3】七桥问题,,图1-2 七桥问题,图1-3 欧拉回路,1-2 数据的逻辑结构,1-2-1 基本概念 1.数据(Data)数据是信息的载体,是对客观事物的符号表示。通俗的说,凡是能被计算机识别、存取和加工处理的符号、字符、图形、图象、声音、视频信号等一切信息都可以称为数据。 2. 数据元素(Data Element)数据元素是对现实世界中某独立个体的数据描述,是数据的基本单位。数据元素也称为结点(Node),在计算机中,常作为一个整体来处理。,3.数据项(Data Item)数据项是数据不可分割的、具有独立意义的最小数据单位,是对数据元素属性的描述。数据项也称为域,或字段(Field)。 4.数据对象(Data Object) 数据对象是性质相同的数据元素的集合,是数据的一个子集。例如在“学生入学情况表”中,数据对象就是全体学生记录的集合。 5.数据逻辑结构(Data Structure)数据的逻辑结构是相互之间存在的一种或多种特定关系的数据元素的集合。,(1)集合——结构中数据元素之间,除了“同属于一个集合”关系之外,别无其它关系。 (2)线性结构——结构中的数据元素之间存在着“一对一”的关系。 (3)树形结构——结构中的数据元素之间存在着“一对多”的关系。 (4)图形结构——结构中的数据元素之间存在着“多对多”的关系。,图1-4所示为四类基本数据结构的示意图,,,,,,,,,,,,,,,,,(b)线性结构,,,,,,,,,,,,,(c)树形结构,(d)图形结构,图1- 4 四类基本数据结构的示意图,,,,,,,,,,(a)集合结构,,,1-2-2 逻辑结构的描述,数据元素之间的逻辑关系,称为数据的逻辑结构。一个数据的逻辑结构可以用二元组来表示:G=(D,R)其中:D是数据元素的集合;R是D上所有数据元素之间关系的有限集合。 【例1-4】一种数据结构Line=(D,R),其中:D={01,02,03,04,05,06,07,08,09,10}R={r}r={,,,,,,,,},【例1-5】一种数据结构Tree=(D,R),其中:D={01,02,03,04,05,06,07,08,09,10}R={r}r={,,,,,,,,},,图1- 6 树形结构,【例1-6】一种数据结构 graph=(D,R),其中:D= {a,b,c,d,e}R={r}r={(a,b),(a,d),(b,d),(b,c),(b,e),(c,d),(d,e)},图1- 7 图形结构,圆括号表示的关系集合是无方向的,如(a,b)表示从a到b之间的边是双向的。其特点是各个结点之间都存在着多对多(M:N)的关系,即每个结点都可以有多个直接前驱或多个直接后继,如图1-7所示,我们把具有这种特点的数据结构叫做图形结,简称图。,1-3 数据的存储结构,数据元素及其关系在计算机存储器内的表示,称为数据的存储结构。四种不同的存储结构: 1. 顺序存储顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如,一个字母占一个字节,输入A、B、C、D、E,并存储在2000起始的连续的存储单元,如图1-8为顺序存储结构。,2000,2001,2002,2003,2004,图1-8 顺序存储结构,……,2. 链式存储借助指示元素存储地址的指针(Pointer)来表示数据元素之间的逻辑关系。例如,图1-9为表示复数z=2.0+4.8i的链式存储结构。其中地址2000存放实部,地址2100存放虚部,实部与虚部的关系用值为”2100”的指针来表示。,3. 索引存储索引存储是在原有存储数据结构的基础上,附加建立一个索引表,索引表中的每一项都由关键字和地址组成。索引表反映了按某一个关键字递增或递减排列的逻辑次序,主要作用是为了提高数据的检索速度。 4. 散列存储散列存储是通过构造散列函数来确定数据存储地址或查找地址的。例如:某一地区进行解放后出生人口的统计。我们用:“出生年份-1948=存储地址”来构造一个函数,就能方便的得到一个某地区解放后出生人口的调查表1-2。,1-4 算法和算法分析,1-4-1 算法特性 1.算法(Algorithm)算法是对特定问题求解步骤的一种描述,是指令的有限序列。其中每一条指令表示一个或多个操作。 2. 算法的特性:(1)有穷性 (2)确定性(3)可行性(正确性)(4)输 入 (5)输 出,3. 算法与程序的区别 (1)一个算法必须在有穷步之后结束;一个程序不一定满足有穷性。 (2)程序中的指令必须是机器可执行的,而算法中的指令则无此限制。 (3)算法代表了对问题的求解过程,而程序则是算法在计算机上的实现。算法用特定的程序设计语言来描述,就成了程序。 (4)算法与数据结构是相辅相承的。,4. 一个好算法应达到的目标 (1)正确性:算法应能满足设定的功能和要求 。 (2)可读性:思路清晰、层次分明、易读易懂 。 (3)健壮性:输入非法数据时应能作适当的反应和处理。 (4)高效性:执行同一问题时时间越短,算法的效率就越高。在有些专业书籍上健壮性也称为鲁棒性(为robust的音译)。 (5)低存储量:完成同一功能,占用存储空间应仅可能少。,1-4-2 算法的效率 事后统计法缺点 (1)必须先运行按照算法编写的程序。 (2)运行时间的统计依赖于计算机硬件和软件的环境,容易掩盖算法本身的优劣。 2 事先估算法 (1)使用何种程序设计语言; (2)采取怎样的 算法策略; (3)算法涉及的问题的规模; (4)编译程序产生的目标代码的质量; (5)机器执行指令的速度。,,1-4-3 算法效率的评价 算法效率的评价用时间复杂度(所需运算时间)和空间复杂度(所占存储空间)表示,重点是时间复杂度 。 1. 时间复杂度(Time Complexity)通常把算法中所包含简单操作次数的多少叫做算法的时间复杂度。但是当一个算法比较复杂时,其时间复杂度的计算会变得相当困难。实际上,没有必要精确地计算出算法的时间复杂度,只要大致计算出相应的数量级(Order)即可。一般情况下,算法中原操作重复执行的次数是规模n的某个函数f (n),算法的时间复杂度T(n)的数量级可记作:T(n)=O(f(n)) (1-1)它表示随着问题规模的扩大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。大写字母O为Order的字头。,【例1-7】交换A和B内容程序段的时间复杂度。 T=A;A=B;B=T; 3条语句的执行的频度均为1,执行时间是与问题规模n无关的常数,算法的时间复杂度为常数阶,即T(n)=O(1)。 【例1-8】执行时间与问题规模相关的例子 (1)x=0; y=0; // 执行2次; (2)for(k=1;k=n;k++) (3) x++; // 执行n次; (4)for(i=1;i=n;i++) (5)for(j=1; j=n;j++) (6) y++; // 执行n2次;执行以上所有语句次数之和为:n2+n+2。当n→∞时,显然有:所以,T(n)=O(n2),,【例1-9】交换A和B内容的另一种方法 (1)A=A+B; (2)B=A-B; (3)A=A-B;例1-9中的3条语句也实现了A和B内容的交换,虽然这种交换数据的方式不太直观,并且需要花费比例1-7更多的执行时间,但是和例1-7中交换数据采用的算法相比,例1-9中交换数据的方法节省了临时变量T所需的内存空间。其实很多实现同样功能的算法都具有这样一种特点:算法甲如果在执行时间上优于算法乙,那么算法乙一般会在执行所需的内存空间方面优于算法甲,有时很难找到一种在时间和空间效率上都很优的算法。在算法设计过程中,往往要根据实际条件的需要来决定是用时间来换空间,还是用空间来换时间。,,对于足够大的n,常用的时间复杂性存在以下顺序:O(1) O(lgn) O(n) O(n*lgn) O(n2) (n3) …… O(2n),2. 空间复杂度(Spase Complexity)一个程序的空间复杂度是指程序运行从开始到结束所需的存储空间。类似于算法的时间复杂度,我们把算法所需存储空间的量度,记作: S(n)=O(f(n))其中n为问题的规模。一个程序上机执行时,除了需要存储空间来存放本身所用的指令、常数、变量和输入数据以外,还需要一些对数据进行操作的工作单元和实现算法所必需的辅助空间。在进行时间复杂度分析时,如果所占空间量依赖于特定的输入,一般都按最坏情况来分析。,小 结,(1)数据结构就是研究数据的逻辑结构、存储结构和运算方法的学科。 (2)数据的逻辑结构包括:集合、线性结构、树形结构、图形结构四种类型。 (3)集合中不存在数据之间的关系;线性结构元素之间存在一对一的关系;树形结构元素之间存在一对多的关系;图形结构元素之间存在多对多的关系。具有一对多和多对多关系的结构又称为非线性结构。 (4)数据的存储结构包括:顺序存储、链式存储、索引存储、散列存储四种。,(5)顺序存储可以采用一维数组来存储;链式存储可以采用链表结构来存储;索引存储则在原有存储数据结构的基础上,附加建立一个索引表来实现,主要作用是为了提高数据的检索速度;而散列存储则是通过构造散列函数来确定数据存储地址或查找地址的。 (6)算法是对特定问题求解步骤的一种描述,是指令的有限序列。算法具有:有穷性、确定性、正确性、输入、输出等特性。 (7)一个好的算法应该达到:正确性、可读性、健壮性、高效性和低存储量等目标。,(8)算法的效率通常用时间复杂度与空间复杂度来评价,应该逐步掌握其基本分析方法。 (9)通常把算法中包含简单操作次数的多少叫做算法的时间复杂度。一般只要大致计算出相应的数量级即可;一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。 (10)一个算法的时间和空间复杂度越好,则算法的效率就越高。,验证性实验1,1.实验目的 (1)复习C(或C++)语言数组的用法; (2)复习C(或C++)语言指针的用法; (3)复习C(或C++)语言结构体的用法; (4)理解算法时间复杂度分析的基本方法; (5)通过实验程序,分析它们的时间复杂度。 2.实验内容 (1)将1~10存入数组a[10],并将其逆序输出。 (2)用指针方式编写程序:从键盘输入10个整型数据,并存入数组,要求将10个数中最大的数与第1个输入的数交换;将10个数中最小的数与最后1个输入的数交换。,(3)有5个学生,每个学生的数据包括学号、姓名、三门课的成绩、平均分。要求:从键盘依次输入5个学生的学号、姓名、三门课成绩,自动计算三门的平均分,并将5个学生的数据在屏幕上输出。,自主性实验1 学生成绩分析程序,1.实验目的 (1)复习C(或C++)语言的基本描述方法。 (2)熟练掌握数组的用法。 (3)提高运用C(或C++)语言解决实际问题的能力。 2.实验内容 设一个班有10个学生,每个学生有学号,以及数学、物理、英语、语文、体育5门课的成绩信息。分别编写3个函数以实现以下3个要求: (1)求数学的平均成绩。 (2)对于有两门以上课程不及格的学生,输出他们的学号、各门课成绩及平均成绩。 (3)输出成绩优良的学生(平均成绩在85分以上或全部成绩都在80分以上)的学号、各门课成绩和平均成绩。 用抓图的形式粘贴到实验报告上)。,3.实验要求 (1)利用C(或C++)语言完成程序设计。 (2)上机调试通过实验程序。 (3)输入10个学生的学号和数学、物理、英语、语文、体育5门课的成绩,检验程序运行的正确性。 (4)总结整个程序的组成和设计思想。 (5)撰写实验报告(把输入数据及运行结果,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:实用数据结构基础(中国铁道出版社 第三版)第1章 绪论.ppt
链接地址:https://www.weizhuannet.com/p-10054327.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开