《ch1 绪论.ppt》由会员分享,可在线阅读,更多相关《ch1 绪论.ppt(43页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、张敬敏个人邮箱:个人邮箱:公共邮箱:公共邮箱:密码:密码:zjmds_2012课程简介课程简介主要内容:主要内容:1.什么是数据结构,为什么学习数据结构什么是数据结构,为什么学习数据结构 2.几种常规的数据结构:线性表,栈和队列,树和二叉树,图几种常规的数据结构:线性表,栈和队列,树和二叉树,图 3.排序和查找排序和查找教材教材 数据结构数据结构C语言版语言版 严蔚敏、吴伟民,清华大学出版社严蔚敏、吴伟民,清华大学出版社参考书参考书 数据结构数据结构 题型题型 题集题集 题解,刘坤起,科学出版社题解,刘坤起,科学出版社 课时安排课时安排 授课授课 :64+24学时学时考核方式考核方式本课程的考
2、核方式为考试。总成绩由平时成绩和考试成绩组成。平时成本课程的考核方式为考试。总成绩由平时成绩和考试成绩组成。平时成绩占绩占30%,考试成绩占,考试成绩占70%。平时成绩平时成绩=到课率到课率(缺一次扣缺一次扣2分分)+实验报告实验报告(少一次扣少一次扣5分分)+闪光点闪光点(2次,次,则平时成绩为满分则平时成绩为满分)1.1 什么是数据结构什么是数据结构1.2 基本概念和术语基本概念和术语 (重点)(重点)1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现(难点)(难点)1.4 算法和算法分析算法和算法分析1.4.1 算法算法1.4.2 算法设计的要求算法设计的要求1.4.3 算法效率的
3、度量算法效率的度量(重点、难点)(重点、难点)1.4.4 算法的存储空间需求算法的存储空间需求第一章第一章 绪论绪论数据结构的非形式定义数据结构的非形式定义数值计算问题的求解数值计算问题的求解特征:特征:基于代数运算的计算问题,例如,矩阵运算、方程组的求基于代数运算的计算问题,例如,矩阵运算、方程组的求解和数字信号处理,等等。解和数字信号处理,等等。举例举例 百鸡百钱问题百鸡百钱问题。公元前五世纪末,我国数学家张丘建在。公元前五世纪末,我国数学家张丘建在算算经经中提出了该问题。问题是这样的中提出了该问题。问题是这样的:“:“鸡翁一值钱五,鸡母一值鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。凡百钱
4、买百鸡,问鸡翁、鸡母、鸡雏各几钱三,鸡雏三值钱一。凡百钱买百鸡,问鸡翁、鸡母、鸡雏各几何?何?”分析并建立数学模型:分析并建立数学模型:设鸡翁的个数为:设鸡翁的个数为:cockcock只,鸡母的个数为:只,鸡母的个数为:henhen只只,鸡雏的个数为:鸡雏的个数为:chickchick只。依题意得到下列方程组:只。依题意得到下列方程组:cock+hen+chickcock+hen+chick=100=100 5cock+3hen+chick/3=100 5cock+3hen+chick/3=100 这就是描述该问题的这就是描述该问题的数学模型数学模型。它是一个它是一个不定方程组不定方程组,其解
5、,其解即为问题的解。即为问题的解。算法设计算法设计 基本思想:用穷举方法求解不定方程,即先穷举满足百鸡条件的基本思想:用穷举方法求解不定方程,即先穷举满足百鸡条件的鸡翁、鸡母、鸡雏的数目,然后再从这些数目中挑选出满足百钱条件鸡翁、鸡母、鸡雏的数目,然后再从这些数目中挑选出满足百钱条件的鸡翁、鸡母、鸡雏的数目。的鸡翁、鸡母、鸡雏的数目。算法如下:算法如下:循环:循环:cockcock从从0 0到到1919,步长为,步长为1 1,做,做 循环:循环:henhen从从0 0到到3333,步长为,步长为1 1,做,做 chick100-cock-hen;chick100-cock-hen;若若5coc
6、k+3hen+chick/3=1005cock+3hen+chick/3=100,则,则 输出输出 cock,hen,chickcock,hen,chick的值(得到一个解)的值(得到一个解);编码:略。编码:略。上机调试程序上机调试程序利用计算机解题的过程利用计算机解题的过程 首先经过首先经过分析问题分析问题,从中抽象出一个适当的,从中抽象出一个适当的数学模型数学模型,然,然后设计或选择一个解此数学模型的后设计或选择一个解此数学模型的算法算法,最后编出,最后编出程序程序进行进行调试调试、测试测试,直至直至得到最终的解答得到最终的解答。解决问题的关键在于。解决问题的关键在于数数学模型的建立和算
7、法的设计学模型的建立和算法的设计。例1 书目自动检索系统登录号:登录号:书名:书名:作者名:作者名:分类号:分类号:出版单位:出版单位:出版时间:出版时间:价格:价格:书目卡片书目卡片书目文件书目文件按按书名书名按按作者名作者名按按分类号分类号索引表索引表线性结线性结构构非数值计算问题例2 人机对奕问题树.非数值计算问题例3 多叉路口交通灯管理问题ABACADBABCBDDADBDCEAEBECED图CEDAB非数值计算问题求解非数值计算的问题求解非数值计算的问题:主要考虑的是设计出主要考虑的是设计出合适的数据结构合适的数据结构及相应的及相应的算法算法。首先首先要考虑对相关的各种要考虑对相关的
8、各种信息信息如何表示、组织和存储?如何表示、组织和存储?因此,可以认为因此,可以认为:数据结构是一门研究数据结构是一门研究非数值计算非数值计算的程序设的程序设计问题中计算机的计问题中计算机的操作对象操作对象以及它们之间的以及它们之间的关关系系和和操作操作的学科。的学科。数据结构是指带运算的具有一定逻辑关系的数数据结构是指带运算的具有一定逻辑关系的数据构成的集合。据构成的集合。数据结构课程的形成和发展:数据结构课程的形成和发展:形成阶段:形成阶段:60年代初期年代初期,“数据结构数据结构”有关的内容散见于有关的内容散见于操作系统、编译原理和表处理语言等课程。操作系统、编译原理和表处理语言等课程。
9、1968年,年,“数据结构数据结构”被列入美国一些大学计算机科学系的被列入美国一些大学计算机科学系的教学计划。教学计划。发展阶段:发展阶段:数据结构的概念不断扩充,包括了网络、集合代数据结构的概念不断扩充,包括了网络、集合代数论、关系等数论、关系等“离散数学结构离散数学结构”的内容。的内容。70年代年代后期,我国高校陆续开设该课程。后期,我国高校陆续开设该课程。数据结构课程数据结构课程所处的地位所处的地位为什么要学习数据结构为什么要学习数据结构1、什么是程序、软件?、什么是程序、软件?程序程序=算法算法+数据结构数据结构 N.沃思(沃思(Niklaus Wirth)算法是程序的算法是程序的骨架
10、骨架,而数据结构是程序的,而数据结构是程序的血脉血脉;数据结构是研究数据结构是研究非数值数据非数值数据的的数学建模数学建模和和数据表示数据表示的;的;软件软件=程序程序+文档(软件工程的观点)文档(软件工程的观点)NiklausNiklaus Wirth Wirth(尼克劳斯(尼克劳斯沃思,沃思,19341934)男,瑞士人,1963年获得加州大学伯克利分校哲学博士,苏黎士联邦高等工业学校教授。他是Pascal语言之父及结构化程序设计的首创者,提出了著名的“数据结构+算法=程序”公式。因开发了EULER、ALGOL-W、MODULA和PASCAL一系列崭新的程序设计语言而获得1984年图灵奖。
11、2.2.电子计算机的主要用途电子计算机的主要用途(1)(1)数值计算数值计算 早期早期 求解梁架结构中的应力问题求解梁架结构中的应力问题 线性方程线性方程人口增长情况预报人口增长情况预报 微分方程微分方程(2)(2)非数值计算非数值计算 后来后来3.3.现实问题求解的一般步骤现实问题求解的一般步骤(1)数值计算数值计算 数学模型数学模型选择计算机语言选择计算机语言 编出程序编出程序测试测试最终解答最终解答 关键是:如何得出数学模型(方程)?关键是:如何得出数学模型(方程)?程序设计人员比较关注程序设计的技巧。程序设计人员比较关注程序设计的技巧。(2)非数值计算问题非数值计算问题数据元素之间的相
12、互关系一般数据元素之间的相互关系一般无法无法用数学方程加以描述用数学方程加以描述1.2 基本概念和术语基本概念和术语(重点)(重点)数据(数据(data)所有能输入到所有能输入到计算机计算机中去的中去的描述客观事物的符号描述客观事物的符号 整数的子集是数据整数的子集是数据 中文文字组成的任何形式的信息是数据中文文字组成的任何形式的信息是数据 图像、声音和视频是数据图像、声音和视频是数据 甲骨文不是数据甲骨文不是数据 某些少数民族文字不是数据某些少数民族文字不是数据 左边示意图中左边示意图中的每个小方框再进的每个小方框再进一步缩小就成为一一步缩小就成为一个点,称为像点,个点,称为像点,每个像点可
13、以用行每个像点可以用行号、列号、色彩来号、列号、色彩来表示(或存储),表示(或存储),将所有像点存储起将所有像点存储起来,就存储了一幅来,就存储了一幅图像。这就是图像图像。这就是图像的数字化。的数字化。以图像为例说明图像是数据以图像为例说明图像是数据数据元素(数据元素(data element)数据的数据的基本单位基本单位,也称,也称节点(节点(node)或记录(或记录(record)数据项(数据项(data item)有独立含义的数据有独立含义的数据最小单位最小单位,也称域也称域(field)数据对象(数据对象(data object)性质相同的数据元素的集性质相同的数据元素的集合,是数据的
14、一个子集。合,是数据的一个子集。客观世界中的数据都不是孤立存在的,换句话客观世界中的数据都不是孤立存在的,换句话说数据之间是有联系的。人们应用计算机处理各种说数据之间是有联系的。人们应用计算机处理各种各样的数据,必然要涉及到数据之间的联系。各样的数据,必然要涉及到数据之间的联系。数据结构数据结构(data structure)指相互之间存在指相互之间存在一种或多种特定关系的数据元素的集合。一种或多种特定关系的数据元素的集合。教师手中的学生花名册是数据结构教师手中的学生花名册是数据结构 列车时刻表是数据结构列车时刻表是数据结构 某大学全体师生是数据结构某大学全体师生是数据结构 某城市公共交通地理
15、图是数据结构某城市公共交通地理图是数据结构n数据结构的形式定义数据结构的形式定义n数据结构是一个二元组:数据结构是一个二元组:nData-Structure=(D,S)n其中:其中:nD是数据元素的有限集,是数据元素的有限集,S是是D上关系的有限集。上关系的有限集。n例例 复数的数据结构定义如下复数的数据结构定义如下:n Complex=(C,R)n其中:其中:nC是含两个实数的集合是含两个实数的集合C1,C2,分别表示复数的实部和分别表示复数的实部和虚部。虚部。nR=P,P是定义在集合上的一种关系是定义在集合上的一种关系C1,C2。元元素之间存在多对多的关系。素之间存在多对多的关系。根据数据
16、元素间关系的基本特性,有四种基本数据结构根据数据元素间关系的基本特性,有四种基本数据结构(集合)(集合)数据元素间除数据元素间除“同属于一个集合同属于一个集合”外,无其它关系外,无其它关系线性结构线性结构一个对一个,如线性表、栈、队列一个对一个,如线性表、栈、队列树形结构树形结构一个对多个,如树一个对多个,如树图状结构图状结构多个对多个,如图多个对多个,如图数据结构包括数据的数据结构包括数据的逻辑结构逻辑结构和数据的和数据的物理结构物理结构。1.1.数据的数据的逻辑结构逻辑结构只抽象反映数据元素的只抽象反映数据元素的逻辑关系逻辑关系2.2.数据的数据的存储(物理)结构存储(物理)结构数据的逻辑
17、结构在计算机数据的逻辑结构在计算机存存储器中的实现储器中的实现/在计算机中的表示在计算机中的表示/在计算机中的映像在计算机中的映像数据的逻辑结构数据的逻辑结构数据的逻辑结构与存储结构密切相关算法设计 逻辑结构算法实现 存储结构存储结构按照数据元素之间的关系在计算机中的两种不同的表示方法分为:顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系存储结构的表示:不以内存地址描述,借用高级语言中的的“数据类型”来描述。如:“一维数组”表示顺序存储结构,以C语言的“指针”描述链式存储结构。元素元素n n.元素元素i i.元素元
18、素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+(n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+(i-1)*m顺序存储顺序存储1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4 4 .14001400 元素元素2 2 15361536 .15361536 元素元素3 3 13461346 链式存储链式存储 h 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算:检索、排序
19、、插入、删除、修改等数据的运算:检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面:数据结构的三个方面:本课程授课内容的体系组织与主线授课内容的体系组织授课内容的体系组织 利用抽象数据类型组织数据结构的内容,利用抽象数据类型组织数据结构的内容,与现代程序理论与技术的发展形成了一致。与现代程序理论与技术的发展形成了一致。主线主线 以每一种以每一种“ADTADT的定义的定义ADTADT的实现的实现ADTADT的应用的应用”为主线展开。为主线展开。线索构成了知识体系的骨架。
20、线索构成了知识体系的骨架。数据类型高级语言中指数据的高级语言中指数据的取值范围取值范围及其上可进行及其上可进行的的操作操作的总称的总称例C语言中,提供int,char,float,double基本数据类型,数组、结构体、共用体、枚举等构造数据类型,还有指针、空(void)类型等。用户也可用typedef自己定义数据类型typedefstructintnum;charname20;floatscore;STUDENT;STUDENTstu1,stu2,*p;1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现本本节节是是难难点,点,重重在在理理解解抽象数据类型(抽象数据类型(abstract
21、 data type)指指数学模型数学模型以及定义在该模型上的一组以及定义在该模型上的一组操作操作.抽象数据类型抽象数据类型和和数据类型数据类型实质上是实质上是一个一个概念。概念。抽象数据类型的三元组表示抽象数据类型的三元组表示ADT=(D,S,P)其中其中:D:数据对象数据对象S:D上的关系集上的关系集P:对:对D的基本操作集的基本操作集本书本书采用如下格式采用如下格式定义抽象数据类型定义抽象数据类型ADT 抽象数据类型名抽象数据类型名 数据对象数据对象:数据关系数据关系:基本操作基本操作:ADT 抽象数据类型名抽象数据类型名其中其中:数据对象数据对象和和数据关系数据关系的定义可以用的定义可
22、以用伪码伪码表示表示基本操作基本操作的的定义格式定义格式为为基本操作名基本操作名(参数表参数表)初始条件初始条件:操作结果操作结果:例例 抽象数据类型抽象数据类型“三元组三元组”的定义的定义ADTTriplet数据对象数据对象:D=e1,e2,e3|e1,e2,e3ElemSet(定义了关系运算的某个集合)数据关系数据关系:R1=,基本操作基本操作:InitTriplet(&T,v1,v2,v3)操作结果:构造一个三元组T,元素e1,e2和e3分别被赋以参数v1,v2和v3的值。DestroyTriplet(&T)操作结果:三元组T被销毁。Get(T,i,&e)初始条件:三元组T已存在,1i3
23、。操作结果:用e返回T的第i个元的值。Put(&T,i,e)初始条件:三元组T已存在,1i3。操作结果:改变T的第i元的值。IsAscending(T)初始条件:三元组T已存在。操作结果:如果T的三个元素按升序排列,则返回1,否则返回0。IsDescending(T)初始条件:三元组T已存在。操作结果:如果T的三个元素按降序排列,则返回1,否则返回0。Max(T,&e)初始条件:三元组T已存在。操作结果:用e返回T的三个元素中的最大值。Min(T,&e)初始条件:三元组T已存在。操作结果:用e返回T的三个元素中的最小值。ADTTriplet基本操作有两种参数:赋赋值值参数只为操作提供输入值;引
24、引用用参数以&打头,除可提供输入值外,还将返回操作结果。所以:如果需要返回操作结果,就用引用参数。TripletLInitTriplet(L,1,2,5)Get(L,2,e)Put(L1,7)数据结构、抽象数据类型与程序设计语言中的数数据结构、抽象数据类型与程序设计语言中的数据类型的概念据类型的概念三者三者之间的之间的异同异同相同相同点:点:本质一致本质一致(都包括(都包括3方面)方面)不同不同点:点:表现形式不同表现形式不同联系联系:数据结构数据结构-ADT 后更容易写程序后更容易写程序ADT借助已有的借助已有的DT来实现来实现 教材教材p9 ADT三元组的三元组的定义定义。教材教材p12
25、ADT三元组的三元组的表示和实现表示和实现(伪伪c)。)。程序程序(也叫(也叫实现实现,即,即c程序,程序,c+程序程序)。)。1.4 算法和算法分析算法和算法分析算法算法(algorithm)对特定问题的求解步骤的一般描述求解步骤的一般描述,是指令的有限序列算法的算法的评价评价(衡量算法优劣的标准)/算法设计的要求正确性正确性(correctness)可读性可读性(readability)健壮性健壮性(robustness)/鲁棒性鲁棒性效率与低存储量效率与低存储量 算法算法特性特性n(1)有穷性有穷性-执行了有限条指令后一定要终止执行了有限条指令后一定要终止。n(2)确定性(无二义确定性(
26、无二义)-算法的每一步操作都必须有确切定义,不得有任何歧算法的每一步操作都必须有确切定义,不得有任何歧义性。义性。n(3)可(能)行性可(能)行性-算法的每一步操作都必须是可行的,即每步操作均能在有算法的每一步操作都必须是可行的,即每步操作均能在有限时间内完成。限时间内完成。n(4)输入数据输入数据-一个算法有一个算法有n(n=0)个初始数据的输入。个初始数据的输入。n(5)输出数据输出数据-一个算法有一个或多个与输入有某种关系的有效信息的输出。一个算法有一个或多个与输入有某种关系的有效信息的输出。算法的描述描述本课程采用类类C语言(c+)算法效率算法效率用依据该算法编制的用依据该算法编制的程
27、序程序在计算机上执行所在计算机上执行所消消耗的时间耗的时间来度量来度量1.1.事后统计事后统计利用计算机内记时功能,不同算法的程序可利用计算机内记时功能,不同算法的程序可以用一组或多组相同的统计数据区分。以用一组或多组相同的统计数据区分。缺点:缺点:必须先运行依据算法编制的程序必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素,所得时间统计量依赖于硬件、软件等环境因素,掩盖算法本身的优劣掩盖算法本身的优劣 2.2.事前分析估计事前分析估计一个高级语言程序在计算机上运行所消一个高级语言程序在计算机上运行所消耗的时间取决于:耗的时间取决于:依据的算法选用何种策略依据的算法选用何
28、种策略 问题的规模问题的规模 程序语言程序语言 编译程序产生机器代码质量编译程序产生机器代码质量 机器执行指令速度机器执行指令速度 结论结论:同一个算法用不同的语言、不同的编译程序、在不同:同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行,效率均不同,的计算机上运行,效率均不同,所以使用所以使用绝对时间单绝对时间单位位衡量算法效率衡量算法效率不合适不合适基本操作重复执行的次数基本操作重复执行的次数记为记为f(n)n:问题的规模:问题的规模 n无穷大无穷大T(n)=O(f(n):表示随问题规模:表示随问题规模n的增大,的增大,算法执行时间的增算法执行时间的增长率和长率和f(n)的增长
29、率相同的增长率相同,称为算法的,称为算法的(渐进)时间复杂度(渐进)时间复杂度 例例1:两个两个N*N矩阵相乘矩阵相乘for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=n;k+)cij=cij+aik*bkj;语句的频度:是指该语句重复执行的次数语句的频度:是指该语句重复执行的次数 n例例2 +x;s=0;nf(n)=1nT(n)=O(f(n)=(1)n例例3 for(i=1;i=n;+i)+x;s+=x;nf(n)=nnT(n)=O(f(n)=O(n)一些特殊情况采用一些特殊情况采用平均复杂度、最好复杂度、最坏复杂度平均复杂度、最好复杂度、最坏复杂度
30、n如如 冒泡排序冒泡排序n本书本书以后各章以后各章,无特殊说明都指,无特殊说明都指,最坏情况下的复杂度最坏情况下的复杂度以下六种计算算法时间的以下六种计算算法时间的多项式多项式是最常用是最常用的。其关系为:的。其关系为:O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数指数时间的关系为:时间的关系为:O(2n)O(n!)O(nn)当当n取得很大时,指数时间算法和多项式时间算法在所需取得很大时,指数时间算法和多项式时间算法在所需时间上非常悬殊。因此,只要有人能将现有指数时间算时间上非常悬殊。因此,只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法,那就取得法中的
31、任何一个算法化简为多项式时间算法,那就取得了一个了一个伟大的成就伟大的成就。算法的存储空间的需求算法的存储空间的需求空间复杂度空间复杂度:S(n)=O(f(n)n:问题的规模问题的规模数据、数据结构等基本概念数据、数据结构等基本概念(掌握)(掌握)数据结构的数据结构的三个方面三个方面的内容的内容(掌握)(掌握)线性和非线性结构的线性和非线性结构的逻辑逻辑特征特征(掌握)(掌握)数据数据存储存储的的2种基本方法种基本方法(掌握)(掌握)ADT(理解)(理解)算法、算法的算法、算法的时间复杂度时间复杂度(掌握)(掌握)本章小结本章小结课课 堂堂 练练 习习1.设数据结构设数据结构A=(D,R),其
32、中,其中D=a,b,c,d,R=r,r=,则数据结构,则数据结构A是(是()。)。(A)线性结构线性结构 (B)树型结构树型结构 (C)图型结构图型结构 (D)集合集合2.计算机中的算法指的是解决某一问题的有限运算计算机中的算法指的是解决某一问题的有限运算序列,它必须具备输入、输出、(序列,它必须具备输入、输出、()等五个特)等五个特征。征。(A)有效性、可移植性和可扩充性有效性、可移植性和可扩充性 (B)有效性、有穷性和确定性有效性、有穷性和确定性 (C)确定性、有穷性和稳定性确定性、有穷性和稳定性 (D)易读性、稳定性和确定性易读性、稳定性和确定性3.设设n为偶数,试计算运行下面的为偶数,
33、试计算运行下面的C语言程序段后语言程序段后m的值,并给出该程序段的时间复杂度。(要求给的值,并给出该程序段的时间复杂度。(要求给出分析计算过程)出分析计算过程)m=0;for(i=1;i=n;i+)for(j=2*i;j=n;j+)m+;课堂练习答案课堂练习答案1.C 2.B3.答案:答案:首先分析出程序段的基本操作是首先分析出程序段的基本操作是m+,然后计算出基本操作的重复执行次数为:然后计算出基本操作的重复执行次数为:(n-1)+(n-3)+(n-5)+3+1=n2/4.所以,所以,m 的值的值是是 n2/4 时间复杂度为:时间复杂度为:O(n2)作 业给出下面几个给出下面几个C语言程序段的时间复杂度。语言程序段的时间复杂度。(1)int i=1;while(i=(y+1)*(y+1)y+;(3)for(i=1;i=n;i+)if(3*i=n)for(j=3*i;j=n;j+)x=x+1;y=3*x+2;(1)O(log5n);(2)O(n);(3)O(n2)。
限制150内