什么是数据结构抽象数据类型及面向对象概念数据结构的抽象

《什么是数据结构抽象数据类型及面向对象概念数据结构的抽象》由会员分享，可在线阅读，更多相关《什么是数据结构抽象数据类型及面向对象概念数据结构的抽象（63页珍藏版）》请在金锄头文库上搜索。

1、n n什么是数据结构什么是数据结构n n抽象数据类型及面向对象概念抽象数据类型及面向对象概念n n数据结构的抽象层次数据结构的抽象层次n n算法定义算法定义n n性能分析与度量性能分析与度量“ “学生学生” ”表格表格“ “课程课程” ”表格表格“ “选课单选课单” ”包含如下信息包含如下信息学号学号 课程编号课程编号 成绩成绩 时间时间学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系学生 (学号,姓名,性别,籍贯)课程 (课程号,课程名,学分)选课 (学号,课程号,成绩)UNIXUNIX文件系统的系统结构图文件系统的系统结构图/ (root)binlibuseretcmath

2、dsswyintaoxieStack.cppQueue.cppTree.cpp数据数据（datadata）n n数据是信息的载体，是描述客观事物数据是信息的载体，是描述客观事物 的数、字符、以及所有能输入到计算的数、字符、以及所有能输入到计算 机中，被计算机程序识别和处理的符机中，被计算机程序识别和处理的符 号的集合。号的集合。uu 数值性数据；数值性数据；uu 非数值性数据非数值性数据。数据元素数据元素 (data element)(data element)n n数据的数据的基本单位基本单位。在计算机程序中常。在计算机程序中常 作为一个整体进行考虑和处理。作为一个整体进行考虑和处理。n n

3、有时一个数据元素可以由若干有时一个数据元素可以由若干数据项数据项 (Data Item)(Data Item)组成。组成。数据项数据项是是具有独立具有独立 含义的最小标识单位含义的最小标识单位。n n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。数据对象数据对象 (data object)(data object)n n数据的子集。具有相同性质的数据成数据的子集。具有相同性质的数据成 员（数据元素）的集合。员（数据元素）的集合。uu整数数据对象整数数据对象 ：N N = 0, = 0, 1, 1, 2, 2, uu学生数据对象。学生数据对象。什么是数据结构什么是数据结构定义定

4、义: : 由某一数据对象及该对象中所有数由某一数据对象及该对象中所有数 据成员之间的关系组成。记为：据成员之间的关系组成。记为：Data_Structure = D, RData_Structure = D, R其中，其中，D D 是某一数据对象，是某一数据对象，R R 是该是该 对象中所有数据成员之间的关系的有限对象中所有数据成员之间的关系的有限 集合。集合。N N 个网点之间的连通关系个网点之间的连通关系树形关系树形关系网状关系网状关系152436152436数据结构数据结构是数据的是数据的组织形式组织形式n n数据元素间的数据元素间的逻辑关系逻辑关系，即数据的，即数据的 逻辑结构；逻辑结

5、构；n n数据元素及其关系在计算机存储内数据元素及其关系在计算机存储内 的表示，即数据的的表示，即数据的存储表示存储表示；n n数据的运算，即对数据元素施加的数据的运算，即对数据元素施加的 操作操作。数据的逻辑结构数据的逻辑结构n n数据的逻辑结构数据的逻辑结构从逻辑关系上描述从逻辑关系上描述 数据数据，与数据的存储无关与数据的存储无关；n n数据的逻辑结构可以看作是数据的逻辑结构可以看作是从具体从具体 问题抽象出来的数据模型问题抽象出来的数据模型；n n数据的逻辑结构数据的逻辑结构与数据元素本身的与数据元素本身的 形式、内容无关形式、内容无关；n n数据的逻辑结构与数据元素的相对数据的逻辑结

6、构与数据元素的相对 位置无关。位置无关。数据的逻辑结构分类数据的逻辑结构分类n n线性结构线性结构uu 线性表线性表n n非线性结构非线性结构uu 树树uu 图（或网络）图（或网络）线性结构线性结构树形结构树形结构 树树 二叉树二叉树 二叉搜索树二叉搜索树1413121123456789103158710119987456623131bindevetclibuser1堆结构堆结构“最大最大”堆堆 “最小最小”堆堆123548711102916410121151236987图结构图结构 网络结构网络结构12564312543611 331814665161921数据的存储结构数据的存储结构n数据

7、的存储结构是逻辑结构用计算 机语言的实现；n数据的存储结构依赖于计算机语言 。u 顺序存储表示u 链接存储表示u 索引存储表示u 散列存储表示主要用于内存的 存储表示主要用于外存 (文 件) 的存储表示抽象数据类型及面向对象概念抽象数据类型及面向对象概念n n数据类型数据类型 定义：定义：一组性质相同的值的集合一组性质相同的值的集合, , 以以 及定义于这个值集合上的一组操作的及定义于这个值集合上的一组操作的 总称。总称。n nC C语言中的数据类型语言中的数据类型char char intint float double void float double void字符型字符型 整型整型 浮

