《数据结构动画版.ppt》由会员分享，可在线阅读，更多相关《数据结构动画版.ppt（61页珍藏版）》请在三一办公上搜索。
1、,下一章,第一章 绪言,1946年，第一台电子计算机ENIACShown here are two women“programming”ENIAC.U.S.Army Photo.,什么是数据结构,系统功能分析,系统输入/输出数据、功能需求,设计合适的数据对象的表示结构,解决特定问题的具体步骤的描述,程序设计一般流程,程序设计：为计算机处理问题编制的一组指令集数据结构：问题的数学模型算 法：处理问题的策略,什么是数据结构,信息结构层次,求解策略层次,语言层次,从问题求解角度上，数据结构和高级程序设计语言（C语言）立足于不同的层面上针对问题时，C语言一般要想该用何种控制结构（分支还是循环）等细节问
2、题；而数据结构主要考虑的问题的描述、信息的结构等宏观问题针对于问题的求解，算法立足于更高的层次:与数据结构相比，它更多地考虑整个问题该用何种策略（思想）求解，而不是其中涉及信息的组织与结构问题的一般求解过程为：分析求解策略设计其中涉及信息的结构用语言加以具体实现,什么是数据结构,系统功能分析,程序设计一般流程,非数值计算问题,?,数值问题例 已知：游泳池的长len和宽wide，求面积area 建模型：问题涉及的对象：游泳池的长len 宽wide，面积area；对象之间的关系：area=lenwide设计 求解问题的方法 编程main()int len,wide,area;scanf(“%d%d
3、%n”,什么是数据结构,书目文件,例1 书目自动检索系统,电话号码查询系统学生成绩管理系统职工信息系统等文档管理的数学模型,例2 人机对奕问题,例2 人机对奕问题,例3 多叉路口交通灯管理问题,所有可能通行方向AB AC ADBA BC BDDA DB DCEA EB EC ED用AB表示AB，余类推,交叉路口的模型,算法设计：穷举法：逐一检查所有可能组合，记录最小分组数和对应分组贪心法：一类典型算法，其宗旨是根据当时掌握的信息，尽可能地向得到解的方向推进,例3 多叉路口交通灯管理问题,例3 多叉路口交通灯管理问题,例3 多叉路口交通灯管理问题,例3 多叉路口交通灯管理问题,例3 多叉路口交通
4、灯管理问题,是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科,数据结构定义：,数据结构学科的地位 综合性的专业基础课 介于数学、计算机硬件和计算机软件之间的核心课程 不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础 本课程的先修课程：离散数学、C语言(或其他程序设计语言)本课程后续课程：面向对象程序设计、操作系统、编译原理、数据库系统、人工智能等,数据（data)所有能输入到计算机中去的描述客观事物的符号,数据元素（data element）数据的基本单位，也称结点（node）或记录（recor
5、d）数据项（data item）有独立含义的数据最小单位，也称域(field),数据对象（data object)性质相同数据元素的集合,整数数据对象 N=0,1,2,基本概念和术语,数据结构（data structure)数据元素和数据元素关系的集合 Data_Structure=D,R,数据的逻辑结构只抽象反映数据元素的逻辑关系,从逻辑关系上描述数据，与数据的存储无关从具体问题抽象出来的数据模型；与数据元素本身的形式、内容无关；与数据元素的相对位置无关。,基本概念和术语,数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,索引存储结构散列存储结构,基本概念和术语,元素n,.,元素i
6、,.,元素2,元素1,Lo,Lo+m,Lo+(i-1)*m,Lo+（n-1)*m,存储地址,存储内容,Loc(元素i)=Lo+（i-1)*m,顺序存储结构,基本概念和术语,1536,元素2,1400,元素1,1346,元素3,元素4,1345,链式存储结构,h,基本概念和术语,基本概念和术语,数据类型一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称,例 C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体等构造数据类型，还有指针、空(void)类型等。用户也可用typedef 自己定义数据类型,typedef struct long num
7、;char name30;char author20;char publisher30;float price;BOOKCARD;BOOKCARD book1,book2,*p;,一些最基本数据结构可以用数据类型来实现，如数组、字符串等另一些常用的数据结构，如栈、线性表、树、图等，不能直接用数据类型来表示,基本概念和术语,数据结构和数据类型的关系“数据结构”是数据类型的抽象；“数据类型”是数据结构在计算机内部的具体表现,Abstract Data Type,ADT,定义：ADT是指一个数学模型和定义在该模型上的一组操作的总称由用户定义,从问题抽象出来的数据模型数据逻辑结构还包括定义在数据模型上
8、的一组抽象运算相关操作不考虑其在计算机内具体存储结构与运算的具体实现算法优点：信息隐蔽和数据封装，使用与实现相分离,使用者只要知道这些操作的用途就可以编程序了；至于这些操作是怎样实现的，以及它在内存中是如何表示的，并不影响使用者所编程序的编码形式。,ADT两个重要特征：数据抽象：用ADT描述程序处理的实体时，强调其本质特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节,抽象数据类型,ADT形式化定义,ADT=（D，S，P）D=数据对象S=D上的关系集P=对D的基本操作集,ADT 抽象数据类型名数据对
9、象：数据关系：基本操作：ADT 抽象数据类型名,基本操作定义格式：基本操作名(参数表)初始条件：操作结果：,赋值参数：只为操作提供输入值引用参数：以&开头，除提供输入值外，还将返回操作结果初始条件：描述了操作执行前数据结构和参数应满足的条件，若不满足，操作失败，并返回相应出错信息。若初始条件为空，则省略之。操作结果：说明操作正常完成之后，数据结构的变化情况和应返回的结果。,抽象数据类型复数的定义,ADT Complex 数据对象：D=e1,e2|e1,e2均为实数 数据关系：R=|e1是复数的实部,e2 是复数的虚部 基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数Z
10、,其实部和虚部分别赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&real)初始条件：复数已存在。操作结果：用real返回复数Z的实部值。GetImag(Z,&imag)初始条件：复数已存在。操作结果：用imag返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1，z2是复数。操作结果：用sum返回两个复数z1,z2的和值 ADT Complex,ADT定义示例,ADT Circle 数据对象：D=r,x,y|r,x,y 均为实数 数据关系：R=|r是半径,是圆心坐标 基本操作：Circle(&C,r,x,y)操作结果：构造
11、一个圆。double Area(C)初始条件：圆已存在。操作结果：计算面积。double Circumsance(C)初始条件：圆已存在。操作结果：计算周长。ADT Circle,抽象数据类型Circle的定义,ADT定义示例,ADT实现,ADT是程序操作/算法实现的依据ADT定义遵循原则：完整性:要能反映所定义的抽象数据类型的全部特性统一性:应是一个前后协调的整体，不应自相矛盾通用性:所定义的抽象数据类型应适用于尽量广泛的对象独立性:应尽可能不依赖于程序语言,ADT形式化定义,抽象数据类型分类分类标准：按照值的不同特性原子类型：变量的值不可分解固定聚合类型：变量的值成分的数目确定可变聚合类型
12、：变量的值成分的数目不确定多形数据类型：变量的值成分不确定（成分类型可变）,需要通过高级编程语言中已实现的数据类型来实现,ADT实现,ADT实现的含义：就是将ADT转换成程序设计语言的说明语句，加上对应于该ADT中的每个操作的函数。,即用适当的数据结构来表示ADT中的数学模型,并用一组函数来实现该模型上的各种操作。,抽象数据类型Complex的实现,/存储结构的定义typedef struct float real;float imag;Complex;,/基本操作的函数原型说明void AssignComplex(Complex,/基本操作的实现void AssignComplex(Comp
13、lex,ADT实现举例,ADT定义与实现的关系,预定义常量和类型：#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE-1#define OVERFLOW-2typedef int Status;,ADT实现中几个问题,引用运算符：&引用是个别名建立引用时,程序用另一个已定义的变量的名字初始化它,从那时起,引用作为目标的别名而使用,对引用的改动实际就是对目标的改动。,例如：int a=4;/*a为普通的整型变量*/int/*b是a的引用变量*/b变量是变量a的引用,b也等于4,这两个变量同步改变,注
14、意：C语言不支持引用类型,ADT实现中几个问题,关于引用：,引用常用于函数形参中,采用引用型形参时,实现数据双向传递,例如：,ADT实现中几个问题,关于引用：,void swap(int x,int y)int temp;temp=x;x=y;y=temp;,当用执行语句swap(a,b)时：a 和b的值没有发生交换,值传递,引用常用于函数形参中,采用引用型形参时,实现数据双向传递,例如：,ADT实现中几个问题,关于引用：,void swap(int*x,int*y)int temp;temp=*x;*x=*y;*y=temp;,当用执行语句swap(&a,&b)时：a 和b的值发生了交换,地
15、址传递,引用常用于函数形参中,采用引用型形参时,实现数据双向传递,例如：,ADT实现中几个问题,关于引用：,void swap(int y=temp；,当用执行语句swap(a,b)时：a 和b的值发生了交换,引用传递,引用方式简洁教材中很多算法都采用引用形式的形参,书上算法采用类C语言书写类C语言与C程序之间的差别：(1)算法中除形式参数外,变量不作定义，在C程序中必须定义；(2)算法中使用的元素类型(ElemType)没有定义，C程序中必须定义；常量OK、ERROR、OVERFLOW等在第一章统一定义；(3)算法中的比较运算符(equal、less)未作定义，C程序中必须定义；(4)必要的
16、头文件(用作输入输出的stdio.h及内存申请的stdlib.h)，在C程序中必须包含。,ADT实现中几个问题,算法（Algorithm）,Pronunciation:al-go-rith-umDerives from the name of the Persian(Baghdad)mathematician:Abu Jafar Muhammad ibn Musa al-Khwarizmi,arithmetic,算法描述与算法分析简介,Definitions of Algorithm:A computable set of steps to achieve a desired resultA
17、clearly specified set of simple instructions to be followed to solve a problemA finite set of instructions that,if followed,accomplishes a particular taskA finite set of rules which gives a sequence of operation for solving a specific type of problem.A step-by-step problem-solving procedure,算法（Algor
18、ithm）解决某一特定问题的具体步骤的描述，是指令的有限序列,算法定义,有穷性(Finiteness)算法必须在执行有限步骤后结束(The algorithm terminates after finite number of steps)确定性(Definiteness)算法每一步骤必须是确切定义的，不能产生二义性(Each instruction is clear and unambiguous)可行性(Effectiveness)算法是能行的(Every instruction must be basic enough to be carried out.It also must be
19、feasible)输入(Input)算法有零个或多个输入(There are zero or more quantities that are externally supplied)输出(Output)算法有一个或多个输出(At least one quantity is produced),算法特性,void exam1()int n=2;while(n%2=0)n=n+2;printf(“%dn”,n);,void exam2()int y=0;int x=3/y;printf(“%d,%dn”,x,y);,违反了有穷性,违反了可行性,这两段描述均不能满足算法的特征,试问它们违反了哪些特
20、征？,算法特性,In natural languages,like English or ChineseFlow chartsPseudo-codeProgramming languages,like C or Java,Recipe:CHOCOLATE CAKE4 oz.chocolate 3 eggs 1 cup butter 1 tsp.vanilla cups sugar 1 cup flourMelt chocolate and butter.Stir sugar into melted chocolate.Stir eggs and vanillaMix in flourSprea
21、d mix in greased panBaked at 350 for 40 minutes or until inserted fork comes out almost cleanCool in pan before eating,Program CodeDeclare variablesChocolate eggs mix butter vanilla sugar flourmix=melted(4*chocolate)+butter)mix=stir(mix+(2*sugar)mix=stir(mix+(3*eggs)+vanilla)mix=mix+flourspread(mix)
22、while(not clean(fork)bake(mix,350),算法描述,Descriptions,衡量算法优劣的标准正确性(Correctness)可读性(Readability)健壮性(Robustness)效率(Efficiency),灵活性（Flexibility）可重用性(Reuseable)自适应性(Adaptability)等,健壮性:1、指当输入数据 非法时，算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。2、处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理,可读性：1、算法主要是为了人的阅读和交流
23、，其次才是为计算机执行，因此算法应该易于人的理解；2、另一方面，晦涩难读的算法易于隐藏较多错误而难以调试。,正确性：有四个层次1、程序中不含语法错误；2、程序对于几组输入数据能够得出满足要求的结果；3、程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；4、程序对于一切合法的输入数据都能得出满足要求的结果。通常以第三层意义上的正确性作为衡量一个算法是否合格的标准,算法评价,Evaluation,例1：在有序表中查找给定值,例2：百钱买百鸡问题,自顶向下，逐步求精,算法设计重要性,举例：数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标；若查找失败，返回-
24、1,方法一：顺序查找,int Search(int a,int n,int k)int i=0;while()i+;if(i=n)return(-1);else return(i);,找64,最多比较 次,查找成功,n,ai!=k,&in,方法二：折半查找,找37,举例：数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标；若查找失败，返回-1,查找成功,方法二：折半查找,找90,举例：数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标；若查找失败，返回-1,查找失败,7,最多比较log2n 1 次,int BiSearch(int a,int n,int k)int l
25、ow,high,mid,found;low=0;high=n-1;found=0;while()if(kamid)else if(k=amid)else if(found=1)return(mid);else return(-1);,(low=high)&(found=0),mid=(low+high)/2;,low=mid+1;,found=1;,high=mid-1;,方法二：折半查找,举例：数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标；若查找失败，返回-1,举例：数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标；若查找失败，返回-1,百钱买百鸡问题,100
26、元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？,方法1用三重循环：for(i=0;i=100;i+)for(j=0;j=100;j+)for(k=0;k=100;k+)if(k%3=0,求解：设母鸡、公鸡、小鸡各为i,j,k只。则有：i+j+k=1005i+3j+k/3=100只需要解出本方程就可以得到答案。,循环次数=101*101*101即约一百万次,方法2用二重循环：k=100-i-jfor(i=0;i=100;i+)for(j=0;j=100;j+)k=100 i j;if(k%3=0,循环次数=101*101即约一万次,百钱
27、买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？,求解：设母鸡、公鸡、小鸡各为i,j,k只。则有：i+j+k=1005i+3j+k/3=100只需要解出本方程就可以得到答案。,方法3用二重循环：钱100元，母鸡5元1只，所以i=20，同样，j=33for(i=0;i=20;i+)for(j=0;j=33;j+)k=100 i j;if(k%3=0,循环次数=21*34=714,百钱买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？,求解：设母鸡、
28、公鸡、小鸡各为i,j,k只。则有：i+j+k=1005i+3j+k/3=100只需要解出本方程就可以得到答案。,方法4用一重循环：合并方程得到:14*i+8*j=200 简化为:7*i+4*j=100 所以有：i=14 又：j=25-7*i/4，故i必为4的倍数for(i=0;i=14;i+4)j=(100 7*i)/4;k=100 i j;if(k%3=0,循环次数=4,百钱买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？,求解：设母鸡、公鸡、小鸡各为i,j,k只。则有：i+j+k=1005i+3j+k/3=100只
29、需要解出本方程就可以得到答案。,1.事后统计利用计算机内记时功能，用一组或多组相同的统计数据区分 缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环 境因素，掩盖算法本身的优劣,2.事前分析估计程序在计算机上运行所消耗 的时间取决于：算法策略 问题规模 程序语言 编译质量 计算机速度,算法时间效率度量方法,（渐近）时间复杂度：算法耗用时间相对问题规 模的增长率 定义：设n是问题规模,T(n)和f(n)是n的函数，当且仅当存在正整数c和n0,使得对所有n n0，满足T(n)cf(n),则T(n)称作大O表示法：T(n)=O(f(n),加法规则(顺序连接)与乘法规则(嵌套连接)
30、,1、O(f(n)+O(g(n)=O(max(f(n),g(n)2、O(cf(n)=O(f(n),c是正整数3、O(f(n)*O(g(n)=O(f(n)*g(n),Asymptotic time complexity,算法时间效率度量方法,T1(n)=O(1),T2(n)=O(n),T3(n)=O(n2),T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2)=O(n2),频度最大语句重复执行次数的阶数,算法时间效率度量方法,例：两个N阶矩阵相乘for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=n;k+)cij=cij+aik*bkj
31、;,算法时间效率度量方法,（渐近）时间复杂度：基本操作重复执行的次数的阶数（算法耗用时间的增长率）大O表示法：T(n)=O(f(n),（渐近）空间复杂度：S(n)=O(f(n),加法规则与乘法规则,最坏情况最好情况平均情况,常用时间复杂度：O(1)-常量型O(n)、O(n2)、O(n3)-多项式型O(log2n)、O(nlog2n)-对数型O(2n)、O(en)-指数型,Asymptotic space complexity,辅助存储空间增长率,算法存储量包括：输入数据所占空间程序本身所占空间辅助变量所占空间,举例：数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标；若查找失败，返
32、回-1,方法一：顺序查找,int Search(int a,int n,int k)int i=0;while()i+;if(i=n)return(-1);else return(i);,找64,最多比较 次,n,ai!=k,&in,T(n)=O(n),最好情况：T(n)=O(1)最坏情况：T(n)=O(n)平均情况：T(n)=O(n),7,最多比较log2n 1 次,int Search(int a,int n,int k)int low,high,mid,found;low=0;high=n-1;found=0;while()if(kamid)else if(k=amid)else if(
33、found=1)return(mid);else return(-1);,(low=high)&(found=0),mid=(low+high)/2;,low=mid+1;,found=1;,high=mid-1;,方法二：折半查找,举例：数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标；若查找失败，返回-1,T(n)=O(log2n),小结在用计算机解题的过程中，算法和数据结构是相辅相成两个方面：数据结构：是算法处理的对象，也是设计算法的基础。一个具体问题的数据往往可采用多种不同的数据结构表示；一个计算过程的实现常有多种可用算法。因此算法和数据结构的选择就成为实现程序的过程中最重要的一个问题。抽象数据类型技术提高了程序设计的抽象层次，也为数据结构和算法的研究提供了一种分层模型。重点掌握数据结构和算法的基本知识，理解它们在问题求解过程中的地位和作用。需要掌握和理解的概念：数据的逻辑结构、存储结构和操作，抽象数据类型，算法分析，空间代价和时间代价等。,
