《ch3--栈-队列-数组.ppt》由会员分享，可在线阅读，更多相关《ch3--栈-队列-数组.ppt（114页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构数据结构Data StructureData Structure 张先宜 13909696718 第3章 栈 队列 数组n3.1 栈栈n3.2 队列队列n3.3 数组数组n3.4 栈的应用栈的应用栈和递归栈和递归 n栈栈和和队列队列也是线性表，是也是线性表，是操作受限操作受限的特殊的线性的特殊的线性表。线性表的插入、删除操作是不受限制的；而表。线性表的插入、删除操作是不受限制的；而栈的插入、删除操作只能在表的同一端进行；队栈的插入、删除操作只能在表的同一端进行；队列的插入操作在表的一端进行，删除操作在表的列的插入操作在表的一端进行，删除操作在表的另一端进行。另一端进行。n但从但从数据类
2、型数据类型角度看，它们是和线性表不相同的角度看，它们是和线性表不相同的两种重要的数据结构。在计算机科学和程序设计两种重要的数据结构。在计算机科学和程序设计中有广范的应用。中有广范的应用。3.1 栈n栈（栈（Stack）栈是一种基本的、重要的、应用广泛的数据）栈是一种基本的、重要的、应用广泛的数据结构。结构。n栈是按栈是按“先进后出先进后出”操作方式组织的数据结构。操作方式组织的数据结构。n日常生活中栈操作方式实例：日常生活中栈操作方式实例：F洗碗摞一堆；书摞成一堆；一些枪支子弹夹中子弹的操作方洗碗摞一堆；书摞成一堆；一些枪支子弹夹中子弹的操作方式等。式等。n计算机中栈的应用实例：计算机中栈的应
3、用实例：F许多类型许多类型CPU的内部就构建了栈；的内部就构建了栈；F在操作系统、编译器、虚拟机等系统软件中栈都有重要的应在操作系统、编译器、虚拟机等系统软件中栈都有重要的应用，比如，函数调用、语法检查等。用，比如，函数调用、语法检查等。F在应用软件设计和实际问题求解中更是经常会用到栈结构，在应用软件设计和实际问题求解中更是经常会用到栈结构，比如，表达式求解、回溯法求解问题、递归实现、递归算法比如，表达式求解、回溯法求解问题、递归实现、递归算法转换为非递归、树和图搜索的非递归实现等。转换为非递归、树和图搜索的非递归实现等。3.1.1 栈的基本概念n栈（栈（Stack）F是限定只能在一端插入和删
4、除元素的线性表。是限定只能在一端插入和删除元素的线性表。n栈顶（栈顶（top）F进行插入和删除操作的一端成为栈顶。进行插入和删除操作的一端成为栈顶。n栈底（栈底（bottom）F另一端成为栈底。另一端成为栈底。n入栈（入栈（push）F栈的插入操作叫入栈（压栈）。栈的插入操作叫入栈（压栈）。n出栈（出栈（pop），），F栈的删除操作叫出栈（弹栈）。栈的删除操作叫出栈（弹栈）。a1a2anana2a1a1 a2 an an an-1 a1入栈(PUSH)出栈(POP)栈顶(top)栈底(bottom)n栈的特性栈的特性F后进先出后进先出(LIFO-Last In First Out)，或，或F先
5、进后出先进后出(FILO-First In Last Out)n栈是栈是操作受限操作受限的线性表。的线性表。3.1.2 栈的基本运算n栈的基本运算与线性表的基本运算类似，但又有栈的基本运算与线性表的基本运算类似，但又有其特殊之处。其特殊之处。n(1)初始化栈：初始化栈：initialStack(S)F设置栈设置栈S S为空栈。为空栈。n(2)判断栈是否为空：判断栈是否为空：stackEmpty(S)F若栈若栈S S为空，返回为空，返回TRUETRUE，否则，返回，否则，返回FALSEFALSE。n(3)取栈顶元素值：取栈顶元素值：stackTop(S,x)F若栈若栈S S不空，将栈不空，将栈S
6、 S的栈顶元素的值送变量的栈顶元素的值送变量x x中，否中，否则应返回出错信息。则应返回出错信息。n(4)判断栈是否为满：判断栈是否为满：stackFull(S)F栈栈S为满时，返回为满时，返回TRUE，否则，返回，否则，返回FALSE。n(5)入栈：入栈：pushStack(S,x)F将值为将值为x的元素插入到栈的元素插入到栈S中。若插入前的栈已经中。若插入前的栈已经满了，不能入栈时，应报出错信息。满了，不能入栈时，应报出错信息。n(6)出栈：出栈：popStack(S)F若栈若栈S不空，删除栈不空，删除栈S的栈顶元素，否则应返回出的栈顶元素，否则应返回出错信息。错信息。3.1.3 顺序栈n
7、1.顺序栈存储结构顺序栈存储结构 采用顺序表来存储的栈采用顺序表来存储的栈#define MaxLen 100 /最大容量最大容量typedef struct elementType dataMaxLen;/存放栈元素存放栈元素 int top;/指示栈顶元素的位置指示栈顶元素的位置 seqStack;ana4a3a2a10 1 2 3 n-1 MaxLen-1 datatopseqStackn2.顺序栈上运算的实现顺序栈上运算的实现n(1)初始化初始化:void initStack(seqStack*S)S-top=-1;ana4a3a2a10 1 2 3 n-1 MaxLen-1 data
8、topseqStackn(2)判栈空判栈空:BOOL stackEmpty(seqStack S)if(S.top=-1)return true;else return false;F以上代码可以用一条语句：以上代码可以用一条语句：return(S.top=-1);ana4a3a2a10 1 2 3 n-1 MaxLen-1 datatopseqStackn(3)判栈满判栈满:BOOL stackFull(seqStack S)if(S.top=MaxLen-1)return TRUE;/栈满，返回栈满，返回true else return FALSE;/栈不满，返回栈不满，返回falsean
9、a4a3a2a10 1 2 3 n-1 MaxLen-1 datatopseqStackn(4)读栈顶元素读栈顶元素:void stackTop(seqStack*S,elementType&x)if(S-top=-1)error(“栈空栈空”);else x=S-dataS-top;/参数参数x返回栈顶元素返回栈顶元素ana4a3a2a10 1 2 3 n-1 MaxLen-1 datatopseqStackn(5)入栈入栈:void pushStack(seqStack*S,elementType x)if(S-top=MaxLen-1)error(“栈满栈满”);else S-top+;
10、/栈顶后移栈顶后移 S-data S-top=x;/元素元素x入栈入栈 n(6)出栈出栈:void popStack(seqStack*S,elementType&x)if (stackEmpty(*S)error(“栈空栈空,不能删除不能删除”);else x=S-dataS-top;/取栈顶元素至取栈顶元素至x S-top-;/栈顶减栈顶减1，即删除了栈顶元素，即删除了栈顶元素 /可用一行代码：可用一行代码：x=S-dataS-top-;n3.顺序栈特点顺序栈特点F所有运算的时间复杂度均为所有运算的时间复杂度均为O(1)；F通常一次性申请空间，只能按最大空间需求分配，通常一次性申请空间，只
11、能按最大空间需求分配，容易造成空间浪费。容易造成空间浪费。-使用链式栈。使用链式栈。F本教材使用数组实现简单易理解，也可以使用本教材使用数组实现简单易理解，也可以使用malloc()或或new申请一块连续的空间实现，但处理和操作申请一块连续的空间实现，但处理和操作较复杂。较复杂。3.1.4 链栈n链栈即采用链式存储结构实现的的栈。链栈即采用链式存储结构实现的的栈。n链栈可用单链表结构来表示。结点结构同单链表。链栈可用单链表结构来表示。结点结构同单链表。n链栈既可以带头结点，也可以不带头结点。链栈既可以带头结点，也可以不带头结点。n在这种表示中，同样要注意栈顶位置的选择。在这种表示中，同样要注意
12、栈顶位置的选择。F不带头结点，栈顶指针不带头结点，栈顶指针top指示有元素结点；指示有元素结点；F带有节点，栈顶指针带有节点，栈顶指针top-next指示首元素结点；指示首元素结点；F事实上，这里的栈顶指针事实上，这里的栈顶指针top即单链表的头指针即单链表的头指针（只是叫法不同）。（只是叫法不同）。data数据元素数据元素next直接后继的地址直接后继的地址数据域数据域指针域指针域n链栈既可以带头结点，也可以不带头结点。链栈既可以带头结点，也可以不带头结点。a1a2an an-1toptop不带头结点的非空链栈不带头结点的非空链栈栈顶指针栈顶指针栈底栈底栈顶结点栈顶结点toptopa1a2a
13、n 头结点头结点带头结点的带头结点的非空链栈非空链栈toptop 头结点头结点带头结点的带头结点的空链栈空链栈栈顶指针栈顶指针栈顶结点栈顶结点栈底栈底栈顶指针栈顶指针n链栈的结点存储同单链表链栈的结点存储同单链表typedef struct lsNodeelementType data;/链栈结点数据域链栈结点数据域struct lsNode*next;/链栈结点指针域链栈结点指针域 sNode,*linkedStack;n不带头结点链栈的基本运算不带头结点链栈的基本运算(1)初始化栈初始化栈F由于不带头结点，初始化仅需将栈顶指针置为空。由于不带头结点，初始化仅需将栈顶指针置为空。【算法描述算
14、法描述】void initialStack(sNode*&top)top=NULL;(2)入栈入栈【算法描述算法描述】void pushStack(sNode*&top,elementType x)sNode*s;s=new sNode;/申请新结点申请新结点s-data=x;/装入元素值装入元素值s-next=top;/新结点链接到栈新结点链接到栈top=s;/更新栈顶指针，使指向新结点更新栈顶指针，使指向新结点(3)出栈出栈bool popStack(sNode*&top,elementType&x)sNode*u;if(top=NULL)return false;/栈空，返回栈空，返回f
15、alse else x=top-data;/取栈顶元素，由变量取栈顶元素，由变量x返回返回 u=top;/栈顶指针保存到栈顶指针保存到u top=top-next;/栈顶指针后移一个元素结点栈顶指针后移一个元素结点 delete u;/释放原栈顶结点释放原栈顶结点 return true;/出栈成功，返回出栈成功，返回truen不带头结点链栈的其他基本运算请您自行完成。不带头结点链栈的其他基本运算请您自行完成。n带头结点的链栈的初始化、插入、删除操作同带带头结点的链栈的初始化、插入、删除操作同带头结点的单链表。头结点的单链表。n带头结点链栈的基本运算请您自行完成。带头结点链栈的基本运算请您自行
16、完成。n栈的链式存储结构（链式栈）特点：栈的链式存储结构（链式栈）特点：F使用连续或不连续的存储空间；使用连续或不连续的存储空间；F各数据元素独立存储，依靠指针链接建立逻辑相邻各数据元素独立存储，依靠指针链接建立逻辑相邻关系；关系；F 对每个数据元素单独申请结点空间；对每个数据元素单独申请结点空间；F 由于动态申请空间，没有栈满溢出问题；由于动态申请空间，没有栈满溢出问题；F 栈顶指针栈顶指针 top 唯一确定一个链式栈；唯一确定一个链式栈；F 链式栈也可以加同构头结点，这种情况下：链式栈也可以加同构头结点，这种情况下：Top-next 指向栈顶元素；指向栈顶元素；若若 top-next 为为
17、 NULL，则为一空栈。，则为一空栈。F 如果同时需要如果同时需要2个以上栈，最好使用链式栈。个以上栈，最好使用链式栈。3.1.5 栈的应用实例1.栈的基本应用实例栈的基本应用实例【例例3.1】输入输入n个整数，逆序输出。个整数，逆序输出。【分析分析】利用栈结构的利用栈结构的FILO特性，输入时采用循环特性，输入时采用循环入栈，输出采用循环出栈。入栈，输出采用循环出栈。【实现代码实现代码】ex31readWrite.cppcoutn;cout请输入数据元素请输入数据元素:endl;for(int i=1;ix;pushStack(S,x);cout逆序输出：逆序输出：;/逆序输出逆序输出whi
18、le(!stackEmpty(S)/n个整数循环出栈个整数循环出栈stackTop(S,x);/取栈顶元素取栈顶元素coutxnext;/L移动指向为逆置的下一结点移动指向为逆置的下一结点ai+1u-next=P;/ai结点的结点的next指向指向p，形成逆置，形成逆置P=u;/p移动指向移动指向ai，P和和u皆指向已逆置的第一结点皆指向已逆置的第一结点L=P;/原表头指向新的表头原表头指向新的表头【解法二解法二】基于栈技术求解。基于栈技术求解。F定义一个顺序栈，栈元素为单链表的结点指针，循定义一个顺序栈，栈元素为单链表的结点指针，循环取出每个结点的指针，入栈。入栈后，原链表尾环取出每个结点的
19、指针，入栈。入栈后，原链表尾结点的指针存放在栈顶，首元素结点指针存放在栈结点的指针存放在栈顶，首元素结点指针存放在栈底。构建逆置链表时，将栈内的指针依次弹出，按底。构建逆置链表时，将栈内的指针依次弹出，按尾插法尾插法重建链表，这样就得到一个就地逆置的链表。重建链表，这样就得到一个就地逆置的链表。栈的元素类型要定义为栈的元素类型要定义为 typedef node*elementType。因为要采用尾插法，重建时要设置。因为要采用尾插法，重建时要设置一个尾指针。一个尾指针。F也可用链栈实现。也可用链栈实现。n【解法二实现解法二实现】ex32p1iListReverse.cppnan结点指针第一个出
20、栈，设为结点指针第一个出栈，设为u，它成为首元素结，它成为首元素结点，须做如下处理：点，须做如下处理：FL=u;FR=u;FL-next=NULL;n其它结点依次出栈，处理：其它结点依次出栈，处理：FR-next=u;/尾插当前结点尾插当前结点Fu-next=NULL;/尾结点尾结点next为空为空FR=u;/移动尾指针移动尾指针n最后出栈的是最后出栈的是a1结点的指针结点的指针 an结点指针结点指针 an-1结点指针结点指针 a2结点指针结点指针a1结点指针结点指针a1a2an an-1toptop【例例3.3】十进制数转换为八进制数。十进制数转换为八进制数。【分析分析】“除除8取余取余”方
21、法。设十进制数为方法。设十进制数为N，循环除，循环除8，取出余数，商，取出余数，商的整数部分重新赋给的整数部分重新赋给N，直至，直至N=0；F将最后的余数作为将最后的余数作为8进制数的最高位，第一个余数作为进制数的最高位，第一个余数作为8进制进制的最低位，得到的最低位，得到8进制数。即：余数逆（反）序输出。操作进制数。即：余数逆（反）序输出。操作过程如下图：过程如下图：F利用栈，每次余数入栈，结束时余数全部出栈即可得到利用栈，每次余数入栈，结束时余数全部出栈即可得到8进进制数。制数。n【问题问题】F十进制转换为二进制数呢？十进制转换为二进制数呢？F十进制转换为十六进制数呢？十进制转换为十六进制
22、数呢？F十进制转换为任意进制数呢？十进制转换为任意进制数呢？2813575152169821880void Dec2Ocx(int N)seqStack S;int Mod,x;initStack(S);/初始化初始化while(N!=0)Mod=N%8;/除除8取余数到取余数到Mod pushStack(S,Mod);/余数入栈余数入栈 N=N/8;/除除8取商，回存到取商，回存到N cout八进制数为：八进制数为：;/以下为出栈输出以下为出栈输出8进制数进制数while(!stackEmpty(S)popStack(S,x);/取栈顶元素入取栈顶元素入x，出栈，出栈 cout next=N
23、ULL;q.rear=q.front;frontrearqn(2)判队空判队空:BOOL queueEmpty(linkQueue&q)return(q.front=q.rear);/简略写法简略写法fronta1a2an 队头队尾rearn(3)取队头取队头:void queueFront(linkQueue&q,elementType&x)if(queueEmpty(q)error(“队列空队列空”);else x=q.front-next-data;fronta1a2an 队头队尾rearn(4)入队入队:void enQueue(linkQueue&q,elementType x)s=
24、new node;s-data=x;s-next=NULL;q.rear-next=s;/以下以下2句次序不能颠倒句次序不能颠倒 q.rear=s;/修改尾指针修改尾指针fronta1a2an 队头队尾rearxsn(5)出队（核心代码）出队（核心代码）u=q.front-next;/取队头指针取队头指针q.front-next=u-next;/修改队头指针修改队头指针delete u；/删除原来队头结点删除原来队头结点fronta1a2an 队头队尾rearun(5)出队（完整描述）出队（完整描述）void outQueue(linkQueue&q,elementType&x)if(q.fr
25、ont=q.rear)error(“下溢出下溢出”);else u=q.front-next;/队头队头 q.front-next=u-next;/修改队头修改队头 x=u-data;/取出队头元素值取出队头元素值 delete u；/删除原来队头删除原来队头 if(q.front-next=NULL)q.rear=q.front;/删除后成为空队列情况删除后成为空队列情况 3.2.6 队列的应用n【例例3.5】杨辉三角杨辉三角n【实现代码实现代码】ex35OutNumber11 121 2 13 3 3 141 4 6 4 155 10 10 5 161 6 15 20 15 6 171 7
26、 21 35 35 21 7 10n【分析分析】杨辉三角的规律是：杨辉三角的规律是：F每行的第一和最后一个数是每行的第一和最后一个数是1；F从第从第3行开始的其余的数是上一行对应位置的行开始的其余的数是上一行对应位置的左右左右两个数的和两个数的和。F例如，第例如，第7行的第行的第3个数个数15是第是第6行中的第行中的第2和第和第3两两个数个数5和和10的和。的和。F由这一规律可知，我们可用上一行的数来求出对应由这一规律可知，我们可用上一行的数来求出对应位置的下一行的内容。位置的下一行的内容。F为此，为此，可用队列来保存上一行的内容可用队列来保存上一行的内容。F每当由上一行的两个数求出下一行的一
27、个数时，其每当由上一行的两个数求出下一行的一个数时，其中的中的前一个便需要删除前一个便需要删除，而，而新求出的数就要入队新求出的数就要入队。n优先级队列优先级队列F插队、特权插队、特权n【布置作业布置作业】F（P87）F3.1、3.5、3.8、3.9、3.11寒雪梅中尽，春风柳上归。【唐.李白】3.3 数组n介绍数组的实现原理介绍数组的实现原理3.3.1 数组的定义和运算n1、数组（、数组（Array）的定义：）的定义：F有限个相同类型的变量组成的序列。有限个相同类型的变量组成的序列。若每个变量是一维数组，则为若每个变量是一维数组，则为二维数组二维数组；若每个变量是若每个变量是n-1维数组，则
28、为维数组，则为n维数组维数组。a11,a12,a1n a21,a22,a2na31,a32,a3n am1,am2,amnmn（a1,a2,a3,an)n n维数组维数组n2、数组的运算：、数组的运算：F给定一组给定一组下标下标，存存/取取数组元素的值；数组元素的值；F计算元素的地址计算元素的地址a11,a12,a1n a21,a22,a2na31,a32,a3n am1,am2,amnmn（a1,a2,a3,an)n n维数组维数组3.3.2 数组的顺序存储n1、行优先存储：、行优先存储：F求元素求元素aij的序号的序号 Num=(i-1)*n+jF求元素求元素aij的地址的地址 Addr=
29、Addr0+(Num-1)*C其中，其中，Addr0为数组首地址；为数组首地址；C为每个元素的长度（字节数）。为每个元素的长度（字节数）。F注意：这里注意：这里数组下标从数组下标从1开始开始。F问题：如果数组下标从问题：如果数组下标从0开始，公式如何调整？开始，公式如何调整？a11,a12,a1n a21,a22,a2na31,a32,a3n am1,am2,amnmna1na11a12a21a22a2namnam1am2aijn2、列优先存储：、列优先存储：F求元素求元素aij的序号的序号 Num=(j-1)*m+iF求元素求元素aij的地址的地址 Addr=Addr0+(Num-1)*C其
30、中，其中，Addr0为数组首地址；为数组首地址；C为每个元素的长度（字节数）。为每个元素的长度（字节数）。F注意：这里注意：这里数组下标从数组下标从1开始开始。F问题：如果数组下标从问题：如果数组下标从0开始，公式如何调整？开始，公式如何调整？a11,a12,a1n a21,a22,a2na31,a32,a3n am1,am2,amnmnam1a11a21a21a22am2amna1na2naijn1、对称矩阵、对称矩阵F特点：特点：aij=ajiF求元素求元素aij的序号的序号 Num=1+2+(i-1)+jF求元素求元素aij的地址的地址 Addr=Addr0+(Num-1)*CAddr0
31、和和C含义同前。含义同前。F存储下三角，存储下三角，i=ja11,a12,a13,a1na21,a22,a23,a1na31,a32,a33,a3n an1,an2,an3,annnna11a21a22annan1an2aija31a32a33naij下三角序号：下三角序号：i=jFNum=1+2+3+(i-1)+j =i*(i-1)/2+j naij上三角序号：上三角序号：i=jFNum=1+2+3+(j-1)+i =j*(j-1)/2+i naij的地址的地址:addr=addr0+(Num-1)*c F其中，其中，Addr0为数组首地址；为数组首地址；FC为每个元素的长度（字节数）。为每
32、个元素的长度（字节数）。n2、三角矩阵、三角矩阵F对称矩阵的求解方法适用于三角矩阵。对称矩阵的求解方法适用于三角矩阵。a11,a21,a22,a31,a32,a33,an1,an2,an3,annnn0a11a21a22annan1an2aija31a32a33n3、对角矩阵、对角矩阵F求元素求元素aij的序号的序号 Num=(3(i-1)-1)+(j-i+2)=2i+j-2 其中：其中：|i-j|0)/终止条件：终止条件：n=0 P(n-1);/递归调用递归调用 cout0)cout0)P1(n-1);cout=1)Hanoi(a,c,b,n-1);/将将a上的上的n-1片判移动到片判移动到
33、b，c为借用盘为借用盘Move(a,c);/最大盘从最大盘从a移到移到c，基本问题，基本问题Hanoi(b,a,c,n-1);/将将b上的上的n-1片判移动到片判移动到c，a为借用盘为借用盘n2.递归的一般形式：递归的一般形式：void RecFunc(参数表参数表)if(递归出口条件递归出口条件)简单操作简单操作;/递归出口（终止条件）递归出口（终止条件）else 简单操作简单操作;RecFunc(参数表参数表);/递归调用递归调用 简单操作简单操作;RecFunc(参数表参数表);/可能有多次递归调用可能有多次递归调用 简单操作简单操作;n3.递归调用需具备的条件递归调用需具备的条件F(1
34、)原问题能逐步分解为更简单的子问题，子问题原问题能逐步分解为更简单的子问题，子问题与原问题定义、求解方法相同，只是参数不同；与原问题定义、求解方法相同，只是参数不同；F(2)最后能分解出可直接求解的基本问题，且可通最后能分解出可直接求解的基本问题，且可通过基本问题的解，回推出原问题的解；过基本问题的解，回推出原问题的解；F(3)必须有明确的递归终止条件（出口条件）。必须有明确的递归终止条件（出口条件）。3.4.2 递归的内部实现原理n一般函数调用的实现一般函数调用的实现F递归调用是一种特殊的函数调用形式。递归调用是一种特殊的函数调用形式。n函数调用栈函数调用栈F系统为每个线程的函数调用开辟一块
35、存储区域，叫系统为每个线程的函数调用开辟一块存储区域，叫函数调用栈（函数调用栈（call stak），如图所示：），如图所示：F每调用一个函数，就在调用栈中开辟一块区域，叫每调用一个函数，就在调用栈中开辟一块区域，叫做栈帧（做栈帧（Stack Frame）保存：）保存：函数实参函数实参返回地址返回地址子函数的局部变量子函数的局部变量相关寄存器的值相关寄存器的值函数返回值函数返回值函数实参函数实参返回地址返回地址相关寄存器值相关寄存器值本地变量本地变量栈帧栈帧n例：例：int main()int m=5;:m=A(m);coutm;return 0;int A(int n)int x=10;:x
36、 x=B(x+n);return x+n;int B(int w)int y=50;return y+w;mian实参实参main返回地址返回地址main寄存器寄存器m=5main栈帧栈帧w=15:B寄存器寄存器y=50n=5:A寄存器寄存器x=10A栈帧栈帧B栈帧栈帧n递归调用与函数调用原理相同，不递归调用与函数调用原理相同，不同只是调用了函数自身。同只是调用了函数自身。n例：主函数中调用例：主函数中调用Fact(3)F省略相关寄存器值省略相关寄存器值int main()Fact(3);:cout0)printf(“%d”,n);p(n-1);n运行结果：运行结果：3 2 1P(3)3n=3P(2)n=22P(1)n=11P(0)n=0n【例例】对下面函数，给出对下面函数，给出p(3)的执行过程和运行的执行过程和运行结果。结果。void p(int n)if(n0)printf(“%d”,n);p(n-1);printf(“%d”,n);n运行结果：运行结果：3 2 1 1 2 3P(3)n=33P(2)n=22P(1)n=11P(0)n=0123本章小节n栈栈-FILOn队列队列-FIFOn数组数组n递归递归n【布置作业布置作业】n（P87-p92）F3.15(1)(2)F3.16(2)(4)(6)F3.17(1)(4)F3.19Thank you！