8、点型浮点型 双精度型双精度型 无值无值 n n构造数据类型由构造数据类型由基本数据类型基本数据类型或或构造构造 数据类型数据类型组成。组成。n n构造数据类型由构造数据类型由不同成分类型不同成分类型构成。构成。n n基本数据类型可以看作是计算机中已基本数据类型可以看作是计算机中已 实现的数据结构。实现的数据结构。n数据类型就是数据结构，不过它是从编 程者的角度来使用的。n数据类型是模板，必须定义属于某种数 据类型的变量，才能参加运算。 抽象数据类型抽象数据类型 ( (ADTsADTs: Abstract Data Types): Abstract Data Types) 由用户定义，用以表示应

9、用问题的由用户定义，用以表示应用问题的 数据模型数据模型。 由由基本的数据类型基本的数据类型组成组成, , 并包括并包括一组一组 相关的服务相关的服务（或称操作）。（或称操作）。 信息隐蔽信息隐蔽和和数据封装数据封装，使用与实现，使用与实现 相分离。相分离。抽 象 数 据 类 型查找 登录 删除 修改 符 号 表自然数的抽象数据类型定义自然数的抽象数据类型定义ADTADT NaturalNumberNaturalNumber is is objects:objects: 一个整数的有序子集合一个整数的有序子集合, ,它开始于它开始于0, 0,结束于机器能表示的最大整数结束于机器能表示的最大整数

10、( (MaxIntMaxInt) )。 Function:Function: 对于所有的对于所有的 x x, , y y NaturalNumberNaturalNumber; ;FalseFalse, , TrueTrue BooleanBoolean, , + +、- -、 /起泡排序起泡排序void dataList : bubbleSort ( ) /对表逐趟比较, ArraySize 是表当前长度int i = 1; int exchange = 1;/当 exchange 为 0 则停止排序while ( i void dataList: BubbleExchange(int i,

11、 int /假定元素未交换for ( int j = ArraySize-1; j = i; j-)if ( Elementj-1 Elementj ) Swap ( j -1, j ); /发生逆序, 交换exchange = 1; /做“发生交换”标志渐进时间复杂度渐进时间复杂度O(f (n)*g (n) = O(n2) BubblrSort n-1趟BubbleExchange ( ) n-i次比较n n有时有时, , 算法的时间复杂度不仅依赖于问题算法的时间复杂度不仅依赖于问题 规模规模n n，还与输入实例的初始排列有关。还与输入实例的初始排列有关。n n在数组在数组 AnAn 中查找

12、给定值中查找给定值 k k 的算法：的算法：int i = n-1; while ( i = 0 return i;n n算法的语句算法的语句 i- 的的频度不仅与频度不仅与 n 有关，有关， 还与还与 A 中各元素的取值，以及，以及 k 的取的取 值值有关。有关。n例：设有两个算法在同一机器上运行， 其执行时间分别为 100n2 和 2n，问：要 使前者快于后者，n 至少要取多大？解答：问题是找出满足 100n2 2n = 8192n = 14时，100n2 = 19600 2n = 16384n = 15时，100n2 = 22500 arraySizearraySize 或者对于某或者对

13、于某 一个一个 k k ( ( 0 0 k k n n ) )，使得使得k k!*2!*2k k maxIntmaxInt 时时，应按出错处理。，应按出错处理。可有如下三种不同的出错处理方式：可有如下三种不同的出错处理方式： 用用 cerrcerr MaxInt / n / 2 )return 0; /直接判断 i!*2i MaxInt 是危险的value *= n * 2;Tn = value; return 1; /n!*2n Tn void main ( ) int AarraySize, i;for ( i = 0; i arraySize; i+ )if ( !calc ( A, i

14、 ) ) cout “failed at “ i endl;break; 1.1 判断下列叙述的对错。 (1) 数据元素是数据的最小单位。 (2) 数据结构是数据对象与对象中数据元素之 间关系的集合。 (3) 数据的逻辑结构是指各数据元素之间的逻 辑关系，是用户按使用需要建立的。 (4) 算法和程序原则上没有区别，在讨论数据 结构时二者是通用的。1.2 判断下列叙述的对错。 (1) 所谓数据的逻辑结构是指数据元素之间的逻辑关系。 (2) 同一数据逻辑结构中的所有数据元素都具有相同的特 性是指数据元素所包含的数据项的个数都相等。 (3) 数据的逻辑结构与数据元素本身的内容和形式无关。 (4) 数据结构是指相互之间存在一种或多种关系的数据元 素的全体。 (5) 从逻辑关系上讲，数据结构主要分为两大类：线性结 构和非线性结构。