数据结构chap2第二章线性表.pptVIP

第2章 线性表 2.1 线性表及其抽象数据类型 线性结构特点：在数据元素的有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个数据元素外，集合中的每个数据元素均只有一个前驱 除最后一个数据元素外，集合中的每个数据元素均只有一个后继 线性表定义：具有相同特性的数据元素组成的有限序列 2.2 线性表的顺序存储结构 顺序分配： 定义：用一组地址连续的存储单元存放一个线性表叫~ 插入 定义：线性表的插入是指在第i（1?i ? n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表 算法时间复杂度T(n) 设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为： 删除 定义：线性表的删除是指将第i（1?i ? n）个元素删除，使长度为n的线性表 算法评价 设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为： 顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 2.3 线性表的链式存储结构 链式存储机构特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 链式存储结构的特点 优点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 缺点 指针占用额外存储空间 不能随机存取，查找速度慢 9 月 9 日作业： P51 1、 5、 8 2.4 栈和队列 线性表的插入和删除操作： 用顺序存储结构： 栈 栈的概念 定义 限定仅在表的同一端进行插入或删除操作的线性表 栈顶(top)：允许被插入和删除的一端 栈底(bottom):表的另一端 空栈：不含元素的栈 基本操作 SETNULL(S) 置为空栈 EMPTY(S) 判断栈是否为空 是返回1;否返回0 PUSHSTACK(S,x) 栈S的顶端插入元素x POPSTACK(S,y) 删除栈S的顶端元素，删除值赋给y 栈的向量存储结构(最简单、最常用) 用向量s[m]来存储栈 m:最大容量 入栈算法 栈的线性链式存储结构 栈的应用 计算表达式 任何一个表达式由操作数、运算符和语句结束符组成 为使编译程序能够正确求值，必须事先规定求值的顺序和规则 对每种运算符赋予一个优先级 运算符：* / + - ； 优先数：2 2 1 1 0 （对表达式进行编译时）设立两个栈：运算符栈、操作数栈 处理原则 遇操作数，则入操作数栈； 遇运算符，进行算符优先级比较 若将n个盘片按规定从A塔移至C塔，移动步骤可分为三步： 把A塔上的n-1个盘片借助C移动到B塔 把第n个盘片从A塔移至C塔 把B塔上的n-1个盘片借助A塔移至C塔 算法用函数hanoi(n,x,y,z)以递归算法实现 作业： P52 11 补充题1：简述队列和栈这两种数据类型的相同点和不同点。 补充题2：铁道按图示进行车厢调度(两侧均为单向行驶) 1)如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？ 2)如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并说明为什么不能得到或如何得到(即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列) 队列 队列的概念 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列的顺序存储结构 实现：用一维数组实现q[M] front(F):队头 指向实际排头元素的前一个位置 rear(R):队尾 指向实际排尾元素位置 存在问题 设数组维数为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出 当front?-1,rear=M-1时，再有元素入队发生溢出——假溢出 队列的链式存储结构 结点定义 2.5 循环线性链表和双向链表 双向链表（double linked list） 单链表具有单向性的缺点 结点定义 2.4 线性表的应用举例 一元多项式的表示及相加 一元多项式的表示： 单链表的结点定义 作业