数据结构第1章绪论.pptVIP

*数据的存储结构（续）例1-5电话号码查询问题。 为便于提高查询的速度，在存储用户数据文件的同时，建立一张姓氏索引表，如图1.7所示。这样，查找一个电话就可以先查找索引表，再查找相应的数据文件，无疑加快了查询的速度。姓名电话丁一…………王二…………张三…………数据文件姓氏地址丁王张…………索引表*数据的存储结构（续） （4）散列存储(HashStructure)：根据数据元素的特殊字段(称为关键字key)，计算数据元素的存放地址，然后数据元素按地址存放，所得到的存储结构为散列存储结构(或Hash结构)。3.数据的操作 一般而言，必须对数据进行加工处理，才能得到问题的解。在非数值性问题中，对数据的操作（或运算）已不限于对数据进行加、减、乘、除等数学运算。数据的操作是定义在逻辑结构上的，而操作的具体实现是在存储结构上进行的。基本的数据操作主要有以下几种： （1）查找：在数据结构中寻找满足某个特定条件的数据元素的位置或值。*数据的操作（2）插入：在数据结构中添加新的数据元素。（3）删除：删去数据结构中指定的数据元素。（4）更新：改变数据结构中某个数据元素一个或多个数据项的值。（5）排序：重新安排数据元素之间的逻辑顺序，使之按（某个数据项的）值由小（大）到大（小）的次序排列。 其中，查找是一种引用型操作，即它不改变现有结构，而其余四种均会改变现有结构，被称为加工型操作。 综上所述，数据结构是一门研究非数值计算的程序设计中计算机操作的对象以及它们之间关系和操作的学科。在本书中，对数据结构的详细讨论，都是从数据的逻辑结构、数据的存储结构和对数据的操作这三方面展开的，读者应掌握住这个规律，以便以后知识的学习。*1.1.3研究数据结构的方法 研究数据结构是为了编写解决问题（或完成任务）的程序。用计算机求解一个实际问题的过程，一般可以用图1.8所示的模型加以描述。图1.8计算机求解问题的流程 即首先要从现实问题出发，抽象出一个适当的数学模型，然后设计一个求解此数学模型的算法，最后根据这个算法编出程序，经过测试、排错、运行直至得到最终的解答。（现实）问题、数学模型、算法和程序是问题求解过程中出现的四个不同的概念。现实问题数学模型算法程序解*研究数据结构的方法 1）问题（Problem） 要完成的任务。例如，在例1–1和例1–2中描述的都是一个问题。在问题的定义中不应包含有关怎样解决问题的限制。只有在问题被准确定义并完全理解后才有可能研究问题的解决方法。然而在问题的定义中应该包含对所有解决方案所需要的资源（比如说，计算机的主存储器和磁盘空间以及运行时间）的限制。 2）数学模型（MathematicalModel） 指用数学的方法精确地把问题描述成为函数。而函数（Function），是输入（即定义域）和输出（即值域）之间的一种映射关系。函数的输入是一个值或一些信息，这些值组成的输入称为函数的参数。不同的输入可以产生不同的输出，但对于给定的输入，每次计算函数时得到的输出必须相同。*研究数据结构的方法 3）算法（Algorithm） 指解决某个问题的一种方法（1.4节将给出详细定义）。如果将问题抽象为数学模型，那么它仅是精确地定义了输入和输出的映射关系，而算法则能把输入转化为输出。一个问题可以有多种算法。一个算法如果比其它算法需要的资源更少，则称这个算法效率更高。 4）程序（Program） 对一个算法用某种程序设计语言的具体实现。由于使用任何一种程序设计语言都可以实现一个算法，所以可能有许多程序都是同一个算法的实现。虽然算法是独立于程序的，但因为最终的目标是问题求解，所以在定义算法时，应该提供足够多的细节，以便转换为程序。我们以C语言作为算法的描述。*1.2抽象数据类型的表示与实现 抽象数据类型（AbstractDataType,简称ADT）是指一个数据结构以及定义在其上的一组操作。本书采用类C语言作为描述算法，这使得数据结构的描述和讨论简明清晰，不拘泥于C语言的细节，又容易转换为C或C++程序。以下面的形式描述ADT： ADT=（D，R，P） 其中，D是数据元素的有限集；R是D上关系的有限集，（D，R）构成了一个数据结构；P是对该数据结构的基本操作集。用以下格式