数据结构 绪论课件

数据结构信息科学与技术学院范红E-mail:ccfanhong@163.com

1数据结构教材及参考书目：数据结构（C语言版）严蔚敏等编清华大学出版社数据结构习题集（C语言版）严蔚敏等编清华大学出版社数据结构C++语言描述刘卫东等译清华大学出版社2数据结构预备知识：C语言程序设计的基本技术离散数学概率论3数据结构第一章绪论第六章树与二叉树第二章线性表第七章图第三章栈和队列第八章动态存储管理第四章串

第九章查找第五章数组与广义表第十章内部排序5第一章绪论目的：了解数据结构的背景掌握一些基本概念和术语掌握抽象数据类型的定义、表示与实现描述算法的类C语言掌握算法分析的一些基本方法6第一章绪论重点：有关数据结构的基本概念和术语掌握抽象数据类型ADT的定义、表示与实现熟悉类C语言的书写规范理解算法五个要素的确切含义掌握估算时间复杂度的方法，了解空间复杂度的度量方法7第一章绪论难点：抽象数据类型ADT的表示与实现算法复杂度的分析方法8一、数据结构形成和发展背景计算机是一门研究用计算机进行信息表示和处理的科学两个问题：

1）信息的表示和组织：直接关系到处理信息的程序的效率；

2）信息的处理：面向系统程序和应用程序的大规模和复杂结构1.1什么是数据结构10二、数据结构1、用计算机解决问题的步骤：具体问题—建立数学模型—设计算法—编制程序—测试和调整—最终答案建立数学模型（关键）：分析问题、提取操作对象、找出对象间关系，对此用数学语言加以描述算法设计：利用建立的数学模型，根据具体问题，设计出解决问题的方法1.1什么是数据结构12二、数据结构2、数据结构主要关心的：结构中各元素之间逻辑关系（数学模型）

线性结构：如图书馆的书目索引

树形结构：见后面例子

图形结构：见后面例子结构中各元素的存储方式结构具有的行为特征（其上的操作）在计算机中的表示和实现

1.1什么是数据结构14例1.图书馆的书目检索系统自动化问题（线性结构）图书馆的一本图书由书名、作者、出版社等数据来描述，根据需要我们选择其中的若干项组成一个数据元素来对应一本书图书馆的编目表反映了书与书之间的关系，是数据元素之间的结构。当然我们还应注意到书是具体地放在某个书架上的，它是编目表的物理实现图书馆从两方面管理图书：物理的藏书和逻辑的编目表。这就是图书馆的结构。和图书馆一样计算机管理数据，也有两个方面：即物理的存储和逻辑的关系1.1什么是数据结构151.1什么是数据结构16例2：下棋问题1.1什么是数据结构17例3.多叉路口交通灯的管理（图结构）11112223344111.1什么是数据结构18数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间相互关系和操作等的学科对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型1.1什么是数据结构20二、数据结构

NiklausWirth：

Algorithms+DataStructures=Programs

程序设计:为计算机处理问题编制一组指令集算法：处理问题的策略数据结构：问题的数学模型1.1什么是数据结构211.2基本概念和术语数据：数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合数值性数据/非数值性数据数据元素：数据基本单位，通常作为一个整体来考虑，如：“树”中的一个棋盘格局；学生信息表，一个数据元素（记录）含若干个数据项等数据项是数据的不可分割的最小单位231.2基本概念和术语数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。数据对象可以是有限的，也可以是无限的整数数据对象:N={0,1,2,…}英文字符类型的数据对象:{A，B，C，D，E，F，…}

学生数据对象：数据表数据、数据元素和数据对象之间的关系：

数据数据元素数据项241.2基本概念和术语数据结构与数据对象之间的区别和联系？数据对象仅仅是数据元素的集合，不涉及这些元素之间的关系描述数据结构不仅要描述数据对象，而且要描述元素彼此之间的关系261.2基本概念和术语数据结构描述

Data-Structure=(D,S)

D——数据集；S——关系集例：复数的数据结构定义如下：

Complex=(C，R)

其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}271.2基本概念和术语数据结构描述

Data-Structure=(D,S)D——数据集；S——关系集例：学科研究课题小组

Group=(P,R)

其中：P={T,G1,G2,…Gn,S11,S12,…Snm}R={R1,R2}R1={<T,Gi>|i=1,2,3}R2={<Gi,Sij>|i=1,2,3,j=1,2}28301.2基本概念和术语数据的物理（存储）结构物理结构：数据结构中数据元素间的关系在存储器中的存储方法（表现和实现）物理结构中的基本定义：

