数据结构

第1章 绪论 【内容提要】数据结构是计算机应用、信息管理与信息系统、电子商务、信息科学与大数据技术等专业重要的专业基础课程，它为后续的专业课程提供了必要的知识和技能准备。本章介绍数据结构的概念和相关术语，以及数据类型的相关知识和算法分析。 【学习要求】了解数据结构的发展历史；掌握和理解数据结构的相关术语与基本概念；运用形式化方法定义和描述一个实际问题对应的数据结构；了解算法的时间复杂度与空间复杂度以及判断算法好坏的方法。 1.1 数据结构的研究现状与发展 1.1.1 国外的研究现状与发展 早在1968年，美国一些学校的计算机系就开始将数据结构作为一门计算机专业的基础课程。数据结构的课程体系*早是由美国计算机专家D. E. Knuth提出的，在他所著的《计算机程序设计技巧》（**卷《基本算法》于1968年出版）一书中，较为系统地描述了客观世界中各类数据的计算机外部结构（逻辑结构）、计算机内部对应的存储方式（存储结构）及其形式化定义和对应的操作之间的关系。其描述方式已经与实际问题的解决方案非常贴近，数据结构作为一门计算机专业的基础课程逐渐成为现实。随后，第二卷《半数字化算法》于1969年出版，第三卷《排序与搜索》于1973年出版，这些著作中的算法及其应用，奠定了数据结构的理论基础。当时，数据结构这门课程已经被美国其他高校所接纳。后来，数据结构课程以算法为主要的讲授内容，成为当时计算机专业的一门重要的基础课程。 20世纪90年代出现的C++语言和Java语言，从根本上解决了计算机网络环境下复杂数据结构应用的问题：如C++语言是面向对象的程序设计语言，它在C语言的基础上发展起来，但它比C语言更容易为人们所学习和掌握。C++以其独*的语言机制在计算机科学的各个领域中得到了广泛应用。面向对象的设计思想是在原来结构化程序设计方法基础上的一次质的飞跃，C++很好地体现了面向对象的各种特性。同样Java语言也是如此，其优点在于：①Java的风格类似于C++；②Java摒弃了C++中容易引发程序错误的地方，如指针和内存管理；③Java提供了丰富的类库。C++和Java语言跨平台、跨系统且操作方便的特点，为复杂数据结构算法的实现带来了非常灵活的操作模式。 1.1.2 国内的研究现状与发展 20世纪70年代后期，数据结构课程在我国已经作为计算机专业一门重要的基础与核心课程，清华大学严蔚敏等学者所编制的教材《数据结构》，逻辑结构清晰、算法丰富，多年来一直作为国内多所高校数据结构课程的首选教材。清华大学的《数据结构》教材*大的特点是：将所有形式的数据结构运用形式化定义方法进行描述，其描述与定义方法严谨，为学生提供了一套逻辑性强的定义方法。与此同时，书中的形式化定义方法还可以将形式化定义用于其他复杂系统的数据结构的定义中。在20世纪80年代，基本上采用Fortran和Basic语言来描述算法。到了20世纪90年代初期，国内大多数教材的算法采用Pascal描述（或类Pascal或伪码来描述），如早期清华大学的《数据结构》教材就是采用这种描述方法。20世纪90年代后期，C语言成为数据结构算法的主要描述语言。2000年以后，随着C++、VC++版本的出现，国内的数据结构教材又以C++、VC++版本为主流。之后，随着强大的网络技术的普及与应用，又出现了跨平台的数据结构版本，如Java、.Net版本。这些语言的诞生与应用，给多系统的复杂数据的整合、定义域知识的描述提供了新的解决方案，尤其是当前大数据的形成和云计算架构的形成，给数据结构课程增添了更多的新模式。 因此，数据结构是一门专业性非常强的计算机基础课程，同时，也是计算机和信息管理等专业必不可缺的核心课程。换句话说，数据结构课程覆盖的专业知识广阔，涉及解决问题的数学模型众多。随着计算机、网络技术的发展和数据处理能力的增强，国内外相关专业开设数据结构课程的学校越来越多，且包括的内容也越来越多。由早先的线性表运算、非线性表运算、堆栈、排队、递归、树、图等传统的数据操作模式，扩充到多系统环境下的多维数据结构、复杂类型的数据结构以及跨平台模式的数据结构模式。 1.1.3 数据结构在计算机专业中的地位 数据结构不仅是计算机和信息管理等专业主要的基础课程，更重要的是作为编译原理、操作系统、数据库原理、汇编语言程序设计、管理与决策等课程的前驱课程，对该课程内容的掌握程度直接反映了计算机软件水平、管理与决策水平的高低。数据结构在计算机专业中的地位如图1.1所示。 图1.1 数据结构在计算机专业中的地位 数据结构并不是要告诉我们怎样编程，而是教会我们如何用*精练的语言和*少的资源编写出*优秀、*合理的算法与程序。换句话说，数据结构存在的意义就是使程序*优化。所以学习数据结构需要一定的基础知识。如果缺乏数据结构的知识，仅仅学会计算机语言的使用，想要编制出好的程序是不可能的，也不可能将客观世界复杂问题对应的实际模型进行建模和求解。同时，在大型软件开发的六个阶段（计划、需求分析、设计、编码、测试和维护）中，数据结构的内容体现在以客观管理问题求解过程中的数据建模及设计为核心，同时也涉及编码和需求分析阶段的一小部分内容。 总之，数据结构随着计算机应用与网络的普及一直在发展，并且面向特殊领域的数据结构也在不断发展，如新兴的图像处理与动画技术需要新的数据结构予以支持。面向对象技术与其他新兴技术的出现，掀起了从更加抽象的层次上讨论数据结构的概念和内容的新趋势。 1.2 什么是数据结构 数据结构课程主要是介绍一些常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示和它们进行各种运算的实现算法。 按照字面含义，数据结构一定包括与数据及其结构相关的含义。广义上，数据结构包括数据的逻辑结构、数据的存储结构和数据运算三个方面，即涉及数据之间的逻辑关系、数据在计算机中的存储方式和相关的一组操作。 1. 数据结构主要任务 数据结构主要任务是：首先，将某实际问题的逻辑结构找出来；然后，在针对该逻辑结构进行科学分析后，映射为其对应的物理结构（即数据结构）形式；*后，对该数据进行操作。 美国计算机科学家Niklaus Wirth（尼 沃思）认为： Algorithms+Data Structure=Programs Algorithms（算法）：实现程序的逻辑步骤。 Data Structure（数据结构）：描述了解决问题的数学模型；解决问题的相关数据集合；数据之间的结构关系集合。 Programs（程序）：为解决实际问题而编制的一组指令集合。 2. 算法、数据结构与程序之间的关系 （1）算法是实现程序的核心。 （2）如果一个问题的解决方法确定，则该问题的数据结构及数据之间的运算关系也是确定的，即该数据结构的选取决定了其算法的时间复杂性——程序运行的时间和速度。 （3）程序运行速度与算法本身、计算机本身、操作系统、网络环境等紧密相关。 如图1.2所示为计算机解决问题的步骤，数据结构的工作主要体现在第1步“分析问题”与第2步“确定处理方案”，这既是*基本的工作，也是*重要的工作。下面将举几个例子来帮助理解。 图1.2 计算机解决问题的步骤 例1.1 求解 。 具体步骤如下。 （1）首先判断该问题是否属于计算问题，即所涉及的运算对象是否属于整型、实型或布尔型的简单变量。 （2）运用某语言将中的a与b分别输入后，再进行计算。 （3）打印或显示运行结果。 例1.2 电话号码的查询。 具体步骤如下。 （1）构造一张电话号码登记表，表中的每个结点存放两个数据项：姓名与电话号码。 （2）按照链表结构构造该问题的数据存储方式，即问题对应的内部存储方式，确定链表的模式，如单链表模式。如图1.3所示。 图1.3 链式电话号码登记表 例1.3 计算矩阵的乘积 。 具体步骤如下。 （1）分析问题中的各个运算参数的外部表示。如图1.4所示。 图1.4 矩阵运算参数的外部表示 （2）确定、与矩阵的内部存储方式。 A. 以行为主序存储。 在内存的顺序是：。 在内存的顺序是：。 在内存的顺序是：。 B. 以列为主序存储。 在内存的顺序是： 在内存的顺序是： 在内存的顺序是： （3）寻址方式决定其计算模式。 A. 如果以行为主序存储，该矩阵乘积的寻址公式为 B. 如果以列为主序存储，该矩阵乘积的寻址公式为 （4）计算矩阵乘积，显示计算结果。 例1.4 单车道车辆进库与出库满足先进后出或者后进先出的规律，也将满足这种规律的运算叫作栈，栈的运算与操作在栈的一端进行（详细内容请参考第3章栈和队列的相关内容）。 例1.5 银行窗口业务处理，满足先来先服务、后来后服务的排队的操作规律，也叫作队列（详细内容请参考第3章栈和队列的相关内容）。 例1.6 图论问题。图的算法将在本书的后面章节介绍，该算法主要包括：图的表示方法、图的遍历、*短路径算法、影响工程进度的关键路径等算法（详细内容请参考第6章图的相关内容）。 以多岔路口交通灯设置问题为例。通常在十字路口只需要设置红、绿两种颜色的交通灯以便维持交通秩序，但在多岔路口则需设置多种颜色的交通灯才能使车辆流通量*大又保证交通秩序。如图1.5（a）所示五岔路口，C和E表示单行道。图1.5（b）表示五岔路口的车流方向，在路的中间有L1～L13共13个交通信号灯，图中箭头方向表示每条路上的车流方向，车流有交叉或者箭头指向相同出口表示两条道路不能同时通车，否则会发生交通事故。当且仅当某个方向上的交通灯变为绿色时，此方向上的车辆才能通行。问怎样变换交通灯的颜色才能使此路口的车都能安全通过又能达到路口的*大流通量？ 图1.5 五岔路口交通灯设置问题 在图1.5中，用一个顶点表示一条通路，两条通路之间相互矛盾的关系用两个顶点之间的连线表示，即若两条通路之间不能同时通车，则两个顶点之间连一条线。因此设置交通灯的问题转换为对图中顶点的着色问题，要求对图中的每个顶点着一种颜色，并且要求有线相连的两个顶点不能同时具有相同的颜色，而总的颜色种类尽可能少。图1.6为其中的一种着色方案。 图1.6 五岔路口交通灯设置问题的一种着色方案 解决方案： 1号灯亮时，只有AB、BA、AC、AD、DC、ED方向上的车能同时通过； 2号灯亮时，只有BC、BD、EA方向上的车能同时通过； 3号灯亮时，只有DA、DB方向上的车能同时通过； 4号灯亮时，只有EB、EC方向上的车能同时通过。 例1.7 报文编码问题。此问题属于*优二叉树问题，即该问题对应的数据结构属于二叉树的优化问题，运用该优化解决方法可解决报文编码问题（详细内容请参考第6章关于哈夫曼树及其应用的相关内容）。 另外，利用数据结构还可以对如下问题提出解决方法：①将文本编辑与操作归结为字符串操作问题；②为提高查找速度提出各类查找算法；③为方便各类快速查找而对数据的科学排序方法。 归纳起来讲，数据结构课程是一门“描述现实世界实体的数学模型（非数值计算）及其操作在计算机中如何表示和实现”的理论和应用性强的计算机专业基础课。 1.3 相关概念 在本节中，我们将对一些概念和术语赋以确定的含义，以便与读者取得“共同的语言”。这些概念和术语将在以后的章节中多次出现。 1. 数据