数据结构 第二章.ppt

2020 2 7 1 数据结构课件 本演示文稿可能包含观众讨论和即席反应 使用PowerPoint可以跟踪演示时的即席反应 在幻灯片放映中 右键单击鼠标请选择 会议记录 选择 即席反应 选项卡必要时输入即席反应单击 确定 撤消此框此动作将自动在演示文稿末尾创建一张即席反应幻灯片 包括您的观点 2020 2 7 2 第2章线性表 2 1线性表的概念及运算2 2线性表的顺序存储2 3线性表的链式存储2 4一元多项式的表示及相加 2020 2 7 3 2 1线性表的概念及运算 2 1 1线性表的逻辑结构2 1 2线性表的抽象数据类型定义 2020 2 7 4 线性表的定义 线性表 LinearList 是由n n 0 个类型相同的数据元素a1 a2 an组成的有限序列 记做 a1 a2 ai 1 ai ai 1 an 数据元素之间是一对一的关系 即每个数据元素最多有一个直接前驱和一个直接后继 线性表的逻辑结构图为 2020 2 7 5 线性表的特点 同一性 线性表由同类数据元素组成 每一个ai必须属于同一数据对象 有穷性 线性表由有限个数据元素组成 表长度就是表中数据元素的个数 有序性 线性表中相邻数据元素之间存在着序偶关系 2020 2 7 6 2 1 2线性表的抽象数据类型定义 抽象数据类型定义 ADTLinearList 数据元素 D ai ai D0 i 1 2 nn 0 D0为某一数据对象 关系 ai ai 1 D0 i 1 2 n 1 基本操作 1 InitList L 操作前提 L为未初始化线性表 操作结果 将L初始化为空表 2 DestroyList L 操作前提 线性表L已存在 操作结果 将L销毁 3 ClearList L 操作前提 线性表L已存在 操作结果 将表L置为空表 ADTLinearList 2020 2 7 7 2 2线性表的顺序存储 2 2 1线性表的顺序存储结构2 2 2线性表顺序存储结构上的基本运算 2020 2 7 8 顺序存储结构的定义 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素 使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中 即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系 采用顺序存储结构的线性表通常称为顺序表 假设线性表中每个元素占k个单元 第一个元素的地址为loc a1 则第i个元素的地址为 loc ai loc a1 i 1 k 2020 2 7 9 顺序存储结构示意图 2020 2 7 10 顺序存储结构的C语言定义 definemaxsize100 线性表可能达到的最大长度 typedefstruct ElemTypeelem maxsize 线性表占用的数组空间 intlast 记录线性表中最后一个元素在数组elem 中的位置 下标值 空表置为 1 SeqList 注意区分元素的序号和数组的下标 如a1的序号为1 而其对应的数组下标为0 2020 2 7 11 2 2 2线性表顺序存储结构的基本运算 线性表的基本运算 查找操作插入操作删除操作顺序表合并算法线性表顺序存储结构的优缺点分析 2020 2 7 12 查找操作 线性表的两种基本查找运算按序号查找GetData L i 要求查找线性表L中第i个数据元素 其结果是L elem i 1 或L elem i 1 按内容查找Locate L e 要求查找线性表L中与给定值e相等的数据元素 其结果是 若在表L中找到与e相等的元素 则返回该元素在表中的序号 若找不到 则返回一个 空序号 如 1 线性表的查找运算算法描述为 2020 2 7 13 线性表的查找运算 intLocate SeqListL ElemTypee i 0 i为扫描计数器 初值为0 即从第一个元素开始比较 while i L last 若没找到 则返回空序号 2020 2 7 14 插入操作 线性表的插入运算是指在表的第i 1 i n 1 个位置 插入一个新元素e 使长度为n的线性表 e1 ei 1 ei en 变成长度为n 1的线性表 e1 ei 1 e ei en 线性表的插入运算算法 2020 2 7 15 插入算法示意图 已知 线性表 4 9 15 28 30 30 42 51 62 需在第4个元素之前插入一个元素 21 则需要将第9个位置到第4个位置的元素依次后移一个位置 然后将 21 插入到第4个位置 2020 2 7 16 插入运算 intInsList SeqList L inti ElemTypee intk if iL last 2 首先判断插入位置是否合法 printf 插入位置i值不合法 return ERROR if L last maxsize 1 printf 表已满无法插入 return ERROR for k L last k i 1 k 为插入元素而移动位置 L elem k 1 L elem k L elem i 1 e 在C语言中数组第i个元素的下标为i 1 L last return OK 算法演示 此处连接算法演示程序 2020 2 7 17 删除操作 线性表的删除运算是指将表的第i 1 i n 个元素删去 使长度为n的线性表 e1 ei 1 ei ei 1 en 变成长度为n 1的线性表 e1 ei 1 ei 1 en 算法思路示意算法实现 2020 2 7 18 删除算法示意 将线性表 4 9 15 21 28 30 30 42 51 62 中的第5个元素删除 2020 2 7 19 删除算法 intDelList SeqList L inti ElemType e 在顺序表L中删除第i个数据元素 并用指针参数e返回其值 intk if iL last 1 printf 删除位置不合法 return ERROR e L elem i 1 将删除的元素存放到e所指向的变量中 for k i ilast k L elem k 1 L elem k 将后面的元素依次前移 L last return OK 2020 2 7 20 合并算法 已知 有两个顺序表LA和LB 其元素均为非递减有序排列 编写一个算法 将它们合并成一个顺序表LC 要求LC也是非递减有序排列 算法思想 设表LC是一个空表 为使LC也是非递减有序排列 可设两个指针i j分别指向表LA和LB中的元素 若LA elem i LB elem j 则当前先将LB elem j 插入到表LC中 若LA elem i LB elem j 当前先将LA elem i 插入到表LC中 如此进行下去 直到其中一个表被扫描完毕 然后再将未扫描完的表中剩余的所有元素放到表LC中 算法实现此处连接算法演示 2020 2 7 21 顺序表合并算法实现 voidmerge SeqList LA SeqList LB SeqList LC i 0 j 0 k 0 while ilast 2020 2 7 22 顺序存储结构的优点和缺点 优点 1 无需为表示结点间的逻辑关系而增加额外的存储空间 2 可方便地随机存取表中的任一元素 缺点 1 插入或删除运算不方便 除表尾的位置外 在表的其它位置上进行插入或删除操作都必须移动大量的结点 其效率较低 2 由于顺序表要求占用连续的存储空间 存储分配只能预先进行静态分配 因此当表长变化较大时 难以确定合适的存储规模 2020 2 7 23 2 3线性表的链式存储 链表定义 采用链式存储结构的线性表称为链表 现在我们从两个角度来讨论链表 1 从实现角度看 链表可分为动态链表和静态链表 2 从链接方式的角度看 链表可分为单链表 循环链表和双链表 2020 2 7 24 2 3 1单链表2 3 2单链表上的基本运算2 3 3循环链表2 3 4双向链表 2 3 5静态链表2 3 6顺序表和链表的比较 链表 2020 2 7 25 2 3 1单链表 结点 Node 为了正确地表示结点间的逻辑关系 必须在存储线性表的每个数据元素值的同时 存储指示其后继结点的地址 或位置 信息 这两部分信息组成的存储映象叫做结点 Node 单链表 链表中的每个结点只有一个指针域 我们将这种链表称为单链表 单链表包括两个域 数据域用来存储结点的值 指针域用来存储数据元素的直接后继的地址 或位置 头指针 指向链表头结点的指针 2020 2 7 26 单链表的示例图 2020 2 7 27 带头结点的单链表示意图 有时为了操作的方便 还可以在单链表的第一个结点之前附设一个头结点 带头结点的空单链表带头结点的单链表 2020 2 7 28 单链表的存储结构描述 typedefstructNode 结点类型定义 ElemTypedata structNode next Node LinkList LinkList为结构指针类型 2020 2 7 29 2 3 2单链表上的基本运算 线性表的基本运算 建立单链表单链表查找单链表插入操作单链表删除算法应用示例 求单链表的长度求两个集合的差 2020 2 7 30 建立单链表 头插法建表算法描述 从一个空表开始 重复读入数据 生成新结点 将读入数据存放到新结点的数据域中 然后将新结点插入到当前链表的表头结点之后 直至读入结束标志为止 2020 2 7 31 头插法建表算法 LinklistCreateFromHead LinkListL Node s intflag 1 设置一个标志 初值为1 当输入 时 flag为0 建表结束 L Linklist malloc sizeof Node 为头结点分配存储空间 L next NULL while flag c getchar if c 为读入的字符分配存储空间 s Node malloc sizeof Node s data c s next L next L next s elseflag 0 2020 2 7 32 尾插法建表 C1 s r L 2020 2 7 33 尾插法建表算法 LinklistCreateFromTail 将新增的字符追加到链表的末尾 LinkListL Node r s intflag 1 L Node malloc sizeof Node 为头结点分配存储空间 L next NULL r L r指针始终动态指向链表的当前表尾 while flag 标志 初值为1 输入 时flag为0 建表结束 c getchar if c s Node malloc sizeof Node s data c r next s r s else flag 0 r next NULL 2020 2 7 34 单链表查找 按序号查找算法描述 设带头结点的单链表的长度为n 要查找表中第i个结点 则需要从单链表的头指针L出发 从头结点 L next 开始顺着链域扫描 用指针p指向当前扫描到的结点 初值指向头结点 pL next 用j做记数器 累计当前扫描过的结点数 初值为0 当j i时 指针p所指的结点就是要找的第i个结点 算法实现 算法演示 2020 2 7 35 按序号查找算法实现 在带头结点的单链表L中查找第i个结点 若找到 1 i n 则返回该结点的存储位置 否则返回NULL Node Get LinkListL inti Node p p L j 0 从头结点开始扫描 while p next NULL jnext j 扫描下一结点 已扫描结点计数器 if i j returnp 找到了第i个结点 elsereturnNULL 找不到 i 0或i n 2020 2 7 36 按值查找算法描述 按值查找是指在单链表中查找是否有结点值等于e的结点 若有的话 则返回首次找到的其值为e的结点的存储位置 否则返回NULL 查找过程从单链表的头指针指向的头结点出发 顺着链逐个将结点的值和给定值e作比较 算法实现 算法演示 单链表查找 2020 2 7 37 按值查找算法实现 在带头结点的单链表L中查找其结点值等于key的结点 若找到则返回该结点的位置p 否则返回NULL Node Locate LinkListL ElemTypekey Node p p L next 从表中第一个结点比较 while p NULL if p data key p p next elsebreak 找到结点key 退出循环 returnp 2020 2 7 38 单链表插入操作 算法描述 要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e 需要首先在单链表中找到第i 1个结点并由指针pre指示 然后申请一个新的结点并由指针s指示 其数据域的值为e 并修改第i 1个结点的指针使其指向s 然后使s结点的指针域指向第i个结点 s a1 ai 1 ai s pre L 2020 2 7 39 单链表插入操作算法实现 voidInsList LinkListL inti ElemTypee 在带头结点的单链表L中第i个结点之前插入值为e的新结点 Node pre s pre L intk 0 while pre NULL 2020 2 7 40 单链表删除 算法描述 欲在带头结点的单链表L中删除第i个结点 则首先要通过计数方式找到第i 1个结点并使p指向第i 1个结点 而后删除第i个结点并释放结点空间 2020 2 7 41 单链表删除算法实现 voidDelList LinkListL inti ElemType e 在带头结点的单链表L中删除第i个元素 并保存其值到变量 e中 Node p r p L intk 0 while p next NULL 释放被删除的结点所占的内存空间 2020 2 7 42 求单链表的长度 算法描述 可以采用 数 结点的方法来求出单链表的长度 用指针p依次指向各个结点 从第一个元素开始 数 一直 数 到最后一个结点 p next NULL intListLength LinkListL L为带头结点的单链表 Node p p L next j 0 用来存放单链表的长度 while p NULL p p next j returnj 算法演示链接 2020 2 7 43 两个有序单链表的合并 有两个单链表LA和LB 其元素均为非递减有序排列 编写一个算法 将它们合并成一个单链表LC 要求LC也是非递减有序排列 要求 利用新表LC利用现有的表LA和LB中的元素结点空间 而不需要额外申请结点空间 例如LA 2 2 3 LB 1 3 3 4 则LC 1 2 2 3 3 3 4 算法描述 要求利用现有的表LA和LB中的结点空间来建立新表LC 可通过更改结点的next域来重建新的元素之间的线性关系 为保证新表仍然递增有序 可以利用尾插入法建立单链表的方法 只是新建表中的结点不用malloc 而只需要从表LA和LB中选择合适的点插入到新表LC中即可 2020 2 7 44 两个有序单链表的合并的算法实现 LinkListMergeLinkList LinkListLA LinkListLB 将递增有序的单链表LA和LB合并成一个递增有序的单链表LC Node pa pb LinkListLC 将LC初始置空表 pa和pb分别指向两个单链表LA和LB中的第一个结点 r初值为LC pa LA next pb LB next LC LA LC next NULL r LC 初始化操作 2020 2 7 45 两个有序单链表的合并的算法实现 续 当两个表中均未处理完时 比较选择将较小值结点插入到新表LC中 while pa NULL MergeLinkList 2020 2 7 46 2 3 3循环链表 循环链表 CircularLinkedList 是一个首尾相接的链表 特点 将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点 就得到了单链形式的循环链表 并称为循环单链表 在循环单链表中 表中所有结点被链在一个环上 带头结点循环单链表示意图 2020 2 7 47 带头结点的循环单链表示意图 空链表 带头结点的一般形式 带尾结点的一般形式 2020 2 7 48 循环单链表合并为一个循环单链表 已知 有两个带头结点的循环单链表LA LB 编写一个算法 将两个循环单链表合并为一个循环单链表 其头指针为LA 算法思想 先找到两个链表的尾 并分别由指针p q指向它们 然后将第一个链表的尾与第二个表的第一个结点链接起来 并修改第二个表的尾Q 使它的链域指向第一个表的头结点 2020 2 7 49 循环单链表合并算法实现 LinkListmerge 1 LinkListLA LinkListLB 此算法将两个链表的首尾连接起来 Node p q p LA q LB while p next LA p p next 找到表LA的表尾 while q next LB q q next 找到表LB的表尾 q next LA 修改表LB的尾指针 使之指向表LA的头结点 p next LB next 修改表LA的尾指针 使之指向表LB中的第一个结点 free LB return LA 2020 2 7 50 2 3 4双向链表 双向链表 在单链表的每个结点里再增加一个指向其前趋的指针域prior 这样形成的链表中就有两条方向不同的链 我们称之为双 向 链表 DoubleLinkedList 双向链表的结构定义 typedefstructDnode ElemTypedata structDNode prior next DNode DoubleList 2020 2 7 51 双链表的结构定义 双链表的结点结构 2020 2 7 52 双向循环链表示意图 空的双向循环链表 非空的双向循环链表 2020 2 7 53 双向链表的前插操作 算法描述 欲在双向链表第i个结点之前插入一个的新的结点 则指针的变化情况如图所示 2020 2 7 54 双向链表的前插操作算法实现 voidDlinkIns DoubleListL inti ElemTypee DNode s p 首先检查待插入的位置i是否合法 若位置i合法 则让指针p指向它 s DNode malloc sizeof DNode if s s data e s prior p prior p prior next s s next p p prior s returnTRUE elsereturnFALSE 算法演示连接 2020 2 7 55 双向链表的删除操作 算法描述 欲删除双向链表中的第i个结点 则指针的变化情况如图所示 2020 2 7 56 双向链表的删除操作算法实现 intDlinkDel DoubleListL inti ElemType e DNode p 首先检查待插入的位置i是否合法 若位置i合法 则让指针p指向它 e p data p prior next p next p next prior p prior free p returnTRUE 2020 2 7 57 2 3 5静态链表 基本概念 游标实现链表的方法 定义一个较大的结构数组作为备用结点空间 即存储池 当申请结点时 每个结点应含有两个域 data域和next域 data域存放结点的数据信息 next域为游标指示器 指示后继结点在结构数组中的相对位置 即数组下标 数组的第0个分量可以设计成表的头结点 头结点的next域指示了表中第一个结点的位置 为0表示静态单链表的结束 我们把这种用游标指示器实现的单链表叫做静态单链表 StaticLinkedList 静态链表的结构定义 静态链表的插入和删除操作示例 基本操作 初始化 分配结点与结点回收 前插操作 删除 2020 2 7 58 静态链表的结构定义 defineMaxsize 链表可能达到的最大长度typedefstruct ElemTypedata intcursor Component StaticList Maxsize 2020 2 7 59 静态链表的插入和删除操作示例 已知 线性表a b c d f g h i Maxsize 11 2020 2 7 60 静态链表初始化 算法描述 初始化操作是指将这个静态单链表初始化为一个备用静态单链表 设space为静态单链表的名字 av为备用单链表的头指针 其算法如下 voidinitial StaticListspace int av intk space 0 cursor 0 设置静态单链表的头指针指向位置0 for k 0 kcursor k 1 连链 space Maxsize 1 cursor 0 标记链尾 av 1 设置备用链表头指针初值 2020 2 7 61 静态链表分配结点与结点回收 分配结点intgetnode int av 从备用链表摘下一个结点空间 分配给待插入静态链表中的元素 inti av av space av cur returni 结点回收voidfreenode int av intk 将下标为k的空闲结点插入到备用链表 space k cursor av av k 2020 2 7 62 2 4一元多项式的表示及相加 一元多项式可按升幂的形式写成 Pn x p0 p1xe1 p2xe2 pnxen 其中ei为第i项的指数 pi是指数ei的项的系数 且1 e1 e2 en 假设Qm x 是一个一元多项式 则它也可以用一个线性表Q来表示 即 Q q0 q1 q2 qm 若假设m n 则两个多项式相加的结果Rn x Pn x Qm x 也可以用线性表R来表示 R p0 q0 p1 q1 p2 q2 pm qm pm 1 pn 2020 2 7 63 一元多项式的存储 一元多项式的顺序存储表示一元多项式的链式存储表示 2020 2 7 64 一元多项式的顺序存储表示1 一元多项式Pn x 的顺序表示有两种 法1 只存储该一元多项式各项的系数 每个系数所对应的指数项则隐含在存储系数的顺序表的下标中 即p 0 存系数p0 对应为x0的系数 p 1 存系数p1 对应为x1的系数 p n 存系数pn 对应为xn的系数 采用这种存储方法使得多项式的相加运算的算法定义十分简单 只需将下标相同的单元的内容相加即可 适合于存储表示非零系数多的多项式 2020 2 7 65 一元多项式的顺序存储表示2 法2 采用只存储非零项的方法 此时每个非零项需要存储 非零项系数和非零项指数 适合存储表示非零项少的多项式 图2 19一元多项式只存非零项存储示意图 2020 2 7 66 一元多项式的链式存储表示 在链式存储中 对一元多项式只存非零项 则该多项式中每一非零项由两部分构成 指数项和系数项 用单链表存储表示的结点结构为 用单链表存储多项式的结点结构如下 structPolynode intcoef intexp Polynode next Polynode Polylist 2020 2 7 67 建立一元多项式链式存储的算法 算法思想 通过键盘输入一组多项式的系数和指数 用尾插法建立一元多项式的链表 以输入系数0为结束标志 并约定建立多项式链表时 总是按指数从小到大的顺序排列 算法描述 Polylistpolycreate Polynode head rear s intc e rear head Polynode malloc sizeof Polynode 建立多项式的头结点 rear始终指向单链表的尾 scanf d d 2020 2 7 68 一元多项式的单链表表示示意图 说明 图示分别为多项式A x 7 3x 9x8 5x17B x 8x 22x7 9x8 2020 2 7 69 两个一元多项式相加 运算规则 两个多项式中所有指数相同的项的对应系数相加 若和不为零 则构成 和多项式 中的一项 所有指数不相同的项均复抄到 和多项式 中 算法实现 算法演示若p expexp 则结点p所指的结点应是 和多项式 中的一项 令指针p后移 若p exp q exp 则结点q所指的结点应是 和多项式 中的一项 将结点q插入在结点p之前 且令指针q在原来的链表上后移 若p exp q exp 则将两个结点中的系数相加 当和不为零时修改结点p的系数域 释放q结点 若和为零 则和多项式中无此项 从A中删去p结点 同时释放p和q结点 2020 2 7 70 两个多项式相加算法实现 voidpolyadd Polylistpolya Polylistpolyb p和q分别指向polya和polyb链表中的当前计算结点 pre指向和多项式链表中的尾结点 whilep NULL q NULL if p expexp 将p结点加入到和多项式中 elseif p exp q exp 若指数相等 则相应的系数相加 若系数为0则删除p q节点 else 将q结点加入到和多项式中 将多项式polya或polyb中剩余的结点加入到和多项式中 2020 2 7 71 2 5顺序表和链表的比较 1 基于空间的考虑2 基于时间的考虑3 基于语言的考虑 2020 2 7 72 线性表链式存储方式的比较 2020 2 7 73 2 6总结与提高 主要知识点1 线性表的特征 线性表中每个数据元素有且仅有一个直接前驱和一个直接后继 第一个结点无前驱 最后一个结点无后继 2 线性表存储方式 线性表顺序存储 顺序表 采用静态分配方式 借助于C语言的数组类型 申请一组连续的地址空间 依次存放表中元素 其逻辑次序隐含在存储顺序之中 2020 2 7 74 2 6总结与提高 线性表链式存储 链表 采用动态分配方式 借助于C语言的指针类型 动态申请与动态释放地址空间 故链表中的各结点的物理存储可以是不连续的 当表长度变化时仅需适当变化指针的联接 适合于表中元素个数动态变化 3 单链表的操作特点 顺链操作技术 指针保留技术4 链表处理中的相关技术 2020 2 7 75 典型题例 例1 已知顺序表L中的数据元素类型为int 设计算法将其调整为左右两部分 左边的元素 即排在前面的 均为奇数 右边所有元素 即排在后面的 均为偶数 并要求算法的时间复杂度为O n 空间复杂度为O 1 2020 2 7 76 例1 问题分析 初见此题 可能会想到额外申请1个顺序表空间 之后依次从顺序表L中选择奇数放入新表前部分 选择偶数放在新表的后半部分 但是题目要求空间复杂度为O 1 很显然上述方法是不可行的 既然要求空间复杂度为O 1 说明只能借助1个辅助空间 分析题目要求 其实我们只需要将位于表左半部分的偶数与位于表右半部分的奇数通过一个辅助变量进行交换即可 为此我们可以设置两个位置指示器i和j i初值为0 j初值为L last 当L elem i 为偶数 L elem j 为奇数时 则将L elem i 与L elem j 交换 否则 L elem i 为奇数 i L elem j 为偶数 j 这样既可以保证算法的时间复杂度为O n 亦可保证空间复杂度为O 1 2020 2 7 77 算法描述 AdjustSqlist SeqList L inti 0 j L last while ielem i 2 0 i 从表的左半部分开始检测 若为奇数 则i加1 直到找到偶数为止 while L elem j 2 0 j 从表的右半部分开始检测 若为偶数 则j减1 直到找到奇数为止 if ielem i L elem i L elem j L elem j t 交换 endofAdjustSqlist 2020 2 7 78 例2 算法实现带头结点单链表的就地逆置问题 问题分析 逆置就是使得表中内容由原来的 a1 a2 ai 1 ai ai 1 an 变为 an an 1 ai 1 ai ai 1 a1 就地逆置就是不需要额外申请结点空间 只需要利用原有的表中的节点空间 若对顺序表中的元素进行逆置 可以借助于 交换 前后相应元素 对单链表中的元素进行逆置 则不能按 交换 思路 因为对于链表中第i个结点需要顺链查找第n i 1 链表长度为n 个结点 逆置链表的时间复杂度将达O n2 2020 2 7 79 算法思路 逆置后的单链表初始为空 表中的结点不是新生成的 而是从原链表中依次 删除 再逐个头插入到逆置表中 类同算法2 5头查法创建链表 设逆置链表的初态为空表 删除 已知链表中的第一个结点