资源描述：
《数据结构算法与应用-c++语言描述003》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、下载第二部分数据结构第3章数据描述从本章开始我们进行数据结构的研究，一直到第12章为止。尽管本章的重点是介绍线性表，但一个主要目标是为了使大家明白，数据可以用不同的形式进行描述或存储在计算机存储器中。最常见的数据描述方法有：公式化描述、链接描述、间接寻址和模拟指针。公式化描述借助数学公式来确定元素表中的每个元素分别存储在何处（如存储器地址）。最简单的情形就是把所有元素依次连续存储在一片连续的存储空间中，这就是通常所说的连续线性表。在链接描述中，元素表中的每个元素可以存储在存储器的不同区域中，每个元
2、素都包含一个指向下一个元素的指针。同样，在间接寻址方式中，元素表中的每个元素也可以存储在存储器的不同区域中，不同的是，此时必须保存一张表，该表的第i项指向元素表中的第i个元素，所以这张表是一个用来存储元素地址的表。在公式化描述中，元素地址是由数学公式来确定的；在链接描述中，元素地址分布在每一个表元素中；而在间接寻址方式下，元素地址则被收集在一张表中。模拟指针非常类似于链接描述，区别在于它用整数代替了C++指针，整数所扮演的角色与指针所扮演的角色完全相同。本章介绍了线性表的四种描述形式，通过考察常见
3、表操作（如插入、删除）的复杂性，给出了每种描述方法的优缺点。在本章中还将学习如何用数组来模拟C++指针。本章所给出的有关数据结构的概念如下：¥抽象数据类型。¥公式化描述、链接描述、间接寻址和模拟指针。¥单向链表、循环链表和双向链表。本章的应用部分集中介绍了链表的应用，之所以这样做，是因为第1章和第2章中所给出的所有程序都采用了公式化的数据表示形式，而现在希望采用链表形式来改写其中的部分程序。二叉排序、基数排序和等价类应用都使用了链表，而凸面体应用则采用了双向链表。二叉排序和基数排序可用来对n个元素
4、进行排序，如果关键值介于一个“合适的范围”内，排序所需要2的时间为(n)。虽然在第2章中所给出的排序算法需要耗时O(n)，但它不需要将关键值限制在一个“合适的范围”内。当关键值介于一个“合适的范围”内时，二叉排序和基数排序要比第2章所给出的排序算法快出许多。在二叉排序的应用中还可以看到如何把函数名作为一个参数传递给C++函数。3.1引言数据对象（dataobject）即一组实例或值，例如：¥Boolean={false,true}76第二部分数据结构下载¥Digit={0,1,2,3,4,5,6,
5、7,8,9}¥Letter={A,B,C,⋯,Z,a,b,⋯,z}¥NaturalNumber={0,1,2,⋯}¥Integer={0,±1,±2,±3,⋯}¥String={a,b,⋯,aa,ab,ac,⋯}Boolean，Digit，Letter，NaturalNumber，Integer和String都是数据对象，true和false是Boolean的实例，而0,1,⋯,和9都是Digit的实例。数据对象的每个实例要么是一个原语（primitive）（或原子（atomic）），要么是由其他
6、数据对象的实例复合而成。在后一种情形下，用术语“元素（element）”来表示对象实例的单个组件。例如，数据对象NaturalNumber的每个实例均可以视为原子，在这种情况下，不必考虑对这些实例做进一步的分解。另一种观点是把NaturalNumber的每个实例看成是由Digit数据对象的若干实例复合而成。按照这种观点，整数675是由数字6，7和5按顺序组成。数据对象String是所有可能的串实例的集合，每个实例均由字符组成。串实例的一些具体例子如：good,atriptoHawaii,going
7、downhill和abcabcdabcde。其中第一个串由四个元素g,o,o和d按序构成，而每个元素又都是数据对象Letter的一个实例。数据对象的实例以及构成实例的元素通常都有某种相关性，例如，自然数0是最小的自然数，1是仅比0大的自然数，而2是1之后的下一个自然数。在自然数675中,6是最高有效位，7在其次，而5是最低有效位。在串good中，g是第一字母，o是第二和第三个字母，而d是最后一个字母。除了相互关联之外，对于任一个数据对象通常都有一组相关的函数。这些函数可以把对象的某个实例转换成该对
8、象的另外一个实例，或转换成另一个数据对象的实例，或者同时进行上述两种转换。函数也可以简单地创建一个新的实例，而不必对一个新创建的实例进行转换。例如，进行自然数相加的函数将创建一个新的自然数，该自然数是两个相加数之和，两个参与加操作的自然数本身不会发生任何变化。数据结构（datastructure）包括数据对象和实例以及构成实例的每个元素之间所存在的各种关系。这些关系可由相关的函数来实现。当我们研究数据结构时，关心的是数据对象（实际上是实例）的描述以及与数据对象相关函数的具体实现。数
