C语言：2.1.9栈队列和树课件.ppt

《C语言：2.1.9栈队列和树课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主讲老师：欢迎您到（千锋学院）来学习!链表,栈,队列和树内容摘要栈的抽象概念与实现栈的应用举例队列抽象概念与应用树抽象概念与应用栈栈的抽象模型一种特殊的列表只能在列表尾部插入和删除元素表头称为栈基或栈底,栈基指针表尾称为栈顶,栈顶指针插入和删除操作都在栈顶后进先出(LIFO)栈的常见操作push:向栈顶插入一个元素pop:移除栈顶上最近插入的一个元素top：返回栈顶元素is_empty,make_empty23619125栈的实现栈可以用列表的任何实现方式：链表或数组链表实现structnode*top=N

2、ULL;voidpush(structnode*p){if(NULL==p)return;p->next=top;top=p;}structnode*pop(){structnode*p=top;top=(!top)?top:top->next;returnp;}1167NULLtop1167NULLtop12栈的实现栈的数组实现structnode*stack[100];inttop=-1;voidpush(structnode*p){stack[++top]=p;}structnode*pop(){re

3、turnstack[top--];}25257栈的应用检查符号对称性当前遇到的符号如果能和栈顶符号匹配，弹出栈顶符号否则，说明是左符号，压入栈顶最后，栈为空说明所有符号正确匹配栈不为空或匹配过程中断，说明可能丢了符号voiddemo(){inta=2;{return;}{printf(“%d“,a);}}({{(栈的应用计算波兰后缀表达式1+2+3*4+5=>12+34*+5+遇到数字：压入栈顶遇到符号：弹出两个元素计算结果：压入栈顶栈式计算机的运行原理213341251720队列概念和实现队列是一种特殊的

4、列表先入先出(FIFO)队列头和队列尾只向队尾插入元素只从队头移除元素常见操作入队(enqueue):向队尾插入元素出队(dequeue):从队头移除元素取对头(front):返回队头元素261enqueuedequeue队列概念和实现数组实现structnode*queue[10];intfront=0,tail=0;intisempty(){returnfront==tail;}intisfull(){return(tail+1)%5==front;}intlength(){return(tail–fr

5、ont+5)%5;}23413456fronttailfronttailtailfront队列概念和实现队列的数组实现structnode*enqueue(structnode*p){if(isfull())returnNULL;queue[tail]=p;tail=(tail+1)%10;returnp;}structnode*dequeue(){if(isempty())returnNULL;front=(front+1)%10;returnqueue[(front-1+10)%10];}2341fro

6、nttail2341fronttail队列概念和实现队列的链表实现与单链表类似用队头指针和队尾指针访问判断队空：队头指针为空队列可以不断增长计算长度：从队头开始，遍历计数入队：tail->next=p;tail=p;出队：p=front;front=front->next;returnp;71167NULLfronttail队列应用等待队列模拟超市排队结账用户请求在服务器端排队等待处理打印二项展开式(a+b)^i的系数11每行数目加一121每个数等与肩膀上两数之和1331146411510105111012

7、1013310队列应用优先级队列优先级最高的永远排队头每次出队，总是优先级最高的元素实现1数组存储入队时放最后面出队时搜索优先级最高的实现2链表存储入队时排序出队时取第一个元素树的概念和实现树的递归定义：数有n个节点组成有一个特定的节点，称为根，只有直接后继，没有直接前驱每个节点和他的后继都是一颗子数二叉树每个节点最多有两个子节点：节点下面有左子树和右子树层数从0开始，第i曾最多2^i个节点123456树的概念和实现数组实现对节点编号按照编号存入数组结构最简单空间最节省根据节点编号推算父节点子节点和兄弟节点

8、13579130123453517913树的概念和实现链表实现structnode{节点存两个指针intid;指向左右子节点structnode*left,*right;}1357913012345135NULL7NULL913NULLNULLNULLNULLNULL树的概念和实现树的遍历前序：根节点，左子树，右子树1379513中序：左子树，根节点，右子树7391513后序：左子树，右子树，根节点7931351