第四章 数据结构重点介绍.ppt

第四章 数据结构 主要内容 4.1 基本数据结构与算法 4.2 线性表 4.3 栈和队列 4.4 树和二叉树 4.5 查找 4.6 内部排序 (2)单链表删除：不需要移动元素,仅修改指针链接 删除结点 删除p指向的结点 只修改p(被删除结点)的前驱结点的指针域即可 步骤 先找到p的前驱结点q 删除p结点，修改q结点指针域 q?next＝p?next C P B A 删除前 P 删除后 q C B A (3)带头结点的单链表 设置：在单链表的第一个结点之前设一个结点(头结点)，其数据域可以不存任何信息，指针域指向第一个结点的指针。 作用：头结点始终存在，地址不变。插入和删除第一个结点时就不影响表头指针(只改变头结点的指针域即可)，简化了 插入、删除算法。 带头结点的单链表L为空的判定条件为：L.next= =NULL 带头结点的单链表 2.循环链表 特点：表中最后一个结点的指针域指向头结点，整个链表首尾相连形成一个环。 优点：从表中任一结点出发均可找到表中其它结点。(单链表每次查找必须从头指针开始，不方便。) 注意：操作和线性链表基本一致，差别是循环条件不是判断p或p-next是否为空,而是它们是否等于头指针 。 带头结点的循环单链表 3.双向链表 设置：双向链表，每个结点有两个指针域，next指向后继结点，prior指向前趋结点。 作用：克服单链表的的缺点—每个结点，只能找到它的后继结点，不能找到前驱结点。若要找前驱结点，必须从头指针开始重新查找。使用双向链表可以方便地沿向前或向后两个方向查找。 (1)插入结点：在p指针所指的结点后插入一个结点q，只需要修改p,q结点的prior和next域即可。(图与步骤见教材P37) (2)删除结点：删除P指针所指结点，只需修改P指针的前驱和后继结点的next，prior域即可。 (图与步骤见教材P38) 4.3 栈和队列 4.3.1 栈 1.栈的定义 定义：只允许在线性表的一端进行插入和删除的线性表。 相关术语： (1)栈顶：允许插入与删除的一端称为栈顶。 指针top指向栈顶位置。 (2)栈底：不允许插入与删除的一端称为栈顶。 指针base指向栈底。 (3)入栈：栈的插入操作(往栈中插入一个元素) (4)出栈：栈的删除操作(从栈中删除一个元素) (5)栈空： top=base (6)栈满： top=m(m为栈最大容量) 栈示意图： 原则：先进后出或后进先出 栈顶元素总是最后入栈，而最先出栈的 栈底元素总是最先入栈，而最后出栈的 2.顺序栈及其运算 栈的两种存储结构 顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 链式存储结构：也称可利用栈。用于收集计算机存储器中所有空闲存储空间。 顺序栈：顺序存储结构的栈称为顺序栈。 链栈：链式存储结构栈称为链栈。 基本运算：入栈、退栈与读栈顶元素 (1)入栈 步骤： 栈顶指针top加1 新元素插入到栈顶指针指向位置 栈顶指针指向存储空间最后一个位置时，栈已满，不能再入栈。称为栈“上溢”错误 (2)出栈 步骤： 栈顶元素赋给一个指定的变量 栈顶指针top减1 栈顶指针为0时,栈空,不能再退栈。称为栈“下溢”错误 (3)读栈顶元素 概念：将栈顶元素赋给一个指定变量 注意：不删除栈顶元素，栈顶指针不会改变 举例 top bottom A B C D E F 10 9 8 7 6 5 4 3 2 1 S(1:10) 有6个元素的栈 A B C D E F X Y S(1:10) top bottom 插入X和Y后的栈 10 9 8 7 6 5 4 3 2 1 bottom A B C D E F X 10 9 8 7 6 5 4 3 2 1 S(1:10) top 退出一个元素后的栈 4.3.2 队列 定义：指允许在一端插入,而在另一端进行删除的线性表。 相关术语(5个)： (1)队尾：允许插入的一端称为队尾。rear队尾指针，始终 指向队尾元素的下一个位置。 (2)队头：允许进行删除的一端称为队头。front队头指针，始终指向队头元素。 (3)入队列：队列插入操作(进队列) (4)出队列：队列的删除操作(退队列) (5)空队列：队列中无数据元素 原则：先进先出 队头元素总是最先进队列的,也总是最先出队列 队尾元素总是最后进队列,也是最后出队列 队列结构示意图：队列Q=(a1，a2, …, an ) a1 ai a2 an … … 队头 队尾 退队 入队 1.链队列 定义：用链表表示的队列。P41 空队列时，头指针fron