第二讲-线性表.ppt

1 课程内容 逻辑结构线性表存储结构顺序表 向量链表典型运算 2 2 1线性表 线性表的抽象数据类型ADT线性表的存储结构线性表的典型操作 3 线性表的概念 线性表定义 由有限结点集N 以及定义在结点集N上的线性关系r所组成的线性结构 这些结点称为线性表的元素 地址相邻的顺序 和 指针指向相邻的顺序 线性表 N r 的数学定义唯一的开始结点 没有前驱 但有一个唯一的直接后继唯一的终止结点 没有后继 但有一个唯一的直接前驱内部结点 有一个唯一的直接前驱 也有一个唯一的直接后继线性表的长度 包含的结点个数 为0的线性表称为空表线性表的关系r是前驱关系 应具有反对称性和传递性 4 举例 长度为k 要求 内部结点具有相同的数据类型每个元素都有自己的位置 5 线性表运算分类 list 创建线性表的一个实例 list 线性表消亡 即析构函数 获取有关当前线性表的信息位置寻内容 内容找位置访问线性表并改变线性表的内容或结构插入 删除 更改等线性表的辅助性管理操作游标管理 当前长度管理 6 线性表ADT templateclassList 线性表类模板list 模板参数Tvoidclear 置空线性表boolisEmpty 线性表为空返回true voidappend ELEMvalue 表尾添加元素value 表长加1 voidinsert intp Tvalue 在p处插入value 表长加1 voiddelete intp 删去第p元素 表的长度减1 boolgetPos int 用value修改p处值 7 线性表的存储结构 定长的静态顺序存储结构又称为向量型的一维数组结构存储在连续的地址区域 随机访问 固定长度缺陷变长的动态线性存储结构链接式存储结构按照前驱关系通过指针将元素链接动态数组提供空间表管理 为长度变化提供方法 长度增大 可申请大空间顺序文件为存储在磁盘上的线性表所用 8 2 2顺序表 向量 顺序表 Sequentiallist 又称向量 Vector 采用定长的一维数组存储结构主要特性 元素的类型相同元素顺序存储在连续存储空间中 每一个元素唯一的索引值 下标 读写元素方便使用常数作为向量长度 程序运行时保持不变 9 逻辑和存储结构 10 向量的类定义 enumBoolean False True constintMax length 100 Template 假定顺序表的元素类型T为ELEMclasslist 顺序表 向量private intmsize 私有变量 顺序表实例的最大长度intcurr len 私有变量 顺序表实例的当前长度ELEM nodelist 私有变量 存储顺序表实例的向量public 以下列出成员函数 顺序表的算子集 intcurr 当前下标 顺序表的公共变量list constintsize 构造算子 实参是表实例的最大长度 list 析构算子 用于将该表实例删去 11 voidclear 将顺序表存储的内容清除 成为空表intlength 返回此顺序表的当前实际长度boolappend constELEM 12 查找元素 目的 查找某个位置的值或者某个值的位置template 假定顺序表的元素类型为TboolarrList getPos int 顺序表没有元素值为value的元素 13 插入元素运算 boolinsert constintp constTvlaue 在当前下标p t位置插入元素新值value curr len k 条件判断 1 当前下标 0 curr len 2 当前长度 msize 14 插入算法 template 假定顺序表的元素类型为TboolarrList insert intp constTvalue inti if curLen maxSize 检查顺序表是否溢出returnfalse if pcurLen 检查插入位置是否合法returnfalse for i curLen i p i aList i aList i 1 从表尾curLen 1起往右移动直到paList p value 位置p处插入新元素curLen 表的实际长度增1returntrue 15 算法执行时间 主要代价元素的移动元素总个数为n 各个位置插入的概率相等为p 1 n平均移动元素次数为总时间开销估计为O n 16 删除元素运算 Delete constintp 下标t位置值作为返回值 并删去该元素 条件判断 1 当前下标 0 curr len 2 当前长度 0 17 删除算法 template 顺序表的元素类型为TboolarrList delete intp inti if curLencurLen 1 检查删除位置是否合法returnfalse for i p i curLen 1 i aList i aList i 1 从位置p开始每个元素左移直到curLen curLen 表的实际长度减1returntrue 18 算法时间代价 与插入操作相似 O n 顺序表读取元素方便 时间代价为O 1 但插入 删除操作则付出时间代价O n 19 2 3链表 LinkedList 链表 linkedlist 指针指向保持前驱关系 节点不必物理相邻动态申请 释放空间适合节点的动态的插入 删除 长度变化无常链接存储方法在非线性结构 如树 图 中的应用分类单链表双链表循环链表 20 单链表 结点类型以及变量说明structListNode ELEMdata 存放线性表结点的数据 ListNode next 存放指向后继结点的指针 typedefListNode ListPtr ListPtrhead tail head指向单链表开始结点的指针 tail指向单链表尾结点的指针 指针域null 21 运算集 查找算法查找单链表中第i个结点算法插入算法插入数据内容为value的新结点 为第i个结点 删除算法删除由参数link所指定的结点求长度算法求单链表中元素的个数 22 单链表 Con HeaderNode不被作为表中的实际元素 值忽略head指向该节点访问必须从head开始查找链表中的元素 23 链表检索 函数返回值是找到的结点指针template 线性表的元素类型为TLink lnkList setPos inti intcount 0 if i 1 returnhead i为 1则定位到头结点Link p head next while p NULL 指向第i结点 i 0 1 n 1 当链表中结点数小于i时返回NULL 24 插入过程描述 p q p setPos i 1 q newListNode p q p q q next p next p next q 25 插入算法 ListNode Insert ELEMvalue inti ListNode p q q newListNode 产生一个新结点空间qp setPos i 1 找到待插位置的前一个位置pif p NULL returnNULL q next p next q data value p next q if q next NULL last q 当插入元素是最后位置时维护尾指针returnq 26 删除结点过程描述 x p p next d next d d p next free d P节点不能不存在或者为尾节点 27 删除算法 template 线性表的元素类型为TboollnkList delete constinti Link p d if p setPos i 1 NULL p tail 待删结点不存在 coutnext d是真正待删结点if d tail 待删结点为尾结点 则修改尾指针tail p p next NULL deleted else p next d next deleted 删除结点d并修改链指针returntrue 28 求长度算法 intlength Link p head next intcount 0 while p NULL p p next count returncount 29 思考题 为什么引入头节点 有利于对空链表进行操作或者在链表表头进行操作等特殊情况的处理 例如单链表为空时的插入 单链表被删除为空表时的处理 插入作为表的第一个节点 删除表的第一个节点 30 单链表分析 单链表的主要不足之处link字段仅仅指向后继结点 不能有效地找到前驱双链表弥补了上述不足之处增加一个指向前驱的指针 31 双链表 类型说明structDblListNode ELEMdata DblListNode prev DblListNode next structDoubleList DblListNode head tail 指向前驱结点 指向后继结点 32 删除结点示意图 删除p所指的结点setPos i p prev next p next p next prev p prev p prev NULL p next NULL free p 33 插入结点示意图 在p所指结点后插入一个新的结点setPos i 1 p q next p next q prev p q p p next q q next prev q q p q 34 循环链表 将单链表或者双链表的头尾结点链接起来 就是一个循环链表 不增加额外存储花销 却给不少操作带来了方便从循环表中任一结点出发 都能访问到表中其他结点 35 几种主要链表比较 36 2 4线性表实现方法的比较 顺序表的主要优点没有使用指针 不用花费额外开销线性表元素的访问非常便利链表的主要优点无需事先了解线性表的长度允许线性表的长度动态变化能够适应经常插入删除内部元素的情况 顺序表是存储静态数据的不二选择链表是存储动态变化数据的良方 37 顺序表和链表的比较 顺序表插入 删除运算时间代价O n 查找则可常数时间完成预先申请固定长度的数组如果整个数组元素很满 则没有结构性存储开销链表插入 删除运算时间代价O 1 但找第i个元素