计算机软件技术基础及实验指导 教学课件 作者 席晓慧 袁玲 第4章 数据结构.ppt

《计算机软件技术基础及实验指导 教学课件 作者 席晓慧 袁玲 第4章 数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章数据结构§4.1数据结构概述§4.1.1数据结构的定义1、数据(data)：数据是一些可以输入到计算机中的描述客观事物的符号,即信息的载体。这些符号可以是数值、字符、图象等。在计算机领域，人们把能够被计算机加工的对象，或者说能够被计算机输入、存储、处理、输出的一切信息都叫做数据。2、数据元素(element)：数据元素是算法可以处理的最小数据单位，是一个数据整体中相对独立的元素。数据元素可以是简单数据，也可以由若干个简单数据（数据项）组成数据元素。数据和数据元素是相对而言的，是整体和个体之间的关系。例如，对一个字符串来说，每个字符都是它的数据元素；对一个数组来

2、说，每个数组元素都是它的数据元素。本书中，经常将数据元素、数据结点、结点、记录这些概念不加区别的使用，它们表示的是同一概念。3、数据项：数据元素由更小的单位——数据项(item)（或成员）所组成，一个记录一般包括一个或若干个数据项。4、数据之间的联系：现实世界中的客观对象在计算机中是用数据来描述的，在现实世界当中，客观对象是有联系的，因此数据之间也是有联系的，数据联系是数据本身所具有的特性。5、数据结构（datastructure）：简单的说，数据结构就是研究数据和数据之间联系的一门学科，它包括三个方面。①数据的逻辑结构②数据的物理结构③数据的运算数据结构通常用二元

3、组表示，其形式如下：Data_struct=(D,R)其中D为数据元素的集合，R为数据元素之间关系的集合。即：D={ai

4、1≤i≤n,n≥0}R={rj

5、1≤j≤m,m≥1}ai为第i个数据元素，n为数据元素的个数，特别地，当n=0，D为空集，则无结构可言。rj表示第j个关系，m为关系的个数。§4.1.2数据结构的基本内容数据结构的基本内容包括数据的逻辑结构、数据的存储结构和数据的运算。1、数据的逻辑结构数据元素之间的逻辑关系就是数据的逻辑结构。一般情况下，一组数据元素并不是杂乱无章的，而是具有某种联系形式。这里的联系形式指数据元素与元素间的相互关系。数据之间的联系

6、可以是固有的，也可以是根据数据处理的需要人为定义的。数据元素之间的联系方式可分为一对一、一对多和多对多三种，根据数据元素之间联系的不同特性，数据的逻辑结构通常有以下三种基本结构。线性结构数据结构中数据元素之间的联系方式是一对一的。树形结构数据结构中数据元素之间的联系方式是一对多的。图形结构或网状结构数据结构中数据元素之间的联系方式是多对多一的。通常我们也把数据的逻辑结构分为线性结构和非线性结构，树形结构和图形结构统称为非线性结构。研究数据结构的目的是为了在计算机上实现对它的操作，因此还需研究如何在计算机中表示数据结构。2、数据的物理结构数据结构（包括数据及其数据之间

7、的关系）在计算机存储器上的存储表示称为数据的物理结构或存储结构。数据结构研究的是数据及其数据之间联系的学科，因此在研究数据的存储结构时，要求数据的存储方式既能表示数据又能表示数据之间的联系。常用数据的存储结构有：顺序存储链式存储索引存储哈希存储顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的关系；链式存储结构是借助指示元素存储位置的指针表示数据元素之间的关系；索引存储结构是为存储的数据建立一个索引表，访问数据时先在索引表中查找，再根据索引表的相关信息访问数据；哈希存储是建立数据的关键字和存储地址之间的对应关系（哈希函数），这样访问一个数据时，可根

8、据哈希函数直接获得该数据在计算机中的存储地址，到该地址访问数据。由于数据的存储结构有多种，所以一种数据的逻辑结构可以根据需要表示成一种或多种存储结构，只要存储结构既能表示数据，也能表示数据之间的联系或者存储结构能满足用户对数据的某种操纵要求即可。在后面的章节中，读者可根据具体的存储实例了解到一种数据的逻辑结构可以采用不同的存储方式进行存储。数据的逻辑结构和物理结构是数据结构两个密切相关的方面，以后读者可看到，一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采取的存储结构。算法的设计取决于数据的逻辑结构，算法的实现依赖于采用的存储结构，在不产生误解的情况下我们也

9、将数据的逻辑结构称为数据结构如何描述存储结构呢？虽然存储结构涉及数据元素及其关系在存储器中的存储方式，但由于本书是在高级语言的层次上讨论数据结构的操作，因此可以借助高级语言中提供的“数据类型”来描述它。例如可以用C语言中提供的“数组类型”来描述顺序存储结构，用“指针”来构造链式存储结构。检索（查找）：在给定的数据结构中，找出满足一定条件的结点来，这个条件往往是一个或几个数据项的值。排序：根据给定的条件，将数据结构中所有结点重新排列顺序插入：在给定的数据结构中，根据某些条件，将一个结点插入到一个合适的位置。删除：在给定的数据结构中，根据某些条件，将一个结点删除。修