数据结构C语言版第2版 严蔚敏.pdf

Data Struc、turc1,c11 c1,1,.,数据结构(Ci;-,f版）（纶2版）本书在选材与编排上，贴近当前苦通高等院校“数据结构”课程的现状和发展趋势，符合最新研究生考试大纲，内容难度适中，突出实用件和应用性全书共8章，内容包括绪论，线性表，栈和队列，串 数组和广义表，树和二又树，图，查找和排序全书采用类C语言作力数据结构和算志的描还语言本版教材主要做了以下万面的修讨 采用“案例驱动”的编写校式书中结合实妳沁用，将各章按照“案例引入一数据结构及其操作一案例分析与实现的案例驱动思路来展开每章使用一个有趣的，问题案例”开、，由该案例逐步引入新的数据结构，然后给出该数据结构的存储表示及各种基本操作的实现，之后进步分析此案例，最终利用该数据结构来实现此案例 算法讲解更加细致新版教材中对每个笃志思想进行详细阐述，将用文字描述的算志步骤与用类C语言表述的算去描述一对应 仇化教材内容参考计算机专业最新的全国统考考研大纲，增加了大纲近两年新增的考点内容，如分块查找 外部排序等，有助于考研学生复习备考使用严蔚敏清华大学教授，长期从事数据结构教学和教材建设，和吴伟民合作编著的（数据结构）曾获“第二届普通高等学校优秀教材全国特等奖”和1996年度国家科学技术进步奖三等奖”，是目前国内数据结构教学领域的经典教材本教材的结构框图放据结构 线性表一树和二叉树7,，-,1，、.，,l I 绪论1 1 栈和队列1，人,A.),“,1 1 串、数组和广义表1 1 排序I 巨Jd文1111;1!II It反补PPT等教学相关资料教学服务与资源网 教忖服务热线：11111一；：111.-,:;2,飞（）I之阱投怕ltfj什f,i1和：I I.,a pl pre、Llllll.Lll个15:行才凡f具1!_)夕孝父t.11fj1j人l义1111;1!.:llld、UF.ihttp:/.ptpre、Llllll.LllI、从尸三三4 405 4、4。元5。3 791157 9 3 50-34郘5 11 7 5 7.1 8,8个丿7 977 89定7 N SBN 19B s 第l章绪论早期的计算机主要用于数值计算，现在，计算机主要用于非数值计算，包括处理字符、表格和图像等具有一定结构的数据。这些数据内容存在着某种联系，只有分清楚数据的内在联系，合理地组织数据，才能对它们进行有效的处理，设计出高效的算法。如何合理地组织数据、高效地处理数据，这就是“数据结构”主要研究的问题。本章简要介绍有关数据结构的基本概念和算法分析方法。1.1 数据结构的研究内容计算机主要用千数值计算时，一般要经过如下几个步骤：首先从具体问题抽象出数学模型，然后设计一个解此数学模型的算法，最后编写程序，进行测试、调试，直到解决问题。在此过程中寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学语言加以描述，即建立相应的数学方程。例如，用计算机进行全球天气预报时，就需要求解一组球面坐标系下的二阶椭圆偏微分方程；预测人口增长情况的数学模型为常微分方程。求解这些数学方程的算法是计算数学研究的范畴，如高斯消元法、差分法、有限元法等算法。数据结构主要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模型，下面通过三个实例加以说明。【例1.1】学生学籍管理系统。高等院校教务处使用计算机对全校的学生情况作统一管理。学生的基本信息，包括学生的学号、姓名、性别、籍贯、专业等，如表1.1所示。每个学生的基本情况按照不同的顺序号，依次存放在“学生基本信息表”中，根据需要对这张表进行查找。每个学生的基本信息记录按顺序号排列，形成了学生基本信息记录的线性序列，呈一种线性关系。表1.1学生基本信患表学号姓名性别籍贯专业060214201 杨阳男安徽计算机科学与技术060214202 薛林男福建计算机科学与技术060214215 王诗萌女吉林计算机科学与技术060214216 冯子哈女山东计算机科学与技术诸如此类的线性表结构还有图书馆的书目管理系统、库存管理系统等。在这类问题中，计算1二数据结构(C语言版）（第2版）l机处理的对象是各种表，元素之间存在简单一对一的线性关系，因此这类问题的数学模型就是各种线性表，施加千对象上的操作有查找、插入和删除等。这类数学模型称为线性”的数据结构。【例1.2】人机对弈问题。计算机之所以能和人对弈是因为已经将对弈的策略在计算机中存储好。由千对弈的过程是在一定规则下随机进行的，所以，为使计算机能灵活对弈，就必须把对弈过程中所有可能发生的清况及相应的对策都加以考虑。以最简单的井字棋为例，初始状态是一个空的棋盘格局。对弈开始后，每下一步棋，则构成一个新的棋盘格局，且相对千上一个棋盘格局的可能选择可以有多种形式，因而整个对弈过程就如同图1.1所示的一棵倒长的树”。在这棵“树”中，从初始状态（根）到某一最终格局（叶子）的一条路径，就是一次具体的对弈过程。人机对弈问题的数学模型就是如何用树结构表示棋盘和棋子等，算法是博弈的规则和策略。诸如此类的树结构还有计算机的文件系统、一个单位的组织机构等。在这类问题中，计算机处理的对象是树结构，元素之间是一对多的层次关系，施加千对象上的操作有查找、插入和删除等。这类数学模型称为“树”的数据结构。例1.3】最短路径问题。从城市A到城市B有多条线路，但每条线路的交通费不同，那么，如何选择一条线路，使得从城市A到城市B的交通费用最少呢？解决的方法是，可以把这类问题抽象为图的最短路径问题。如图1.2所示，图中的顶点代表城市，有向边代表两个城市之间的通路，边上的权值代表两个城市之间的交通费。求解A到B的最少交通费用，就是要在有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。图I.I井字棋的对弈树图1.2最短路径问题2l第1章绪论1最短路径问题的数学模型就是图结构，算法是求解两点之间的最短路径。诸如此类的图结构还有网络工程图和网络通信图等，在这类问题中，元素之间是多对多的网状关系，施加于对象上的操作依然有查找、插入和删除等。这类数学模型称为“图”的数据结构。从上面三个实例可以看出，非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图的数据结构。因此，简单地说，数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。20世纪60年代初期，“数据结构“有关的内容散见于操作系统、编译原理等课程中。1968年，“数据结构”作为一门独立的课程 被列入美国一些大学计算机科学系的教学计划，同年，著名计算机科学家D.E.Knuth教授发表了计算机程序设计艺术 第一卷基本算法。这是第一本较系统地阐述“数据结构“基本内容的著作。之后，随着大型程序和大规模文件系统的出现，结构化程序设计成为程序设计方法学的主要研究方向，人们普遍认为程序设计的实质就是对所处理的问题选择一种好的数据结构，并在此结构基础上施加一种好的算法，著名科学家Wirth教授的算法喽戏结构程序 正是这种观点的集中体现。目前，数据结构 在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着密切的关系，无论是编译程序还是操作系统都涉及数据元素 在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以使查找和存取数据元素更为方便。因此，可以认为数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程。有关“数据结构”的研究仍不断发展，一方面，面向各专门领域中特殊问题的数据结构正 在研究和发展；另一方面，从抽象数据类型的观点来讨论数据结构，巳成为一种新的趋势，越来越被 人们所重视。1.2 基本概念和术语下列概念和术语将在以后各章节中多次出现，本节先对这些概念和术语赋予确定的含义。1.2.1 数据、数据元素、数据项和数据对象数据(Data)是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑中用到的字符串，多媒体程序处理的图形、图像、声音及动画等通过特殊编码定义后的数据。数据元素(Data Element)是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、记录等。数据元素用千完整地描述一个对象，如前一节示例中的一名学生记录，树中棋盘的一个格局（状态），以及图中的一个顶点等。数据项(Data Item)是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。数据对象(Data Object)是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N=O,士1士2,字母字符数据对象是集合C=A,B,，Z,a,b,，z,学生基本信息表也可以是一个数据对象。由此可以看出，不论数据元素集合是无限集（如整数集），或是有限集（如字母字符集），还是由多个数据项组成的复合数据元素（如学生表）的3=才数据结构(C语言版）（第2版）1集合，只要集合内元素的性质均相同，都可称之为一个数据对象。1.2.2 数据结构数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带”结构的数据元素的集合，“结构”就是指数据元素之间存在的关系。数据结构包括逻辑结构和存储结构两个层次。1.逻辑结构数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立千计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两个要素：一是数据元素；二是关系。数据元素的含义如前所述，关系是指数据元素间的逻辑关系。根据数据元素之间关系的不同特性，通常有四类基本结构，如图1.3所示。它们的复杂程度依次递进。oo。集合结构?线性结构树结构图结构图1.3四类基本逻辑结构关系图下面四种结构中所举的示例是以某班级学生作为数据对象（数据元素是学生的学籍档案记录），来分别考察数据元素之间的关系。(1)集合结构数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。(2)线性结构数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。(3)树结构数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。(4)图结构或网状结构数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图状结构或网状结构。其中集合结构、树结构和图结构都属千非线性结构。线性结构包括线性表（典型的线性结构，如例1.1中的学生基本信息表）、栈和队列（具有特4l第1章绪论I殊限制的线性表，数据操作只能在表的一端或两端进行）、字符串（也是特殊的线性表，其特殊性表现在它的数据元素仅由一个字符组成）、数组（是线性表的推广，它的数据元素是一个线性表）、广义表（也是线性表的推广，它的数据元素是一个线性表，但不同构，即或者是单元素，或者是线性表）。非线性结构包括树（具有多个分支的层次结构）和二叉树（具有两个分支的层次结构）、有向图（一种图结构，边是顶点的有序对）和无向图（另一种图结构，边是顶点的无序对）。这几种逻辑结构可以用一个层次图描述，如图1.4所示。数据的逻辑结构图1.4几种逻辑结构层次图2.存储结构数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。把数据对象存储到计算机时，通常要求既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系，数据元素在计算机内用一个结点来表示。数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构 和链式存储结构。(1)顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。对于前面的“学生基本信息表”，假定每个结点（学生记录）