计算机文化基础 教学课件 作者 978-7-302-23234-6 电子教案第十二章 数据结构.ppt

《计算机文化基础 教学课件 作者 978-7-302-23234-6 电子教案第十二章 数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十二章数据结构主要内容：12.1数据结构的主要研究内容12.2数据结构基本概念12.3数据的逻辑结构12.4线性表及其顺序存储结构12.5栈和队列12.6树与二叉树12.7查找技术12.8排序技术12.1数据结构的主要研究内容■12.1数据结构的主要研究内容数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：1．数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构包含

2、：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。2．各数据元素在计算机中存储关系，即数据的存储结构。数据的存储结构有顺序、链接、索引等。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般只在高级语言的层次上讨论存储结构。对各种数据结构进行的运算。3.数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指只知道这些操作是“做什么”，而无须考虑“如何做”。只有确定了存储结构之后，才考虑

3、如何具体实现这些运算。12.2数据结构基本概念■12.2.1数据数据是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据是信息的载体，它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。随着计算机应用领域的扩大，数据可以分为两大类：一类是整数、实数等数值数据；另一类是图形、图像、声音、文字等非数值数据。这里要注意数据并不等于数字，数字是隶属于数据的。■12.2.2数据元素与数据项数据元素也称为元素、结点、顶点或记录，是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成，数据项是数据的最小单位。数据元素具有广泛的含义，一般来

4、说，现实世界中客观存在的一切个体都可以是数据元素。例如在表12-1中，整个表记录的是学生成绩数据，每个学生的记录行是其中一个数据元素，即该表由4个数据元素构成，而某一个数据元素（记录行）又是由5个数据项组成。例如语文成绩67则是表中第一个数据元素（记录行）中的数据项。数据项是不可再分的数据内容。数据对象是性质相同的数据元素的集合。如上例中一个班级的成绩表可以看作一个数据对象。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。学号姓名语文数学英语04060101李丽67878304060102张鹏92826404060

5、103刘海78727604060104金玉566871■12.2.3数据结构数据元素都不是孤立存在的，而是在它们之间存在着某种特定的关系，这种数据元素相互之间的关系称为结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系(或直接前驱与直接后继关系)来描述。例如，在考虑一年四个季节的顺序关系时，则“春”是“夏”的前件（即直接前驱），而“夏”是“春”的后件（即直接后继）。同样，“夏”是“秋”的前件，“秋”是“夏”的后件；“秋”是“冬”的前件，“冬”是“秋”的后件。前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据

6、元素之间的任何关系都可以用前后件关系来描述。■12.2.4数据的逻辑结构通俗地说，数据结构是指带有结构的数据元素的集合。在此，所谓结构实际上就是指数据元素之间的前后件关系。数据元素之间的前后件关系即指它们的逻辑关系，而与它们在计算机中的存储位置无关。所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。图12-1数据的逻辑结构表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻的直接前趋（ImmediatePredecessor）最多只有一个；与表中任一结点相邻的直接后继（ImmediateSu

7、ccessor）也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继，故称之为终端结点。上述结点间的关系构成了这张学生成绩表的逻辑结构。逻辑结构主要可分为线性结构（线性表、栈和队列）和非线性结构（树、图和集合）。如图12-1所示。■12.2.5数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。在数据的存储结构中，不仅要存放各数据元素的信息，还存放元素之间的前后件关系的信息。