C语言：2.1.8链表栈队列和树课件.ppt

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

1、主讲老师：欢迎您到（千锋学院）来学习!链表,栈,队列和树内容摘要抽象数据类型抽象列表单链表双向链表循环链表栈的抽象概念与实现栈的应用举例队列抽象概念与应用树抽象概念与应用抽象数据类型模块化设计函数长度不要超过一页小模块易于编写和调试模块化设计利于团队协作开发把依赖关系封装在模块内部抽象数据类型是一组操作一次编写，处处使用用户不需要关心操作的具体实现对实现的修改不会影响到用户代码抽象数据类型抽象数据类型举例列表栈队列树，集合，图可能的操作并，交，补求大小，查找，排序插入，删除类似于简单数据类型的+-*/%抽象列表抽象列表(List)A1,A2,A3,……,A

2、n有n个元素的列表，大小个n有０个元素的列表称为空列表元素结点类型相同常见操作依次打印列表元素voidPrintList(ListX);清空列表元素voidMakeEmpty(ListX);向特定位置上插入一个或多个元素voidInsert(ListX,intpos);删除指定位置上的一个或多个元素voidDelete(ListX,intpos);查找特定元素所在位置intFind(ListX,Elemente);取下一个元素，取前一个元素ElementNext(ListX,Elementp);抽象列表列表的数组实现PrintList　循环打印各个元素Ma

3、keEmpty　数组各个元素置为空Insert插入元素并把该位置后面的元素依次后移Delete删除元素并把该位置后面的元素依次前移Find循环比较各个元素Next返回下一个数组元素Previous返回上一个数据元素IsTail判断是否表尾的结点插入删除不方便，而且需要考虑超出数组大小的情况单链表抽象列表的结构体实现用结构体定义元素结点每个结点包括数据和下一个结点的指针最后一个结果的下结点指针为空(NULL)记录表头指针，通过表头来访问链表E1E2E3E4E5E6NULL341571167NULL单链表插入节点34151167NULL341571167NUL

4、L341571167NULL插入节点删除节点34151167NULL341571167NULL341571167NULL删除节点遍历节点查找节点创建链表初始时，没有结点，链表为空表头指针是空指针使用链表时，首先要判断链表是否为空通过插入操作来给链表增加节点使用链表双向链表每个节点中除了数据成员外，有两个指针，一个指向前驱节点，一个指向后继节点。插入和删除时需要注意前后向指针345NULL55NULL插入节点删除节点循环链表链表的头结点和尾结点连接在一起，构成一个环使用表头指针来访问3415711链表应用练习：使用循环链表来解约瑟夫问题练习：使用链表进行整数

5、排序：把要排序的数依次插入到链表里，先找找到合适的位置，再进行插入操作。练习：归并排序练习：用链表来表示多项式，比如：5x^6+3x^4+2x+1每个节点存储的信息包括系数，指数。定义并实现多项式的加法、减法和乘法操作。栈栈的抽象模型一种特殊的列表只能在列表尾部插入和删除元素表头称为栈基或栈底,栈基指针表尾称为栈顶,栈顶指针插入和删除操作都在栈顶后进先出(LIFO)栈的常见操作push:向栈顶插入一个元素pop:移除栈顶上最近插入的一个元素top：返回栈顶元素is_empty,make_empty23619125栈的实现栈可以用列表的任何实现方式：链表或数

6、组链表实现structnode*top=NULL;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(){return

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

8、队头移除元素常见操作入队(enqueue):向队尾插入元素出队(d