数据结构课件第1章

上课前需要说明的几个问题：任课教师：王岁花联系电话：136639012732.交流信箱：dsjiaoxue@126.com3.公共信箱：

公共信箱：dsggxx@126.com

密码：dsggxx20084.关于数据结构课程：教材、重要性、时间按排（54+36）考试成绩=期末考试*70%+平时成绩*30%5.平时成绩主要是实验作业完成情况，实验每次点名，随机抽查验收，查看程序运行。1.1什么是数据结构1.2基本概念和术语1.4算法和算法分析1.3抽象数据类型本章小结、教材、参考文献作业1.1什么是数据结构1)数据结构讨论的范畴NiklausWirth程序=数据结构+算法

用计算机解决一个具体问题时，大致需要经过下列几个步骤:（1）抽象出一个适当的数学模型（2）设计一个解此数学模型的算法（3）编出程序进行测试、修改直至得到最终结果。

例1.田径赛的时间安排问题设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示），设计比赛日程表，使得用尽可能少的时间段完成比赛。姓名项目1项目2项目3丁一马二张三李四王五跳高标枪标枪铅球跳远跳远100米铅球100米200米200米跳高200米用无向图的着色问题解决！！（1）设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米

A B CDE F（2）用顶点代表比赛项目（3）用边连接不能同时进行比赛的项目如下图所示：姓名项目1项目2项目3丁一马二张三李四王五ACCDBBEDEFFAF韦尔奇.鲍威尔（WelchPowell)方法：

1.将图G中的结点按度递减的顺序排列。

2.用没有用过的颜色对第一个点着色，并且按排列次序，对与前面着色点不相邻的点着相同颜色。

3.从序列中删除第2步着过色的点。

4.重复第2、3步，直到序列为空。

例:对上例，执行算法第1步结果为：

{F,A,E,B,C,D}

重复执行第2,3步序列变化为：{A,E,B,C,D}{E,B,D}{B}{}

图的变化为：

数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作等的学科。2)数据结构对研究对象及其之间关系的描述。结构数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D：是数据元素的有限集

S：是D上关系的有限集。（逻辑结构）1.2基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能被输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项(DataItem）:一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素间关系的不同，数据结构或分为四种：线性结构：结构中的数据元素之间存在一对一的关系。树型结构（层次结构）：结构中的数据元素之间存在一对多的关系。图状结构（网状结构）：结构中的数据元素之间存在多对多的关系。集合：结构中的数据元素除了同属于一个集合外，别无其它关系。Data_Structures=(D,S)（逻辑结构）数据的存储结构

——

逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)21.顺序映象：借助于元素在计算机存储器中的存储位置来描述元素之间的逻辑关系。例：关系的映象方法（表示<x,y,z>的方法）

xyz2.链式映象借助于指示元素存储地址的指针表示元素之间的逻辑关系。xyz……^在不同的编程环境中，存储结构可有不同的描述方法。

当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。数据类型：数据类型是一个值的集合和定义在这组值

集上的一组操作的总称。例如：C-语言中的int,float,char等抽象数据类型(AbstractDataType简称ADT)：是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型的描述方法:

抽象数据类型可用（D，S，P）三元组表示,其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

本门课采用下面格式表示抽象数据类型：ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名

其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将带回操作结果。引用变量和引用参数“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。

“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。例如：抽象数据类型三元组的定义：P9#include"stdio.h"voidmain(){intx=3,y=4,&z=x;printf("x=%d,y=%d,z=%d\n",x,y,z);z=x+y;printf("x=%d,y=%d,z=%d\n",x,y,z);}运行结果:x=3,y=4,z=3x=7,y=4,z=7voidsum1(inta,intb,intc){c=a+b;return;}voidsum2(inta,intb,int&c){c=a+b;return;}voidmain(){intx=3,y=4,z=5;printf("x=%d,y=%d,z=%d\n",x,y,z);sum1(x,y,z);printf("x=%d,y=%d,z=%d\n",x,y,z);sum2(x,y,z);printf("x=%d,y=%d,z=%d\n",x,y,z);}运行结果x=3,y=4,z=5x=3,y=4,z=5x=3,y=4,z=7//------采用动态分配的顺序存储结构-----typedefElemType*Triplet;//由InitTriplet分配三个元素存储空间//Triplet类型是ElemType类型的指针//存放ElemType类型的地址例如：抽象数据类型三元组的定义：P9//bo1_1.cpp抽象数据类型Triplet和ElemType//(由c1_1.h定义)的基本操作(8个)StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){//操作结果:构造三元组T,依次置T的三个元素的初

//值为v1,v2和v3if(!(T=(ElemType*)malloc(3*sizeof(ElemType))))exit(OVERFLOW);T[0]=v1,T[1]=v2,T[2]=v3;returnOK;}StatusGet(TripletT,inti,ElemType&e){//初始条件：三元组T已存在，1≤i≤3。

//操作结果：用e返回T的第i元的值

