第1章绪论13-14new.ppt
《第1章绪论13-14new.ppt》由会员分享,可在线阅读,更多相关《第1章绪论13-14new.ppt(86页珍藏版)》请在三一文库上搜索。
1、1,数 据 结 构,主讲教师 :吴志刚 电 话 : 62506822 (O) Email : 答疑地点 :计算机科学系(9#305) 答疑时间 :每周三第二大节,中原工学院计算机学院,2,使用教材 严蔚敏、吴伟民 :数据结构(C语言版) 清华大学出版社 (1997) 严蔚敏、吴伟民 :数据结构习题集(C语言版) 清华大学出版社 (1997) 参考教材: 殷人昆 :数据结构(用面向对象方法与C+描述) 清华大学出版社 (1997) 胡学刚:数据结构算法设计指导 .清华大学出版社 李春保:数据结构习题与解析(C语言篇), 清华大学出版社,2001年1月。¥28 Bruno R.Preiss:数据
2、结构与算法 电子工业出版社 (2003) 其他参考资料: 学校图书馆、计算机学院资料室,3,考核成绩(本课程为考试课),平时成绩(30% ) 书面作业 10 (布置几次、是否按时交、质量如何) 课堂讨论和提问 5 (有成绩记录) 上机实验 10 (实验考勤、实验报告是否按时交、质量如何) 考勤与综合表现 5 (不缺课、不迟到、认真听课、遵守课堂纪律) 期末考试(70%) 诚信保证:“我XXX 真诚地保证:我自己独立地完成了整个作业、实验程序从分析、设计到编码的所有工作。我没有抄袭任何其他人的作业或代码。” 附在作业或实验报告前,4,内容安排(74=58+16)|60=48(6)+12,注:放假
3、占用6学时,实际授课学时为:58-6 =52,5,学习方式,听课:启发式,重在主动思考、积极参与 逐步培养分析问题、解决问题的技能。 上课要求:讨论时自由,听讲时绝对要保持安静! 读书:预习、复习(多研读算法) 作业、实验和课外作业(大作业):多实践 1、多做习题 2、多练习:算法转化为程序 3、多实践带有实际背景的算法问题,6,基于知识 能力与素质协调发展的瀑布式教学理念,7,教学理念获奖证书,2008年河南省教育科学研究优秀成果二等奖,8,教学理念获奖证书,2008年河南省信息技术教育优秀成果三等奖,9,教学理念获奖证书,2010年河南省高校教学技能竞赛二等奖,10,本课程的地位,是学习操
4、作系统、编译原理、数据库原理等计算机专业核心课程的基础和必要条件,考研的重头课; 必修的专业 计算机类、电讯通信类、信息管理类、信息安全 从事计算机应用、软件行业的必备条件。,教材P4 图1.4”数据结构“是介于数学、计算机硬件和计算机软件三者之间的一门核心课程,11,第一章 绪 论,1.1 什么是数据结构(数据结构讨论的范畴) 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求,12,课前索引,【重点和难点】 本章讨论的都是一些基本概念,因此没有难点,重点
5、在于了解有关数据结构的各个名词和术语的含义,以及语句频度和时间复杂度、空间复杂度的估算。 【知识点】 数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度 .,13,课前索引,【学习指南】 1. 熟悉各名词、术语的含义,掌握基本概念,特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质,哪些是存储结构的性质。 2. 了解抽象数据类型的定义、表示和实现方法。 3. 熟悉类C语言的书写规范,特别要注意值调用和引用调 用的区别,输入、输出的方式以及错误处理方式。 4. 理解算法五要素的确切含义和对算法正确性的理解。 5. 掌握计算语句频度和估算算法
6、时间复杂度的方法。,14,1.1 什么是数据结构,一、引言(数据结构的概况:引入) 概括地说,数据结构是与程序设计密切相关的一门课程,它主要是研究和解决非数值计算问题的程序设计中,如何合理地组织、存储和处理数据。 如:学生信息管理系统 :信息如何表示、处理(高效) 算法 + 数据结构 = 程序设计 (Algorithm + Data Structures =Programs) 瑞士著名计算机科学家、Pascal语言发明者N.沃思教授提出(经典书名) 。,15,1.1 什么是数据结构(续),程序设计(实质):编制一套让计算机按照人的旨意进行操作 (去处理问题)的一组有序“指令”。 ( 数据结构
7、+ 算法 = 程序设计 ) 程序设计首先需要解决两个问题: 数据结构:对处理的问题如何表示,即问题的数学模型是什么。 算 法:怎么去处理问题,即处理问题的策略(在该数学模型上的操作) (任何程序设计都包含这两方面的内容。 ),16,1、早期的计算机主要用于科学计算: 如天文研究、工程计算等方面的纯数值计算,方程求解等。 2、计算机技术的飞速发展引起其应用领域的扩大: 科学计算:天气预报 控制:工业自动化、航天飞机,数控机床 数据处理:声音、图形、图像, 管理:数据库,办公自动化 3、计算机处理的对象发生复杂变化,处理问题的方法 也非常复杂: 纯数值数据 非数值数据(具有一定的结构)如:字符、
8、表格、声音、图形、图像等,并且相互之间存在着联系。,二、数据结构的发展背景 -简略,用原有的处理数值数据的方法(代数/微分方程组),计算机无法识别、处理。,17,例一、图书馆的书目检索系统自动化问题。 一本书的书目信息(编者、书名、出版社、出版时间、定价等内容)如何在计算机内表示,如何检索(按书名、编者或是出版社)-显然上述问题无法用方程组来表示。 算法:? 模型:? (表格(交大) - :线性表(元素间线性关系) 例二、多交叉路口的红绿灯管理。 一般十字路口横竖两个方向都设有两个红绿灯,分别控制左拐、直行和右拐以保持正常的交通秩序,而在多叉路口需设几个红绿灯。那么如何控制这些红绿灯既使交通不
9、堵塞,又使流量最大呢?若要编制程序解决问题,首先要解决一个如何表示的问题。 模型:?:图(多对多网状关系) 算法:?:哪些路口可同时流通(绿色),而哪些不能(红色)-图着色问题,登录号 书名 作者名 分类号 ,非数值数据计算问题实例,18,例三、煤气管道的铺设问题。 如下图所示,需为城市的各小区之间铺设煤气管道,对 n 个小区只需铺设 n-1 条管线(若干种),由于地理环境不同等因素使铺设各条管线所需费用不同(如图上所标识),如何铺设使投资成本最低?这是一个讨论图的生成树的问题。 算法:? 图的最小生成树 模型:? 图,非数值数据处理实例(续),19,例四、人机对奕,棋盘为3x3,当一方的三个
10、棋子占同一方的同一行,或同一列,或同一对角线时,胜利。这里就存在棋子、棋盘格局的表示问题、对弈的过程有如何表示等问题。 算法:? 对弈的规则和策略 模型:? 树(棋盘及棋盘的格局) (一对多的层次关系) 树根是对弈开始之前的棋盘格局,所有的叶子就是可能出现的结局,对弈过程就是从树根沿树叉到某个叶子的过程。,非数值数据处理实例(续),20,从上述例子可以看出,要编程实现上述问题,必须解决两方面的问题: 、问题的数学模型的确立 首先要解决的是上述问题的描述,即问题的数学模型的建立,显然他们的数学模型不能用数学方程来描述。那么这些数学模型是什么,问题所涉及的对象如何表示。这正是数据结构所研究的主要对
11、象。 、确定在数学模型上进行的操作(找出处理问题的方法) 从问题抽象出其数学模型,这并不是数据结构课程研究的最终目的 ,而是讨论这些非数值计算问题中的数学模型怎么在计算机中表示,以及如何实现在数学模型上的操作。这正是数据结构这门课程所研究的主要内容。,三、数据结构所研究的范畴,21,概括地说,数据结构是一门讨论“非数值计算“的程序设计问题中的数学模型(现实世界的抽象描述)及施加在其上的操作在计算机中如何表示和实现的学科。 如学生信息管理系统中学生、成绩的表示及其查询、排序等操作实现。,三、数据结构所研究的范畴(续),22,数据结构涵盖的内容,23,一、基本概念和术语 数据(Data): 在计算
12、机科学中,是指所有能输入到计算机中并被计算机程序处理的符号的总称(集合)。 它是对客观事物的符号表示(描述),是计算机处理的信息的特定的符号表示形式(信息的载体) 。 数据结构中所讨论数据的范畴很广泛,如:字符、声音、图形、图像等多媒体信息。随着计算机的发展,数据的范畴不断扩大。,1.2 基本概念和术语(理解),24,数据元素(Data Element): 是数据(集合)中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的“基本单位”,但不是最小单位,它常常有若干数据项(是对数据元素不同属性的描述,具有独立的意义)组成。,一、基本概念和术语(2),比如,在学生信息管理
13、系统中,一条学生纪录就是一个数据元素(学号、姓名、性别等数据项组成)。,描述一个学生信息的数据元素由上述6个数据项组成,三者之间的关系:数据 数据元素 数据项,例: 班级通讯录 个人记录 姓名、年龄,25,关键字 指能识别一个或多个数据元素的数据项。若能起唯一识别作用,则称之为 “主” 关键字,否则称之为 “次” 关键字。 如:学生纪录(学号,姓名,性别,班级) 数据对象(Data Object): 是性质相同的数据元素的集合。是数据的一个子集。 如:整数、实数等。它们是数据的一个子集。,一、基本概念和术语(3),26,两类数据元素: 一类是不可分割的“原子”型数据元素,如:整数“5”,字符
14、“N” 等; 另一类是由多个款项构成的数据元素(结构型),其中每个款项被称为一个“数据项”,是对数据元素某种属性的描述,具有独立的意义。 例如描述一个学生信息的数据元素由下列6个数据项组成: 组合项,一、基本概念和术语(4),原子项,27,1、数据结构 定义: 是相互之间存在一种或多种特定关系(结构)的数据元素的集合。 说明:在客观世界中存在的各个事物之间存在着千丝万缕的“联系”,因此当用计算机对它进行处理的时候必然也要将这种关系描述进去,如数学方程就是变量之间的约束关系的一种描述,在此称这种关系为结构。 可以说,数据结构是一堆数据元素和这些数据元素之间的关系的总和, 换句话说,数据结构是带“
15、结构“的数据元素的集合。,二、数据结构(Data Structure),28,例如,一个2行3列的矩阵,含6个数据元素a1, a2, a3,a4,a5,a6 的集合,且集合上存在“行关系”和“列关系”两个次序关系, 可以用下述数据结构来描述: a1,a2,a3,a4,a5,a6 元素集合,其中 行关系为: , 列关系为:,。 -线性关系集合 以上所举数据结构例子中的关系都是“线性”的次序关系”,数据元素之间还可能存在非线性的关系,如1.1节中的“管道图”,人机对弈中的“树型”关系。,2、数据结构举例 NO,a1 a2 a3 a4 a5 a6,29,根据数据元素之间所存在的关系(结构)不同,数据
16、结构通常有四种基本类型: 线性结构:结构中的数据元素之间存在一对一的次序关系。 例,用三个 4 位数表示一个 12 位数:123456789123 可表示为: a1(1234),a2(5678),a3(9123) a1,a2,a3存在次序关系、,不同于、,树型结构:结构中的数据元素之间存在一对多的层次关系。 例如,三代家谱图(层次:辈分)。,3、数据结构的四种基本类型,30,图状结构或网状结构: 结构中的数据元素之间存在多对多的网状关系。 集合结构:结构中的数据元素除了同属于一种类型外,别无其它关系(特殊的关系)。,注:上述四种结构主要是对数据元素之间存在的逻辑关系的描述。,3、数据结构的四种
17、基本类型(续),31,解释: 什么叫数据的逻辑结构?,答:指数据元素之间的逻辑关系。即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。上述四类结构既是数据的逻辑结构:,集合结构: 仅同属一个集合 线性结构: 一对一(1:1) 树 结 构: 一对多(1:n) 图 结 构: 多对多 (m:n),非线性,线 性,数据的逻辑结构即可用图形表示,也可代数关系表示,32,数据结构的形式定义为一个二元组: Data-Structure=(D,S) 其中:D是数据元素的有限集, S是D上关系的有限集。 例 复数的数据结构定义如下: (复数x=C1 + C2 i ) Complex=(C,R) 其中
18、: C是含两个实数的集合C1,C2,分别表示复数的实部和虚部。 R=P,P是定义在集合上的一种序偶关系: 。 有序对,区别(),4、数据结构的形式定义(逻辑结构的表示),33,(1) S=(D, R) D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d),解: 上述表达式可用图形表示为:,b c a e f d,此结构为线性的。,例:用图形表示下列数据结构,并指出它们是属于 线性结构还是非线性结构。,二元组举例,34,(2) S=(D, R) D=di | 1i5 R=, 1 ij 5,d1 d5 d2 d4 d3,该结构是非线性的。,
19、解:上述表达式可用图形表示为:,思考: R= (di , dj), 1i,j5,35,三、数据的存储结构,数据结构应该包括数据的“逻辑结构”和数据的“物理结构”两个方面(层次)。 数据的逻辑结构,是对数据元素之间存在的逻辑关系的描述,它可以用图形表示,也可以用二元组表示。 数据的物理结构,又称数据的存储结构,是数据的逻辑结构在计算机中的表示(映像),包括数据元素的表示和关系的表示。,36,用二进制位(bit)的“位串” 表示数据元素 在计算机中表示信息的最小单位是“位(bit)”,任何一个数据元素都可以用一个 “位串” 表示,如: A=( 01000001)2 位串元素(结点) 当数据元素由多
20、个数据项构成时,每个数据项即为表示数据元素的位串中的一个“子位串“。,数据元素的表示(映像):,37,表示有序对的方法 所有的关系均可用一个有序对集合表示。 (注:有序对y是x的后继, x是y的前驱) 例如:有一个线性结构B=(D,R),其中 D=A,B,C,D,E A-B-C-D-E R=, 有序对集 一个的有序对是构成关系的基本单位,因此讨论关系的表示方法只需讨论这个有序对在计算机中的表示方法即可,即如何表示 “y是x的后继”。,关系的表示(映像)方法:,38,有序对的两种映象方法一:,顺序映象: 以数据元素存储位置的相邻表示后继关系 (逻辑相邻) 比如线性结构B=(D,R),R=, 顺序
21、存储示意图 顺序存储的特点: 用数据元素在存储器中的相对位置(相邻)来隐含地表示数据元素之间的逻辑关系,只存储数据元素本身的值,不用另外存储关系。缺点:占连续空间,顺序存储,39,有序对的两种映象方法二:,链式映象 有序对 以和x绑定在一起的附加信息(指针)表示后继关系,这个指针即为 y 的存储地址,由此得到的数据存储结构为“链式存储结构”。 结点结构 例如: R=, 结点 链式存储示意图 链式存储的特点: 不仅要存储数据元素本身,还要存储其关系信息(增加一个指向其后继的地址指针),链式存储,40,存储结构的描述方法 -简略,在不同编程环境中,存储结构有不同的描述方法。 当用高级程序编程时,通
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 绪论 13 14 new
链接地址:https://www.31doc.com/p-2093574.html