线性表的逻辑结构、顺序表示与链式表示.ppt

上节课要点回顾 数据结构定义 指互相有关联的数据元素的集合 用D S D S 数据结构内容 数据的逻辑结构 存储结构和运算算法效率指标 时间效率和空间效率 数据结构课程的内容 逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构 近3周上课内容 第2章线性表第3章栈和队列第4章串 线性结构 在数据元素的非空有限集中 有且仅有一个开始结点和一个终端结点 并且所有结点都最多只有一个直接前趋和一个直接后继 可表示为 a1 a2 an 线性结构的特点 逻辑 存储和运算 线性结构包括线性表 堆栈 队列 字符串 数组等等 其中 最简单 最常用的是 线性表 见第2章 简言之 线性结构反映结点间的逻辑关系是一对一的 第2章线性表 2 1线性表的逻辑结构2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 4应用举例 a1 a2 ai 1 ai ai 1 an 2 1线性表的逻辑结构 1 线性表的定义 是n个数据元素的有限序列 n 0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标 是元素的序号 表示元素在表中的位置 n为元素总个数 即表长 空表 线性终点 例1分析26个英文字母组成的英文表 A B C D Z 例2分析学生情况登记表 数据元素都是记录 元素间关系是线性 数据元素都是字母 元素间关系是线性 同一线性表中的元素必定具有相同特性 线性表的抽象数据类型的定义 ADTList 数据对象 D ai ai Elemset i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 基本操作 InitList L 操作结果 构造一个空的线性表LDestroyList L 初始条件 线性表已存在操作结果 销毁线性表L ClearList L 初始条件 线性表已存在操作结果 置线性表L为空表IsListEmpty L 初始条件 线性表已存在操作结果 若线性表L为空表 则返回TRUE 否则返回FALSEListLength L 初始条件 线性表已存在操作结果 返回线性表L数据元素个数GetElem L i e 初始条件 线性表已存在 1 i ListLenght L 操作结果 用e返回线性表L中第i个数据元素的值 locateElem L e compare 初始条件 线性表已存在 compare 是数据元素判定函数操作结果 返回线性表L中第1个与e满足关系comare 的数据元素的位序PriorElem L cur e pre e 初始条件 线性表已存在操作结果 若cur e是线性表L的数据元素 且不是第一个 则用pre e返回它的前驱 否则操作失败 pre e无定义NextElem L cur e next e 初始条件 线性表已存在操作结果 若cur e是线性表L的数据元素 且不是第最后一个 则用next e返回它的后继 否则操作失败 next e无定义 ListTraverse L visit 初始条件 线性表已存在操作结果 遍历线性表 依次对线性表L的每个数据元素调用visit 函数 一旦visit 失败 则操作失败ListInsert L i e 初始条件 线性表已存在 1 i ListLenght L 1 操作结果 在线性表L中第i个数据元素之前插入新元素e L长度加1ListDelete L i e 初始条件 线性表已存在 1 i ListLenght L 操作结果 删除线性表L中第i个数据元素 用e返回其值 L长度减1 ADTList 上述是线性表抽象数据类型的定义 其中只是一些基本操作 另外可以更复杂 如将两个线性表合并等 复杂的操作可用基本操作实现 例3 将两个非递减的表合成为一个非递减的表voidMergeList Listla Listlb list while i la len 2 2线性表的顺序表示和实现 2 2 1顺序表的表示2 2 2顺序表的实现2 2 3顺序表的运算效率分析 本节小结 2 2 1顺序表的表示 用一组地址连续的存储单元依次存储线性表的元素 可通过数组来实现 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构 线性表的顺序表示又称为顺序存储结构或顺序映像 顺序存储定义 顺序存储方法 简言之 逻辑上相邻 物理上也相邻 线性表顺序存储特点 逻辑上相邻的数据元素 其物理上也相邻 若已知表中首元素在存储器中的位置 则其他元素存放位置亦可求出 利用数组下标 计算方法是 参见存储结构示意图 设首元素a1的存放地址为LOC a1 称为首地址 设每个元素占用存储空间 地址长度 为L字节 则表中任一数据元素的存放地址为 LOC ai LOC a1 L i 1 LOC ai 1 LOC ai L 线性表的顺序存储结构示意图 地址内容元素在表中的位序 1 i 2 n 空闲区 i 1 L b LOC a1 b L b i 1 L b n 1 L b max 1 L 例4 一个一维数组 下标的范围是 到 每个数组元素用相邻的 个字节存储 存储器按字节编址 设存储数组元素 的第一个字节的地址是98 则 的第一个字节的地址是 113 因此 LOC M 3 98 5 3 0 113 解 地址计算通式为 LOC ai LOC a1 L i 1 线性表的顺序存储结构定义 静态 defineMAXSIZE100typedefstruct ElemTypeelem MAXSIZE intlength SqList elem length SqListL 声明L顺序表 L inta a 2 2 2顺序表的实现 或操作 回忆 数据结构基本运算操作有 插入 删除 查找 排序 修改 1 插入 在线性表的第i个位置前插入一个元素 使长度为n的线性表变为长度为n 1的线性表 实现步骤 将第n至第i位的元素向后移动一个位置 将要插入的元素写到第i个位置 表长加1 注意 事先应判断 插入位置i是否合法 表是否已满 a1 a2 ai 1 ai an a1 a2 ai 1 x ai an 程序实现 StatusListInsert Sq SqList 顺序表插入的演示 实现步骤 将第i 1至第n位的元素向前移动一个位置 表长减1 注意 事先需要判断 删除位置i是否合法 2 删除 删除线性表的第i个位置上的元素 使长度为n的线性表变为长度为n 1的线性表 a1 a2 ai 1 ai ai 1 an a1 a2 ai 1 ai 1 an 程序实现 StatusListDelete Sq Sqlist 顺序表删除的演示 2 2 3顺序表的运算效率分析 时间效率分析 插入算法花费的时间 主要在于循环中元素的后移当插入位置为1时 需n次移动 当插入位置为n时 不需移动元素 当插入位置为i时 移动次数为n i 1 假定在表中任意位置插入元素都是等概率的 在第i个位置上插入元素的概率p i 1 n 1 插入操作时间效率 平均移动次数 删除操作时间效率 平均移动次数 删除算法花费的时间 主要在于循环中元素的前移当删除位置为1时 需n 1次移动 当插入位置为n时 不需移动元素 当插入位置为i时 移动次数为n i 假定在表中任意位置删除元素都是等概率的 则删除第i个位置上元素的概率q i 1 n 本节小结 线性表顺序存储结构特点 逻辑关系上相邻的两个元素在物理存储位置上也相邻 优点 可以随机存取表中任一元素O 1 存储空间使用紧凑缺点 在插入 删除某一元素时 需要移动大量元素O n 预先分配空间需按最大空间分配 利用不充分 表容量难以扩充为克服这一缺点 我们引入另一种存储形式 链式存储结构 见2 3节 2 3线性表的链式表示和实现 2 3 1链表的表示2 3 2链表的实现2 3 3链表的运算效率分析 本节小结 2 3 1链表的表示用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai 除存储本身信息外 还需存储其直接后继的信息结点数据域 元素本身信息指针域 指示直接后继的存储位置 例线性表 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 43 13 1 NULL 37 7 19 25 头指针 与链式存储有关的术语 1 结点 数据元素的存储映像 由数据域和指针域两部分组成 2 链表 n个结点由指针链组成一个链表 它是线性表的链式存储映像 称为线性表的链式存储结构 3 单链表 双链表 多链表 循环链表 结点只有一个指针域的链表 称为单链表或线性链表 有两个指针域的链表 称为双链表 有多个指针域的链表 称为多链表 首尾相接的链表称为循环链表 循环链表示意图 何谓头指针 头结点和首元结点 头指针是指向链表中第一个结点 或为头结点或为首元结点 的指针 单链表可由一个头指针唯一确定 头结点是在链表的首元结点之前附设的一个结点 数据域内只放空表标志和表长等信息 首元结点是指链表中存储线性表第一个数据元素a1的结点 一个线性表的逻辑结构为 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 其存储结构用单链表表示如下 请问其头指针的值是多少 例 答 头指针是指向链表中第一个结点的指针 因此关键是要寻找第一个结点的地址 31 头指针的值是31 上例链表的逻辑结构示意图有以下两种形式 区别 无头结点 有头结点 答 讨论1 在链表中设置头结点有什么好处 讨论2 如何表示空表 头结点即在链表的首元结点之前附设的一个结点 该结点的数据域中不存储线性表的数据元素 其作用是为了对链表进行操作时 可以对空表 非空表的情况以及对首元结点进行统一处理 编程更方便 答 无头结点时 当头指针的值为空时表示空表 有头结点时 当头结点的指针域为空时表示空表 typedefstructnode ElemTypedata 数据域structLnode next 指针域 LinkNode LinkList LinkList为Lnode类型的指针 对于单链表的抽象描述 LinkNodes1 定义改结构体类型的变量S1 等价于 structnodes1 LinkListp1 定义该类型的指针变量 等价于 LinkNode p1 等价于 structnode p1 补充 结构类型的C语言表示法 介绍三个有用的库函数 都在中 sizeof x 计算变量x的长度 malloc m 开辟m字节长度的地址空间 并返回这段空间的首地址 free p 释放指针p所指变量的存储空间 即彻底删除一个变量 2 3 2链表的实现 1 单链表的建立和输出2 单链表的修改3 单链表的插入4 单链表的删除5 应用举例6 其它链表形式 1 单链表的建立和输出 头插法建单链表的演示 尾插法建单链表的演示 1 单链表的建立和输出 实例 用单链表结构来存放26个英文字母组成的线性表 A B C Z 请写出C语言程序 难点分析 每个数据元素在内存中是 零散 存放的 其首地址怎么找 又怎么一一链接 实现思路 先开辟头指针 然后陆续为每个数据元素开辟存储空间并赋值 并及时将地址送给前面的指针 将全局变量及函数提前说明 include includetypedefstructnode chardata structnode next Lnode LinkList Lnode p q head intn intm sizeof Lnode 结构类型定义好之后 每个变量的长度就固定了 m求一次即可 等价于 LinkListp q head LinkLists head LinkList malloc m p head s LinkList malloc m s data a i 1 p next s p s p next NULL returnhead head是全局变量 此语句可省 LinkListbuild Step1 先建立一个头结点 并记为当前结点Step2 for i 1 i 26 i step21 为当前字母建立结点 step22 将当前结点链入链表尾step23 将当前结点作为表尾结点 Step3 将真正的表尾结点的next域置为空Step4 返回链表头指针 LinkListbuild 字母链表的生成 要一个一个链入 LinkLists head LinkList malloc m p head s LinkList malloc m s data a i 1 p next s p s p next NULL returnhead head是全局变量 此语句可省 LinkListbuild 字母链表的生成 要一个一个链入 inti LinkLists head LinkList malloc m m sizeof test 前面已求出p head for i 1 idata i a 1 为第i个结点值域赋值p next s 让指针变量p改为指向新结点s p next NULL 最后一个结点的next为空returnhead 新手特别容易忘记 voiddisplay head 字母链表的输出 p head next 只要没到最后一个元素 就不停地 顺藤摸瓜 输出while p NULL printf c p data p p next 讨论 要统计链表中数据元素的个数 该如何改写 sum intsum 0 课堂练习 有线性表 有n个整数组成 n和n个整数均有用户输入 请建立单链表提示 Step1 定义结构体Step2 定义功能函数LinkListbuild Step3 在主函数中调用intmain 2 单链表的修改 或读取 思路 要修改第i个数据元素 关键是要先找到该结点的指针p 然后给p data赋值即可 难点 单链表中想取得第i个元素 必须从头指针出发寻找 顺藤摸瓜 不能随机存取 StatusGetElem L LinkListL inti ElemType 3 单链表的插入 在链表中插入一个元素的示意图如下 p next s next 1 元素x结点应预先生成 2 结点b做x的后继 即把结点b的地址存入s的next域 3 结点x作为a的后继 即把结点x的地址s存入P的next域 s LinkList malloc m s data x s next p next p next的值即b的地址 p next s 如果把以上两个语句颠倒顺序 可以吗 3 结点x作为a的后继 s next p next 2 结点b做x的后继 p next s p next 找不到了 StatusListInsert LinkList 单链表结点插入的演示 p L next j 1 while p j i p p next j if p NULL i 1 s LinkList malloc m s data x s next p next p next s StatusListInsert LinkList 单链表结点插入的演示 4 单链表的删除 在链表中删除某元素的示意图如下 删除步骤 即核心语句 q p next 保存b的指针 靠它才能指向cp next q next a c两结点相连free q 删除b结点 彻底释放 p next p next next 删除b 让p的next域存c的地址 StatusListDelete LinkList 单链表结点的删除演示 5 应用举例 两个链表的归并 教材P31 算法要求 已知 线性表A B 分别由单链表LA LB存储 其中数据元素按值非递减有序排列 要求 将A B归并为一个新的线性表C C的数据元素仍按值非递减排列 设线性表C由单链表LC存储 假设 A 3 5 8 11 B 2 6 8 9 11 预测 合并后C 2 3 5 6 8 8 9 11 11 用链表可表示为 头结点 算法分析 算法主要包括 搜索 比较 插入三个操作 搜索 需要两个指针搜索两个链表 比较 比较结点数据域中数据的大小 插入 将两个结点中数据小的结点插入新链表 La Pa Pb用于搜索La和Lb Pc指向新链表当前结点 链表Pc的结点都是重新生成 空间效率低 La Lb Lc Pc 提高空间效率 算法实现 voidMergeList L LinkList La LinkList Lb LinkList Lc 按值排序的单链表La Lb 归并为Lc后也按值排序 4 free Lb 释放Lb的头结点 MergeList L 3 如果La没有结束 将La的剩余部分链入Lc否则 将Lb的剩余部分链入Lc 2 当 pa pb都非表尾 将pa pb结点按大小依次插入C中 如果 pa所指结点小于pb 将pa作为pc的后继 pa成为Lc最新结点 否则 将pb作为pc的后继 pb成为Lc最新结点 1 pa pb指向La Lb的首元结点 用La的头结点做Lc的头结点 3 if pa pc next pa elsepc next pb 2 while papb pb next 3 pc next pa pa pb 1 pa La next pb Lb next pc La voidMergeList L LinkList 释放Lb的头结点 MergeList L 算法实现 讨论1 链表能不能首尾相连 怎样实现 答 能 只要将表中最后一个结点的指针域指向头结点即可 P next head 这种形成环路的链表称为循环链表 特别 带头结点的空循环链表样式 参见教材P35 特点 1 从任一结点出发均可找到表中其他结点 2 操作仅有一点与单链表不同 循环条件单链表 p NULL或p next NULL循环链表 p head或p next head 6 其它链表形式 讨论2 单链表只能查找结点的直接后继 能不能查找直接前驱 如何实现 答 能 只要把单链表再多开一个指针域即可 例如用 next和 prior 双向链表在非线性结构 如树结构 中将大量使用 这种有两个指针的链表称为双向链表 其特点是可以双向查找表中结点 参见教材P35 39 特别 带头结点的空双向链表样式 Head 猴子选猴王 有n个猴子 编号从1到n 站成一圈从编号为1的猴子开始从1到3报数 凡报数为3的猴子退出圈子 圈中最后剩下的一个猴子就是猴王 从键盘读入猴子个数n 输出猴王的编号 可以用循环队列来模拟此过程 请编程实现 解题思路 1 先建立循环队列 1 2 n 2 模拟报数过程 删除报数为3的结点 当链表中只剩一个结点时 报数过程结束只有一个结点的循环链表有何特征 p next p 程序实现 1 建立循环链表 1 2 n LinkListbuild intn inti LinkListhead p s p head LinkList malloc sizeof Lnode p data 1 for i 2 idata i p next s p s p next head 建立循环returnhead intcount LinkListhead inti 1 LinkListq p head while p next p 当圈中猴子多于1个if i 2 跳过下一个 重新报数q p next p next q next free q p p next i 1 else 正常报数p p next i returnp data 程序实现 2 报数过程模拟 2 3 3链表的运算效率分析 1 查找因线性链表只能顺序存取 即在查找时要从头指针找起 查找的时间复杂度为O n 时间效率分析 2 插入和删除因线性链表不需要移动元素 只要修改指针 一般情况下时间复杂度为O 1 空间效率分析 链表中每个结点都要增加一个指针空间 相当于总共增加了n个整型变量 空间复杂度为O n 2 4 1多项式的线性表表示An x anxn an 1xn 1 a1x a0用线性表表示为 A an an 1 a1 a0 若多项式的阶次很高 而系数ai不为零的很少 则这种表示浪费空间 可写为 A x amxem am 1xem 1 a1xe1 a0 xe0 用线性表表示为 A am em am 1 em 1 a1 e1 a0 e0 比如 A x 2x32 3x2表示为线性表 A 2 32 3 2 2 4应用举例 一元多项式的计算 多项式相加的方法 A B C线性表C置空各取线性表A和B的第一个元素作为当前处理的元素比较当前处理的元素的指数值 相等 系数相加若不为零追加到线性表C 各取线性表A和B的下一个元素作为当前处理的元素 若指数不相等 则把大的元素追加到线性表C 取该元素所在线性表的下一个元素作为当前处理的元素 重复步骤3直到其中一个线性表处理完毕 再把另一个线性表的剩余元素追加到线性表C 一 多项式的数组存放 defineMAXN100typedefstructterm floatcoef 系数coefficientintexp 指数exponent TERM TERMpoly MAXN 2 4 2顺序结构的加法实现 二 程序实现 intah at bh bt ch ct free intappend floatc inte if free MAXN return 1 poly free ceof c poly free exp e free return 0 intpoly add intah intat intbh intbt int ch p int ct p inta p b p a exp b exp floatc coef a p ah b p bh ch p free while a pb exp if append poly a p coef a exp return 1 a p else if append poly b p coef b exp return 1 b p while b p bt if append poly b p coef poly b p exp return 1 b p while a p at if append poly a p coef poly a p exp return 1 a p ct p free 1 分析 设多项式A和B的非零项个数为m和n 该算法的时间复杂度为O m n 结点形式为 coefexplink include stdio h typedefstructnode floatcoef intexp structnode l