数据结构第一章绪论

数据结构新疆大学软件学院孙华

电话-mail:xj_sh@163.com2015-2016学年第一学期

使用教材：严蔚敏吴伟民编著，数据结构（C语言版），清华大学出版社参考书：1、曹桂琴编著，数据结构基础，大连理工大学出版社。2、晋良颖编，数据结构，人民邮电出版社3、BrunoR.Preiss，数据结构与算法，电子工业出版社使用教材及参考书课程教学目的在计算机及其应用的各个领域中，都会用到各种各样的数据结构，通过本课程使学生学会分析和研究计算机加工对象的特性，选择合适的数据结构和存储表示，以及编制相应的实现算法．课程教学基本要求:本课程介绍各种最常用的数据结构，阐述各种数据结构内涵的逻辑关系，讨论它们在计算机中的存储表示，以及在这些数据结构上的运算和实际的执行算法，并对算法的效率进行简要的分析和讨论。数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法）的研究范围，而且和计算机软件的研究有着密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。课程介绍数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。程序＝算法＋数据结构目前在我国，《数据结构》已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。通过对这门课程的学习可增强选择合适的数据结构与编写高效的程序的能力。课程介绍教学安排及考试讲课学时：50学时上机时间：4次（共8学时）考试成绩计算：平时成绩（考勤、作业及上机）30分考试（70分）

目录第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章内部排序第10章文件计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。与此对应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据。为了编写出一个“好”的程序，必须分析待处理的对象的特征以及各对象之间存在的关系，这就是“数据结构”这门学科形成和发展的背景。第一章绪论第一章绪论用计算机解决一个具体问题时，大致需要经多下列几个步骤：首先要从具体问题抽象出一个适当的数学模型然后设计一个解此数学模型的算法，最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。然而，更多的非数值问题无法用数学方程描述。什么是数据结构呢？先看以下几个例子。1.1什么是数据结构书目文件按书名按作者名按分类号索引表线性表例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片树……..……..…...…...…...…...例2人机对奕问题对于一个多叉路口，设计一个交通信号灯的管理系统。首先需要分析一下所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。CEDAB例3多叉路口交通灯管理问题可通行方向ABACADBABCBDDADBDCEAEBECEDCEDAB例3多叉路口交通灯管理问题有些通行方向显然不能同时进行，相应的结点间画一条连线。ABACADBABCBDDADBDCEAEBECED图1.2交叉路口的图示模型CEDAB图把图1.2中的结点进行分组，使得有结点相连的结点不在同一个组里。

地图着色问题如果把上图中的一个结点理解为一个国家，结点之间的连线看作两国有共同边界，上述问题就变成著名的“着色问题”：即求出最少要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。通过上面的分析，我们就获得了该交通管系统的数学模型。下面就可以着手进行算法的设计。例3多叉路口交通灯管理问题算法设计2.“贪心法”

while有结点未着色；{选择一种新颜色；

在未着色的结点中,给尽可能多的彼此结点之间没有边点着色；}1.对n个结点，逐个测试其所有组合；例3多叉路口交通灯管理问题ABACADBABCBDDADBDCEAEBECED图1.2交叉路口的图示模型图ABACADBABCBDDADBDCEAEBECEDCEDAB着色结果把上面方法应用于图1.2，得到下面的分组：

绿色：AB,AC,AD,BA,DC,ED

蓝色：BC,BD,EA

红色：DA,DB

白色：EB,EC例3多叉路口交通灯管理问题描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。数据结构就是研究数据的逻辑结构和物理结构它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。第一章绪论数据(Data):是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。对计算机科学而言，数据的含义极为广泛，如图像、声音等都可以通过编码而归之于数据的范畴。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。例如，例1－2中的“树”中的一个棋盘格局，例1－3中的“图”中的一个园圈都被称为一个数据元素。1.2基本概念和术语一个数据元素可由若干个数据项组成。例如，例1－1中一本书的书目信息为一个数据元素，而书目信息中的每一项（如书名、作者名等）为一个数据项。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N＝{0，±1，±2，…}，字母字符数据对象是集合C＝{A，B，C，…}。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。1.2基本概念和术语数据结构主要指逻辑结构和物理结构。数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构结构中的数据元素之间存在一对一的关系。三、树型结构结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。1.2基本概念和术语数据结构的形式定义为：数据结构是一个二元组：

Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。1.2基本概念和术语数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。数据结构在计算机中有两种不同的表示方法：

顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。1.2基本概念和术语元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址

存储内容

指针1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

链式存储

h

数据的逻辑结构

数据的存储结构

数据的运算：检索、排序、插入、删除、修改等

线性结构

非线性结构

顺序存储

链式存储线性表栈队树形结构图形结构数据结构的三个方面：1.2基本概念和术语数据类型：数据类型是一个值的集合和定义在这个值集范围上的一组操作的总称。例如，C语言中的整型变量，其值集为某个区间上的整数，定义在其上的操作为：加、减、乘、除和取模等算术运算。按“值”的不同特性，高级程序语言中的数据类型可分为：一类是非结构的原子类型。原子类型的值是不可分解的。如：C语言中的基本类型（整型、实型、字符型和枚举类型）、指针类型和空类型。另一类是结构类型。结构类型的值是由若干成分按某种结构组成的。例如数组的值由若干分量组成。每个分量可以是整数，也可以是数组等。1.2基本概念和术语抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。和数据结构的形式定义相对应，抽象数据类型可用三元组描述如下：（Ｄ，Ｓ，Ｐ）D是数据对象，S是D上的关系集，P是对D的基本操作集。1.2基本概念和术语本书采用以下格式定义抽象数据类型抽象数据类型的定义：

ADT抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据逻辑关系的定义>

基本操作：<基本操作的定义>}ADT抽象数据类型名基本操作的定义格式为：

基本操作名（参数表）

初始条件：<初始条件描述>

操作结果：<操作结果描述>1.2基本概念和术语抽象数据类型三元组的定义：ADTTriplet{数据对象：D={e1,e2,e3|e1,e2,e3ElemSet}数据关系：R1={<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3)操作结果：构造了三元组T，元素e1,e2和e3分别赋以参数v1,v2和v3的值。}ADTTriplet1.2基本概念和术语ADTTriplet{数据对象：D={e1,e2,e3|e1,e2,e3ElemSet}数据关系：R1={<e1,e2>,<e2,e3>}基本操作：Get(T，i，&e)初始条件：三元组T已存在，1i3操作结果：用e返回T的第i元的值。}ADTTriplet1.2基本概念和术语抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。由于本书在高级程序设计语言的虚拟层次上讨论抽象数据类型的表示和实现，并且讨论的数据结构及其算法主要是面向读者，故采用介于伪码和C语言之间的类C语言作为描述工具，有时也用伪码描述一些只含抽象操作的抽象算法。这使得数据结构和算法的描述和讨论简明清晰，不拘泥于C语言的细节，又能容易转换成C或者C＋＋程序。1.3抽象数据类型的表示和实现本书采用的类C语言精选了C语言的一个核心子集，同时作了若干扩充，增强了语言的描述功能。以下对其作简要说明。（1）预定义常量和类型

//函数结果状态代码#defineTRUE1#defineFLASE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函数的类型，其值是函数结果状态代码

TypedefintStatus;1.3抽象数据类型的表示和实现（2）数据结构的表示用类型定义（typedef）描述。数据元素类型约定为Elemtype，由用户在使用该数据类型时定义。（3）基本操作的算法都用以下形式的函数描述：函数类型

