第二章 线性表_1

1 53 第一章回顾 1 程序设计和算法 数据结构的关系2 数据结构讨论的内容3 数据结构的定义4 抽象数据类型的概念5 算法及其度量 2 53 练习 设n为正整数 试确定下列各程序段中前置以记号 的语句的频度i 1 k 0 while i n 1 k 10 i i n 1 3 53 i 1 k 0 do k 10 i i while i n 1 n 1 但n 1时特殊 是1次 4 53 x n y 0 n是不小于1的常数while x y 1 y 1 y 5 53 x 91 y 100 while y 0 if x 100 x 10 y elsex 1100 6 53 数据结构部分的起点 什么是线性结构 7 53 第1章绪论第2章线性表第3章栈和队列第4章串第5章数组第6章树和二叉树第9章查找第10章排序数据库部分 目录 8 53 线性结构的定义 若结构是非空有限集 则有且仅有一个开始结点和一个终端结点 并且所有结点都最多只有一个直接前趋和一个直接后继 可表示为 a1 a2 an 简言之 线性结构反映结点间的逻辑关系是的 特点 只有一个首结点和尾结点 特点 除首尾结点外 其他结点只有一个直接前驱和一个直接后继 线性结构包括 线性表 堆栈 队列 字符串 数组等 其中最典型 最常用的是 线性表 一对一 1 1 9 53 第2章线性表 2 1线性表的类型定义2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 4应用举例 10 53 a1 a2 ai 1 ai ai 1 an 2 1线性表的定义 用数据元素的有限序列表示 n 0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标 是元素的序号 表示元素在表中的位置 n为元素总个数 即表长 n 0 空表 线性终点 11 53 A B C D Z 例2分析学生情况登记表是什么结构 分析 数据元素都是同类型 记录 元素间关系是线性的 分析 数据元素都是同类型 字母 元素间关系是线性的 注意 同一线性表中的元素必定具有相同特性 例1分析26个英文字母组成的英文表是什么结构 12 53 同一数据逻辑结构中的所有数据元素都具有相同的特性 是指数据元素所包含的数据项的个数都相等 是指各元素具有相同的数据类型 试判断下列叙述的正误 13 53 线性表的抽象数据类型的定义 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 基本操作 结构初始化 销毁结构 引用型操作 加工型操作 ADTList 14 53 线性表的抽象数据类型的定义 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 基本操作 结构初始化 InitList L 操作结果 构造一个空的线性表L 销毁结构 DestroyList L 初始条件 线性表L已存在 操作结果 销毁线性表L 15 53 引用型操作 ListEmpty L 初始条件 线性表L已存在 操作结果 若L为空表 则返回TRUE 否则返回FALSE ListLength L 初始条件 线性表L已存在 操作结果 返回L中元素个数 PriorElem L cur e pre e 初始条件 线性表L已存在 操作结果 若cur e是L中的数据元素 但不是第一个 则用pre e返回它的前驱 否则操作失败 pre e无定义 NextElem L cur e next e 初始条件 线性表L已存在 操作结果 若cur e是L中的数据元素 且不是最后一个 则用next e返回它的后继 否则操作失败 next e无定义 16 53 GetElem L i e 初始条件 线性表L已存在 1 i LengthList L 操作结果 用e返回L中第i个元素的值 LocateElem L e compare 初始条件 线性表L已存在 compare 是元素判定函数 操作结果 返回L中第1个与e满足关系compare 的元素的位序 若这样的元素不存在 则返回值为0 ListTraverse L visit 初始条件 线性表L已存在 visit 为元素的访问函数 操作结果 依次对L的每个元素调用函数visit 一旦visit 失败 则操作失败 17 53 加工型操作 ClearList L 初始条件 线性表L已存在 操作结果 将L重置为空表 PutElem L i e 初始条件 线性表L已存在 1 i LengthList L 操作结果 L中第i个元素赋值同e的值 ListInsert L i e 初始条件 线性表L已存在 1 i LengthList L 1 操作结果 在L的第i个元素之前插入新的元素e L的长度增1 ListDelete L i e 初始条件 线性表L已存在且非空 1 i LengthList L 操作结果 删除L的第i个元素 并用e返回其值 L的长度减1 ADTList 18 53 利用上述定义的线性表 可以完成其他更复杂的操作 19 53 例2 1已知集合A和B 求两个集合的并集 使A A B 且B不再单独存在 分析 以线性表LA和LB分别表示集合A和B 对集合B中的所有元素一个一个地检查 将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去 具体操作步骤为 1 从线性表LB中取出一个数据元素 GetElem Lb i e 2 依值在线性表LA中进行查询 LocateElem LA e equal 3 若不存在 则将它插入到LA中 ListInsert LA n 1 e 重复上述三步直至LB遍历止 20 53 对应的线性表基本操作 1 GetElem Lb i e 2 LocateElem LA e equal 3 ListInsert LA n 1 e voidunion List 销毁线性表LB union 21 53 例2 有顺序表A和B 其元素均按从小到大的升序排列 编写一个算法将它们合并成一个顺序表C 要求C的元素也按从小到大的升序排列 基本思路 依次扫描A和B的元素 比较当前元素ai和bj if ai bj ai赋给Ck i k else bj赋给Ck j k 将未完的那个顺序表中余下部分赋给C 22 53 voidMergeList SqListLa SqListLb SqList Lc 算法2 2 已知线性表La和Lb中的数据元素按值非递减排列 归并La和Lb得到新的线性表Lc Lc的数据元素也按值非递减排列 inti 1 j 1 k 0 InitList Lc 创建空表Lc La len ListLength La Lb len ListLength Lb 依次扫描A和B的元素 比较当前元素ai和bj while i La len 23 53 教材例2 1 求两个线性表的 并 即 LAULB 算法至少有两种 LA和LB都是无序表 则从LB中取元素逐一与LA中所有元素比较 相同则不插入LA中 O ListLength LA ListLength LB 若LA和LB已经是有序表 则 归并 的时间效率可以大大提高 O ListLength LA ListLength LB 24 53 2 2 1顺序表的表示 用一组地址连续的存储单元依次存储线性表的元素 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构 线性表的顺序表示又称为顺序存储结构或顺序映像 顺序存储定义 顺序存储方法 特点 逻辑上相邻的元素 物理上也相邻 可以利用数组V n 来实现 注意 在C语言中数组的下标是从0开始 即 V n 的有效范围是从V 0 V n 1 25 53 1 逻辑上相邻的数据元素 其物理上也相邻 2 若已知表中首元素在存储器中的位置 则其他元素存放位置亦可求出 利用数组V n 的下标 设首元素a1的存放地址为LOC a1 称为首地址 设每个元素占用存储空间 地址长度 为L字节 则表中任一数据元素的存放地址为 LOC ai 1 LOC ai LLOC ai LOC a1 L i 1 对上述公式的解释如图所示 线性表顺序存储特点 26 53 地址内容元素在表中的位序 1 i 2 n 空闲区 i 1 L b LOC a1 b L b i 1 L b n 1 L b max 1 L LOC ai LOC a1 L i 1 线性表的顺序存储结构示意图 下标起点是1 27 53 设有一维数组 下标的范围是 到 每个数组元素用相邻的 个字节存储 存储器按字节编址 设存储数组元素 的第一个字节的地址是98 则 的第一个字节的地址是多少 答案 113 但此题要注意下标起点是从0开始 LOC M 3 98 5 4 1 113 解 已知地址计算通式为 LOC ai LOC a1 L i 1 例1 或用 3 0 28 53 charV 30 voidbuild 字母线性表的生成 即建表操作 inti V 0 a for i 1 i n 1 i V i V i 1 1 核心语句 法1V i V i 1 1 法2V i a i 法3V i 97 i 例2 用数组V来存放26个英文字母组成的线性表 a b c z 写出在顺序结构上生成和显示该表的C语言程序 省略了include语句 29 53 voidmain void 主函数 字母线性表的生成和输出 n 26 n是表长 是数据元素的个数 而不是V的实际下标build display voiddisplay 字母线性表的显示 即读表操作 inti for i 0 i n 1 i printf c v i printf n 执行结果 abcdefghijklmnopqrstuvwxyz 30 53 2 2 2顺序表的实现 或操作 数据结构的基本运算 修改 插入 删除 查找 排序 1 修改通过数组的下标便可访问某个特定元素并修改之 核心语句 V i x 显然 顺序表修改操作的时间效率是O 1 31 53 在线性表的第i个位置前插入一个元素 实现步骤 将第n至第i位的元素向后移动一个位置 将要插入的元素写到第i个位置 表长加1 for j n j i j a j 1 a j a i x n 元素后移一个位置 插入x 表长加1 核心语句 2 插入 注意 事先应判断 插入位置i是否合法 表是否已满 应当符合条件 1 i n 1或i 1 n 1 32 53 在线性表的第i个位置前插入一个元素的示意图如下 插入25 33 53 实现步骤 将第i 1至第n位的元素向前移动一个位置 表长减1 删除线性表的第i个位置上的元素 for j i 1 j n j a j 1 a j n 元素前移一个位置 表长减1 核心语句 3 删除 注意 事先需要判断 删除位置i是否合法 应当符合条件 1 i n或i 1 n 34 53 删除顺序表中某个指定的元素的示意图如下 35 53 顺序表的运算效率分析 算法时间主要耗费在移动元素的操作上 因此计算时间复杂度的基本操作 最深层语句频度 T n O 移动元素次数 而移动元素的个数取决于插入或删除元素的位置 思考 若插入在尾结点之后 则根本无需移动 特别快 若插入在首结点之前 则表中元素全部要后移 特别慢 应当考虑在各种位置插入 共n 1种可能 的平均移动次数才合理 讨论1 若在长度为n的线性表的第i位前插入一个元素 则向后移动元素的次数f n 为 f n n i 1 时间效率分析 36 53 推导 假定在每个元素位置上插入x的可能性都一样 即概率P相同 则应当这样来计算平均执行时间 将所有位置的执行时间相加 然后取平均 若在首结点前插入 需要移动的元素最多 后移次数为n 若在a1后面插入 要后移n 1个元素 后移次数为n 1 若在an 1后面插入 后移次数为1 若在尾结点an之后插入 则后移次数为0 故插入时的平均移动次数为 n n 1 2 n 1 n 2 O n 共有多少种插入形式 连头带尾有n 1种 所有可能的元素移动次数合计 0 1 n n n 1 2 37 53 同理可证 顺序表删除一元素的时间效率为 T n n 1 2 O n 想一想 顺序表插入 删除算法的平均空间复杂度为多少 插入效率 删除效率 教材P25算法2 5也是对执行效率的推导 因为没有占用辅助空间 含义 对于顺序表 插入 删除操作平均需要移动一半元素 n 2 O 1 即插入 删除算法的平均时间复杂度为O n 38 53 defineLIST MAX LENGTH100 线性表的最大长度typedefintElemType typedefstruct ElemType elem 指向存放线性表中数据元素的基地址intlength 线性表的当前长度 SQ LIST 39 53 典型操作的算法实现 1 初始化线性表LintInitList SQ LIST 成功返回OK sizeof x 算符的意思是 计算变量x的长度 字节数 malloc m 函数的意思是 新开一片大小为m字节的连续空间 并把该区首址作为函数值 40 53 2 销毁线性表LvoidDestroyList SQ LIST 释放线性表占据的所有存储空间 41 53 3 清空线性表LvoidClearList SQ LIST 将线性表的长度置为0 42 53 4 求线性表L的长度intGetLength SQ LISTL return L length 43 53 5 判断线性表L是否为空intIsEmpty SQ LISTL if L length 0 returnTRUE elsereturnFALSE 44 53 6 获取线性表L中的某个数据元素的内容intGetElem SQ LISTL inti ElemType 45 53 7 在线性表L中检索值为e的数据元素intLocateELem SQ LISTL int compare ElemType ElemType 操作结果 返回L中第1个与e满足关系compare 的数据元素的位序 若这样的数据元素不存在 则返回值为0 ElemType p inti 1 i的初值为第1个元素的位序 p L elem p的初值为第1个元素的存储位置 while i L length intequal ElemTypea ElemTypeb 根据a或 b 分别返回0或1 if a b return1 elsereturn0 LocateElem L j equal 46 53 8 将线性表L中第i个数据元素删除intListDelete SQ LIST 47 53 9 在线性表L中第i个数据元素之前插入数据元素eintListInsert SQ LIST 48 53 进一步讨论 顺序表的存储结构是一维数组 如果插入的元素个数超过数组定义的长度怎么办 采用动态分配的一维数组 49 53 动态数组简介 先为顺序表空间设定一个初始分配量 一旦因插入元素而空间不足时 可为顺序表增加一个约定长度的空间增量 defineLIST INIT SIZE100 存储空间的初始分配量 defineLISTINCREMENT10 存储空间的分配增量Typedefstruct ElemType elem 表基址 用指针 elem表示 intlength 表长度 表中有多少个元素 intlistsize 当前分配的表尺寸 字节单位 SqList 注 三个分量可简写为 L elemL lengthL listsize 存储结构描述如下 见教材P22 50 53 StatusInitList Sq SqList InitList Sq 动态创建一个空顺序表的算法 51 53 动态顺序表的插入算法StatusListInsert Sq SqList L inti ElemTypee 在顺序线性表中第i个位置之前插入新的元素e if iL length 1 returnERROR 检验i值的合法性 if L length L listsize 若表长超过表尺寸则要增加尺寸 new