《数据结构课件2.pptx

数据结构电子教案第一章 数据结构概论殷人昆 王宏第一章 数据结构概论什么是数据结构抽象数据类型及面向对象概念算法定义算法简单性能分析与度量示例 —“学生”表格“课程”表格 “选课单”包含如下信息 学号 课程编号 成绩 时间 学生选课系统中实体构成的图状结构课程(课程号,课程名,学分)学生(学号,姓名,性别,籍贯)选课(学号,课程号,成绩)/ (root)userbinetclibswyinwh jiamathdsqueue.cppstack.cpptree.cppUNIX文件系统的结构图(层次结构)数据（Data）数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据的分类： 数值型数据（整数、浮点数、双精度数） 非数值型数据（字符、文字、语音、图形、图像）数据元素 (Data Element)数据的基本单位是数据元素 。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项 (data item)组成。数据项是具有独立含义的最小标识单位（初等项与组合项）。数据元素又称为元素、结点、记录。姓名学号性别出生年月年 月籍贯所在院系112233665454 数据元素之间通常不是孤立的，它们往往存在这样或那样的关系，数据元素之间的这种关系称为结构。例：N 个顶点之间的连通关系 树结构图结构什么是数据结构 由某一数据元素的集合以及该集合中所有 数据元素之间的关系组成。记为： Data_Structure = {D, R} 其中，D 是某一数据元素的集合，R 是该集合中所有数据元素之间的关系的有限集合。 数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和数据的运算。数据结构反映数据的组织形式包括三个方面：数据元素间的逻辑关系，即数据的逻辑结构；数据元素及其关系在计算机存储内的表示，即数据的存储表示 (存储结构)；数据的运算，即对数据元素施加的操作。数据的逻辑结构分类数据的基本逻辑结构1. 线性结构 1 (除始结点与终结点外，每个结点有唯一的前驱和后继)2. 非线性结构 * 层次结构 　 树结构 2 (除根外每个结点有唯一的前驱，但后继不加限制) * 群结构（元素同属于一个集合，但无顺序关系） 图结构与网络结构 3 (结点的前驱与后继数目均无限制)useretcdevbinlib19164331322566878953410108795711112131411线性结构层次结构　树形结构 树\多叉树 二叉树121119257106163107354828941112堆结构 一种特殊的树结构 “最大”堆“最小”堆16121221519663116333146554418图结构 网络结构数据的存储结构数据的存储结构是各种逻辑结构在计算机中的物理存储表示；建立一种由逻辑结构到物理存储空间的映射数据的4种存储结构（依赖于计算机语言） 顺序存储 链接存储 索引存储 散列存储主要用于内存数据的存储表示 数据的四种存储结构顺序存储 逻辑上相邻的元素存放在物理位置相邻的存储单元中链接存储 元素之间的逻辑关系由附加的指针指示索引存储 在存储元素信息的同时建立附加的索引表散列存储 根据结点的关键码通过一个散列函数计算得到存储地址抽象数据类型及面向对象概念数据类型 数据类型是一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称。在程序设计语言中，一个变量的数据类型不仅规定了变量的取值范围，而且定义了该变量可用的操作。例：C语言中的基本数据类型 charint float double void 字符型 整型 浮点型 双精度型 无值 构造数据类型由基本数据类型或构造数据类型组成，可由不同成分类型构成。基本数据类型可以看作是程序设计语言中已实现的数据结构。数据类型本身就是数据结构，不过它是从编程者的角度来使用的。数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。 抽象数据类型 (ADTs: Abstract Data Types)抽象：抽取反映问题本质的东西，忽略非本质的细节。一旦一个抽象问题得到解决，则很多同类问题便可迎刃而解。用户自定义数据类型即是对多种可能的结构和实现的一种抽象。ADT: 由用户自定义，用以表示应用问题的数据模型。ADT由基本数据类型（或构造数据类型）组成, 并包括一组相关的服务(或操作)。特点：将数据和操作封装在一起，用户程序只能通过ADT所定义的操作来访问其中的数据，从而实现信息隐藏。 抽象数据类型的表示抽象数据类型可用三元组表示: （D, R, P）