《数据结课程的内容》由会员分享，可在线阅读，更多相关《数据结课程的内容（44页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程的内容数据结构课程的内容1讨论：讨论： 已知已知L L是无表头结点的单链表，且是无表头结点的单链表，且P P结点既不是首结点既不是首元结点，也不是尾元结点，请写出在元结点，也不是尾元结点，请写出在P P结点后插结点后插入入S S结点的核心语句序列。结点的核心语句序列。答：答：此题答案不唯一。此题答案不唯一。法二：已知法二：已知P结点，则不必结点，则不必“顺藤摸瓜顺藤摸瓜”，直接链接，直接链接即可。即可。(4)S-next=P-next;(1)P-next=S;法一：从头法一：从头“摸摸”起：起：(7)Q=P;(11)P=L;(8)while(P-next!=Q)P=P-next;(
2、10)P=Q;(4)S-next=P-next;(1)P-next=S;23.1栈（栈（Stack）第三章第三章栈和队列栈和队列3.2队列队列（Queue）1.定义定义2.逻辑结构逻辑结构3.存储结构存储结构4.运算规则运算规则5.实现方式实现方式1.定义定义2.逻辑结构逻辑结构3.存储结构存储结构4.运算规则运算规则5.实现方式实现方式31.定义定义3.1栈栈与同线性表相同，仍为一对一关系与同线性表相同，仍为一对一关系。用顺序栈或链栈存储均可，但以顺序栈更常见用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出只能在栈顶运算，且访问结点时依照后进先出（LIFO）或
3、先进后出（或先进后出（FILO）的原则。的原则。关键是编写入栈和出栈函数，具体实现依顺关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。序栈或链栈的不同而不同。基本操作有入栈、出栈、读栈顶元素值、建基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。栈、或判断栈满、栈空等。3.存储结构存储结构4.运算规则运算规则5.实现方式实现方式 2.逻辑结构逻辑结构限定只能在表的一端进行插入和删除运算的限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）线性表（只能在栈顶操作）4问：堆栈是什么？它与一般线性表有什么不同？问：堆栈是什么？它与一般线性表有什么不同？3.1栈栈答
4、：答：堆栈是一种特殊的线性表，它只能在表的一端堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。与一般线性表的区别：仅在于运算规则不同。一般线性表一般线性表堆栈堆栈逻辑结构：一对一逻辑结构：一对一逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序表、链表存储结构：顺序栈、链栈存储结构：顺序栈、链栈运算规则：随机存取运算规则：随机存取运算规则：后进先出运算规则：后进先出(LIFO)“进进”压入压入=PUSH（x)“出出”弹出弹出=POP(y)5栈栈是仅在是仅在表尾表尾进行插入、删除操作的线
5、性表。进行插入、删除操作的线性表。表尾表尾(即即an端端)称为称为栈顶栈顶top;表头表头(即即a1端端)称为称为栈底栈底base例如：例如：栈栈s=(a1,a2,a3,.,an-1,an)a1称为称为栈底元素栈底元素an称为称为栈顶元素栈顶元素插入元素到插入元素到栈顶栈顶（即表尾）的操作，称为（即表尾）的操作，称为入栈入栈。从从栈顶栈顶（即表尾）删除最后一个元素的操作，称为（即表尾）删除最后一个元素的操作，称为出栈出栈。教材教材P44P44对对栈栈有更详细定义：有更详细定义：强调：强调：插入和删除都只能在表的一端（栈顶）进行！插入和删除都只能在表的一端（栈顶）进行！6顺序栈示意图顺序栈示意图
6、s a1 a2 a3dataa4(栈底栈底)(栈顶栈顶)99.3210top7 a1 a2 an顺序栈顺序栈Sai表和栈的操作区别表和栈的操作区别对线性表对线性表s=(a1,a2,.,an-1,an)表头表头表尾表尾栈底栈底base栈顶栈顶top低地址低地址高地址高地址写入：写入：vi=ai读出：读出：x=vi压入：压入：PUSH(an+1)弹出：弹出：POP(x)前提：一定要预设栈顶指针前提：一定要预设栈顶指针top！低地址低地址高地址高地址vi a1 a2ai an 顺序表顺序表Vn an+18入栈操作入栈操作例如用堆栈存放（例如用堆栈存放（A A，B B，C C，D D） （注意要遵循注
7、意要遵循“后进先出后进先出” ” 原则）原则）AACBABAtop核心语句：核心语句：top=L; 顺序栈中的顺序栈中的PUSHPUSH函数函数status Push(ElemType x) if(topM)上溢 else vtop+top+=x;Push (B);Push (C);Push (D);toptoptoptop低低地址地址LPush (A);高地址高地址MBCD9 出栈操作出栈操作例如从栈中取出例如从栈中取出BB （注意要遵循注意要遵循“后进先出后进先出” ” 原则）原则）DCBAtoptopDCABDCBAtopDCBAtoptop低低地址地址L高地址高地址MD核心语句：核心语
8、句：Pop();Pop();Printf(Pop();顺序栈中的顺序栈中的POPPOP函数函数status Pop( )status Pop( ) if(top=L) if(top=L) 下溢下溢 else y=velse y=v-top-top; ; return(y); return(y); 10例例1：一个栈的输入序列是一个栈的输入序列是12345，若在入栈的过，若在入栈的过程中允许出栈程中允许出栈，则栈的输出序列则栈的输出序列43512可能实现可能实现吗吗？12345的输出呢？的输出呢？43512不不可可能能实实现现，主主要要是是其其中中的的12顺顺序序不不能能实现；实现；12345的
9、输出可以实现，只需压入一个立即弹的输出可以实现，只需压入一个立即弹出一个即可。出一个即可。 435612中到了中到了12顺序不能实现；顺序不能实现；135426可以实现。可以实现。例例2：如果一个栈的输入序列为如果一个栈的输入序列为123456，能否得，能否得到到435612和和135426的出栈序列？的出栈序列？答：答：答：答：11例例3（严题集（严题集3.1）一个栈的输入序列为一个栈的输入序列为123，若在，若在入栈的过程中允许出栈，则可能得到的出栈序列是入栈的过程中允许出栈，则可能得到的出栈序列是什么？什么？答：答： 可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解： 1 1入
10、入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入入3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合计有合计有5 5种可能性。种可能性。12例例4：计算机系计算机系2001年考研题（程序设计基础）年考研题（程序设计基础）设依次进入一个栈的元素序列为设依次进入一个栈的元
11、素序列为c，a，b，d，则则可得到出栈的元素序列是：可得到出栈的元素序列是：）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，bA、D可以可以（B、C不行）。不行）。讨论：有无通用的判别原则？讨论：有无通用的判别原则？有。在可能的输出序列中，不存在这样的输入序列有。在可能的输出序列中，不存在这样的输入序列i i，j j，k k，能同时满足能同时满足 ijk ijk 和和 PjPj PkPkPidata=x;p-link=st;st=p; S Status pop( ) pop( ) if(stif(st=NULL)=NULL)下溢下溢 elsey=elsey=stst-dat
12、a;p=-data;p=st;stst;st= =stst-link; -link; free(p); return(y);free(p); return(y); 链栈链栈入栈入栈函数函数链栈链栈出栈出栈函数函数插入插入表头表头从表头从表头删除删除17 链栈不必设头结点，因为栈顶（表头）操作链栈不必设头结点，因为栈顶（表头）操作链栈不必设头结点，因为栈顶（表头）操作链栈不必设头结点，因为栈顶（表头）操作频繁；频繁；频繁；频繁；采用链栈存储方式，可使多个栈共享空间；采用链栈存储方式，可使多个栈共享空间；采用链栈存储方式，可使多个栈共享空间；采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化
13、较大，且存在多个栈的当栈中元素个数变化较大，且存在多个栈的当栈中元素个数变化较大，且存在多个栈的当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。情况下，链栈是栈的首选存储方式。情况下，链栈是栈的首选存储方式。情况下，链栈是栈的首选存储方式。说说明明18问：为什么要设计堆栈？它有什么独特用途？问：为什么要设计堆栈？它有什么独特用途？1.调用函数或子程序非它莫属；调用函数或子程序非它莫属；2.递归运算的有力工具；递归运算的有力工具；3.用于保护现场和恢复现场；用于保护现场和恢复现场；4.简化了程序设计的问题简化了程序设计的问题。答：答：19数制转换（十转数制转换（十转N）P4
14、8设计思路：用栈暂存低位值设计思路：用栈暂存低位值例例2：括号匹配的检验括号匹配的检验P49设计思路：用栈暂存左括号设计思路：用栈暂存左括号例例3：表达式求值表达式求值-P52设计思路：用栈暂存运算符设计思路：用栈暂存运算符例例4：汉诺仪（汉诺仪（Hanoi）塔）塔-P55设计思路：用栈实现递归调用设计思路：用栈实现递归调用例例1：20例例3表达式求值表达式求值(这是栈应用的典型例子这是栈应用的典型例子)这里，这里，表达式求值的算法是表达式求值的算法是“算符优先法算符优先法”。例如：例如：3*（72）（1）要正确求值，首先了解算术四则运算的规则：）要正确求值，首先了解算术四则运算的规则：a.从
15、左算到右从左算到右b.先乘除，后加减先乘除，后加减c.先括号内，后括号外先括号内，后括号外由此，此表达式的计算顺序为：由此，此表达式的计算顺序为：3*（72）=3*5=1521（2）根据上述三条运算规则，在运算的每一步中，对）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符任意相继出现的算符 1和和 2，都要比较优先权关系。都要比较优先权关系。算符优先法所依据的算符间的优先关系算符优先法所依据的算符间的优先关系见教材见教材P53表表3.1（是提供给计算机用的表！）（是提供给计算机用的表！）由表可看出，右括号由表可看出，右括号)和井号和井号#作为作为 2时时级别最低；级别最低；由由c
16、规则规则得出：得出：*，/，+，-为为 1时的优先权低于时的优先权低于（，高于，高于）由由a规则规则得出：得出：（=）表明括号内运算，已算表明括号内运算，已算完。完。#=#表明表达式求值完毕。表明表达式求值完毕。栈的应用（表达式求值）栈的应用（表达式求值）22（3）算法思想：）算法思想：设定两栈：设定两栈：操作符栈操作符栈OPTR，操作数栈操作数栈OPND栈初始化栈初始化：设操作数栈：设操作数栈OPND为空；操作符栈为空；操作符栈OPTR的栈的栈底元素为表达式起始符底元素为表达式起始符#；依次读入字符依次读入字符：是操作数则入：是操作数则入OPND栈，栈，是操作符则要判断：是操作符则要判断：i
17、f操作符操作符栈顶元素栈顶元素，压入，压入OPTR栈。栈。栈的应用（表达式求值）栈的应用（表达式求值）23栈的应用（表达式求值）栈的应用（表达式求值）OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#Ge
18、tTop(opnd)24StatusEvaluateExpression(OperandType&result)InitStack(OPND);InitStack(OPTR);Push(OPTR,#);c=getchar();while(c!=#)&(GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getchar();elseswitch(compare(c,GetTop(OPTR)case:Push(OPTR,c);c=getchar();break;case=:Pop(OPTR);c=getchar();break;case1时时,则则设法将设法将前前
19、n1个盘子个盘子借助借助z，从从x移移到到y柱上，把柱上，把盘子盘子n从从x移到移到z柱上；柱上；把把n1个盘子个盘子从从y移到移到z柱上。柱上。x y zx y znn126VoidHanoi(intn,charx,chary,charz)/将将n个个编号从上到下为编号从上到下为1n的盘子从的盘子从x柱，借助柱，借助y柱移到柱移到z柱柱if(n=1)move(x,1,z);/将编号为将编号为1的的盘子盘子从从x柱移到柱移到z柱柱else/将将n-1个个编号从上到下为编号从上到下为1n-1的盘子从的盘子从x柱，借助柱，借助y柱移到柱移到z柱柱Hanoi(n-1,x,z,y);move(x,n,
20、z);/将编号为将编号为n的的盘子盘子从从x柱移到柱移到z柱柱/将将n-1个个编号从上到下为编号从上到下为1n-1的盘子从的盘子从y柱，借助柱，借助x柱移到柱移到z柱柱Hanoi(n-1,y,x,z);/Hanoi271.定定义义3.2队列队列与同线性表相同，仍为一对一关系与同线性表相同，仍为一对一关系。顺序队顺序队或或链队链队，以循环顺序队更常见。，以循环顺序队更常见。只能在队首和队尾运算，且访问结点时依照只能在队首和队尾运算，且访问结点时依照先进先出先进先出（FIFO）的原则。的原则。关键是掌握关键是掌握入队入队和和出队出队操作，具体实现依顺操作，具体实现依顺序队或链队的不同而不同。序队或
21、链队的不同而不同。基本操作有入队或出队，建空队列，判队空基本操作有入队或出队，建空队列，判队空或队满等操作。或队满等操作。3.存储结构存储结构4.运算规则运算规则5.实现方式实现方式 2.逻辑结构逻辑结构只能在表的一端进行插入运算，在表的另一只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表端进行删除运算的线性表（头删尾插头删尾插）28队列队列 （QueueQueue）是仅在是仅在表尾表尾进行插入操作，在进行插入操作，在表头表头进行删进行删除操作的线性表。除操作的线性表。表尾即表尾即an端，称为端，称为队尾队尾；表头即表头即a1端，称为端，称为队头队头。它是一种先进先出（它是一种先进
22、先出（）的线性表。）的线性表。例如：队列例如：队列Q=(a1,a2,a3,.,an-1,an)插入元素称为插入元素称为入队入队；删除元素称为；删除元素称为出队出队。队头队头队尾队尾教材教材P59P59对队列有更详细定义：对队列有更详细定义：队列的抽象数据类型定义见教材队列的抽象数据类型定义见教材5960队列的存储结构为队列的存储结构为链队链队或或顺序队顺序队（常用循环顺序队）（常用循环顺序队）29链队列示意图链队列示意图讨论：讨论：空队列的特征？空队列的特征？Q(队尾队尾)(队首队首)fronta1a2a3rearpfrontrear怎样实现入队和出队操作？怎样实现入队和出队操作？入队（尾部插
23、入）：入队（尾部插入）：rear-next=S;rear=S;出队（头部删除）：出队（头部删除）：front-next=p-next;完整动作设计参完整动作设计参见教材见教材P61-62队列会满吗？队列会满吗？front=rear一般不会，因为删除时有一般不会，因为删除时有free动作。除非内存不足！动作。除非内存不足！30顺序队示意图顺序队示意图Q(队尾队尾)(队首队首)front a1 a2 a3dataa40.99rear队列会满吗？队列会满吗？很可能会，因为数组前很可能会，因为数组前端空间无法释放端空间无法释放。因此因此数组应当有长度限制。数组应当有长度限制。空队列的特征？空队列的特征
24、？约定：约定：front=rear队尾后地址队尾后地址入队入队(尾部插入尾部插入)：vrear=e;rear+;出队出队(头部删除头部删除)：x=vfront;front+;讨论：讨论：假溢假溢假溢假溢出出出出有有缺缺陷陷怎样实现入队和怎样实现入队和出队操作？出队操作？3.2队列队列31问：什么叫问：什么叫“假溢出假溢出”？如何解决？如何解决？答：答：在顺序队中，当尾指针已经到了数组在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫中还有空位置，这就叫“假溢出假溢出”。3.2队列队列解决假溢出的途径解决假溢出的途径采用循
25、环队列采用循环队列32a3a2a10123N-1rearfront循环队列（臆造）循环队列（臆造）循环队列（臆造）循环队列（臆造）顺序队列顺序队列顺序队列顺序队列a3a2a1frontrear 0 1 2 3 . .N-1新问题：新问题：在循环队列中，空队特征是在循环队列中，空队特征是front=rear；队满时也会有队满时也会有front=rear；判决条件将出现二义性！判决条件将出现二义性！解决方案有三：解决方案有三：加设标志位，让删除动作使其为加设标志位，让删除动作使其为1,插入动作使其为插入动作使其为0,则可识别当前则可识别当前front=rear使用一个计数器记录队列中元素个数（即队
26、列长度）；使用一个计数器记录队列中元素个数（即队列长度）；人为浪费一个单元，令人为浪费一个单元，令队满特征为队满特征为front=(rear+1)%N；33队空条件队空条件:front=rear(初始化时：初始化时：front=rear)队满条件队满条件：front=(rear+1)%N(N=maxsize)队列长度：队列长度：L=（Nrearfront）%NJ2J3J1J4J5frontrear选用选用空闲单元法：空闲单元法：即即front和和rear之一指向实元素，另一指向空闲元素。之一指向实元素，另一指向空闲元素。 问问2：在具有在具有n个单元的循个单元的循环队列中，队满时共有多少环队列
27、中，队满时共有多少个元素？个元素？n-1个个6问问1：左图中队列长度左图中队列长度L=？34J6J5J7J8J9例例1：一循环队列如下图所示，若先删除一循环队列如下图所示，若先删除4个元素，接着再个元素，接着再插入插入4个元素，请问队头和队尾指针分别指向哪个位置个元素，请问队头和队尾指针分别指向哪个位置?J2J3J1J4J5frontrear解：解：由图可知，队头和队尾指针的初态分别为由图可知，队头和队尾指针的初态分别为front=1和和rear=6。frontrear删除删除4个元素后个元素后front=5；再插入再插入4个元素后，个元素后，r=(6+4)%6=4frontfrontfron
28、tfrontfront35例例2：数组数组n用来表示一个循环队列，用来表示一个循环队列，f为当前队列头为当前队列头元素的元素的前一前一位置，位置，r为队尾元素的位置。假定队列中元素的为队尾元素的位置。假定队列中元素的个数小于个数小于n，计算队列中元素的公式为计算队列中元素的公式为:（）（）rf（）（）（nfr）%n（）nrf（）（nrf）%n4种公式哪种合理？种公式哪种合理？当当rf时（时（A）合理；合理；当当rf时（时（C）合理；合理；分析分析：综合综合2种情况，以种情况，以（D）的表达最为合理的表达最为合理例例3：在一个循环队列中，若约定队首指针指向队首元素在一个循环队列中，若约定队首指针
29、指向队首元素的的前一个前一个位置。那么，从循环队列中删除一个元素时，其位置。那么，从循环队列中删除一个元素时，其操作是操作是先先，后，后。移动队首指针移动队首指针取出元素取出元素36问：为什么要设计队列？它有什么独特用途？问：为什么要设计队列？它有什么独特用途？1.离散事件的模拟（模拟事件发生的先后顺序）；离散事件的模拟（模拟事件发生的先后顺序）；2.操作系统中多道作业的处理（一个操作系统中多道作业的处理（一个CPU执行多个作执行多个作业）；业）；3.简化程序设计。简化程序设计。答：答：循环队列的操作实现循环队列的操作实现见教材见教材P64P6437循环队列的操作实现循环队列的操作实现1）初始
30、化一空队列初始化一空队列算法要求：生成一空队列算法要求：生成一空队列算法操作：为队列分配基本容量空间算法操作：为队列分配基本容量空间设置队列为设置队列为空队列空队列，即即front=rear=0（也可为任意单元，如也可为任意单元，如2，或，或4）;38算法：算法：StatusInitQueue(SqQueue&q)/初始化空循环队列初始化空循环队列qq.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);/分配空间分配空间if(!q.base)exit(OVERFLOW);/失败，退出程序失败，退出程序q.front=q.rear=
31、0;/置空队列置空队列returnOK;/InitQueue;新开单元的地址为新开单元的地址为0则表示内存不足则表示内存不足39算法说明：向循环队列的队尾插入一个元素算法说明：向循环队列的队尾插入一个元素分分析析：(1)插入前应当先判断队列是否满插入前应当先判断队列是否满if(q.rear+1)%QUEUE_MAXSIZE)=q.front)returnERROR;(2）插入动作插入动作q.baseq.rear=e;q.rear=(q.rear+1)%QUEUE_MAXSIZE;2）入队操作入队操作40StatusEnQueue(SqQueue&q,QElemTypee)/向循环队列向循环队列
32、q的队尾加入一个元素的队尾加入一个元素eif(q.rear+1)%QUEUE_MAXSIZE=q.front)returnERROR;q.baseq.rear=e;/存储存储q.rear=(q.rear+1)%QUEUE_MAXSIZE;/指针后移指针后移returnOK;/EnQueue;2）入队操作（完整函数）入队操作（完整函数）413）出队操作）出队操作算法说明：删除队头元素，返回其值算法说明：删除队头元素，返回其值e分分析：析：（1）在删除前应当判断队列是否空；在删除前应当判断队列是否空；if(q.front=q.rear)returnERROR;（2）插入动作分析；插入动作分析；因为
33、队头指针因为队头指针front指向队头元素的位置，所以：指向队头元素的位置，所以：e=q.baseq.front;q.front=(q.front+1)%QUEUE_MAXSIZE;42StatusDeQueue(SqQueue&q,QElemType&e)/若队列不空，删除循环队列若队列不空，删除循环队列q的队头元素，的队头元素，/由由e返回其值，并返回返回其值，并返回OKif(q.front=q.rear)returnERROR;/队列空队列空e=q.baseq.front;q.front=(q.front+1)%QUEUE_MAXSIZE;returnOK;/DeQueue算法：算法：4
34、3讨论（代本讨论（代本章章小结）小结）线性表、栈与队的异同点线性表、栈与队的异同点相相同同点点：逻逻辑辑结结构构相相同同，都都是是线线性性的的；都都可可以以用用顺顺序序存存储储或或链链表表存存储储；栈栈和和队队列列是是两两种种特特殊殊的的线线性性表表，即即受受限限的的线线性表性表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。不同点：不同点： 运运算算规规则则不不同同，线线性性表表为为随随机机存存取取，而而栈栈是是只只允允许许在在一一端端进进行行插插入入和和删删除除运运算算，因因而而是是后后进进先先出出表表LIFOLIFO；队队列列是是只只允允许许在在一一端端进进行行插插入入、另另一一端端进进行行删删除除运运算算，因因而而是先进先出表是先进先出表FIFOFIFO。 用途不同，线性表比较通用；堆栈用于函数调用、递归用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。和简化设计等。44
