《数据结构与算法》配套PPT电子课件
数据结构与算法配套PPT电子课件,数据结构与算法,数据结构,算法,配套,PPT,电子,课件
第三章第三章栈和队列栈和队列本章介绍在程序设计中常用的两本章介绍在程序设计中常用的两种数据结构种数据结构栈和队列栈和队列它们的逻辑结构和线性表相同,其特点在于运算它们的逻辑结构和线性表相同,其特点在于运算受到了限制:栈按受到了限制:栈按“后进先出后进先出”的规则进行操作,的规则进行操作,队列按队列按“先进先出先进先出”的规则进行操作,故称运算的规则进行操作,故称运算受限制的线性表。受限制的线性表。第三章第三章 栈和队列栈和队列 3.1 3.1 栈栈 3.2 3.2 栈的应用举例栈的应用举例 3.33.3栈与递归栈与递归 3.4 3.4 队列队列 3.1 栈3.1.1 栈的概念3.1.2 栈的顺序存储和实现3.1.3 栈的链式存储和实现3.13.1栈栈栈是限定仅能在表尾一端进行插入、删除操作的线性表(a1,a2,.,ai-1,ai,ai+1,an)插入删除3.1.1栈的概念一什么是栈3.13.1栈栈栈的示意图出栈进栈栈的特点栈的特点后进先出后进先出第一个进栈的元素在栈底,最后一个进栈的元素在栈顶,第一个出栈的元素为栈顶元素,最后一个出栈的元素为栈底元素栈顶栈底ana2a13.13.1栈栈二二栈的基本操作栈的基本操作栈初始化:栈初始化:Init_Stack(s)初始条件:栈初始条件:栈s不存在不存在操作结果:构造了一个空栈。操作结果:构造了一个空栈。判栈空:判栈空:Empty_Stack(s)初始条件:栈初始条件:栈s已存在已存在操作结果:若操作结果:若s为空栈返回为为空栈返回为1,否则返回为,否则返回为0。入栈:入栈:Push_Stack(s,x)初始条件:栈初始条件:栈s已存在已存在操操作作结结果果:在在栈栈s的的顶顶部部插插入入一一个个新新元元素素x成成为为新新的的栈栈顶顶元素。栈发生变化。元素。栈发生变化。出栈:出栈:Pop_Stack(s)初始条件:栈初始条件:栈s存在且非空存在且非空操操作作结结果果:栈栈s的的顶顶部部元元素素从从栈栈中中删删除除,栈栈中中少少了了一一个个元元素。栈发生变化。素。栈发生变化。读栈顶元素:读栈顶元素:Top_Stack(s)初始条件:栈初始条件:栈s存在且非空存在且非空操作结果:栈顶元素作为结果返回,栈不变化。操作结果:栈顶元素作为结果返回,栈不变化。3.13.1栈栈栈栈topbasebasetopbasetopbasetopAABCDEAB 栈操作图示空栈 A进栈 B C D E 进栈E D C 出栈 3.13.1栈栈3.1.2栈的顺序存储和实现栈的顺序存储和实现一、栈的顺序存储结构如何存储栈?进栈、出栈等操作如何实现?1栈的顺序存储结构栈的顺序存储结构#define MAX 50#define MAX 50TypedefTypedef structstruct intint stackMAX;stackMAX;intint top;top;SeqstackSeqstack;SeqstackSeqstack*s;*s;3.13.1栈栈约定约定栈顶指针指向栈顶元素的下一个位置当栈用顺序结构存储时,栈的基本操作如建空栈、进栈、出栈等操作如何实现?顺序栈的图示toptopMAX-1nn-1n-210a an na an-1n-1a a2 2a a1 13.13.1栈栈1)进栈操作进栈操作viodPush(intx)if(s-top=MAX)printf(“overflow”);elses-stacks-top=x;s-top+;MAX-1nn-1n-210a an na an-1n-1a a2 2a a1 1x进栈前topx进栈后MAX-1nn-1n-210 x xa an na an-1n-1a a2 2a a1 1top3.13.1栈栈2)出栈操作)出栈操作intpop()if(s-top=0)printf(“underflow”);return(NULL);s-top-;return(s-stacks-top);出栈操作前出栈操作后MAX-1nn-1n-210a an na an-1n-1a a2 2a a1 1MAX-1nn-1n-210a an na an-1n-1a a2 2a a1 1toptop共享栈共享栈n n#define MAX 100#define MAX 100n nIntInt stackMAX,top1=0,top2=MAX-1;stackMAX,top1=0,top2=MAX-1;top1top2栈1栈2栈1进栈 top1+1栈2进栈 top2-1top1top2top1top2时出现时出现“上溢上溢”3.13.1栈栈2栈的链式存储和实现栈的链式存储和实现栈的链式存储结构,也称链栈,如图所示:栈的链式存储结构,也称链栈,如图所示:在前面学习了线性链表的在前面学习了线性链表的插入删除操作算法,插入删除操作算法,不难写出链式栈初始化、不难写出链式栈初始化、进栈、出栈等操作的算法进栈、出栈等操作的算法Data nexttoptop栈顶栈底an-1a1an3.13.1栈栈(1)(1)进栈算法NODE*top;NODE*top;Void Void push(intpush(int x)x)NODE*p=(NODE NODE*p=(NODE*)*)malloc(sizeof(NODEmalloc(sizeof(NODE););p-data=x;p-data=x;p-next=top;p-next=top;top=p;top=p;3.13.1栈栈(2)(2)出栈算法出栈算法NODE*pop();NODE*pop();NODE*p;NODE*p;if(top=NULL)return(NULL);if(top=NULL)return(NULL);p=top;p=top;top=p-next;top=p-next;return(p);return(p);小小 结结 1栈是限定仅能在表尾一端进行插入、栈是限定仅能在表尾一端进行插入、删除操作的线性表;删除操作的线性表;2栈的元素具有后进先出的特点;栈的元素具有后进先出的特点;3栈顶元素的位置由一个称为栈顶指针的栈顶元素的位置由一个称为栈顶指针的变量指示,变量指示,进栈、出栈操作要修改栈顶指针;进栈、出栈操作要修改栈顶指针;3.13.1栈栈3.23.2栈的应用举例栈的应用举例栈的应用举例栈的应用举例例例1数制转换数制转换对于输入的任意一个非负十进制数,显示输出与其等值的八进制数对于输入的任意一个非负十进制数,显示输出与其等值的八进制数数制转换方法数制转换方法N=(Ndiv8)10 8+Nmod8N:十进制数,十进制数,div:整除运算,整除运算,mod:求余运算;求余运算;(1348)10=2 83+5 82+0 8+4=(2504)8N1348168212Ndiv81682120Nmod84052计算时从低位到高位计算时从低位到高位顺序产生八进制数的顺序产生八进制数的各个数位各个数位结果:结果:2 5 0 42 5 0 4显示时按从高位到低位的显示时按从高位到低位的顺序输出顺序输出3.23.2栈的应用举例栈的应用举例voidconversion()InitStack(s);/建空栈建空栈scanf(“%d”,&x);/输入一个非负十进制整数输入一个非负十进制整数while(x!=0)/x不等于零循环不等于零循环push(s,x%8);/x/8第一个余数进栈第一个余数进栈x=x/8;/整除运算整除运算while(!StackEmpty(s)/输出存放在栈中的八制输出存放在栈中的八制数位数位x=pop(s);printf(“%d”,x);算法3.73.23.2栈的应用举例栈的应用举例栈的应用举例栈的应用举例例例2表达式求值表达式求值1)问题的提出设计一个小计算器:对键入的表达式进行求值。如何对表达式求值呢?高级语言中的赋值语句:变量=表达式;Y=2;Y=2;Z=3;Z=3;X=y+z*2;X=y+z*2;2)表达式的构成表达式的构成操作数操作数+运算符运算符+界符(如括号)界符(如括号)3)表达式的求值表达式的求值:例例5+6(1+2)-4按照四则运算法则,上述表达式的计算过程为:按照四则运算法则,上述表达式的计算过程为:5+6(1+2)-4=5+6 3-4=5+18-4=23-4=193.23.2栈的应用举例栈的应用举例1234如何确定运算符的运算顺序?4)算符优先关系表算符优先关系表表达式中任何相邻运算符表达式中任何相邻运算符c1、c2的优先关系有:的优先关系有:c1c2:c1的优先级高于的优先级高于c2+c2 c1-*/()#+-*/()#=算符间的优先关系表算符间的优先关系表注:注:c1 c2是相邻算符,是相邻算符,c1在左在左,c2在右在右算符的优先级设置算符的优先级设置算符算符栈内优先级栈外优先级*/+-+-()#4 43 31 15 50 0-1-1-1-15 50 02 23.23.2栈的应用举例栈的应用举例栈的应用举例栈的应用举例5)算符优先算法算符优先算法从左向右扫描表达式:遇操作数保存;遇运算符号cj与前面的刚扫描过的运算符ci比较若cicj则保存cj,(因此已保存的运算符的优先关系为c1c2c3cj则说明ci是已扫描的运算符中优先级最高者,可进行运算;若ci=cj则ci为(,cj为),说明括号内的式子已计算完,需要消去括号;5+4(1+2)-6后面也许有优先级更高的算符+(后保存的算符有优先级高用两个栈分别保存扫描过程中遇到的操作数和运算符算符比较算法算符比较算法Char Precede(char c1,char c2)Char Precede(char c1,char c2)intint c_temp1,c_temp2;c_temp1,c_temp2;switch(c1)switch(c1)case *:case *:case /:c_temp1=4;break;case /:c_temp1=4;break;case +:case +:case -:c_temp1=2;break;case -:c_temp1=2;break;.switch(c2)switch(c2)case *:case *:case /:c_temp2=3;break;case /:c_temp2=3;break;case +:case +:case -:c_temp2=1;break;case -:c_temp2=1;break;.续续if(c_temp1c_temp2)return();if(c_temp1c_temp2)return(c_temp2)return();if(c_temp1c_temp2)return();3.23.2栈的应用举例栈的应用举例在算符优先算法中,建立了两个工作栈。一个是在算符优先算法中,建立了两个工作栈。一个是OPTR栈,用以保存运栈,用以保存运算符一个是算符一个是OPND栈,用以保存操作数或运算结果。栈,用以保存操作数或运算结果。intexpress()/运算数栈,运算数栈,OP为运算符集合。为运算符集合。InitStack(OPTR);Push(OPTR,#);InitStack(OPND);w=qetchar();While(w!=#|GetTop(OPTR)!=#)if(!In(w,OP)Push(OPND,w);w=getchar();/不不是是运运算符则进栈算符则进栈else/In(w,OP)判判断断c是是否否是是运运算算符符的的函函数数3.23.2栈的应用举例栈的应用举例续续switch(Precede(GetTop(OPTR),w)case:/新输入的算符新输入的算符c优先级低,即栈顶算符优先权高,优先级低,即栈顶算符优先权高,/出栈并将运算结果入栈出栈并将运算结果入栈OPNDop=Pop(OPTR);b=Pop(OPND);a=Pop(OPND);Push(OPND,Operate(a,op,b);break;returnGetTop(OPND);表达式求值示意图:5+6(1+2)-4 topbaseOPTR栈#OPND栈topbase5toptop+top6toptop(top1top+top2toptoptoptop3toptoptoptoptop18toptop toptop23top-top4toptoptop top19toptoptop5读入表达式过程:+6(1+2)-4#=191+2=363=185+18=2323-4=19在计算机中,表达式可以有三种不同的标识方法:在计算机中,表达式可以有三种不同的标识方法:在计算机中,表达式可以有三种不同的标识方法:在计算机中,表达式可以有三种不同的标识方法:设设设设 exp=exp=exp=exp=S1S1S1S1+OP+OP+OP+OP+S2S2S2S2 则称则称则称则称:OP+:OP+:OP+:OP+S1S1S1S1+S2S2S2S2 为表达式的前缀表示法为表达式的前缀表示法为表达式的前缀表示法为表达式的前缀表示法 S1S1S1S1+OP+OP+OP+OP+S2 S2 S2 S2 为表达式的中缀表示法为表达式的中缀表示法为表达式的中缀表示法为表达式的中缀表示法 S1S1S1S1+S2S2S2S2+OP +OP +OP +OP 为表达式的后缀表示法为表达式的后缀表示法为表达式的后缀表示法为表达式的后缀表示法可见,它以运算符所在的不同位置而命名的。可见,它以运算符所在的不同位置而命名的。例如:例如:exp=exp=abab+(c-d/e)f(c-d/e)f前缀式:前缀式:ababc/defc/def中缀式:中缀式:abab+c-d/efc-d/ef后缀式:后缀式:a abbcdecde/ff 结论:结论:1.操作数之间的相对次序不变;操作数之间的相对次序不变;2.运算符的相对次序不同;运算符的相对次序不同;3.中缀式丢失了括号信息;致使运算次序不确定;中缀式丢失了括号信息;致使运算次序不确定;4.前缀式的运算规则为:前缀式的运算规则为:连续出现的两个操作数和他们之前连续出现的两个操作数和他们之前且紧靠它们的运算符构成一个最小表达式;且紧靠它们的运算符构成一个最小表达式;5.后缀式的运算规则为:后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的顺序,运算符在式中出现的顺序恰为表达式的顺序,每个运算符在它之前出现,且紧靠它的两个每个运算符在它之前出现,且紧靠它的两个操作数构成一个表达式。操作数构成一个表达式。3.3栈与递归栈与递归一般函数的调用机制A()B();C()B()C();调用调用返回返回函数调用顺序 A B C函数返回顺序 C B A后调用的函数先返回函数调用机制可通过栈来实现函数调用机制可通过栈来实现计算机正是利用栈来实现函数的调用和返回的3.33.3栈与递归栈与递归1什么是递归什么是递归递递归归是是一一个个很很有有用用的的工工具具,在在数数学学和和程程序序设设计计等等许许多多领领域域中中都用到了递归。都用到了递归。递递归归定定义义:简简单单地地说说,一一个个用用自自己己定定义义自自己己的的概概念念,称称为为递递归归定义。定义。例例n!=1*2*3*4*(n-1)*nn!递归定义递归定义n!=1当当n=0时时n!=n(n-1)!当当n0时时用(n-1)!定义n!3.33.3栈与递归栈与递归2递归函数:一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。A()A();B()C()C();B();A直接调用自己B间接调用自己3.33.3栈与递归栈与递归2递归算法的编写递归算法的编写1)将问题用)将问题用递归的方式描述(定义)递归的方式描述(定义)2)根据问题的递归描述(定义)编写)根据问题的递归描述(定义)编写递归算法递归算法问题的递归描述(定义)问题的递归描述(定义)递归定义包括两项递归定义包括两项基本项(终止项):描述递归终止时问题的求解;基本项(终止项):描述递归终止时问题的求解;递递归归项项:将将问问题题分分解解为为与与原原问问题题性性质质相相同同,但但规规模模较较小小的的问题;问题;例例n!的递归定义的递归定义基本项:基本项:n!=1当当n=0递归项:递归项:n!=n(n-1)!当当n0用(n-1)!定义n!3.33.3栈与递归栈与递归例例1 1 编写求解编写求解 阶乘阶乘n!n!的递归算法的递归算法首先给出阶乘首先给出阶乘n!n!的递归定义的递归定义 n!n!的递归定义的递归定义 基本项:基本项:n!=1 n!=1 当当 n=1n=1 递归项:递归项:n!=n(n-1)!n!=n(n-1)!当当 n 1n 1intint fact(intfact(int n)n)/算法功能是求解并返回算法功能是求解并返回n n的阶乘的阶乘 ifif(n=1n=1)returnreturn(1 1););else returnelse return(n*fact(n-1)n*fact(n-1)););3.33.3栈与递归栈与递归我们看一下n=3 阶乘函数fact(n)的执行过程Main()Main()intint n=3,y;n=3,y;L y=L y=fact(n)fact(n);调用调用调用intfact(n)If(n=1)return(1););ElseL1return(n*fact(n-1)););n=3intfact(intn)If(n=1)return(1););ElseL1return(n*fact(n-1)););n=2intfact(intn)If(n=1)return(1););ElseL1return(n*fact(n-1)););n=1L 3L 3L1 1L1 1L1 2L1 2返回1 1返回2 2返回6 61 1n*fact(n-1)n*fact(n-1)fact(n)返回地址 实参 注意递归调用中 栈的变化例2 hanoi 塔问题。圆盘移动时必须遵循下列规则:圆盘移动时必须遵循下列规则:圆盘移动时必须遵循下列规则:圆盘移动时必须遵循下列规则:(1 1)每次只能移动一个圆盘;)每次只能移动一个圆盘;)每次只能移动一个圆盘;)每次只能移动一个圆盘;(2 2)圆盘可以插在)圆盘可以插在)圆盘可以插在)圆盘可以插在XX、Y Y和和和和Z Z中的任一塔座上;中的任一塔座上;中的任一塔座上;中的任一塔座上;(3 3)任何时刻都不能将与一个较大的圆盘压在较小的圆盘)任何时刻都不能将与一个较大的圆盘压在较小的圆盘)任何时刻都不能将与一个较大的圆盘压在较小的圆盘)任何时刻都不能将与一个较大的圆盘压在较小的圆盘之上。之上。之上。之上。算法如下:算法如下:Void Void hanoi(inthanoi(int n,charn,char x,charx,char y,char z)y,char z)/将塔座将塔座将塔座将塔座x x上按直径由小到大且自上而下编号为上按直径由小到大且自上而下编号为上按直径由小到大且自上而下编号为上按直径由小到大且自上而下编号为1 1至至至至n n的的的的n n个圆盘按规则搬到塔座个圆盘按规则搬到塔座个圆盘按规则搬到塔座个圆盘按规则搬到塔座z z上,上,上,上,y y可用作辅助塔座。可用作辅助塔座。可用作辅助塔座。可用作辅助塔座。/搬动操作搬动操作搬动操作搬动操作move(x,n,zmove(x,n,z)可定义为(可定义为(可定义为(可定义为(c c是初值为是初值为是初值为是初值为0 0的全局变量,对搬动计数):的全局变量,对搬动计数):的全局变量,对搬动计数):的全局变量,对搬动计数):/printf(“%i.movprintf(“%i.mov disk%I from%c to%d disk%I from%c to%d n”,+c,n,x,zn”,+c,n,x,z););if(n=1)if(n=1)move(x,1,z);move(x,1,z);else else hanoi(n-1,x,z,y);hanoi(n-1,x,z,y);move(x,n,zmove(x,n,z););hanoi(n-1,y,x,z);hanoi(n-1,y,x,z);执行过程:执行过程:栈的相关作业题栈的相关作业题:1 1、若按课本、若按课本、若按课本、若按课本3.1.13.1.1节中图节中图节中图节中图3.13.1(b b)所示铁道进行车厢调)所示铁道进行车厢调)所示铁道进行车厢调)所示铁道进行车厢调度(注意:两侧铁道均为单向行使道),则请回答:度(注意:两侧铁道均为单向行使道),则请回答:度(注意:两侧铁道均为单向行使道),则请回答:度(注意:两侧铁道均为单向行使道),则请回答:(1 1)如果进战的车厢顺序为)如果进战的车厢顺序为)如果进战的车厢顺序为)如果进战的车厢顺序为123123,则可能得到的出站车厢,则可能得到的出站车厢,则可能得到的出站车厢,则可能得到的出站车厢序列是什么?序列是什么?序列是什么?序列是什么?(2 2)如果进站的车厢序列为)如果进站的车厢序列为)如果进站的车厢序列为)如果进站的车厢序列为123456123456,则能否得到,则能否得到,则能否得到,则能否得到435612435612和和和和134526134526的出站序列,并请说明为什么不能的出站序列,并请说明为什么不能的出站序列,并请说明为什么不能的出站序列,并请说明为什么不能得到或者如何得到(即写出以得到或者如何得到(即写出以得到或者如何得到(即写出以得到或者如何得到(即写出以“S”S”表示进栈和以表示进栈和以表示进栈和以表示进栈和以“X”X”表示出栈的栈操作序列)。表示出栈的栈操作序列)。表示出栈的栈操作序列)。表示出栈的栈操作序列)。2 2、按照四则运算加、减、乘除和幂(、按照四则运算加、减、乘除和幂(、按照四则运算加、减、乘除和幂(、按照四则运算加、减、乘除和幂()优先关系的惯例,)优先关系的惯例,)优先关系的惯例,)优先关系的惯例,并仿照课堂上所讲的例子,画出对下列表达式求值时操作并仿照课堂上所讲的例子,画出对下列表达式求值时操作并仿照课堂上所讲的例子,画出对下列表达式求值时操作并仿照课堂上所讲的例子,画出对下列表达式求值时操作数栈和运算符栈的变化过程:数栈和运算符栈的变化过程:数栈和运算符栈的变化过程:数栈和运算符栈的变化过程:AABC/D+EBC/D+EF F 3 3.4 队列队列3 3.4.4.1 .1 队列队列的概念的概念3.43.4.2 .2 循环队列循环队列 队列队列的顺序存储和实现的顺序存储和实现3.43.4.3 .3 队列队列的链式存储和实现的链式存储和实现3 344队列队列3.4.1队列的概念队列的概念一一什么是队列什么是队列队列是限定仅能在表头进行删除,表尾进行插入的线性表(a1,a2,.,ai-1,ai,ai+1,an)插入删除3 344队列队列 a a1 1 a a2 2 a a3 3 a an n入队列队头队尾出队列队队 列列 的的 示示 意意 图图队列的特点队列的特点先进先出先进先出第一个入队的元素在队头,第一个入队的元素在队头,最后一个入队的元素在队尾,最后一个入队的元素在队尾,第一个出队的元素为队头元素,第一个出队的元素为队头元素,最后一个出队的元素为队尾元素最后一个出队的元素为队尾元素队列也是一种运算受限制的线性表,所以又叫先进先出队列也是一种运算受限制的线性表,所以又叫先进先出队列也是一种运算受限制的线性表,所以又叫先进先出队列也是一种运算受限制的线性表,所以又叫先进先出表表表表(FIFO)(FIFO)。3 344队列队列二二队列的抽象数据类型定义队列的抽象数据类型定义三三ADTQueue四四数据对象数据对象:D=ai|aiElemSet,i=1,2,n,n=0五五数据关系:数据关系:R1=|ai-1,aiD,i=1,2,n六a1为队头元素,an为队尾元素七七基本操作:基本操作:八八队列初始化:队列初始化:Init_Queue(q)九九初始条件:初始条件:队队q不存在。不存在。十十操作结果:构造了一个空队。操作结果:构造了一个空队。入队操作:入队操作:入队操作:入队操作:In_Queue(q,xIn_Queue(q,x),),初始条件:队初始条件:队初始条件:队初始条件:队q q存在。存在。存在。存在。操作结果:对已存在的队列操作结果:对已存在的队列操作结果:对已存在的队列操作结果:对已存在的队列q q,插入一个元素,插入一个元素,插入一个元素,插入一个元素x x到队尾,到队尾,到队尾,到队尾,队发生变化。队发生变化。队发生变化。队发生变化。出队操作:出队操作:出队操作:出队操作:Out_Queue(q,xOut_Queue(q,x)初始条件初始条件初始条件初始条件:队队队队q q存在且非空存在且非空存在且非空存在且非空操作结果:删除队首元素,并返回其值,队发生变化。操作结果:删除队首元素,并返回其值,队发生变化。操作结果:删除队首元素,并返回其值,队发生变化。操作结果:删除队首元素,并返回其值,队发生变化。读队头元素:读队头元素:Front_Queue(q,x)初始条件初始条件:队队q存在且非空存在且非空操作结果:读队头元素,并返回其值,队不变;操作结果:读队头元素,并返回其值,队不变;判队空操作:判队空操作:Empty_Queue(q)初始条件:队初始条件:队q存在存在操作结果:若操作结果:若q为空队则返回为为空队则返回为1,否则返回为,否则返回为0。ADTqueue3 344队列队列1 1、顺序队(队列的顺序存储和实现)、顺序队(队列的顺序存储和实现)、顺序队(队列的顺序存储和实现)、顺序队(队列的顺序存储和实现)#define MAX 50 /*#define MAX 50 /*数据结构定义数据结构定义*/intint queueMAX;queueMAX;intint front=-1;rear=-1;front=-1;rear=-1;intint insert_queue(intinsert_queue(int x)/*x)/*入队列入队列*/if(rear=MAX-1)return(0);if(rear=MAX-1)return(0);rear+;rear+;queuerear=x;return(1);queuerear=x;return(1);intint del_queue()/*del_queue()/*出队列出队列*/if(rear=front)return(0);if(rear=front)return(0);front+;return(queuefront);front+;return(queuefront);rearfrontJ1J2rearfrontJ2(a)空队列(b)J1,J2相继入队列(c)J1出队(d)J3,J4和J5相继入队之后,J2出队rearfront-1012343.43.4队列队列rearfrontJ5J4J3front,rear均为整数用箭头指示只是为了直观又有又有J6入队入队,怎么办?怎么办?3.43.4队列队列3.4.2循环队列循环队列队列的顺序存储和实现队列的顺序存储和实现1.循环队列循环队列frontrearJ6J4J53 124 05rear54 03 12frontJ6J7J8J9J4J5frontrear54 03 12(b)队空(c)队满队空、队满都有front=rear如何判断循环队列队空、队满?J7rear3.43.4队列队列有两种方法:1)另设一个标志位以区分队空、队满。)另设一个标志位以区分队空、队满。2)少用一个存储单元,队满条)少用一个存储单元,队满条:front=rear+1;front54 03 12J6J7J8J4J5(d)rear3.43.4队列队列1)初始化操作)初始化操作功能:功能:建一个空建一个空队列队列Q;算法:算法:IntqueueMAX;Intfront,rear;intInitQueue_Sq()/构造一个空队列Qfront=0;rear=0;Return(1)二二循环队列的基本操作算法循环队列的基本操作算法frontrear54 03 12建一个空队列Q3.43.4队列队列6)入队操作入队操作功能:将元素功能:将元素x插入队尾插入队尾frontrear54 03 12J1J3J2xfrontrear54 03 12J1J3J2元素 x 入队前元素 x 入队后3.43.4队列队列求余运算入队操作算法:入队操作算法:intinsert_queue(intx)/*入队列入队列*/if(rear+1)%MAX=front)return(0);rear=(rear+1)%MAX;queuerear=x;return(1);3.43.4队列队列7)出队操作)出队操作功能:删除队头功能:删除队头元素;元素;frontrear54 03 12J1J3J2出队操作前frontrear54 03 12J1J3J2出队操作后3.43.4队列队列出队操作算法:出队操作算法:intdel_queue()/*出队列出队列*/if(rear=front)return(0);return(queuefront);front=(front+1)%MAX;3.4.3链队列链队列队列的链式存储结构和实现队列的链式存储结构和实现一一链队列链队列frontrear空链队列a1frontrear a2链队列图示3.43.4队列队列3.43.4队列队列二二 链队列的类型定义链队列的类型定义structstruct node /node /链队列结点链队列结点的类型定义的类型定义 intint data;data;structstruct node*next;node*next;typedeftypedef structstruct node NODE;node NODE;NODE*front,*rear;NODE*front,*rear;三三三三链队列的基本操作链队列的基本操作链队列的基本操作链队列的基本操作1 1、入列运算、入列运算、入列运算、入列运算Void addqlink(int x)NODE*p;p=(NODE*)malloc(sizeof(NODE);p-data=x;p-next=NULL;rear-next=p;rear=p;2 2、出列运算、出列运算、出列运算、出列运算NODE*NODE*deleqlinkdeleqlink()()NODE*p;NODE*p;if(front=rear)return(NULL);if(front=rear)return(NULL);p=front-next;p=front-next;front-next=p-next;front-next=p-next;if(front-next=NULL)rear=front;if(front-next=NULL)rear=front;return(p);return(p);3 3、元素记数运算元素记数运算元素记数运算元素记数运算int count()int i;NODE*p;if(front=rear)return(0);for(p=front-next;i=1;p!=p-next)i+;return(i);3.43.4队列队列四队列的应用队列的应用1)解决计算机主机与外设不匹配的问题;2)解决由于多用户引起的资源竞争问题;3)离散事件的模拟-模拟实际应用中的各种排队现象;4)用于处理程序中具有先进先出特征的过程;在操作系统课程中会讲到 小小 结结 1队列是限定仅能在表尾一端进行插入,队列是限定仅能在表尾一端进行插入,表头一端删除操作的线性表;表头一端删除操作的线性表;2队列中的元素具有先进先出的特点;队列中的元素具有先进先出的特点;3队头、队尾元素的位置分别由称为队头队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示,指针和队尾指针的变量指示,4入队操作要修改队尾指针,出队操作要入队操作要修改队尾指针,出队操作要修改队头指针;修改队头指针;返回目录返回目录主讲人:张晓玲主讲人:张晓玲 2 数据结构题集数据结构题集(C语言版)语言版)严蔚敏 吴伟民 清华大学出版社 参考教材参考教材1 数据结构数据结构(C语言版)语言版)严蔚敏 吴伟民 清华大学出版社&第一章第一章 绪论绪论 1.1 1.1 数据结构讨论的范畴;数据结构讨论的范畴;1.2 1.2 数据结构的有关基本概念;数据结构的有关基本概念;1.3 1.3 抽象数据类型的表示与实现;抽象数据类型的表示与实现;1.4 1.4 算法及算法分析(算法评价)算法及算法分析(算法评价)数据结构是什么数据结构是什么?Niklaus Wirth AlgorithmData Structures Programs 程序设计:程序设计:为计算机解题(处理问题)编制的一组为计算机解题(处理问题)编制的一组 指令集。指令集。算法:算法:对某类信息进行处理对某类信息进行处理,处理问题的策略。处理问题的策略。数据结构数据结构:处理的信息怎么表示处理的信息怎么表示,问题的数学模型。问题的数学模型。任何问题都包括这两个方面任何问题都包括这两个方面的问题,包括数值计算和非的问题,包括数值计算和非数值计算数值计算 数值问题与非数值问题数值问题与非数值问题1 1)数值计算中的程序设计的问题)数值计算中的程序设计的问题例例1 1 已知:游泳池的长已知:游泳池的长lenlen和宽和宽widewide,求面积求面积area?area?建模型:建模型:问题涉及的对象:游泳池的长问题涉及的对象:游泳池的长lenlen 宽宽widewide,面积面积areaarea;对象之间的关系:对象之间的关系:area=area=lenlen widewide (算法)算法)设计求解问题的方法设计求解问题的方法 编程编程 main()int len,wide,area;scanf(“%d%d%n”,&l,&w);area=len*wide;printf(“area=%d”,area);例例2 2:结构静力分析计算:结构静力分析计算 线性代数方程组线性代数方程组例例3 3:全球天气预报:全球天气预报 环流模式方程组环流模式方程组 学号学号 姓名姓名 性别性别 出生日期出生日期 籍贯籍贯 入学成绩入学成绩 所在班级所在班级 00201 杨润生 男 82/06/01 广州 561 00计算机200102 石磊 男 83/12/21 汕头 512 00计算机100202 李梅 女 83/02/23 阳江 532 00计算机200301 马耀先 男 82/07/12 广州 509 00计算机32 2)非数值计算的程序设计问题)非数值计算的程序设计问题例例 2 2 已知某级学生情况已知某级学生情况 ,要求分班按入学成绩排列要求分班按入学成绩排列顺序顺序。学生管理数据库系统学生管理数据库系统算法:?需要解决的问题?如何解决?用户界面?算法:?需要解决的问题?如何解决?用户界面?模型:?各种各样的表格和数据库模型:?各种各样的表格和数据库在这类文档管理的数学模型中在这类文档管理的数学模型中,计算机处理的对象之间计算机处理的对象之间通常存在着一种最简单的线性关系通常存在着一种最简单的线性关系 ,这类数学模型称这类数学模型称为线性模型。为线性模型。v例 3 迷宫问题。在迷宫中,每走到一处,接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出,则可得一棵“树”。入入口口 出口出口算法:?走迷宫的规则和策略算法:?走迷宫的规则和策略模型:?迷宫、迷宫的每一处模型:?迷宫、迷宫的每一处v城市间交通网问题城市间交通网问题算法:?交通网中要解决的问题?算法:?交通网中要解决的问题?模型:?每一条通路、每一个路口模型:?每一条通路、每一个路口综合各种程序设计问题,抽取它具体的物理含义,可以得到几种数学模型,例如:1 1、与数值计算相关的问题:、与数值计算相关的问题:线性代数方程、非线性代数方程、常微分方程(计算机求解的问题就是计算数学要研究的问题)2 2、与非数值计算相关的问题:、与非数值计算相关的问题:问题的表示和求解的方法,就是数据结构要讨论的内容。数据结构的研究问题:数据结构的研究问题:非数值数据之间的结构关系,及如何表示,如何存储,如何处理。本课程讨论的问题:本课程讨论的问题:应用中常用的几种数据间的结构关系,及如何表示,如何存储,如何处理。数据:数据:所有能输入到计算机中所有能输入到计算机中,且被计算机处理的符号的集合,且被计算机处理的符号的集合,是计算机操作对象的总称;是计算机操作对象的总称;是计算机处理的信息的某种特定的符号表示形式。是计算机处理的信息的某种特定的符号表示形式。数据元素:数据元素:数据中的一个数据中的一个“个体个体”,数据结构中讨论的基本单位。数据结构中讨论的基本单位。相当于相当于“记录记录”,在计算机程序中通常作为一个整体考虑和处理。在计算机程序中通常作为一个整体考虑和处理。数据项数据项:相当于记录的相当于记录的“域域”,是数据的不可分割的最小是数据的不可分割的最小单位单位,如学号。数据元素是数据项的集合。如学号。数据元素是数据项的集合。例如:运动员(数据元素)数据对象数据对象:性质相同的数据元素的集合.例如:所有运动员的记录集合姓名姓名俱乐部名称俱乐部名称出生日期出生日期参加日期参加日期职务职务业绩业绩年年月月日日数据结构:数据结构:是相互间存在某种关系的数据元素集合。例如:一个含有12位数的十进制数,可以用三个4位的十进制数表示 3214,6587,9345-a1(3124),a2(6587),a3(9345)在a1,a2和a3之间存在“次序”关系,次序不能颠倒 a1,a2,a3!=a2,a1,a3a1,a2,a3!=a2,a1,a3数据结构是带结构的数据元素的集合数据结构是带结构的数据元素的集合又例:又例:2 2行行3 3列二维数组列二维数组a1,a2,a3,a4,a5,a6a1,a2,a3,a4,a5,a6 行的次序关系:行的次序关系:row=,row=,列的次序关系列的次序关系:colcol=,=,a1a2a3a4a5a6数据结构是带结构的数据元素的集合数据结构是带结构的数据元素的集合再例,一维数组a1,a2,a3,a4,a5,a6存在次序关系次序关系:|i=1,2,3,4,5,6|i=1,2,3,4,5,6不同的关系构成不同的结构不同的关系构成不同的结构数据结构是带结构的数据元素的集合数据结构是带结构的数据元素的集合对每种数据结构,主要讨论如下两方面的问题:对每种数据结构,主要讨论如下两方面的问题:1)数据的逻辑结构,数据结构的基本操作;2)数据的存储结构,数据结构基本操作的实现;数据的逻辑结构:数据的逻辑结构:数据之间的结构关系,是数据之间的结构关系,是具体具体关系的抽象。关系的抽象。数据结构的基本操作:数据结构的基本操作:指对数据结构的加工处理指对数据结构的加工处理数据的存储结构数据的存储结构(物理结构物理结构):数据结构在计算机内存中的表示数据结构在计算机内存中的表示数据结构基本操作的实现数据结构基本操作的实现:基本操作在计算机上的实现(方法基本操作在计算机上的实现(方法)1 1数据的逻辑结构数据的逻辑结构 2 2、数据的存储结构、数据的存储结构 3 3、数据的运算:检索、排序、插入、删除、修改等。、数据的运算:检索、排序、插入、删除、修改等。A A线性结构线性结构 B B非线性结构非线性结构A A 顺序存储顺序存储 B B 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面 某班学生基本情况登记表,记录了每个学生的学号 姓名 专业 政治 面貌,表中的记录是按学生的学号顺序排列的。学号学号 姓名姓名 专业专业 政治面藐政治面藐 001001 王洪王洪 计算机计算机 党员党员 002 002 孙文孙文 计算机计算机 团员团员 003003 谢军谢军 计算机计算机 团员团员 004004 李辉李辉 计算机计算机 团员团员 005005 沈祥福沈祥福 计算机计算机 党员党员 006006 余斌余斌 计算机计算机 团员团员 007007 巩力巩力 计算机计算机 团员团员 008008 孔令辉孔令辉 计算机计算机 团员团员学生基本情况登记表的图示学生基本情况登记表的图示学生间学号顺序关系学生间学号顺序关系是一种线性结构关系是一种线性结构关系例例一一 常用的数据逻辑结构常用的数据逻辑结构 1)集合集合 2 2)线性结构线性结构 3 3)树结构树结构 4 4)图结构图结构 5 5)其它复杂结构)其它复杂结构 001001003003002002004004006006005005008008007007 家族的族谱家族的族谱 假设某家族有假设某家族有1010个成员个成员A A,B B,C C,D D,E E,F F,G G,H H,I I,J J,他们之间的血缘关系可以用如下图表示。他们之间的血缘关系可以用如下图表示。例例家族的成员之间是一种树型结构关系家族的成员之间是一种树型结构关系J JI IA AC CB BD DH HG GF FE EJ JI IA AC CB BD DH HG GF FE EJ JI IA AC CB BD DH HG GF FE EJ JI IA AC CB BD DH HG GF FE EJ JI IA AC CB BD DH HG GF FE E1423 D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)213 D=1,2,3 R=(1,2),(2,3),(3,2),(1,3)图形结构图形结构节点间的连结是任意的节点间的连结是任意的例例二数据结构的表示二数据结构的表示 图示表示图示表示 图示表示是由顶点和边构成的图,其中顶点表示数据图示表示是由顶点和边构成的图,其中顶点表示数据 ,边表示数据之间的结构关系;,边表示数据之间的结构关系;001001003003002002004004006006005005008008007007学生基本情况表的图示表示学生基本情况表的图示表示家族树的图示表示家族树的图示表示J JI IA AC CB BD DH HG GF FE E学生基本情况表的二元组表示学生基本情况表的二元组表示(D D,S S)二元组表示二元组表示 二元组表示是用一个二元组(二元组表示是用一个二元组(D D,S S)表示数据结构,表示数据结构,其其中中 D D 是数据元素集合,是数据元素集合,S S 是是 D D 上关系的集合。上关系的集合。D=001D=001,002002,003003,004004,005005,006006,007007,008008S=R S=R R=R=,001001003003002002004004006006005005008008007007 家族树的二元组表示(家族树的二元组表示(D D,S S)D=AD=A,B B,C C,D D,E E,F F,G G,H H,I I,JJ S=R S=R R=R=A,B,A,B,J JI IA AC CB BD DH HG GF FE E.数据元素的映像方法:用二进制位数据元素的映像方法:用二进制位(bit)(bit)的位串表示数据的位串表示数据元素元素(321)10=(501)8=(101000001)2 A=(101)8=(001000001)2三三 数据的存储结构数据的存储结构逻辑结构在存储器中的映像逻辑结构在存储器中的映像2.2.关系的映像方法关系的映像方法:(表示:(表示 的方法)的方法)有序对是关系的基本单位,关系的映像就有序对是关系的基本单位,关系的映像就是有序对的映像是有序对的映像J JI IA AC CB BD DH HG GF FE E元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+(n-1)*m存储地址存储地址存储内容存储内容Loc(a)=Lo+(i-1)*m顺顺序序存存储储每个元素所占用每个元素所占用的存储单元个数的存储单元个数以存储位置以存储位置的相邻来表的相邻来表示后继关系示后继关系y y的存储位置的存储位置和和x x的存储位的存储位置的次序关置的次序关系系元素n.元素i.元素2元素1存储内容顺序存储结构常用于线性数据结构,将逻辑顺序存储结构常用于线性数据结构,将逻辑上相邻的数据元素存储在物理上相邻的存储上相邻的数据元素存储在物理上相邻的存储单元里。单元里。顺序存储结构的三个弱点:顺序存储结构的三个弱点:1.1.作插入或删除操作时,需移动大量元数。作插入或删除操作时,需移动大量元数。2.2.长度变化较大时,需按最大空间分配。长度变化较大时,需按最大空间分配。3.3.表的容量难以扩充。表的容量难以扩充。1536元素21400元素11346元素3 元素41345h 链式存储链式存储 每个节点都由两部分组成:每个节点都由两部分组成:数据域数据域和和指针域指针域。数据域数据域存放元素本身的数据,存放元素本身的数据,指针域指针域存放指针。存放指针。数据元素之间逻辑上的联系由指针来体现。数据元素之间逻辑上的联系由指针来体现。1536元素21400元素11346元素3 元素4head 1346 元素3 1536 .1536 元素2 1400 .元素4 1346 1400 元素1 1345 指针 存储内容存储地址 链式存储链式存储 13451536元素21400元素11346元素3 元素41345h 链式存储 1.1.比顺序存储结构的存储密度小比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成每个节点都由数据域和指针域组成)。2.2.逻辑上相邻的节点物理上不必相邻。逻辑上相邻的节点物理上不必相邻。3.3.插入、删除灵活插入、删除灵活 (不必移动节点,只要改变节点中的指针不必移动节点,只要改变节点中的指针)。链接存储结构特点:链接存储结构特点:在不同的编程环境中,存储结构可有不同的描述方法。在不同的编程环境中,存储结构可有不同的描述方法。当用高级程序设计语言进行编程时,通常可用高级语言当用高级程序设计语言进行编程时,通常可用高级语言中提供的数据类型描述之。中提供的数据类型描述之。例如:例如:以三个带有次序关系的整数表示一个长整数,可以以三个带有次序关系的整数表示一个长整数,可以利用利用C C语言中提供的整数数组类型,定义长整数为:语言中提供的整数数组类型,定义长整数为:TypedefTypedef intint long_int3 long_int3 一、数据类型一、数据类型 在用高级程序语言编写的程序中,必须对程在用高级程序语言编写的程序中,必须对程序中出现的每个变量、常量或表达式,明确说序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。明它们所属的数据类型。例如,C 语言中提供的基本数据类型基本数据类型有:整型整型 intint浮点型浮点型 floatfloat字符型字符型 charchar逻辑型逻辑型 boolbool (C+C+语言)语言)双精度型双精度型 doubledouble实型实型(C+C+语言)语言)数据类型数据类型 是一个值的集合值的集合和定义在此集合上的一组操作一组操作的总称。不同类型的变量,其所能取的值的范围值的范围不同,所能进进行的操作行的操作不同。二、抽象数据类型二、抽象数据类型 (Abstract Data Type(Abstract Data Type 简称简称ADT)ADT)是指是指一个数学模型一个数学模型以及定义在此数学模型以及定义在此数学模型上的上的一组操作一组操作。例如,抽象数据类型复数的定义:例如,抽象数据类型复数的定义:数据对象:数据对象:De1,e2e1,e2RealSet 数据关系:数据关系:R1|e1是复数的实数部分|e2 是复数的虚数部分 ADT Complex ADT Complex 基本操作:基本操作:AssignComplexAssignComplex(&Z,v1,v2)(&Z,v1,v2)操作结果:构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。DestroyComplexDestroyComplex(&Z)(&Z)操作结果:复数Z被销毁。GetRealGetReal(Z,&(Z,&realPartrealPart)初始条件:复数已存在。操作结果:用realPart返回复数Z的实部值。GetImagGetImag(Z,&(Z,&ImagPartImagPart)初始条件:复数已存在。操作结果:用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)Add(z1,z2,&sum)初始条件:z1,z2是复数。操作结果:用sum返回两个复数z1,z2 的和值。ADT Complex ADT Complex假设:z1和z2是上述定义的复数则 Add(z1,z2,z3)操作的结果z3=z1+z2即为用户企求的结果ADT ADT 有两个重要特征有两个重要特征:数据抽象数据抽象 用用ADTADT描述程序处理的实体时,强调的描述程序处理的实体时,强调的是其本质的特征、其所能完成的功能以及它和外部是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。用户的接口(即外界使用它的方法)。数据封装数据封装 将实体的外部特性和其内部实现细节将实体的外部特性和其内部实现细节分离,并且对外部用户隐藏其内部实现细节。分离,并且对外部用户隐藏其内部实现细节。抽象数据类型的描述方法抽象数据类型的描述方法抽象数据类型可用(D D,S S,P P)三元组表示。其中:D 是数据对象;S 是 D 上的关系集;P 是对 D 的基本操作集。ADTADT 抽象数据类型名抽象数据类型名 数据对象:数据对象:数据对象的定义 数据关系:数据关系:数据关系的定义 基本操作:基本操作:基本操作的定义 ADT ADT 抽象数据类型名其中基本操作的定义格式为其中基本操作的定义格式为:基本操作名基本操作名(参数表)初始条件:初始条件:初始条件描述 操作结果操作结果:操作结果描述 赋值参数赋值参数 只为操作提供输入值。引用参数引用参数 以&打头,除可提供输入值外,还将返回操作结果。初始条件初始条件 描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息。操作结果操作结果 说明了操作正常完成之后,数据结构的变化状况和应返回的结果。若初始条件为空,则省略之。抽象数据类型需要通过固有数据类型抽象数据类型需要通过固有数据类型(高级编高级编程语言中已实现的数据类型程语言中已实现的数据类型)来实现。来实现。例如,对以上定义的复数。例如,对以上定义的复数。typedef struct float realpart;float imagpart;complex;/-/-存储结构的定义存储结构的定义/-/-基本操作的函数原型说明基本操作的函数原型说明void Assign(complex&Z,float realval,float imagval);/构造复数 Z,其实部和虚部分别被赋以参数/realval 和 imagval 的值float GetReal(cpmplex Z);/返回复数 Z 的实部值float Getimag(cpmplex Z);/返回复数 Z 的虚部值void add(complex z1,complex z2,complex&sum);/以 sum 返回两个复数 z1,z2 的和 /-基本操作的实现基本操作的实现void add(complex z1,complex z2,complex&sum)/以以 sum sum 返回两个复数返回两个复数 z1,z2 z1,z2 的和的和 sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;其它省略 我们各章都是从抽象数据类型的角度开我们各章都是从抽象数据类型的角度开始讨论数据结构,数据结构和它的操作是始讨论数据结构,数据结构和它的操作是一个整体。一个整体。一一 算法的概念算法的概念 算法是求解问题的操作序列算法是求解问题的操作序列 算法的基本特征:算法的基本特征:1 1)有输入;)有输入;2 2)有输出;)有输出;3 3)有穷性;)有穷性;4 4)确定性;)确定性;5 5)可行性。)可行性。求两个正整数求两个正整数 m m,n n 中的最大数中的最大数MAXMAX的算法的算法 (1 1)若)若 m n m n 则则 max=mmax=m (2 2)若若 m=n m=n 则则 max=n max=n 例例.有穷性对于任意一组合法输入值,在执行有穷步骤对于任意一组合法输入值,在执行有穷步骤之后,一定能结束。即:算法中的每一个步骤都能在有限之后,一定能结束。即:算法中的每一个步骤都能在有限的时间内完成。的时间内完成。.确定性在每种情况下所应执行的操作,在算法中都在每种情况下所应执行的操作,在算法中都有确定的规定,使算法的执行者或阅读者都能明确其含义有确定的规定,使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下,算法都只有一条执行路及如何执行。并且在任何条件下,算法都只有一条执行路径。径。.可行性算法中的所以操作都必须足够基本,都可以算法中的所以操作都必须足够基本,都可以通过已经实现的基本操作运算有限次实现之。通过已经实现的基本操作运算有限次实现之。4.有输入作为算法加工对象的量值,通常体现为算法中作为算法加工对象的量值,通常体现为算法中的一组变量,有些输入量需要在算法执行过程中输入,而的一组变量,有些输入量需要在算法执行过程中输入,而有的算法表面上可以没有输入,实际上已经被嵌入算法之有的算法表面上可以没有输入,实际上已经被嵌入算法之中。中。5.有输出它是一组与它是一组与“输入输入”有确定关系的量值,是算有确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法法进行信息加工后得到的结果,这种确定关系即为算法的功能。的功能。描述算法的书写规则描述算法的书写规则v所有算法均以函数形式给出,算法的输入数据来自参数表v参数表的参数在算法之前均进行类型说明v有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明评价算法标准(设计算法时,通常要考虑到达的目标)算法的正确性,可读性,可维护性,健壮性等.二、算法效率的衡量方法和准则二、算法效率的衡量方法和准则 通常有两种衡量算法效率的方法(1)事后统计的方法 缺点:1、必须执行程序 2、其他因素掩盖算法本质(2)事前分析估算的方法与算法执行时间相关的因素:v算法选用的策略v问题的规模v编写程序的语言v编译程序产生的机器代码的质量v计算机执行指令的速度一个特定算法的“运行工作量”的大小,只依赖于问题的规模(通常用整数n表示),或者说,它是问题规模的函数。假如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同。则可记作:T(n)=O(f(n)如何估算算法的渐进时间复杂度:算法控制结构原操作(固有数据类型的操作)算法的执行时间原操作(i)的执行次数原操作(i)的执行时间(定值,可忽略)算法的执行时间与原操作执行次数之和成正比,通称为算法的时间复杂度。1 1 算法时间复杂度算法时间复杂度T T(n n)从算法中选取一种对于所研究的问题来说是从算法中选取一种对于所研究的问题来说是基本操作基本操作的原操作的原操作,以该基本操作在算法中重复执行的次数作为算法以该基本操作在算法中重复执行的次数作为算法运行时间的衡量标准运行时间的衡量标准。O O(n n3 3)称为矩阵相乘算法称为矩阵相乘算法时间复杂度时间复杂度;O O(n n3 3)表示矩阵相乘算法执行时间与表示矩阵相乘算法执行时间与n n3 3成正比成正比,即即O O(n n3 3)与与n n3 3 同一数量级;同一数量级;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 n3 3 例例 矩阵相乘的基本运算:乘法矩阵相乘的基本运算:乘法 加法;加法;有些算法,基本操作执行次数与问题的输入数据有有些算法,基本操作执行次数与问题的输入数据有关,这时可考虑关,这时可考虑 (1 1)算法平均时间复杂度算法平均时间复杂度 (2 2)算法在最坏情况下的时间复杂度算法在最坏情况下的时间复杂度 100100元买元买100100支笔支笔,其中钢笔其中钢笔 3 3元元/支支,圆珠笔圆珠笔 2 2元元/支支,铅笔铅笔 0.50.5元元/支支.写算法输出各种组合方案。写算法输出各种组合方案。例例?解法解法1#define N 100void scheme()int i,j,k,count,money;for(i=0;i=N;i+)for(j=0;j=N;j+)for(k=0;k=N;k+)count=i+j+k;money=3*i+2*j+0.5*k;if(count=N&money=N)printf(“%d,%d,%d n%”,i,j,k);算法的时间复杂度为算法的时间复杂度为O(NO(N3 3)解法解法2#define N 100#define N 100Void scheme()Void scheme()intint i,j;i,j;for(i=0;i=N/3;i+)for(i=0;i=N/3;i+)for(j=0;j=(N-3*i)/2;j+)for(j=0;j=(N-3*i)/2;j+)if(3*i+2*j+0.5*(N-i-j)=N)if(3*i+2*j+0.5*(N-i-j)=N)printf(printf(“%d%d,%d,%dn%,%d,%dn%”,i,j,N-i-,i,j,N-i-j);j);时间复杂度为时间复杂度为O(NO(N2 2)1.1.2 2 算法空间复杂度算法空间复杂度S(nS(n)2.算法的存储量包括:算法的存储量包括:输入数据所占的空间;输入数据所占的空间;程序本身所占的空间;程序本身所占的空间;辅助变量所占的空间。辅助变量所占的空间。在本课程中,用执行算法所需的辅助空间的在本课程中,用执行算法所需的辅助空间的大小作为算法所需空间的度量。大小作为算法所需空间的度量。设执行算法所需的辅助空间是问题规模设执行算法所需的辅助空间是问题规模n n的某个函数的某个函数g(ng(n),),则算法空间复杂度记作:则算法空间复杂度记作:S S(n n)=O(g(nO(g(n)表示算法辅助空间的增长率表示算法辅助空间的增长率与与g(n)的增长率相同的增长率相同例例计算计算 解法解法1 1 先计算先计算x x 的幂的幂,存于存于power power 中中,再分别乘以相应的系数再分别乘以相应的系数#define N 100#define N 100 float evaluate(float float evaluate(float coefcoef,float x,float x,intint n)n)float powerN,f;float powerN,f;intint i;i;for(power 0=1,i=1;i=n;i+)for(power 0=1,i=1;i=n;i+)poweripoweri=x*poweri-1;=x*poweri-1;for(f=0,i=0;i=N;i+)for(f=0,i=0;i=0;i-),i=n-1;i=0;i-)f=f*f=f*x+coefix+coefi;return(f);return(f);时间复杂度为时间复杂度为O(n).O(n).空间复杂度为空间复杂度为O(1)O(1)v理解什么是数据结构,数据结构这门课程所研究的内容;v理解数据结构这门课程的一些基本概念,掌握数据结构的分类和表示;v理解抽象数据类型含义和表示v学会算法的时间复杂度和空间复杂度的分析返回目录
收藏