1）位：二进制中的一位；信息表示的最小单位

2）元素（结点）：由若干位组合起来形成的一个位串，可看成是数据元素在计算机中的映象

3）数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串311.2基本概念和术语按照物理结构的不同分为：1）顺序存储结构：利用在存储器中的物理关系来表示逻辑关系。逻辑上相邻的数据元素存储在物理位置上相毗邻的存储单元里，元素的关系由存储单元的邻接关系来体现2）链式存储结构：数据元素可以在计算机内任意位置上存放（它不要求逻辑上相邻的元素在物理位置上也相邻)，用在存储器中附加指针的方式来表示逻辑关系。将数据元素存放的存储单元分为两个部分，分别存放数据和指针，称为数据域和指针域321.2基本概念和术语数据的逻辑结构和物理结构的关系：逻辑结构只抽象地描述数据元素逻辑关系（简称数据结构）物理结构是一个逻辑结构映像到计算机中所得到的存储表示算法的设计：取决于选定的数据逻辑结构算法的实现：依赖于采用的存储结构331.2基本概念和术语数据类型用以刻画（程序）操作对象的特性。一个值的集合（整型变量）+该集合上定义的一组操作(不体现值间关系)（加、减等操作）类型明显或隐含地规定了：在程序执行期间变量或表达式所有可能的取值范围以及在这些值上允许进行的操作341.2基本概念和术语抽象数据类型：数据结构+定义在此结构上的一组操作（和其在计算机上的表示和实现无关）。不再局限于前述各处理器中已定义并实现的数据类型，还包括用户自定义的数据类型351.2基本概念和术语抽象数据类型1）一个含抽象数据类型的软件模块包含：定义、表示和实现2）三元组表示（D,S,P）

D：数据对象，S：D上的关系集，P：D上的基本操作集361.2基本概念和术语抽象数据类型定义：

ADT抽象数据类型名{

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

数据关系：<数据关系定义>

基本操作：<基本操作定义>}ADT抽象数据类型名其中：1）数据对象和数据关系的定义用伪码表示；371.2基本概念和术语抽象数据类型定义：2）基本操作的定义：基本操作名（参数表）初始条件：（初始条件描述）操作结果：（操作结果描述）基本操作有两种参数：

赋值参数：为操作提供输入值

引用参数：以&打头，除提供输入值外，还将返回操作结果381.2基本概念和术语抽象数据类型定义：2）基本操作的定义：

初始条件：描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息

操作结果：说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之391.2基本概念和术语抽象数据类型三元组的定义:（P9，例1-6）ADTTriplet{

数据对象：D={e1,e2,e3|e1,e2,e3ElemSet}

数据关系：R1={<e1,e2>,<e2,e3>}

基本操作：

InitTriplet(&T)

DestroyTriplet(&T) Get(T,i,&e) Put(&T,i,e) …}ADTTriplet401.3抽象数据类型的表示与实现可以通过固有数据类型表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作利用类C语言（C语言的一个核心子集）作为描述工具类C语言描述：P10-13

typedef

数据类型定义

ElemType

数据元素类型

Status函数结果状态的整数描述与运算&&,或运算||41类C语言描述：P10-13

内存的动态分配与释放指针变量=new数据类型

delete指针变量基本操作的算法：函数描述函数结果主要状态代码：

TURE,OK=1FALSE,ERROR=0OVERFLOW=-21.3抽象数据类型的表示与实现42类C语言描述：P10-13

几组特殊的赋值形式：交换赋值，数组赋值，条件赋值选择语句：条件语句，开关语句循环语句：for,while,do-while

输入和输出语句：三种结束语句return,break,exit

注释：基本函数：max,min,abs,eof,eoln1.3抽象数据类型的表示与实现43例1-7抽象数据类型Triplet的表示和实现（P11-13）基本操作的函数原型：

StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3);//操作结果：构造了三元组T，e1,e2和e3被赋以参数v1,v2,v3的值

StatusDestroyTriplet(Triplet&T)；

//操作结果：三元组T被销毁。

StatusGet(TripletT,inti,ElemType&e);//初始条件：三元组T已存在，1i3//操作结果：用e返回T的第i元的值。1.3抽象数据类型的表示与实现44例1-7抽象数据类型Triplet的表示和实现（P11-13）基本操作的实现：

StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){//构造三元组T，依此置T的三个元素的初值为v1,v2,v3 T=(ElemType*)malloc(3*sizeof(ElemType));if(!T)exit(OVERFLOW);T[0]=v1;T[1]=v2;T[2]=v3;returnOK;}1.3抽象数据类型的表示与实现45例1-7抽象数据类型Triplet的表示和实现（P11-13）基本操作的实现：

StatusDestroyTriplet(Triplet&T){//销毁三元组T free(T);T=null;returnOK;}StatusGet(TripletT,inti,ElemType&e){//1i3,用e返回T的第i元的值。

if(i<1||i>3)returnERROR;e=T[i-1];returnOK;}1.3抽象数据类型的表示与实现46例：复数抽象数据类型示例ADTComplex{ 数据对象：D={c1,c2|c1,c2R(R为实数集）} 数据关系：S={<c1,c2>（c1为实部，c2为虚部）} 基本操作： voidAssign(&A,c1,c2） voidAdd(&A,B) voidMinus(&A,B) voidMultiply(&A,B) voidDivide(&A,B) ...}ADTComplex1.3抽象数据类型的表示与实现471.4算法和算法分析算法：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作算法的五个重要特性：

1）有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成

2）确定性：算法中每一条指令必须有确切的含义，不存在二义性。且算法只有一个入口和一个出口481.4算法和算法分析算法的五个重要特性：

3）可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的

4）输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合

5）输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量491.4算法和算法分析算法设计的要求：

1）正确性：算法应满足具体问题的需求

a）程序不含语法错误；b）程序对于一般输入数据的正确性；c）程序对于苛刻、刁难输入数据的正确性；d）程序对于一切合法输入数据的正确性

2）可读性：算法应该好读。以有利于人对程序的理解

3）健壮性：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果501.4算法和算法分析算法设计的要求：

4）效率与低存储量需求

效率：算法执行时间

存储量需求：算法执行过程中所需要的最大存储空间

一般，这两者与问题的规模有关511.4算法和算法分析算法效率的度量算法执行时间的度量方法：1）事后统计的方法：收集此算法的执行时间和实际占用空间的统计资料缺陷：a）必须先运行依据算法编制的程序；b）依赖于计算机的硬件、软件等环境因素2）事前分析估算的方法：求出该算法的一个时间界限函数算法运行所消耗的时间取决于：a）依据的算法选用何种策略；b）问题的规模；c）书写程序的语言；d）编译程序所产生的机器代码的质量；e）机器执行指令的速度521.4算法和算法分析算法的时间度量1）原操作：基本操作2）算法的时间度量：原操作重复执行的次数3）算法的渐近时间复杂度：原操作重复执行的次数是问题规模n的某个函数f(n)T(n)=O(f(n))4）频度：原操作重复执行的次数531.4算法和算法分析算法的时间度量常见的时间复杂度：

1）O(1)常量阶2）O(n)线性阶

3）O(n2)平方阶4）O(n3)立方阶

5）O(logn)对数阶6）O(2n)指数阶541.4算法和算法分析算法的时间度量六种常用计算算法时间的多项式的关系为：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间的关系为：

O(2n)<O(n!)<O(nn)

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，若能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就551.4算法和算法分析算法的时间度量例1.{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)如果将s=0也看成是基本操作，则语句频度为1，其时间复杂度仍为Ｏ(1)，即常量阶例2.for(i=1;i<=n;++i){++x;s+=x;}

语句频度为：n

其时间复杂度为：O(n)

即时间复杂度为线性阶561.4算法和算法分析算法的时间度量例3.for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}

语句频度为：n2

其时间复杂度为：O(n2)

即时间复杂度为平方阶。571.4算法和算法分析算法的时间度量例4.两个N*N矩阵相乘的算法for(i=1;i<=n;++i) for(j=1;j<=n;++j) { c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j]; /*原操作*/ }问题规模：n原操作：c[i][j]+=a[i][k]*b[k][j];基本操作重复执行的次数：f(n)=n3该算法时间度量记作T(n)=O(f(n))=O(n3)时间复杂度：O(n3)581.4算法和算法分析算法的时间度量在难以精确计算基本操作执行次数的情况下，只需求出它关于n的增长率或阶即可。例

for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i][j]=x;}591.4算法和算法分析算法的时间度量当基本操作执行次数随问题的输入数据集变化时，计算平均时间复杂度或最坏情况下的上界。例有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集的不同而不同（冒泡排序法）voidBubble_Sort(inta[],intn){for(i=n-1,change=TRUE;i>=1&&change;--i) {change=FALSE; for(j=0;j<i;j++)

if(a[j]>a[j+1]) {a[j]>a[j+1];change=TRUE;}