绪论数据结构与算法.pptVIP

课程编号：T050307 英文译名：DATA STRUCTURE and ALGORITHMS 总 学 时：52/12 授课对象：计算机科学与技术 本科生 先修课程：集合与图论、C程序设计 课程要求：必修课 课程分类：技术基础 授课教师：廖明宏 郭茂祖 张岩 李秀坤 李治军 答疑地点：综合楼516、D楼实验室 办公电话86413341 课程网站： 教学目的: (1)学会分析和研究计算机处理的数据对象的特性,掌握常用数据结构内在的逻辑关系、在机内的存储表示,掌握常用数据结构上的运算操作的动态性质和执行算法. (2)能够为实际应用选择适当的数据结构、存储结构和相应算法； (3)初步掌握算法性能的分析方法。 考核要求： (1)考试:70%; (2)作业:10%; (3)实验:20%; 1.1数据结构的研究对象 1.2数据结构的发展概况 1.3抽象数据型(ADT) 1.4逐步求精的程序设计方法 1.1数据结构的研究对象 1.1.1基本概念和术语 1.1.2四种基本的逻辑结构 1.1.3四种基本的存储结构 1.1.4数据结构的研究对象 1.1.1基本概念和术语 一.客观世界与计算机世界的关系 客观世界 概念世界 机器世界 映象 抽象 映象 实现 (逻辑模型) 映象 模拟 客观世界与计算机的关系 计算机科学是研究信息表示和信息处理的科学。信息在计算机内是用数据表示的。用计算机解决实际问题的实质可以用下图表示： 二.基本概念和术语 1.数据: 数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。 2.数据元素 数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。 3.数据项 是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。 4.数据对象 性质相同的元素的集合叫做数据对象。 5.结点 数据元素在机内的位串表示，即数据元素在计算机内的映象。 6.域/字段 当数据元素由若干个数据项组成时，位串中对应于各个数据项的子串称为域/字段，是数据元素中数据项在计算机中的映象。 7.信息表 计算机程序所作用的一组数据通常称为信息表，是数据对象在计算机中的映象。 8.数据结构 数据结构指的是数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数据元素及其相互间的关系的数学描述。 9.逻辑结构和存储结构 (1)逻辑结构 数据结构中描述的是数据元素之间的抽象关系(逻辑关系)，称为逻辑结构。 (2)存储结构/物理结构 数据结构在计算机中的表示（映象）称为存储结构/物理结构。 (3)数据元素之间的关系（逻辑结构）在计算机中有两种表示方法：顺序映象(表示)和非顺序映象(表示)，从而导致两种不同的存储结构：顺序结构和链式结构。 顺序映象（表示）的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 非顺序映象（表示）的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系。 1.1.2四种基本的逻辑结构 1.集合结构 结构中的数据元素之间除了撌粲谕桓黾蠑的关系之外，别无其他关系。关系比较松散，可用其他结构来表示。 结构中的数据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继。 2.线性结构 3.树型结构 结构中的数据元素之间存在一个对多个的关系，即层次关系，即每一层上的元素可能与下层的多个元素相关，而至多与上层的一个元素相关。 结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系。 4.网状/图型结构 一般将逻辑结构分为线性结构（2）和非线性结构（ 1，3，4 ）两种。 1.1.3四种基本的存储方式 1.顺序存储方式 。 。 2.链式存储方式 1.1.3四种基本的存储方式 。 4.散列存储方式 3.索引存储方式 。 1.1.4数据结构的研究对象 数据结构的研究对象(研究内容) 1.数据对象的结构形式,各种数据结构的性质(逻辑结构); 2.数据对象和敼叵禂在计算机中的表示(物理结构/存储结构); 3.数据结构上定义的基本操作(算法); 4.算法的效率; 5.数据结构的应用,如数据分类,检索. 1.2数据结构的发展概况 1.程序设计方法学的发展极大地促进了数据结构的发展 2.数据结构在计算机科学中的地位 (1)计算机科学及其应用的发展时数据结构成为独立学科. (2)以数据为中心的程序设计方法推动了数据结构的发展. 面向过程的程序设计的特点是以程序为中心,侧重于建立程序,程序在简单的数据结构上进行复杂的运算,软件设计的主要工作就