函数名（函数参数表）{//算法说明语句序列}//函数名

1.3抽象数据类型的表示和实现（4）赋值语句有简单赋值变量名=表达式；串值赋值变量名1=变量名2=……=表达式成组赋值（变量名1，。。。，）=（表达式1，）交换赋值变量名变量名条件赋值变量名=条件表达式？表达式T：表达式F1.3抽象数据类型的表示和实现（5）选择语句有条件语句1if（表达式）语句；条件语句2if（表达式）语句；Else语句开关语句1switch(表达式){case值1：语句序列1；break;Default:语句序列n+1;}开关语句2switch{case条件1：语句序列1；break;Default:语句序列n+1;}1.3抽象数据类型的表示和实现（6）循环语句有For语句for（赋初值表达式；条件；修改表达式序列）语句；While语句while（条件）语句；do-while语句do{语句序列}while（条件）；1.3抽象数据类型的表示和实现（7）结束语句函数结束语句return表达式；return；Case结束语句break;异常结束语句exit(异常代码)（8）输入和输出语句输入语句scanf([格式串]，变量1，变量n)；输出语句printf([格式串]，表达式1，表达式2)；1.3抽象数据类型的表示和实现（9）注释单行注释//文字序列（10）基本函数有求最大值max(表达式1，表达式n）求最小值min(表达式1，表达式n）求绝对值abs(表达式)求不足整数值floor（表达式）判定行结束eoln（文件变量）或eoln1.3抽象数据类型的表示和实现（11）逻辑运算约定与运算&&:对于A&&B,当A的值为0时,不再对B求值。或运算||：对于A||B,当A的值为非0时,不再对B求值。1.3抽象数据类型的表示和实现例题：抽象数据类型Triplet的表示和实现//--------采用动态分配的顺序存储结构----------------TypedefElemType*Triplet://--------基本操作的函数原形说明----------------//initTriplet分配三个元素存储空间StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3）；//操作结果：构造了三元组T，元素e1，e2和e3分别赋以参数v1，v2和v3的值。1.3抽象数据类型的表示和实现StatusDestroyTriplet(Triplet&T）；//操作结果：三元组T被消除。StatusGet(Triplet&T，inti，ElemType&e）；//初始条件：三元组T已存在，1i3。

//操作结果：用e返回T的第i元的值。1.3抽象数据类型的表示和实现//--------基本操作的实现----------------StatusGet(Triplet&T，inti，ElemType&e）{//1i3,用e返回T的第i元的值。

If(i<1||i>3)returnERROR;e=T[i-1]；

returnOK;}//Get}ADTTriplet1.3抽象数据类型的表示和实现算法是对特定问题求解步骤的一种描述，它是指令的有限序列，每一条指令表示一个或多个操作。算法有五个特性：1.4算法和算法分析（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入一个算法有零个或多个输入。（5）输出一个算法有一个或多个输出。评价一个好的算法有以下几个标准:（1）正确性（2）可读性算法应该好读。（3）健状性算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。（4）效率与存储量需求效率是指算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。2、算法设计的要求程序不含语法错误。程序对于几组输入数据能够得出满足规格说明的结果。程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明的结果。程序对于一切合法的输入数据都能产生满足规格说明的结果。正确性（算法应满足具体问题的需求）算法执行时间需要通过依据该算法编制的程序在计算机上运行时所消耗的时间度量。度量一个程序的执行时间通常有两种方法。事后统计的方法

一是必须先运行依据算法编制的程序二是所得时间的统计量依赖于计算机的硬件、软件等环境因素求出该算法的一个时间界限函数事前分析估算的方法

依据的算法选用何种策、问题的规模、书写的语言、编译程序所产生的机器代码的质量、机器执行指令的速度。所以，人们常常采用事前分析估算的方法。3、算法效率的度量使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件软件有关的因素，可以认为一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量表示），或者说，它是问题规模的函数。一个算法是由控制结构（顺序分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于研究问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。3、算法效率的度量一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作T(n)=O(f(n))它表示随着问题规模n的增加，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。3、算法效率的度量显然，被称作问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。语句的频度是指的是该语句重复执行的次数。例２{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)。如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。3、算法效率的度量例３、for(i=1;i<=n;++i){++x;s+=x;}语句频度为：2n

其时间复杂度为：O(n)即时间复杂度为线性阶。例４、for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}语句频度为：2n2时间复杂度为：O(n2)即时间复杂度为平方阶。3、算法效率的度量定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)。证略。例５for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}语句频度为：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2时间复杂度为O(n2),

即此算法的时间复杂度为平方阶。3、算法效率的度量for(i=1;i<=n;++