C语言：2.1.8链表栈队列和树.pptVIP

内容摘要 抽象数据类型 抽象列表 单链表 双向链表 循环链表 栈的抽象概念与实现 栈的应用举例 队列抽象概念与应用 树抽象概念与应用 抽象数据类型 模块化设计 函数长度不要超过一页 小模块易于编写和调试 模块化设计利于团队协作开发 把依赖关系封装在模块内部 抽象数据类型是一组操作 一次编写，处处使用 用户不需要关心操作的具体实现 对实现的修改不会影响到用户代码 抽象数据类型 抽象数据类型举例 列表 栈 队列 树，集合，图 可能的操作 并，交，补 求大小，查找，排序 插入，删除 类似于简单数据类型的+-*/% 抽象列表 抽象列表(List) A1, A2, A3, … …, An 有n个元素的列表，大小个n 有０个元素的列表称为空列表 元素结点类型相同 常见操作 依次打印列表元素 void PrintList(List X); 清空列表元素 void MakeEmpty(List X); 向特定位置上插入一个或多个元素 void Insert(List X, int pos); 删除指定位置上的一个或多个元素 void Delete(List X, int pos); 查找特定元素所在位置 int Find(List X, Element e); 取下一个元素，取前一个元素 Element Next(List X, Element p); 抽象列表 列表的数组实现 PrintList　循环打印各个元素 MakeEmpty　数组各个元素置为空 Insert 插入元素并把该位置后面的元素依次后移 Delete 删除元素并把该位置后面的元素依次前移 Find 循环比较各个元素 Next 返回下一个数组元素 Previous 返回上一个数据元素 IsTail 判断是否表尾的结点 插入删除不方便，而且需要考虑超出数组大小的情况 单链表 抽象列表的结构体实现 用结构体定义元素结点 每个结点包括数据和下一个结点的指针 最后一个结果的下结点指针为空(NULL) 记录表头指针，通过表头来访问链表 单链表 插入节点 插入节点 删除节点 删除节点 遍历节点 查找节点 创建链表 初始时，没有结点，链表为空 表头指针是空指针 使用链表时，首先要判断链表是否为空 通过插入操作来给链表增加节点 使用链表 双向链表 每个节点中除了数据成员外，有两个指针，一个指向前驱节点，一个指向后继节点。 插入和删除时需要注意前后向指针 插入节点 删除节点 循环链表 链表的头结点和尾结点连接在一起，构成一个环 使用表头指针来访问 链表应用 练习：使用循环链表来解约瑟夫问题 练习：使用链表进行整数排序：把要排序的数依次插入到链表里，先找找到合适的位置，再进行插入操作。 练习：归并排序 练习：用链表来表示多项式，比如： 5x^6 + 3x^4 + 2x +1 每个节点存储的信息包括系数，指数。 定义并实现多项式的加法、减法和乘法操作。 栈 栈的抽象模型 一种特殊的列表 只能在列表尾部插入和删除元素 表头称为栈基或栈底, 栈基指针 表尾称为栈顶, 栈顶指针 插入和删除操作都在栈顶 后进先出(LIFO) 栈的常见操作 push: 向栈顶插入一个元素 pop: 移除栈顶上最近插入的一个元素 top：返回栈顶元素 is_empty, make_empty 栈的实现 栈可以用列表的任何实现方式：链表或数组 链表实现 struct node *top = NULL; void push( struct node *p) { if(NULL ==p) return; p-next = top; top =p; } struct node* pop() { struct node *p = top; top = (!top)? top: top-next; return p; } 栈的实现 栈的数组实现 struct node *stack[100]; int top = -1; void push(struct node *p) { stack[++top] = p; } struct node * pop() { return stack[top --]; } 栈的应用 检查符号对称性 当前遇到的符号如果能和栈顶符号匹配，弹出栈顶符号 否则，说明是左符号，压入栈顶 最后，栈为空说明所有符号正确匹配 栈不为空或匹配过程中断，说明可能丢了符号 void demo() { int a=2; { return; } { printf(“%d “, a); } } 栈的应用 计算波兰后缀表达式 1 + 2 + 3*4 +5 = 1 2 + 3 4 * + 5 + 遇到数字：压入栈顶