搜索
数据结构•第一章绪论•第二章线性表•第三章数组和广义表•第四章栈和队列•第五章串•第六章树•第七章图•第八章查找•第九章排序第一章绪论本章学习要求：•了解数据结构的研究内容。•理解掌握数据结构的基本概念和术语。•了解数据元素间的结构关系。•理解掌握算法及算法的描述1.1数据结构的发展1.1.1数据结构的发展简史最早对这一发展作出杰出贡献的是D.E.Kunth教授和C.A.R.Hoare(霍尔)。D.E.Kunth的《计算机程序设计技巧》和霍尔的《数据结构札记》对数据结构这门学科的发展作出了重要贡献。随着计算机科学的飞速发展，到20世纪80年代初期，数据结构的基础研究日臻成熟，已经成为一门完整的学科。1.1.2数据结构的研究内容用计算机解决一个具体的问题时，大致需要经过以下几个步聚：（1）分析问题，确定数据模型。（2）设计相应的算法。（3）编写程序，运行并调试程序直至得到正确的结果。[例1.1]学生成绩表学号姓名高数数据结构8201001李红89908201002杜刚9587…………82010040刘珊8786一个数据元素数据项[例1.2]组织示意图学院教务处学生处总务处图书馆电教中心团委财务科后勤中心[例1.3]七桥问题Euler在1736年访问俄罗斯的哥尼斯堡时，他发现当地的居民正从事一项非常有趣的消遣活动。哥尼斯堡城中有一条名叫勒格尔的河流横经其中，在河上建有七座桥如图所示：ADBC这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。设四块陆地分别为A、B、C、D，Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示，便得到如下的图形：ADCB1327645后来推论出此种走法是不可能的。他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。即每个点如果有进去的边就必须有出来的边，因此每一个陆地与其他陆地连接的桥数必为偶数。七桥所成的图形中，没有一点含有偶数条数，因此上述的任务是不可能实现的。1.2数据结构的基本概念和术语•数据（data）：是指在计算机科学中能够被计算机输入、存储、处理和输出的一切信息，是计算机处理的信息的某种特定的符号表示形式。包括数字、英文、汉字、以及表示图形、声音、光和电的符号等。•数据项(DataItem)：是数据的最小单位，有时也称为域（field），即数据表中的字段。数据项是具有独立含义的不可分割的最小标识单位。1.2数据结构的基本概念和术语•数据元素(DataElement)：是数据的基本单位，在计算机信息处理中通常作为一个整体来考虑。一个数据元素可以由若干个数据项组成，数据元素也称为元素、结点、顶点、记录。•数据对象(DataObject)：具有性质相同的数据元素的集合，是数据的一个子集。如整数数据对象是集合N={0,±1,±2,…}。1.2数据结构的基本概念和术语•数据类型：是一个值的集合和定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合：值的集合和操作集合。其中值的集合定义了该类型数据元素的取值，操作集合定义了该类型数据允许参加的运算，例如C语言中的int类型，取值范围是[-32768～32767]，主要的运算为加、减、乘、除、取模、乘方等。•数据结构(DataStructure)：带结构的数据元素的集合，描述了一组数据元素及元素间的相互关系。数据元素间的关系包括三个方面：数据的逻辑结构、存储结构和操作集合。1.2数据结构的基本概念和术语•数据类型：是一个值的集合和定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合：值的集合和操作集合。其中值的集合定义了该类型数据元素的取值，操作集合定义了该类型数据允许参加的运算，例如C语言中的int类型，取值范围是[-32768～32767]，主要的运算为加、减、乘、除、取模、乘方等。•数据结构(DataStructure)：带结构的数据元素的集合，描述了一组数据元素及元素间的相互关系。数据元素间的关系包括三个方面：数据的逻辑结构、存储结构和操作集合。1.3数据的逻辑结构逻辑结构（logicalstructure）：是指数据元素之间的逻辑关系，是用户使用需要建立起来的数据组织形式，是独立于计算机的。根据数据元素之间的不同关系，有以下四种基本逻辑结构：（1）线性结构：结构中的数据元素之间是一对一的关系。在线性结构中，有且仅有一个开始结点和一个终端结点，除了开始结点和终端结点，其余结点都有且仅有一个直接前趋和一个直接后继。1.3数据的逻辑结构（2）树状结构或层次结构：数据元素之间存在着一对多的关系。比如部门之间的隶属关系、人类社会的父子关系、上下级关系等。在树形结构中，除根结点之外，每个结点都有唯一直接前趋，所有的结点都可以有0个或多个直接后继。1.3数据的逻辑结构（3）图形结构或网状结构：结构中的数据元素之间存在着多对多的关系。在图状结构中，每个结点都可以有多个直接前趋和多个直接后继。（4）集合结构：数据元素间除了同属于一个集合的关系外，无任何其他关系。1.3数据的逻辑结构•一个数据结构的逻辑结构G可以用二元组来表示：•G=（D，R）•其中：•D是数据元素的集合；•R是D上所有数据元素之间关系的集合（表示各元素的前趋、后继关系）。R中的关系圆括号表示是双向的，尖括号表示是单向的。•[例1-4]一种数据结构Graph=（D，R）•其中：•D={A，B，C，D，E}•R={r}•r={(A,B),(A,C),(B,C),(B,D),(B,E),(C,E)}•r中的(A,B)表示顶点A到顶点B之间的边是双向的，上述的结构关系如图1-5所示。ADCBE1.4数据的存储结构数据的存储结构(storagestructure)又称物理结构，是数据的逻辑结构在计算机存储器中的存储形式（或称映象）。•（1）顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，可用一维数组描述。•（2）链式存储结构：借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。可用指针描述，数据元素不一定存在地址的存储单元，存储处理的灵活性较大。•（3）索引存储：是在原有存储数据结构的基础上，附加建立一个索引表，索引表中的每一项都由关键字和地址组成。采取索引存储的主要作用是为了提高数据的检索速度。•（4）散列存储：是通过构造散列函数来确定数据存储地址或查找地址的。1.5算法和算法的描述1.5.1什么是算法1．算法的的概念算法是为了解决某类问题而规定的一个有限长的操作序列，是对解题过程的准确而完整的描述。2．算法的特性一个算法一般具有以下特性：（1）输入：一个算法必须有0个或多个输入。这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。（2）确定性：算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、清晰地规定。（3）有穷性：一个算法无论在什么情况下都应在执行有穷步后结束。1.5算法和算法的描述（4）可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（5）输出：一个算法应有一个或多个输出，输出的量是算法计算的结果。3.算法与程序的区别（1）算法代表了对问题的求解过程，而程序则是算法在计算机上的实现。算法用特写的程序设计语言来描述，就成了程序。（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。（3）一个算法必须在有穷步之后结束，一个程序不一定满足有穷性。（4）可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（5）输出：一个算法应有一个或多个输出，输出的量是算法计算的结果。3.算法与程序的区别（1）算法代表了对问题的求解过程，而程序则是算法在计算机上的实现。算法用特写的程序设计语言来描述，就成了程序。（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。（3）一个算法必须在有穷步之后结束，一个程序不一定满足有穷性。1.5.2算法设计的要求通常设计一个“好”的算法应考虑达到如下目标：（1）正确性：在合理的数据输入下，能在有限的运行时间内得到正确的结果。（2）可读性：程序可读性好，有助于人对算法的理解。（3）健壮性：当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。（4）高效性：对同一个问题，执行时间越短，算法的效率越高。（5）低存储量：完成相同的功能，执行算法所占用的存储空间应尽可能的少。1.5.4算法的描述算法可以用流程图、自然语言、计算机程序语言或其他语言来描述，但描述必须精确地说明计算过程。在本书中算法是以函数形式描述，描述如下：类型标识符函数名（形式参数表）╱*算法说明＊╱｛语句序列｝1.5.4算法效率的评价算法可以用流程图、自然语言、计算机程序语言或其他语言来描述，但描述必须精确地说明计算过程。在本书中算法是以函数形式描述，描述如下：类型标识符函数名（形式参数表）╱*算法说明＊╱｛语句序列｝1．时间复杂度（TimeComplexity）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数ƒ(n)，算法的时间量度记作：T（n）=O(ƒ(n))它表示随问题规模n的增大，算法执行时间的增长率和ƒ(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。1.5.4算法效率的评价算法可以用流程图、自然语言、计算机程序语言或其他语言来描述，但描述必须精确地说明计算过程。在本书中算法是以函数形式描述，描述如下：类型标识符函数名（形式参数表）╱*算法说明＊╱｛语句序列｝1．时间复杂度（TimeComplexity）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数ƒ(n)，算法的时间量度记作：T（n）=O(ƒ(n))它表示随问题规模n的增大，算法执行时间的增长率和ƒ(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。1.5.4算法效率的评价算法可以用流程图、自然语言、计算机程序语言或其他语言来描述，但描述必须精确地说明计算过程。在本书中算法是以函数形式描述，描述如下：类型标识符函数名（形式参数表）╱*算法说明＊╱｛语句序列｝1．时间复杂度（TimeComplexity）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数ƒ(n)，算法的时间量度记作：T（n）=O(ƒ(n))它表示随问题规模n的增大，算法执行时间的增长率和ƒ(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。1.5.4算法效率的评价[例1-5]在下列的三个程序中(a)x=0(b)for(i=1;i=n;i++)x=x+1(c)for(i=1;i=n;i++)for(j=1;j=n;j++)X=X+i*j上述三个语句的频度分别为1，n,n22.空间复杂度（SpaceComPlexity）一个程序的空间复杂度是指程序运行从开始到结束所需要的存储空间。包括算法本身所占用的存储空间、输入数据占用的存储空间以及算法在运行过程中的工作单元和实现算法所需辅助空间。第二章线性表本章学习要求：•系统学习线性表的存储结构及其基本操作。•理解线性表的逻辑结构•理解掌握线性表的顺序存储结构及操作•理解掌握线性表的链式存储结构及操作2.1线性表逻辑结构2.1.1线性表的定义1．线性表的定义线性表（LinearList）是具有相同数据类型的数据元素的一个有限序列。通常表示为：（a1，a2，…ai，ai+1…an）其中n为线性表的长度，n≥0；当n=0时表示一个空表。线性表相邻元素之间存在着顺序关系。a1叫表头元素，an叫表尾元素。除第一个和最后一个元素外，每个元素都只有一个前趋和一个直接后继。ai-1称为ai的直接前趋结点，ai+1称为ai的直接后继结点。表中的元素可以是一个数，也可以是由多个数据项组成的复