绵1亘 畅迹 随着现代电子计算机技术的发展,计算机的应用领域从最初的简单科学计算逐步发展到 人类活动的各个领域,例如企业管理、工程过程控制、经济系统工程及管理信息系统等。计 算机处理的对象从简单的数值和字符扩大到现在带有不同复杂结构的各种数据,例如图像、 声音及信号等。面对不同的数据处理对象,不同的需求,数据的组织形式、存储及运算必须 有不同的方法,才能进行有效的处理。因此努力研究数据的内在结构,分析待处理对象的特 征以及各处理对象之间的关系,才能寻找到某些规律性的方法,编写出好的程序。这就是“数 据结构”这门课形成和发展的背景。 11什么是数据结构 数据结构和算法是程序设计最重要的两个内容。 那么什么是数据结构呢?简单地说,数据结构是数据的组织、存储和运算的总和。它是 信息的一种组织方式,是以数据按某种组织关系联系起来的一批数据,其目的是提高算法的 效率,然后用一定的方式存储到计算机中,并且它通常与一组算法的集合相对应,通过这组 算法集合可以对数据结构中的数据进行某种操作。 在计算机处理的大量数据中,它们都是相互关联的。 例如:学生信息检索系统。 问题:查找某个学生的有关情况,或者想查询某个专业或年级的学生的有关情况。 解决:建立相关的数据结构,按照某种算法编写相关程序,就可以用计算机实现自动检 索。由此,可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、 专业及年级顺序排列的索引表,如图1.1所示。由这4张表构成的文件便是学生信息检索的 数学模型,计算机的主要操作便是按照某个特定要求(如给定姓名)对学生信息文件进行 查询。 总结:诸如此类的还有电话自动査号系统、考试査分系统及仓库库存管理系统等。在这 类文档管理的数学模型中,计算机处理的对象之间通常存在着一种简单的线性关系,这类数 学模型可称为线性的数据结构。 例如:计算机和人对奕问题。 问题:计算机是如何与人对奕的。 解决:将对奕的策略事先存入计算机。由于对奕的过程是在一定规则下随机进行的,所 以,为使计算机能灵活对奕就必须对对奕过程中所有可能发生的情况以及相应的对策都考虑
数据结构 学号姓名性别专业 年 02001承志男「计算机科学与技术m级 02000廖诗佳女信息与计算科学02级 崔文靖|8 090周晶女「数学与应用数学0级 何文颖|6 0张会友赐僧息与计算科学0银,使2 0909石宝男计算机科学与技术0级周晶3 040801何文女计算机料学与技术叫4级 石宝国5 04Q鑫男数学与应用数学叫级 施子健|10 040803崔文靖男信息与计算科学04级 吴承志1 050601周 女|计算机科学与技术05级 周鑫7 050602施子健男数学与应用数学05级 张会友4 (a)学生信息表 (b)姓名索引表 04级6,7,8 计算机科学与技术1,5,6,9 05级910 信息与计算科学2,4,8 02级1,2.3 数学与应用数学3 03级 (c)专业索引表 (d)年级索引表 图11学生信息查询系统中的数据结构 周全,并且,一个“好”的棋手在对奕时不仅要看棋盘当时的状态,还应能预测棋局发展的 趋势,甚至最后结局。因此,在对奕过程中,计算机操作的对象是对奕过程中可能出现的棋 盘状态—格局。如图1.2最上方所示为井字棋的1个格局,而格局之间的关系是由比赛规 则决定的。通常,这个关系不是线性的。因为从一个棋盘格局可以派生出几个格局,例如从 图12最上方所示的一个格局可以派生出5个格局,如图12中间所示,而从每一个新的格局 又可派生出4个可能出现的格局,如图12最下方所示。因此,若将从对奕开始到结束的过 程中所有可能出现的格局都画在一张图上,则可得到一棵倒长的“树”。“树根”是对奕开始 之前的棋盘格局,所有的“叶子”就是可能出现的结局,对奕的过程就是从树根沿树叉到叶 子的过程。 副姗崗 o。□o o■o o0 od od oao 图1.2井字棋对奕“树 总结:“树”可以是某些非数值计算问题的数学模型,它也是一种数据结构
第1章概述 例如:教学计划编排问题。 问题:一个教学计划包含许多课程,在这些课程之间,有些必须按规定的先后次序进行, 有些则没有次序要求。即需要解决有些课程之间有先修和后续的关系,有些课程可以任意安 排次序。 解决:这种各个课程之间的次序关系可用一个称作图的数据结构来表示,如图13所示。 有向图中的每个顶点表示一门课程,如果从顶点v到v之间存在有向边《v,y,则表示课 程讠必须先于课程j进行。 课程代号 课程名称 先修课程 高等数学 程数学 C3 桦通物理 Ct 程序设计基础 C语言程序设计c1C4 离散数学 C, Ce 数据结构ccc C 编译方法 C CT 计算机组成原理 操作系统 Co C7 (a)计算机专业的课程设置 (b)表示课程之间优先关系的有向图 图13教学计划编排问题的数据结构 总結:这类课程编排问题及日常生活中常见的交通、道路问题的数学模型是一种所谓图” 的数駕结均。 综上三个例子可见描述这类非数值计算问题的数学模型不再是数学方程,而是诸如表、 树和图之类的数据结构。因此,简单说来,数据结构是一门研究非数值计算的程序设计问题 中计算机的操作对家以及它们之间的关系和操作等的学科。 12基本概念和术语 数据结构的基本术语是学习数据结构的基础,因此有必要先弄清楚相关的一些术语。 1.数据 数据(Daa)即信息的载体,是对客观事物的符号表示,指能输入到计算机中并能被计
数据结构 算机程序处理的符号的总称。如整数、实数、字符、文字、声音、图形及图像等都是数据。 2.数据元素 数据元素( Data Element)是数据的基本单位,它在计算机处理和程序设计中通常被作为 一个整体进行考虑和处理。例如,上节中的“树”中的一个棋盘格局。一个数据元素一般由 个或多个数据项组成。例如,一个学生的信息为一个数据元素,而一个学生的信息中的每 一项(如姓名、专业及年级等)为一个数据项。数据项是数据的不可分割的最小单位。 3.数据对象 数据对象( Data Object是具有相同特征的数据元素的集合,是数据的一个子集。例如, 整数数据对象是集合№={(0,±1,±2…},字母字符数据对象是集合C={A',B,…z"}。 4.数据结构 数据结构( Data Structure)是数据元素的组织形式,或数据元素相互之间存在的一种或 多种特定关系的集合。从上节的例子可以看出,在任何问题中,数据元素都不是孤立存在的, 在它们之间存在着某种关系,这种数据元素相互之间的关系称为结构。根据数据元素之间关 系的不同特征,通常有下列四类基本结构,它们的复杂程度依次递进。例如,以某班级学生 作为数据对象,数据元素是学生的学籍档案,考察数据元素之间的关系。 (1)集合 结构中的数据元素之间除了“同属于一个集合”的关系外,别无其他关系。例如,认定 个学生是否为班级的成员。 (2)线性结构 结构中的数据元素之间存在一个对一个的关系。例如,以学生入学报到的时间先后顺序 排列数据元素。 (3)树型结构 结构中的数据元素之间存在一个对多个的关系。例如,班级中的管理体系,班长管理多 个班委,每个班委管理多个成员 (4)图状结构或网状结构 结构中的数据元素之间存在多个对多个的关系。例如,同学之间的朋友关系。 图14为上述四类基本结构的关系图。由于“集合”是数据元素之间关系极为松散的 种结构,所以也可用其他结构来表示它。因此“数据结构”中通常只讨论后三种逻辑结构, 其中树型结构和图结构都属于非线性结构。 (a)集合结构 (b)线性结构 (c)树型结构 (d)图形结构 图14四类基本结构关系图 数据结构的形式定义为:数据结构是一个二元组 Data Structure=(D,S),其中D是数据 元素的有限集,S是D上关系的有限集。下面举例说明。 例如:在计算机科学中,复数可取如下定义:复数是一种数据结构 Complex=(C,R),其
第1章概述 中C是含两个实数的集合{cl,c2},R={P},而P是定义在集合C上的一种关系{<cl,c2>}, 其中有序偶<c1,c2>表示c1是复数的实部,c2是复数的虚部 5.数据的逻辑结构 数据的逻辑结构( Logical Structure)是指数据结构中数据元素之间的逻辑关系。它是从 具体问题中抽象出来的数学模型,是独立于计算机存储器的(与具体的计算机无关)。数据的 逻辑结构可分为四种基本类型:集合结构、线性结构、树型结构和图形结构。表和树是最常 用的两种高效数据结构,许多高效的算法可以用这两种数据结构来设计实现。表是线性结构 (全序关系),树(偏序或层次关系)和图(局部有序)是非线性结构。 6.数据的存储结构 数据的存储结构( Physical Structure)是数据的逻辑结构在计算机内存中的存储方式,又 称物理结构。数据存储结构的实现要用计算机编程语言来实现,因而依赖于具体的计算机语 言。数据存储结构有顺序和链式两种不同的方式。顺序存储结构的特点是要借助数据元素在 存储器中的相应位置来体现数据元素相互间的逻辑关系,而链式存储结构则通过表示数据元 素存储地址的指针来表示数据元素之间的逻辑关系。顺序存储结构通常用高级编程语言中的 一维数组”来描述或实现,而链式存储结构则通常用链表来实现。在实际应用中,解决不同 的问题时,设计不同的算法要依据数据的逻辑结构,但算法如何实现又要取决于存储结构。 在顺序存储结构的基础上,又可延伸变化出另外两种存储结构,即索引存储和散列存储 索引存储就是在数据文件的基础上增加了一个索引表文件,通过索引表建立索引,可以 把一个顺序表分成几个顺序子表,其目的是在查询时提高查找效率,避免盲目查找。 散列存储就是通过数据元素与存储地址之间建立起某种映射关系,使每个数据元素与每 个存储地址之间尽量达到一一对应的目的。这样,查找时同样可提高效率。 上述基本的存储结构既可以单独使用,也可以组合使用,如何选择应视具体要求而定, 主要考虑的是操作运算的方便以及算法的时空要求。 7.数据类型 数据类型( Data Type)是一组具有相同性质的操作对象以及该组操作对象上的运算方法 的集合,如整数类型、字符类型等。每一种数据类型都有其具有自身特点的一组操作方法(即 运算规则) 8.抽象数据类型 抽象数据类型( Abstract Data Type)是指一个数学模型以及在该模型上定义的一套运算 规则的集合。在对抽象数据类型进行描述时,要考虑到完整性和广泛性。完整性就是要能体 现所描述的抽象数据类型的全部特征,广泛性就是所定义的抽象数据类型适用的对象要广。 在大型程序设计和系统软件开发中,对抽象数据类型运用得较多。 1.3数据结构的重要性 1.数据结构理论的发展历史 数据结构”作为一门独立的课程在国外是从1968年才开始设立的。1968年在美国一些 大学的计算机系的教学计划中,把“数据结构”规定为一门课程,但对课程的范围没有作明