文档介绍：第12章数据结构绪论
教学目标:通过本章的学习,使读者能够掌握数据结构的概念和有关的术语。
C语言程序设计与数据结构
什么是数据结构
计算机科学技术的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。为了有效地处理数据,需要为数据建立一定的结构,描述所处理的对象的特性以及各对象之间的关系。
数据结构这门学科主要是研究各种结构、定义在各种结构上的操作和这些操作在计算机中的实现方法。
C语言程序设计与数据结构
用计算机解决一个具体问题时要考虑以下步骤
从具体问题中抽象出一个适当的数学模型。即从具体问题中找出操作对象之间含有的关系,然后用数学语言加以描述。
设计一个适合该数学模型的算法(Algorithm)。
编写程序。
(4) 进行测试、调整、修改,直至解决问题。
所以,数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。
C语言程序设计与数据结构
实际问题中,各个对象之间的关系有:
线性的:列车中各车箱之间的关系,排队买车票的人之间的关系,一叠盘子中各盘子之间的关系都是线性的。
层次的:在军队的编制中,军下面是师,师下面是团,军、师、团之间是层次关系;在人的辈分关系中,祖辈下是父辈,父辈下是子辈,这些是层次关系;在学校的编制中,学校分成若干个学院、学院下又分成若干个系、系下又分成若干个教研室,这些也都是层次关系。
网状的:在城市铁路交通图中,各城市之间的关系是网状关系。在电话网中,各电话之间是网状关系。
对象之间的关系
C语言程序设计与数据结构
基本概念和术语
数据
数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中,数据的含义非常广泛,我们把一切能够输入到计算机中并被计算机程序处理的信息,包括文字、表格、图象等,都称为数据。
C语言程序设计与数据结构
数据举例
一个个人书库管理程序所要处理的数据可能是一张如表所示的表格。
C语言程序设计与数据结构
结点
结点也叫数据元素,它是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和处理。例如,在上表所示的个人书库中,为了便于处理,把其中的每一行(代表一本书)作为一个基本单位来考虑,故该数据由10个结点构成。
一般情况下,一个结点中含有若干个字段(也叫数据项)。例如,在上表所示的表格数据中,每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。
字段是构成数据的最小单位。
C语言程序设计与数据结构
逻辑结构
结点和结点之间的逻辑关系称为数据的逻辑结构。
在上表所示的表格数据中,各结点之间在逻辑上有一种线性关系,它指出了10个结点在表中的排列顺序。根据这种线性关系,可以看出表中第一本书是什么书,第二本书是什么书,等等。
C语言程序设计与数据结构
存储结构
数据在计算机中的存储表示称为数据的存储结构。
在上表所示的表格数据在计算机中可以有多种存储表示,例如,可以表示成数组,存放在内存中;也可以表示成文件,存放在磁盘上,等等。
C语言程序设计与数据结构
数据处理
数据处理:是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。
例:
从数据结构S中找出满足条件的结点在 S 中位置的运算是___型运算。
从数据结构S中读出结构中指定位置上内容运算是___型运算。
从数据结构S中修改结构中某指定结点内容的运算是____型运算。
C语言程序设计与数据结构