《数据结构教程》第一章 绪论.doc

11第1章 绪论绪 论“数据结构”是计算机及相关专业的专业基础课之一，是一门十分重要的核心课程，主要学习用计算机实现数据组织和数据处理的方法。通过学习它，也将为计算机专业后续课程（如操作系统、编译原理、数据库原理和软件工程等）的学习打下坚实的基础。另外，随着计算机应用领域的不断扩大，非数值计算问题占据了当今计算机应用的绝大部分，简单的数据类型已经远远不能满足需要，各数据元素之间的复杂联系已经不是普通数学方程式所能表达的了，无论设计系统软件还是应用软件都会用到各种复杂的数据结构。因此，掌握好数据结构课程的知识，对于提高解决实际问题的能力将会有很大的帮助。实际上，一个“好”的程序无非是选择一个合理的数据结构和好的算法，而好的算法的选择很大程度上取决于描述实际问题所采用的数据结构，所以，要想编写出“好”的程序，仅仅学习计算机语言是不够的，必须扎实地掌握数据结构的基本知识和基本技能。1.1 什么是数据结构在了解数据结构的重要性之后，开始讨论数据结构的定义，本节先从一个简单的学生表例子入手，继而给出数据结构的严格定义，接着分析数据结构的几种类型，最后给出数据结构和数据类型之间的区别与联系。1.1.1 数据结构的定义数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。例如，日常生活中使用的各种文字、数字和特定符号都是数据。从计算机的角度看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。它是计算机操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式（例如，200402班学生数据就是该班全体学生记录的集合）。数据元素是数据（集合）中的一个“个体”，是数据的基本单位（例如，200402班中的每个学生记录都是一个数据元素），在计算机中通常被作为一个整体来进行考虑和处理。在有些情况下，数据元素也称为元素、结点、顶点、记录等。有时候，一个数据元素可以由若干个数据项组成。数据项是具有独立含义的数据最小单位，也称为字段或域（例如，200402班中每个数据元素即学生记录是由学号、姓名、性别和班号等数据项组成）。数据对象是性质相同的数据元素的集合，它是数据的一个子集。数据结构是指数据以及相互之间的联系，可以看作是相互之间存在着某种特定关系的数据元素的集合，因此，可以把数据结构看成是带结构的数据元素的集合。数据结构包括如下几个方面： 数据元素之间的逻辑关系，即数据的逻辑结构。 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。 施加在该数据上的操作，即数据的运算。数据的逻辑结构是从逻辑关系上（主要是指相邻关系）描述数据的，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。一般只在高级语言（例如，C/C+语言）的层次上来讨论存储结构。数据的运算是定义在数据的逻辑结构之上的，每种逻辑结构都有一组相应的运算。例如，最常用的运算有：检索、插入、删除、更新、排序等。数据的运算最终需在对应的存储结构上用算法实现。因此，数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。【例1.1】 有一个学生表（数据）如表1.1所示。这个表中的数据元素是学生记录，每个数据元素由4个数据项（即学号、姓名、性别和班号）组成。讨论其存储结构。表1.1 学生表学 号姓 名性 别班 号学 号姓 名性 别班 号1张斌男990112王奇男99018刘丽女990226董强男990234李英女99015王萍女990120陈华男9902解：该表中的记录顺序反映了数据元素之间的逻辑关系，可以用学号标识每个学生记录，这种逻辑关系可以表示为：，。其中尖括号“”表示元素ai和ai+1之间是相邻的，即ai在ai+1之前，ai+1在ai之后。这些数据在计算机存储器中的存储方式就构成了存储结构。通常可以采用C/C+语言中的结构体数组和链表两种方式实现其存储结构。存放上述学生表的结构体数组Stud定义如下：struct int no; /*存储学号*/ char name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ Stud7=1, 张斌, 男, 9901, , 5, 王萍, 女, 9901;数组Stud中各元素在内存中顺序存放，即Studi存放在Studi+1之前，而Studi+1存放在Studi之后。存放学生表的链表的结点类型StudType定义为：typedef struct studnode int no;/*存储学号*/ char name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ struct studnode *next;/*存储指向下一个学生的指针*/ StudType;图1.1 学生表的链表存储结构学生表中每个学生记录采用一个StudType类型的结点存储，一个学生结点的next域指向逻辑结构中它的后继学生对应的结点。从而构成一个链表，其存储结构如图1.1所示，首结点的指针为head，用它来标识该学生链表。由head所指结点的next域得到下一个结点的地址，然后由它得到下一个结点的地址，如此这样，可以找到任何一个结点的地址。对于学生表这种数据结构，可以进行一系列的运算，例如，增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等。从前面介绍的两种存储结构看到，同样的运算，在不同的存储结构中其实现过程是不同的。例如，若查找学号为20的学生的姓名，对于Stud数组，可以从Stud0开始比较，Stud0.no不等于20，再与Stud1.no比较，直到Stud3.no等于20，返回Stud3.name。而对于head为首结点指针的链表，从head所指结点开始比较，*headno不等于20，从它的next域得到下一个结点的地址，再与下一个结点的no域比较，直到某结点的no域等于20，返回其name域。从【例1.1】可以得到结论：对于一种数据结构，其逻辑结构总是唯一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。为了更确切地描述一种数据结构，通常采用二元组表示：B=(D,R)其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R所组成。即：D=di |1in,n0R=rj |1jm,m0其中di表示集合D中的第i个结点或数据元素，n为D中结点的个数，特别地，若n=0，则D是一个空集，因而B也就无结构可言，有时把这种情况认为是具有任一结构。rj表示集合R中的第j个关系，m为R中关系的个数，特别地，若m=0，则R是一个空集，表明集合D中的结点间不存在任何关系，彼此是独立的。D上的一个关系r是序偶的集合，对于r中的任一序偶（x，yD），把x叫做序偶的第一结点，把y叫做序偶的第二结点，又称序偶的第一结点为第二结点的直接前驱（通常简称前驱），称第二结点为第一结点的直接后继（通常简称后继）。如在的序偶中，x为y的前驱，而y为x的后继。若某个结点没有前驱，则称该结点为开始结点；若某个结点没有后继，则称该结点为终端结点。对于对称序偶，即R，R(x, yD)，则用圆括号代替尖括号，即(x, y)R。【例1.2】 采用二元组表示例1.1的学生表。解：学生表中共有7个结点，依次用d1d7表示，则对应的二元组表示为B=(D,R)，其中：D=d1,d2,d3,d4,d5,d6,d7R=rr=,一种数据结构还能够利用图形形象地表示出来，图形中的每个结点对应着一个数据元素，两结点之间的连线对应着关系中的一个序偶。1.1.2 逻辑结构类型在不会产生混淆的前提下，常常将数据的逻辑结构简称为数据结构。数据的逻辑结构主要有以下几类。（1）集合集合是指数据元素之间除了“同属于一个集合”的关系外，别无其他关系。（2）线性结构线性结构是指该结构中的结点之间存在一对一的关系。其特点是开始结点和终端结点都是唯一的，除了开始结点和终端结点以外，其余结点都有且仅有一个前驱，有且仅有一个后继。顺序表就是一种典型的线性结构。（3）树形结构树形结构是指该结构中的结点之间存在一对多的关系。其特点是每个结点最多只有一个前驱，但可以有多个后继，可以有多个终端结点。二叉树就是一种典型的树形结构。（4）图形结构图形结构是指该结构中的结点之间存在多对多的关系。其特点是每个结点的前驱和后继的个数都可以是任意的。因此，可能没有开始结点和终端结点，也可能有多个开始结点、多个终端结点。树形结构和图形结构统称为非线性结构，该结构中的结点之间存在一对多或多对多的关系。由图形结构、树形结构和线性结构的定义可知，线性结构是树形结构的特殊情况，而树形结构又是图形结构的特殊情况。【例1.3】 有一种数据结构B1=(D,R)，其中：D=1,5,8,12,20,26,34R=rr=,画出其逻辑结构表示。解：对应的图形如图1.2所示。图1.2 对应B1的逻辑结构图示从该例中看出，每个数据结点有且仅有一个前驱结点（除第一个结点外），有且仅有一个后继结点（除最后一个结点外）。这种数据结构的特点是结点之间为一对一的联系，即线性关系。这种数据结构就是线性结构。图1.3 对应B2的逻辑结构图示【例1.4】 有一种数据结构B2=(D,R)，其中：D=a,b,c,d,e,f,g,h,i,jR=rr=, ,画出其逻辑结构表示。解：对应的图形如图1.3所示。从该例中看出，每个结点有且只有一个前驱结点（除树根结点外），但有多个后继结点（树叶结点可看做具有0个后继结点）。这种数据结构的特点是数据元素之间为一对多联系，即层次关系。这种数据结构就是树形结构。【例1.5】 有一种数据结构B3=(D,R)，其中：D=a,b,c,d,eR=rr=(a,b),(a,c),(b,c),(c,d),(c,e),(d,e)画出其逻辑结构表示。解：对应的图形如图1.4所示。从该例中看出，每个结点可以有多个前驱结点和多个后继结点。这种数据结构的特点是数据元素之间为多对多联系，即图形关系。这种数据结构就是图形结构。【例1.6】 有一种数据结构B4=(D,R)，其中：D=48,25,64,57,82,36,75R=r1,r2r1=,r2=,画出其逻辑结构表示。解：对应的图形如图1.5所示。它是一种图形结构，其中r1（对应图中虚线部分）为线性结构，r2（对应图中实线部分）为树形结构。 图1.4 对应B3的逻辑结构图示图1.5 对应B4的逻辑结构图示1.1.3 存储结构类型【例1.1】中对学生表采用了数组和链表两种存储方式，前者是典型的顺序存储方法，后者是典型的链式存储方法。归纳起来，在数据结构中有以下4种常用的存储方法。1顺序存储方法该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如C/C+）的数组来描述的。顺序存储方法的主要优点是节省存储空间，因为分配给数据的存储单元全用于存放结点的数据（不考虑C/C+语言中数组需指定最大大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每个结点对应有一个序号，由该序号可直接计算出结点的存储地址（例如，对于数组A，其序号为数组元素的下标，数组元素Ai可以通过*(A+i)进行存取）。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。2链式存储方法该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，通常要借助于计算机程序设计语言（例如C/C+）的指针类型来描述。链式存储方法的主要优点是便于修改，在进行插入、删除运算时，仅需修改相应结点的指针域，不必移动结点。但与顺序存储方法相比，链式存储方法的主要缺点是存储空间的利用率较低，因为分配给数据的存储单元有一部分被用来存储结点之间的逻辑关系了。另外，由于逻辑上相邻的结点在存储空间中不一定相邻，所以不能对结点进行随机存取。3索引存储方法该方法通常是在存储结点信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：(关键字，地址)，关键字唯一标识一个结点，地址作为指向结点的指针。这种带有索引表的存储结构可以大大提高数据查找的速度。线性结构采用索引存储方法后，可以对结点进行随机访问。在进行插入、删除运算时，只需移动存储在索引表中对应结点的存储地址，而不必移动存放在结点表中结点的数据，所以仍保持较高的数据修改运算效率。索引存储方法的缺点是增加了索引表，降低了存储空间的利用率。4哈希（或散列）存储方法该方法的基本思想是根据结点的关键字通过哈希（或散列）函数直接计算出一个值，并将这个值作为该结点的存储地址。哈希存储方法的优点是查找速度快，只要给出待查结点的关键字，就可立即计算出该结点的存储地址。但与前三种存储方法不同的是，哈希存储方法只存储结点的数据，不存储结点之间的逻辑关系。哈希存储方法一般只适合要求对数据能够进行快速查找和插入的场合。上述4种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储映像。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，要视具体要求而定，主要考虑的是运算方便及算法的时空要求。1.1.4 数据结构和数据类型数据类型是和数据结构密切相关的一个概念，容易引起混淆。本节介绍两者之间的差别和抽象数据类型的概念。1数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。数据类型是值的集合和定义在此集合上的一组操作的总称。数据类型可分为简单类型和结构类型两种。简单类型中的每个数据（即简单数据）都是无法再分割的整体，如一个整数、实数、字符、指针、枚举量等都是无法再分割的整体，所以它们所属的类型均为简单类型。结构类型由简单类型按照一定的规则构造而成，且结构类型中还可以包含结构类型，所以一种结构类型中的数据（即结构数据）可以分解为若干个简单数据或结构数据，每个结构数据仍可再分。例如C/C+语言中的数组是一种结构类型，它由固定个数的同一类型的数据顺序排列而成；结构体也是一种结构类型，它由固定个数的不同类型的数据顺序排列而成。数据类型也可以被定义为一种数据结构和对该数据结构允许进行的运算集。对于简单类型，其数据结构就是相应取值范围内的所有数据，每一个数据值是不可分的独立整体，因而数据值内部无结构可言。对于结构类型，其数据结构就是相应元素的集合（它实际上是该结构类型中的一个值）和元素之间所含关系的集合。总之，数据结构是指计算机处理的数据元素的组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。在程序设计语言提供的数据类型支持下，可以根据从问题中抽象出来的各种数据模型，逐步构造出描述这些数据模型的各种新的数据结构。下面总结C/C+语言中常用的数据类型。（1）C/C+语言的基本数据类型C/C+语言中的基本数据类型有int型、float型和char型。int型可以有三个限定词：short，long和unsigned，分别为短整数、长整数和无符号整数。float型有三种形式：float，double和long double，分别为单精度浮点型、双精度浮点型和长浮点型。（2）C/C+语言的指针类型C/C+语言允许直接对存放变量的地址进行操作。如定义int i，则&i表示变量i的地址，也称作指向变量i的指针。存放地址的变量称作指针变量。有关指针的两个操作是：对于定义int i，则&i操作是取变量i的地址；对于定义int *p，这里的p是指向一个整数的指针，则*p操作是取p指针所指的值，即p所指地址的内容。（3）C/C+语言的数组类型数组是同一类型的一组有序数据的集合。数组有一维数组和多维数组。数组名标识一个数组，下标指示一个数组元素在该数组中的顺序位置。数组下标的最小值称为下界，在C/C+语言中总是为0。数组下标的最大值称为上界，在C/C+语言中数组上界为数组大小减1。例如，int a10，定义了包含10个整数的数组a。（4）C/C+语言中的结构体类型结构体是由一组称结构体成员的项组成，每个结构体成员都有自己的标识符。例如，如下语句：struct teacherint no; char name8; int age;定义了一个结构体类型teacher，下面的语句定义了该类型的两个变量t1和t2：struct teacher t1, t2;（5）C/C+语言中的共用体类型共用体是把不同的成员组织为一个整体，它们在存储器中共享一段存储单元，但不同的成员以不同的方式被解释。例如，如下语句：union tagint no1; char no22;定义了一个共用体类型tag，下面的语句定义了该类型的一个变量t：union tag t;变量t的整型成员no1和字符数组成员no2共享相同的存储单元。（6）C/C+语言中的自定义类型C/C+语言中允许使用typedef关键字来定义同名的数据类型名，例如：typedef char ElemType;将char类型与ElemType等同起来。（7）引用运算符C+语言中提供了一种引用运算符“&”，引用是个别名，当建立引用时，程序用另一个已定义的变量或对象（目标）的名字初始化它，从那时起，引用作为目标的别名使用，对引用的改动实际就是对目标的改动。例如：int a=4;int &b=a;说明变量b是变量a的引用，b也等于4，之后这两个变量同步改变。引用常用于函数形参中，采用引用型形参时，在函数调用时将形参的改变回传给实参，例如，有如下函数（其中的形参均为引用型形参）：void swap(int &x,int &y) /*形参前的“&”符号不是指针运算符, 而是引用*/ int tmp=x; x=y;y=tmp当用执行语句swap(a,b)时，a和b的值发生了变换。2抽象数据类型抽象数据类型（abstract data type，ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。一个具体问题的抽象数据类型的定义通常采用简洁、严谨的文字描述，一般包括数据对象（即数据元素的集合）、数据关系和基本运算三方面的内容。抽象数据类型可用（D,S,P）三元组表示。其中：D是数据对象；S是D上的关系集；P是D中数据运算的基本运算集。其基本格式如下：ADT抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本运算：基本运算的定义 ADT抽象数据类型名其中基本运算的定义格式为：基本运算名(参数表)：运算功能描述基本运算有两种参数：赋值参数只为运算提供输入值。引用参数以&打头，除可提供输入值外，还将返回运算结果。例如，抽象数据类型复数的定义为：ADT Complex 数据对象： D=e1,e2|e1,e2均为实数 数据关系： R1=| e1是复数的实数部分,e2 是复数的虚数部分 基本操作： AssignComplex(&Z,v1,v2)：构造复数Z,其实部和虚部分别赋予参数v1和v2的值。 DestroyComplex(&Z)：复数Z被销毁。 GetReal(Z,&real)：用real返回复数Z的实部值。 GetImag(Z,&Imag)：用Imag返回复数Z的虚部值。 Add(z1,z2,&sum)：用sum返回两个复数z1,z2的和值。 ADT Complex抽象数据类型有两个重要特征：数据抽象和数据封装。所谓数据抽象，是指用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。所谓数据封装，是指将实体的外部特性和其内部实现