第二章 线性表.ppt

第二章线性表 2 1线性表的类型定义ADT2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 4线性表两种实现方法的比较2 5其他类型的线性表 循环链表 双链表 静态链表等 第二章线性表 数据元素之间是一种线性关系 即在数据元素的非空有限集中数据元素的排列是顺序的 线性结构 线性结构是一个数据元素的有序 次序 而不是数据 集 线性结构 在数据元素的非空的有限集合中 存在唯一的一个被称为 第一个 的数据元素 存在唯一的一个被称为 最后一个 的数据元素 除第一个元素外 集合中每个元素都有且仅有一个 直接 前驱 除最后一个元素外 集合中每个元素都有且仅有一个 直接 后继 线性表 LinearList 定义 定义 n个具有相同特性的数据元素组成的有限序列 表示 a1 ai 1 ai ai 1 an ai 1是ai的直接前驱元素 ai 1是ai的直接后继元素数据元素ai在线性表中有确定的位置i i称为位序线性表中数据元素的个数n称为线性表的长度 n 0时 线性表称为空表 2 1线性表的抽象数据类型定义 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 称n为线性表的表长 称n 0时的线性表为空表 数据关系 R ai ai 1 D 1 2 n 设线性表为 a1 a2 ai ai 1 an 称i为ai在线性表中的位序 基本操作 线性表初始化 ListInit L 初始条件 线性表L不存在 操作结果 构造一个空的线性表L 求线性表的长度 ListLength L 取表元素 ListGet L i 按值查找 ListLocate L x 清空线性表 ListClear L 判空线性表 ListEmpty L 求前驱 ListPrior L e 求后继 ListNext L e 插入 ListInsert L i e 删除 ListDelete L i ADTList 线性表举例1 遍历线性表L ListTraverse ListL visit 遍历线性表if ListEmpty L printf 空表 elsefor i 1 i ListLength L i visit ListGet L i 访问可以是查询 输出元素 修改元素和打印元素等操作 线性表举例2 合并线性表L ListListMerge ListLa ListLb La和Lb是两个非递减有序的线性表 将线性表La和Lb合并成一个新的线性表Lc Lc也非递减 ListInit Lc i j 1 k 0 La len ListLength La Lb len ListLength Lb while i bj ListInsert Lc k ai i else ListInsert Lc k bj j 可能有相同的元素 即无公差 注意ListInsert函数的调用方法 函数的返回值为List类型 线性表举例2续 合并线性表L while i La len Lb已空 将La表的剩余部分复制到新表ai ListGet La i ListInsert Lc k ai while j Lb len La已空 将Lb表的剩余部分复制到新表bj ListGet Lb j ListInsert Lc k bj return Lc ListMerge 算法的时间复杂度显然为 O ListLength La ListLength Lb 2 2线性表的顺序表示和实现 任何一个算法的设计取决于选定的逻辑结构 而算法的实现依赖于采用的存储结构 介绍线性表的存储结构 线性表的顺序表示和实现 线性表的顺序表示 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素 用这种存储形式存储的线性表称为顺序表 设a 的存储地址为Loc a 每个数据元素占L个存储单元 则第i个数据元素的地址为 Loc ai Loc a1 i 1 L1 i n 顺序表用元素的物理关系 存储位置 表达了数据元素的逻辑关系 可以随机存取 线性表的起始地址称作线性表的基地址 线性表的顺序表示和实现 顺序存储结构的线性表的类型定义如下 typedefstruct ElemTypedata MAXSIZE 存放线性表的数组intlength length是顺序表的长度 SeqList 可以是int float等类型 用数组表示顺序表 顺序表上基本运算的实现 1 顺序表的初始化 SeqListSeqListInit 构造一个空的线性表LSeqListL 定义L为顺序表L length 0 顺序表的长度为0returnL 函数返回值的类型 顺序表上基本运算的实现 2 插入运算 在第i个位置 插入元素e思想 把第i个位置开始的元素 依次后移步骤 1 当前表是否已经满 2 输入是否有效 3 插入元素 顺序表上基本运算的实现 2 插入元素 voidSeqListInsert SeqListL inti ElemTypex 在顺序表中的第i个位置插入元素xif L length MAXSIZE printf 表满 exit 0 表满 退出if iL length 1 printf 位置错 exit 0 插入位置错 退出 因为下标从0开始 因此第i个数据元素是L data i 1 for j L length 1 j i 1 j L data j 1 L data j 第i个位置后的数组元素逐一后移L data i 1 x 新元素插入到第i个位置L length 顺序表长度加1 该算法注意检查边界条件 如位置i length 1时 即插入在最后一个元素后 而i 1时 表示插入在表头 思考 如果for循环改为如下 for j i 1 j L length 1 j 结果将如何 插入结果看教材P 23 图2 3 插入算法的时间复杂度分析 基本操作是移动数据 在第i个位置插入x 从an到ai都要向后移动一个位置 共需移动n i 1个元素 i的取值范围为 即有n 1个位置插入 设在第i个位置插入的概率为pi 平均移动数据元素的次数 期望值 为 设则 即时间复杂度为O n 顺序表上基本运算的实现 3 删除运算 删除第i个元素e思想 把第i 1个位置开始的元素 依次前移步骤 1 要检查删除位置的有效性 2 依次移动元素3 长度减1 顺序表上基本运算的实现 3 删除元素 voidSeqListDelete SeqListL inti 删除顺序表中的第i个元素if iL length printf 位置非法 exit 0 检查空表及删除位置的合法性for j i j L length 1 j L data j 1 L data j 向上移动 逐一前移L length 顺序表长度减1 请看教材P 24 图2 4 注意边界条件元素位置为 a i 1 注意元素的位置为i 但是其下标为i 1 如长度为10 则下标最大为9 删除算法的时间复杂度分析 基本操作是移动数据 删除第i个元素时 从ai 1到an都要向前移动一个位置 共需移动n i个元素 i的取值范围为 平均移动数据元素的次数 期望值 为 设在第i个位置删除的概率为pi n i 1 1 n i 即时间复杂度为O n 顺序表上基本运算的实现 4 按值查找 intSeqListLocate SeqListL ElemTypex 在顺序表L中查找第一个与x值相等的元素 若查找成功 则返回它在顺序表中的位置 否则 返回0 i 1 while i L length 查找失败 该算法的时间复杂度为O ListLength L 注意是位置 而不是下标 顺序结构的优缺点 优点 算法简单 容易实现 可以实现随机存取 缺点 插入和删除操作复杂 移动大量的数据元素 在插入操作时 还要涉及到重新分配大块空间问题 使用情况 建立结构后只做大量的查询而很少做插入 删除的场合 顺序表算法设计例 用顺序表表示集合 设计算法实现集合的求交集运算 C A B 即C中元素是A B中的公共元素 解 算法为 扫描A中的元素A data i 若它与B中某个元素相同 表示是交集元素 将其放到C中 voidIntersection SeqListA SeqListB SeqListC inti j k 0 for i 0 i A lenghth i j 0 while j B length 修改集合长度 Intersection 该算法的时间复杂度为O n2 思考 求C A B即并集运算 C中元素为A和B中非重复出现的所有元素 算法 先将A复制到C中 然后扫描B中的元素B data i 若它与A中所有元素均不相同 表示是并集元素 将其放到C中 求C A B 顺序表算法设计例 设计一个高效算法 从顺序表中删除所有元素值为x的元素要求复杂度为O 1 算法 首先确定表L中第一个值为x的元素的位置i 然后依次检查L data i 1 L data length 中每个元素L data j i 1 j L length 若L data j x 则将L data j 存入L data i 中 并令i 最后顺序表长度为i 算法如下 Voiddelallx SequListL ElemTypex 删除所有值为x的元素inti 0 j while i L length delallx 本算法只扫描一次顺序表 即将值不为x的元素前移了只一次 所以为O n 思考 有其它方法吗 从头开始扫描表L 用k记录下元素值为x的元素的个数 对于不等于x的元素 前移k个位置 算法如下 Voiddelallx2 SequListL ElemTypex 删除所有值为x的元素inti 0 k 0 while i L length if L data i x k k记录被删记录的个数elseL data i k L data i 前移k个位置i L length L length k delallx2 时间复杂度仍然为O n 2 3线性表的链式表示和实现 线性表的链式表示 以链式结构存储的线性表称之为线性链表 线性表中的数据元素可以用任意的存储单元来存储 逻辑相邻的两元素的存储空间可以是不连续的 为表示逻辑上的顺序关系 对表的每个数据元素除存储本身的信息之外 还需存储指示其后继的信息 这两部分信息组成数据元素的存储映象 称为结点 node 可以考虑利用小的零散空间 串 起来 表示线性表 即把线性表的元素分散插入到系统所控制的零散空间中 然后用 指针 串起来 组成一个有序的线性表 用指针表示数据元素的有序性 这样的小空间 可以是连续的 也可以不是连续的 空间至少包括 数据元素和指针两个区域 线性表的链式表示 单链表结构图示 链表 结点ai head 单链表结构图示 单链表的头指针为H LinkListH 单链表的C表示 结点描述方法 typedefstructNode ElemTypedata structNode next LNode LinkedList 关于typedefTypedefintINTEGER 则可以 INTEGERa b 相当于 inta b 带头结点的单链表 通常情况下 在第一个结点前附设一个结点 成为 头结点 LNode p p LNode malloc sizeof LNode 则完成了申请一块LNode类型的存储单元的操作 并将其地址赋值给变量p 线性链表操作的实现 1 带头结点的单链表的初始化 LinkedListLinkedListInit 建立一个空的单链表L LNode malloc sizeof LNode if L null printf 没有足够的内存空间 exit 0 L next NULL returnL 时间复杂度为O 1 线性链表操作的实现 2 求表长 intLinkedListLength LinkedListL 求带头结点的单链表的长度p L next p指向链表的第一个结点j 0 while p j p p next p所指的是第j个结点returnj 该算法的操作主要是指针的移动 指针从头移到尾 所以时间复杂度为 O n 而不是头结点 注意边界条件 如空表时 线性链表操作的实现 3 按序号查找 取第i个元素 LinkedListLinkedListGet LinkedListL inti 在单链表L中查找第i个元素结点 若查找成功则返回指向 该结点的指针 否则返回空指针 if inext p指向第一个元素结点j 1 计数器初始化while p NULL 参数i太大 查找失败 该算法的操作仍然是指针的移动 时间复杂度为 O n 注意边界条件 如果i 1时 指针指向的位置 如果把j置为0如何 教材P 27 算法2 11 线性链表操作的实现 4 按值查找 元素定位 LinkedListLinkedListLocate LinkedListL ElemTypex 在单链表L中查找值为x的结点 找到后返回其指向该结 点的指针 否则返回空指针 p L next j 1 while p NULL 该算法的操作仍然是指针的移动 时间复杂度为 O n 当然也可以返回该结点的位置j 如果不存在 返回为0 教材P 28 算法2 12 线性链表操作的实现 5 若p表示当前结点 pre表示前一个结点 在p前插入元素ss next pre next pre next s 插入元素 P s 线性链表操作的实现 5 插入算法1 voidLinkedListInsert1 LinkedListL LinkedListp ElemTypex 在结点p之前插入元素为x的结点pre L pre为前驱结点的指针while pre next p 插入新结点 时间复杂度为O n 注意模拟插入在第一个结点前 教材P 29 算法2 16 线性链表操作的实现 5 插入算法2 voidLinkedListInsert2 LinkedListL inti ElemTypex 在单链表L的第i个位置上插入值为x的元素p L j 1 while p 新结点插入在第i 1和第i个结点之间 注意边界条件 插入在第一个结点前和最后一个结点 线性链表操作的实现 6 若p表示当前结点 pre表示前一个结点 pre next p next free p p pre next 删除元素 pre p 线性链表操作的实现 6 删除元素 voidLinkedListDel LinkedListL inti 删除单链表L上的第i个结点if L next NULL printf 空表 n exit 0 if inext 释放被删除结点 时间复杂度为O n 教材P 30 算法2 17 线性链表操作的实现 7 建立单链表 头插法 线性链表操作的实现 7 头插法建立单链表算法 LinkedListLinkedListCreat1 用头插法建立带头结点的单链表LinkedListL L LNode malloc sizeof LNode L next NULL 初始化一个空链表 L为头指针scanf 三个关键语句 注意该算法输入数据的顺序和线性表中的数据顺序是相反的 教材P 31 算法2 18 线性链表操作的实现 7 建立单链表 尾插法 注意该图应该有头结点 线性链表操作的实现 7 尾插法建立单链表算法 LinkedListLinkedListCreat3 用尾插法建立带头结点的单链表LinkedListL L LNode malloc sizeof LNode 申请头结点L next NULL r L 初始化 尾指针指向头结点scanf 教材P 32 算法2 20 注意与教材对最后一个结点的不同处理方法 链式结构的特点 非随机存贮结构 所以取表元素要慢于顺序表 适合于插入和删除操作节约了大块内存实际上用空间换取了时间 结点中加入了指针 使得这两种操作转换为指针操作 2 4线性表实现方法的比较 实现不同顺序表方法简单 各种高级语言中都有数组类型 容易实现 链表的操作是基于指针的 相对来讲复杂些 存储空间的占用和分配不同从存储的角度考虑来看 顺序表的存储空间是静态分配的 在程序执行之前必须明确规定它的存储规模 也就是说事先对 MAXSIZE 要有合适的设定 过大造成浪费 过小造成溢出 而链表是动态分配存储空间的 不用事先估计存储规模 可见对线性表的长度或存储规模难以估计时 采用链表 线性表运算的实现不同按序号访问数据元素 使用顺序表优于链表 插入删除操作 使用链表优于顺序表 O 1 O n 第二章复习 下述哪一条是顺序存储结构的优点 北方交通大学2001一 4 2分 A 存储密度大B 插入运算方便C 删除运算方便D 可方便地用于各种逻辑结构的存储表示答案为 A 第二章复习 链表不具有的特点是 福州大学1998一 8 2分 A 插入 删除不需要移动元素B 可随机访问任一元素C 不必事先估计存储空间D 所需空间与线性长度成正比答案为 B 第二章复习 下面的叙述不正确的是 南京理工大学1996一 10 2分 A 线性表在链式存储时 查找第i个元素的时间同i的值成正比B 线性表在链式存储时 查找第i个元素的时间同i的值无关C 线性表在顺序存储时 查找第i个元素的时间同i的值成正比D 线性表在顺序存储时 查找第i个元素的时间同i的值无关答案为 B和C 第二章复习 在单链表中设置头结点的作用是 哈尔滨工业大学2000二 1 1分 答案为 主要是使插入和删除等操作统一 在第一个元素之前插入元素和删除第一个结点不必另作判断 另外 不论链表是否为空 链表指针不变 第二章复习 对于一个具有n个结点的单链表 在已知的结点 p后插入一个新结点的时间复杂度为 在给定值为x的结点后插入一个新结点的时间复杂度为 哈尔滨工业大学2001一 1 2分 答案为 O 1 O n 第二章复习 线性表有两种存储结构 一是顺序表 二是链表 试问 1 如果有n个线性表同时并存 并且在处理过程中各表的长度会动态变化 线性表的总数也会自动地改变 在此情况下 应选用哪种存储结构 为什么 2 若线性表的总数基本稳定 且很少进行插入和删除 但要求以最快的速度存取线性表中的元素 那么应采用哪种存储结构 为什么 西安电子科技大学1999软件二 1 5分 答案 1 应选择链式存储结构 因为它可动态申请内存空间 不受表长度 即表中元素个数 的影响 插入 删除时间复杂度为O 1 答案 2 应选择顺序存储结构 顺序表可以随机存取 时间复杂度为O 1 第二章复习 设单链表结点指针域为next 试写出删除链表中指针p所指结点的直接后继的C语言语句 北京科技大学2000一 3 答案为 q p next p next q next free q 将带头结点的单链表就地逆置 LinkedListinvert LinkedListhead 就地逆置单链表p head next p为工作指针 指向第一个元素head next NULL 保留第一个元素的指针后 将头结点的指针域置空while p NULL 将原链表的元素按头插法插入 r p next 暂存p的后继p next head next 逆置 头插法插入 head next p 头结点的指针域指向新插入的结点p r 恢复待处理结点 return head invert 算法中对单链表中每个结点只处理一次 其时间复杂度为O n 教材P 39 算法2 9 算法设计题 在一个非递减有序的线性表中 有数值相同的元素存在 若存储方式为单链表 设计算法去掉数值相同的元素 使表中不再有重复的元素 分析算法的时间复杂度 题目分析 在链表中 删除数值相同的元素 要知道被删除元素结点的前驱结点 算法如下 LinkedListDelSame LinkedListla la是非递减有序的单链表 本算法去掉数值相同的元素 使表中不再有重复的元素 pre la next pre是p所指向的前驱结点的指针p pre next p是工作指针 设链表中至少有一个结点while p NULL if p data pre data 处理相同元素值的结点 u p p p next pre next p free u 释放相同元素值的结点else pre p p p next 处理前驱 后继元素值不同 pre next p 应该去掉 DelSame 算法中对单链表中每个结点只处理一次 其时间复杂度为O n 教材P 40 算法3 20 教材错误 算法说明 算法中假设链表至少有一个结点 即初始时pre不为空 否则p next无意义 算法中最后一条语句pre next p是必须的 因为链表最后可能有数据域值相同的结点 这些结点均被删除 指针后移使p NULL而退出while循环 所以应有pre next p使链表有尾 若链表尾部没数据域相同的结点 pre和p为前驱和后继 pre next p也是对的 书上这段话应该去掉 2 5其它链表之 循环链表 单循环链表 循环链表 链表尾结点的指针域指向头结点 这样形成的链表我们叫做循环链表 可以从链表中任意一个结点开始遍历整个链表 在单循环链表上的操作与非循环链表的操作基本上相同 只是把判断指针是否为NULL改为是否是头指针即可 连接两个单循环链表L1和L2 操作如下 p R1 next 保存L1的头结点指针R1 next R2 next next 头尾连接free R2 next 释放第二个表的头结点R2 next p 注意 单循环链表往往只设置尾指针 而用一个指向尾结点的指针来标识 这样在进行某些操作的时候可以提高效率 使得复杂度从O n 降到O 1 某些操作如 最后一个元素之后插入一个元素和删除第一个元素 2 5其它链表之 双链表 希望查找前驱的时间复杂度达到O 1 我们可以用空间换时间 每个结点再加一个指向前驱的指针域 使链表可以进行双方向查找 用这种结点结构组成的链表称为双向链表 结点的结构图 既可方便的找后继 亦可方便的找前驱 即以空间换时间 双向链表的逻辑表示 prior data next 带头结点的双向循环链表 空双循环链表 带头结点的双向循环链表结点 双向链表的C表示 typedefstructDNode ElemTypedata structDNode prior next DLNode DLinkedList 双向链表结点的类型定义如下 双向链表的插入 p s p prior next s s prior p prior s next p p prior s 1 2 顺序相反的话有可能断链 所以应该注意其顺序 双向链表的删除 p 1 2 p prior next p next P next prior p prior free p 注意 双向链表的插入和删除不必要用额外的指针指向某结点的前驱结点 2 5其它链表之 静态链表 用数组表示线性表L 2 3 4 6 8 9 这次虽然我们使用的是数组 但是并不是采用顺序存储结构 而是使用的链式存储结构 数组SL MAXSIZE 中存放着链表L 其中链表SL是一个带头结点的单链表 如果实现算法的高级语言没有指针类型 即可用数组表示和实现链表 称为静态链表 此处的指针即为结点的相对地址 即为数组的下标 空指针用 1表示 静态链表 静态链表 静态链表定义如下 defineMAXSIZE1000typedefstruct ElemTypedata intnext 指针域 SLinkedList MAXSIZE 静态链表应用例略 请看教材p 37 例2 5 线性链表应用例 有序线性链表合并 pa pb La Lb Lc La pc Lc 有序线性链表合并 pa datadata pa pb La Lb Lc La if pa datadata pc next pa pc pa pa pa next 有序线性链表合并 pa data pb data pa pb La Lb Lc La pc if pa data pb data pc next pb pc pb pb pb next 有序线性链表合并 pa data pb data pa pb La Lb Lc La pc if pa data pb data pc next pb pc pb pb pb next 有序线性链表合并 pa