第 13 章 数据结构基础13.1 概述利用计算机进行数据处理是计算机应用的一个重要领域。数据是对客观事物的符号表 示，是由大量的数据元素组成的。这些元素之间具有一定的逻辑关系，需要存放在计算机 中。因此，数据在计算机中如何组织，以便高效率地处理，节省存储空间，是数据处理的 关键问题。了解和掌握数据结构的基本思想和方法，对充分发挥计算机的效能，为应用所涉及的 数据选择适当的逻辑结构、 存储结构以及相应的算法， 编制出高质量的程序是很有帮助的。13.1.1 数据结构的基本概念数据 是指所有能输入到计算机中并能被计算机程序处理的符号的集合。 如数值、 字符、 声音、图像等。数据元素 是组成数据的基本单位，在计算机中通常作为一个整体进行处理。一个数据 元素可由一个或多个数据项组成，数据项是有独立含义的数据的最小单位，也称为结点或 记录。例如学生学籍表是数据，每一名学生的记录就是一个数据元素。数据对象 是性质相同的数据元素的集合，是数据的一个子集。例如，集合 N=0 ，1，2, 表示的数据对象是全体整数。数据类型 是指一个值的集合和定义在该集合上的一组操作的总称。例如C 语言中的整数类型，其值集为某一区间的整数，定义在其上的一组操作为：加、减、乘、除和取模等 算术运算。数据结构 是指相互之间存在一种或多种特定关系的数据元素集合。在任何问题中，数 据元素都不是孤立存在的，在它们之间存在着某种关系，这种数据元素相互之间的关系就 是结构。定义一个数据结构由两部分组成，一是数据结构中数据元素的集合；另一个是数据结 构中所有关系的集合。通常可用一个二元组来表示：B=(D,R),D 是数据元素的有限集， R是D上关系的有限集。例如，英文 26 个字母表的数据结构用二元组可表示为 :B=D,RD= a , b, c, -x ,y ,zR=(a,b),(b,c),； (y,z)此例中的数据元素是简单项。数据结构是一门研究数据的组织、存储和运算的一般方法的学科，应包括三个方面的 内容，即研究数据的逻辑结构和存储结构以及它们之间的相互关系，并对这种结构定义相 应的运算。数据的逻辑结构是指只抽象地反映数据元素之间的逻辑上联系的结构，与数据 的存储无关。存储结构又称为物理结构，是指数据在计算机中的存储方式。如图13-1 所示。线性表Y栈线性结构fI队列数据的逻辑结构树形结构非线性结构 = L图形结构顺序存储I链式存储数据结构研究的三个方面L.数据的存储结构构.数据的操作：检索、排序、插入、删除、修改等。图13-1数据结构研究的三个方面问题1 数据的逻辑结构 数据的逻辑结构，反映数据元素的逻辑关系。主要有四种基本数据结构：(1) 集合：数据元素之间同属于一个集合，别无其他关系；(2) 线性结构：结构中的数据元素之间存在一对一的线性关系；(3) 树形结构：结构中的元素之间存在着一对多的层次关系；(4) 图形结构或网状结构：结构中的元素之间存在着多对多的任意关系。图13-2(a)、(d)给出了这四种基本结构的关系图。集合 (b) 线性结构(c)图13-2 四种基本结构的关系图2.数据的存储结构数据的存储结构是指数据元素在计算机中以什么方式存储，也称为物理结构，是逻辑 结构在计算机中的存储映像和实现，它包括数据元素的表示和关系的表示。数据的存储结构主要有两大类：顺序存储结构和非顺序存储结构。顺序存储结构是指用一组连续的存储单元来存放具有某种结构的数据元素，也称为结 点。它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储 单元的邻接关系来体现。非顺序存储结构通常采用链式存储结构，用任意的存储单元来存放结点，因此，每个 结点中至少包含一个指针域，数据元素之间逻辑上的联系是由指针来体现的。这种存储结 构可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中。3 .数据的操作数据的操作就是对数据进行的处理，讨论数据结构的目的就是在计算机中实现操作。 数据在计算机内的有效组织将直接影响数据处理的效率，数据结构就是研究数据的表示及 其相关的运算操作。算法的基本概念1. 算法定义用计算机解决一个实际问题，首先应进行程序设计，而程序设计主要包括算法的设计 和数据结构的设计。“算法”与“数据结构”是密不可分的关系。算法是规则的有限集合，是对特定问题求解步骤的一种逻辑描述。一个算法应该具有 如下特性：(1) 有穷性：算法必须在执行有穷步之后结束。(2) 确定性：算法的每一步必须是确切定义的，无二义性。(3) 可行性：算法的每一步都是能够实现的，即可操作的。(4) 输入：算法有多个或0个输入。(5) 输出：算法至少有 1个或若干个输出。设计一个“好”的算法，通常要考虑达到以下目标：(1) 正确性：所谓正确是指算法应当满足具体问题的要求，对于一切合法的输入都能 产生满足规格说明要求的结果。(2) 易读性：算法主要是为了人的阅读与交流，尤其是在信息化的今天尤为重要，所 以要求算法要有助于人们对算法的理解，以便更好的推广使用，让其充分发挥效益。(3) 健壮性：是指当输入非法数据时，算法也能适当地作出反应或进行处理，而不会 产生莫明其妙的输出结果，更不会死机和死循环。(4) 高效率和低存储量：所谓效率，指的是执行时间，即对于同规模的问题，哪种算 法所用的时间少，哪种算法就效率高。存储量需求是指解决相同规模的问题，所需的最大 存储空间。哪种算法所用的空间少，就相对是好的算法。2 算法的性能评价算法的性能评价是对问题规模与该算法在运行时所占用的空间与所耗费的时间给出一 个数量关系的评价，用时间复杂度和空间复杂度度量。(1) 算法的时间复杂度算法的时间复杂度不是算法执行时间的精确度量，而是用来评估算法的时间增长趋势，只与问题规模有关。应当抛弃具体机器条件，仅考虑算法本身的效率高低。为便于比较解 决同一问题的不同算法的性能，通常以算法中基本操作重复执行的频度作为算法的时间度 量标准。记作：T( n)=)(f( n) T( n)是问题规模的函数，门表示数量级随问题规模n的增大，算法执行时间的增长率T(n)和f(n)的增长率相同。简称时间复杂度。通常应选择算法内重复执行次数最多的基本语句，作为算法执行时间量度。一般 情况下是最深层循环内的基本语句。例 13-1x+=5;例13-2两个nx n阶矩阵相乘。算法中单个语句的执行次数2233单个语句的频度为 1,则 程序段的时间复杂度为T(n)=0(1)for(i=0;i n ;i+)nfor(j=0;j n;j+)n cij=0;nfor(k=0;k =0)个数据元素构成的有限序列，如( al, a2, . , ai, . , an), 表中元素的个数 n(n为)称为线性表的长度，n=0时，称为空表。线性表中数据元素可以有不同的含义。例如 26个英文字母表：(A, B, C, ，Z)就是一个简单的线性表，表中 每一个字母就是一个数据元素，每个元素之间存在着惟一的顺序关系。在较为复杂的线性 表中，数据元素可由若干数据项组成。如学生成绩表中，每名学生的成绩信息由学号、数 学成绩、物理成绩等数据项组成，一条信息称为一个记录，由这些记录组成的线性表称为 文件。2. 线性表的特点有且仅有一个被称作“第一个”的数据元素； 有且仅有一个被称作最后一个”的数据元素； 除第一个和最后一个元素外，集合中的其他数据元素均只有一个前驱和一个后继。对线性表进行的操作主要有如下几种：(1) 初始化 设定一个空的线性表。(2) 求长度即得到表中有多少个元素。(3) 取元素即得到表中某位置的元素。(4定位 给定值x，确定表中与之相等的元素的位置，如没有相等的元素存在，则 给出错误信息。(5) 前插在指定位置的元素之前插入一个元素，插入后表中长度加1。(6) 删除 删除指定位置的元素，删除后表中长度减1。1322线性表的存储及运算1线性表的顺序存储结构线性表的顺序存储是一种最简单的存储方法，也称为顺序表。可以用数组表示。线性表的顺序存储具有以下特点：把线性表中数据元素依次存放到一组连续的存储单元中，每个数据元素对应一个 存储单元，逻辑上相邻的元素存储在计算机前后相邻的存储空间中。线性表中数据元素类型一致，占用相同大小的存储单元。 存储空间利用率高。做插入、删除时需移动大量兀素。通过下标地址计算公式可容易得到第i个元素的存储地址，可随机存取表中任何一个元素，适合频繁查找操作的线性表。2 线性表的链式存储结构线性表的链式存储结构是指每个元素对应内存的一个存储空间，称作结点。把线性表 的元素存放到一个由这种结点组成的链表中，链表中的每个结点至少由两部分组成，即数 据域和指针域。链表结点结构如图 13-3所示。数据域指针域图13-3链表存储结点示意图数据域存放线性表的一个元素，指针域存放其后继结点的地址，最后一个结点的指针 域为空指针。采用这种存储结构，逻辑上相邻的数据元素在内存中的物理存储空间不一定 相邻。例如线性表元素1,元素2,元素3,元素4,按链式存储则对应的存储空间可能为图 13-4所示。图13-4链式存储结构示意图具有链式存储结构的线性表也被称为线性链表或单链表。链表可以有不带头结点和带头结点两种。带头结点的线性链表的逻辑状态如图13-5所示。头结点的数据域可以不存放任何信息，也可以存储线性表的长度等附加信息。头指针变量L指向链表的头结点。aia2图13-5带头结点的线性链表L指向链表中的第一个不带头结点的线性链表逻辑状态如图13-6所示。头指针变量结点。L a1a2图13-6不带头结点的线性链表3 链表结点的定义和分配 线性链表的数据结构可由typedef struct LNodeint data;struct LNode link;C语言中的“结构类型”来描述。/*数据域*/* 指针域*/NODE;线性表的存储空间可在程序运行期间动态分配，如需要向线性表中插入一个结点，只需调用c语言的动态空间分配函数（alloc或malloc函数）动态申请一个存储结点存放相应信息，并把新申请的结点插入到链表的适当位置上。删除一个结点意味着结点将被系统 回收。C语言中free函数用来动态回收结点。链式存储结构具有如下特点：（1）插入、删除运算灵活方便，不需要移