内蒙古大学《算法与数据结构》讲义03数据描述
53页1、下载第3章数 据 描 述从本章开始我们进行数据结构的研究,一直到第1 2章为止。尽管本章的重点是介绍线性表,但一个主要目标是为了使大家明白, 数据可以用不同的形式进行描述或存储在计算机存储器中。最常见的数据描述方法有:公式化描述、链接描述、间接寻址和模拟指针。公式化描述借助数学公式来确定元素表中的每个元素分别存储在何处(如存储器地址) 。最简单的情形就是把所有元素依次连续存储在一片连续的存储空间中,这就是通常所说的连续线性表。在链接描述中,元素表中的每个元素可以存储在存储器的不同区域中,每个元素都包含一个指向下一个元素的指针。同样,在间接寻址方式中,元素表中的每个元素也可以存储在存储器的不同区域中,不同的是,此时必须保存一张表,该表的第 i项指向元素表中的第 i个元素,所以这张表是一个用来存储元素地址的表。在公式化描述中,元素地址是由数学公式来确定的;在链接描述中,元素地址分布在每一个表元素中;而在间接寻址方式下,元素地址则被收集在一张表中。模拟指针非常类似于链接描述,区别在于它用整数代替了 C + +指针,整数所扮演的角色与指针所扮演的角色完全相同。本章介绍了线性表的四种描述形式,通
2、过考察常见表操作(如插入、删除)的复杂性,给出了每种描述方法的优缺点。在本章中还将学习如何用数组来模拟 C + +指针。本章所给出的有关数据结构的概念如下: 抽象数据类型。 公式化描述、链接描述、间接寻址和模拟指针。 单向链表、循环链表和双向链表。本章的应用部分集中介绍了链表的应用,之所以这样做,是因为第 1章和第2章中所给出的所有程序都采用了公式化的数据表示形式,而现在希望采用链表形式来改写其中的部分程序。二叉排序、基数排序和等价类应用都使用了链表,而凸面体应用则采用了双向链表。二叉排序和基数排序可用来对n 个元素进行排序,如果关键值介于一个“合适的范围”内,排序所需要的时间为(n)。虽然在第2章中所给出的排序算法需要耗时O (n2),但它不需要将关键值限制在一个“合适的范围”内。当关键值介于一个“合适的范围”内时,二叉排序和基数排序要比第2章所给出的排序算法快出许多。在二叉排序的应用中还可以看到如何把函数名作为一个参数传递给C + +函数。3.1 引言数据对象(data object)即一组实例或值,例如: B o o l e a n =false, true 第二部分数 据 结
3、构 Digit = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 L e t t e r = A, B, C, , Z, a, b, , z NaturalNumber = 0, 1, 2, Integer = 0, 1, 2, 3, String = a, b, , aa, ab, ac, B o o l e a n,D i g i t,L e t t e r,N a t u r a l N u m b e r,I n t e g e r和S t r i n g都是数据对象,t r u e和f a l s e是B o o l e a n的实例,而 0, 1, , 和9 都是Digit 的实例。数据对象的每个实例要么是一个原语(p r i m i t i v e) (或原子(a t o m i c) ) ,要么是由其他数据对象的实例复合而成。在后一种情形下,用术语“元素(e l e m e n t) ”来表示对象实例的单个组件。例如,数据对象NaturalNumber 的每个实例均可以视为原子,在这种情况下,不必考虑对这些实例做进一步的分解。另一种观点是把NaturalNu
4、mber 的每个实例看成是由D i g i t数据对象的若干实例复合而成。按照这种观点,整数6 7 5是由数字6,7和5按顺序组成。数据对象S t r i n g是所有可能的串实例的集合,每个实例均由字符组成。串实例的一些具体例子如:good, a trip to Hawaii, going down hill和a b c a b c d a b c d e。其中第一个串由四个元素 g, o,o 和d 按序构成,而每个元素又都是数据对象L e t t e r的一个实例。数据对象的实例以及构成实例的元素通常都有某种相关性,例如,自然数 0是最小的自然数,1是仅比0大的自然数,而2是1之后的下一个自然数。在自然数 6 7 5中, 6是最高有效位, 7在其次,而5是最低有效位。在串good 中,g 是第一字母,o 是第二和第三个字母,而d 是最后一个字母。除了相互关联之外,对于任一个数据对象通常都有一组相关的函数。这些函数可以把对象的某个实例转换成该对象的另外一个实例,或转换成另一个数据对象的实例,或者同时进行上述两种转换。函数也可以简单地创建一个新的实例,而不必对一个新创建的实例进行转换。
5、例如,进行自然数相加的函数将创建一个新的自然数,该自然数是两个相加数之和,两个参与加操作的自然数本身不会发生任何变化。数据结构(data structure)包括数据对象和实例以及构成实例的每个元素之间所存在的各种关系。这些关系可由相关的函数来实现。当我们研究数据结构时,关心的是数据对象(实际上是实例)的描述以及与数据对象相关函数的具体实现。数据对象的良好描述可以有效地促进函数的高效实现。最常使用的数据对象以及函数都已经在 C + +中被当作标准的数据类型加以实现,如整数对象( i n t )、实数对象( f l o a t )、布尔对象( b o o l )等。所有其他的数据对象均可以采用标准数据类型、枚举类型以及由C + +的类、数组和指针特性所提供的组合功能来描述。例如,可以用一个字符数组s 来描述String 的实例:char sMaxSize;有关数据结构的研究包括两个部分。本章按照数据的各种描述方法进行组织,即基于公式的描述、链表描述、简接寻址和模拟指针。我们利用数据对象线性表来演示这些方法。在后续章节中将研究其他流行的数据描述方法,如矩阵、栈、队列、字典、优先队列和图。3
《内蒙古大学《算法与数据结构》讲义03数据描述》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义03数据描述》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页