if(i<1||i>3)returnERROR;e=T[i-1];returnOK;}StatusPut(TripletT,inti,ElemTypee){//初始条件：三元组T已存在，1≤i≤3。

//操作结果：改变T的第i元的值为eif(i<1||i>3)returnERROR;T[i-1]=e;returnOK;}StatusIsAscending(TripletT){//初始条件：三元组T已存在。操作结果：如果

//T的三个元素按升序排列，返回1，否则返回0return(T[0]<=T[1]&&T[1]<=T[2]);}StatusIsDescending(TripletT){//初始条件:三元组T已存在。

//操作结果:如果T的三个元素按降序排列,返回1,否则返回0return(T[0]>=T[1]&&T[1]>=T[2]);}StatusMax(TripletT,ElemType&e){//初始条件：三元组T已存在。

//操作结果：用e返回T的三个元素中的最大值

e=(T[0]>=T[1])?((T[0]>=T[2])?T[0]:T[2]):

((T[1]>=T[2])?T[1]:T[2]);returnOK;}StatusMin(TripletT,ElemType&e){//初始条件：三元组T已存在。

//操作结果：用e返回T的三个元素中的最小值

e=(T[0]<=T[1])?((T[0]<=T[2])?T[0]:T[2]):((T[1]<=T[2])?T[1]:T[2]);returnOK;}1.3抽象数据类型的表示与实现本书采用类C-语言作为描述工具，类C-精选了C语言的一个核心子集，同时做了若干扩充修改，增强了语言的描述功能。P10-111.4算法和算法分析1）什么是算法？算法（Algorithm)是对特定问题求解步骤的描述。描述算法的方法有：自然语言、流程图、N-S图和伪码语言等。本书采用类C语言来描述算法。伪码语言是包括高级语言的三种基本结构、自然语言和数学语言成份的面向读者的一种语言。2）一个算法必须满足的五个准则：（1）有穷性一个算法必须在执行有穷步骤之后正常结束，而不能形成无穷循环，且必须在有穷时间内完成。（2）确定性（无二义）:

算法的每一步操作都必须有确切含义，不得有任何二义性。（3）可行性:

算法中的每一条指令必须是切实可执行的，即原则上可以通过已经实现的基本运算执行有限次来实现。（4）输入：一个算法有n（n>=0)个初始数据的输入。（5）输出：一个算法有一个或多个与输入有某种关系的有效信息的输出。3）算法设计的要求正确性、可读性、健壮性和效率与存储量要求。

程序正确性的五个层面：（1）不含语法错误（2）程序对于n组输入数据能够得出满足规格说明要求的结果。（3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果。（4）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。（5）用数学方法证明程序的正确性

嫦娥一号：98.8万行源代码，421万份文件，打印出来有23000页。用了160多万行程序证明它的正确性。可读性、健壮性和效率与存储量要求。

4）高效率与低存储量需求

通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。算法效率的衡量方法和准则衡量算法效率的方法:缺点：1．必须执行程序

2．其它因素掩盖算法本质事后统计法：事前分析估算法和算法执行时间有关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度

一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数f(n)。算法=控制结构+原操作//基本操作（固有数据类型的操作）算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间

算法的执行时间

与原操作执行次数之和

成正比

从算法中选取一种对于所研究的问题来说是

基本操作

的原操作，以该基本操作

在算法中重复执行的次数

作为算法运行时间的衡量准则。表示随着问题规模的增大，算法执行时间增长增长率和f(n)相同，称作算法的渐近时间复杂度，简称为时间复杂度。一般情况下，算法中基本操作执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：T(n)=O(f(n))(M是>0的常数)

也可以用：如何估算算法的时间复杂度？例：2n3+1000n2+1=O(n3)1000n2+n+1000000=O(n2)例一两个矩阵相乘voidmult(inta[],intb[],intc[]){//以二维数组存储矩阵元素，c为a和b的乘积

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];}//for}//mult基本操作:乘法操作时间复杂度:O(n3)例二冒泡排序基本操作:

交换两个相邻元素的操作时间复杂度:O(n2)voidbubble_sort(inta[],intn){//将a中整数序列重新排列成自小至大有序的整数序列。for(i=n-1,change=TRUE;i>=1&&change;--i)}//bubble_sort{change=FALSE;

//change为元素进行交换标志

for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TRUE;}}//一趟冒泡交换次数：最好情况：0最坏情况：n(n-1)/2最坏情况下的时间复杂度平均时间复杂度若不特别说明，以后我们所说的都是最坏情况下的时间复杂度常见函数的时间复杂度按数量递增排列及增长率。常数阶O(1)对数阶O(log2n)线性阶O(n)线性对数阶O(nlog2n)平方阶O(n2)立方阶O(n3)……多项式阶O(nk)指数阶O(2n）1.10按增长率由小到大的排列顺序是：(2/3)n,2100,log2(log2n),log2n,(log2n)2,,n2/3,n/log2n,n,nlog2n,n3/2,(4/3)n,(3/2)n,nlog2n,n!,nn解题依据为：

4)算法的存储空间需求算法的空间复杂度定义为:

表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。S(n)=O(g(n))算法的存储量包括:输入数据所占空间程序本身所占空间辅助变量所占空间

若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

若需存储量依赖于特定的输入，则通常按最坏情况考虑。

若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。例如在进行冒泡排序时所需的额外的空间就是一个常数,空间复杂度为O(1)。本章小结1.基本概念和术语数据、数据元素、数据项、数据结构、数据对象、数据结构（逻辑结构、存储结构、运算）、多形数据类型、抽象数据类型（定义、表示和实现）2.抽象数据类型：描述、类-C中的基本语句和函数3.算法：算法的时间复杂度（渐近时间复杂度、最坏情况下的时间复杂度和平均时间复杂度），算法的空间复杂度（原地工作、额外空间）。对O的理解4.编程常用头文件：

#include<string.h>#include<ctype.h>#include<malloc.h>//malloc(),alloc(),realloc()等

#include<limits.h>//INT_MAX等

#include<stdio.h>//EOF(=^Z或F6),NULL#include<stdlib.h>//srand(),rand(),exit(n)#include<io.h>//eof()#include<math.h>//floor(),ceil(),abs()#include<process.h>//exit(n)#include<iostream.h>//cout,cin5.函数结果状态代码

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;//Status是函数的类型,//其值是函数结果状态代码，如OK等

typedefintBoolean;//Boolean是布尔类型,其//值是TRUE或FALSE6.上机环境及注意事项

上机环境VC++6.0,