信息技术教程：数据结构的选择对运行与存储效率的影响

2023-10-22 理论教育版权反馈

【摘要】：通常情况下，精心选择的数据结构可以带来更高的运行效率或者存储效率。图3.40家庭关系的树型描述假如一位旅客要从济南出发去福州，他希望选择一条途中中转次数最少的路线。图3.41城市和城市相互之间的图型描述数据的存储结构实质上是它的逻辑结构在计算机存储器上的实现，是数据结构在计算机中的表示（映像）。

如今，计算机已深入到人类社会的各个领域，计算机的应用不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。比如在图书馆的图书管理系统、人机对弈、多岔路口交通信号灯管理中，计算机加工处理的对象不是纯粹数值而是诸如字符、表、图像等各种具有一定结构的数据。由此，在程序设计过程中，必须分析这些数据元素之间存在的一种或多种特定关系以及作用于其上的函数或运算。通常情况下，精心选择的数据结构可以带来更高的运行效率或者存储效率。

数据结构的研究不仅涉及计算机硬件（存储设备和存取方法等）、计算机软件（数据元素在存储器中的分配），还要考虑到信息检索过程中如何组织数据，以方便查找和存储数据元素。数据结构是一门介于数学、计算机硬件、计算机软件三者之间的核心课程。

通常，研究数据结构一般包括三个方面的内容，即数据的逻辑结构、数据的存储结构和定义在这些数据上的运算。

数据的逻辑结构中描述的是数据元素之间的逻辑关系。通常有下列4类基本结构：集合、线性结构、树型结构、网状（图）结构。

线性结构中，在数据元素非空的有限集合的前提下，要求：存在唯一的一个被称作“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个元素之外，集合中的每一个数据元素均只有一个前驱；除最后一个元素之外，集合中的每一个数据元素均只有一个后继。线性结构中的数据元素可以是一个数字或一条记录，甚至其他更复杂的信息。由于数据元素之间有明确的顺序关系，这个集合将构成一个有方向的线性链表，如图3.39所示。

图3.39　有方向的线性链表

如果要描述人类社会的族谱或各种社会组织关系，这种关系将不是线性的，可以用“树”来形象描述。例如，祖父有两个儿子，每个儿子又有两个儿子，可以得到这个家庭关系的树型描述如图3.40所示。当然其中的数据元素可以是一个数字或一条记录，甚至其他更复杂的信息。(www.chuimin.cn)

pagenumber_ebook=98,pagenumber_book=89

图3.40　家庭关系的树型描述

假如一位旅客要从济南出发去福州，他希望选择一条途中中转次数最少的路线。假设他每到一个城市都要换车。由于城市和城市相互之间存在道路，则可以使用“图”这种结构解决这个问题。如图3.41所示，我们需要从顶点“济南”出发，搜索每一条可以到达“福州”的路径，这个问题就是搜索一条由济南到福州所含边最少的路径。

pagenumber_ebook=99,pagenumber_book=90

图3.41　城市和城市相互之间的图型描述

数据的存储结构实质上是它的逻辑结构在计算机存储器上的实现，是数据结构在计算机中的表示（映像）。数据元素在计算机中有两种不同的表示方法，即顺序存储和非顺序存储，因此得到两种不同的存储结构——顺序存储结构和链式存储结构。顺序存储结构是数据元素在存储器中按照先后顺序进行存放的存储结构，非顺序存储结构是借助于数据元素存储地址（指针）表示数据元素间的逻辑关系的存储结构。

不同数据结构有其相应的运算，常见的运算有数据检索、插入、删除、更改、排序等。

信息技术教程：数据结构的选择对运行与存储效率的影响

相关推荐