第二章线性表2011.ppt

第2章线性表 本章主要介绍下列内容线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构线性表的应用举例 退出 2 1线性表的定义和基本操作2 2线性表的顺序存储结构2 3线性表的链式存储结构2 4线性表的应用举例 2 1线性表的定义和基本操作 2 1 1线性表的定义线性表是由n n 0 个类型相同的数据元素组成的有限序列 通常表示成下列形式 L a1 a2 ai 1 ai ai 1 an 其中 L为线性表名称 习惯用大写书写 ai为组成该线性表的数据元素 习惯用小写书写 线性表中数据元素的个数被称为线性表的长度 当n 0时 线性表为空 又称为空线性表 举例La 34 89 765 12 90 34 22 数据元素类型为int Ls Hello World China Welcome 数据元素类型为string Lb book1 book2 book100 数据元素类型为下列所示的结构类型 structbookinfo intNo 图书编号char name 图书名称char auther 作者名称 2 1 2线性表的基本操作1 初始化线性表LInitList L 2 销毁线性表LDestoryList L 3 清空线性表LClearList L 4 求线性表L的长度ListLength L 5 判断线性表L是否为空IsEmpty L 6 获取线性表L中的某个数据元素内容GetElem L i e 7 检索值为e的数据元素LocateELem L e 8 返回线性表L中e的直接前驱元素PriorElem L e 9 返回线性表L中e的直接后继元素NextElem L e 10 在线性表L中插入一个数据元素ListInsert L i e 删除线性表L中第i个数据元素ListDelete L i e 设n个人围坐在一个圆桌周围 现在从第s个人开始报数 数到第m个人 让他出局 然后从出局的下一个人重新开始报数 数到第m个人 再让他出局 如此反复直到所有的人全部出局为止 下面要解决的Josephus问题是 对于任意给定的n s和m 求出这n个人的出局序列 请以n 9 s 1 m 5为例 人工模拟Josephus的求解过程以求得问题的解 2 2线性表的顺序存储结构 2 2 1线性表的顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素 如下图2 1所示 图2 1线性表顺序存储结构示意图 其中 L为每个数据元素所占据的存储单元数目 相邻两个数据元素的存储位置计算公式LOC ai 1 LOC ai L线性表中任意一个数据元素的存储位置的计算公式为 LOC ai 1 LOC a1 i 1 L顺序存储结构的特点 1 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系 即线性表的逻辑结构与存储结构 物理结构 一致 2 在访问线性表时 可以利用上述给出的数学公式 快速地计算出任何一个数据元素的存储地址 因此 我们可以粗略地认为 访问每个数据元素所花费的时间相等 这种存取元素的方法被称为随机存取法 使用这种存取方法的存储结构被称为随机存储结构 在C语言中 实现线性表的顺序存储结构的类型定义 defineLIST MAX LENGTH100 线性表的最大长度typedefstruct EntryType item 指向存放线性表中数据元素的基地址intlength 线性表的当前长度 SQ LIST 2 2 2典型操作的算法实现1 初始化线性表LintInitList SQ LIST L L item EntryType malloc LIST MAX LENGTH sizeof EntryType 分配空间if L item NULL returnERROR 若分配空间不成功 返回ERRORL length 0 将当前线性表长度置0returnOK 成功返回OK 2 销毁线性表LvoidDestroyList SQ LIST L if L item free L item 释放线性表占据的所有存储空间 3 清空线性表LvoidClearList SQ LIST L L length 0 将线性表的长度置为0 4 求线性表L的长度intGetLength SQ LISTL return L length 5 判断线性表L是否为空intIsEmpty SQ LISTL if L length 0 returnTRUE elsereturnFALSE 6 获取线性表L中的某个数据元素的内容intGetElem SQ LISTL inti EntryType e if iL length returnERROR 判断i值是否合理 若不合理 返回ERROR e L item i 1 数组中第i 1的单元存储着线性表中第i个数据元素的内容returnOK 7 在线性表L中检索值为e的数据元素intLocateELem SQ LISTL EntryTypee for i 0 i L length i if L item i e returni 1 return0 8 在线性表L中第i个数据元素之前插入数据元素eintListInsert SQ LIST L inti EntryTypee if L length LIST MAX LENGTH returnERROR 检查是否有剩余空间if iL length 1 returnERROR 检查i值是否合理for j L length 1 j i 1 i 将线性表第i个元素之后的所有元素向后移动L item j 1 L item j L item i 1 e 将新元素的内容放入线性表的第i个位置 L length returnOK 9 将线性表L中第i个数据元素删除intListDelete SQ LIST L inti EntryType e if IsEmpty L returnERROR 检测线性表是否为空if iL length returnERROR 检查i值是否合理 e L item i 1 将欲删除的数据元素内容保留在e所指示的存储单元中for j i jlength 1 j 将线性表第i 1个元素之后的所有元素向前移动L item j 1 L item j L length returnOK 插入算法的分析假设线性表中含有n个数据元素 在进行插入操作时 若假定在n 1个位置上插入元素的可能性均等 则平均移动元素的个数为 删除算法的分析在进行删除操作时 若假定删除每个元素的可能性均等 则平均移动元素的个数为 分析结论顺序存储结构表示的线性表 在做插入或删除操作时 平均需要移动大约一半的数据元素 当线性表的数据元素量较大 并且经常要对其做插入或删除操作时 这一点需要值得考虑 2 3线性表的链式存储结构 线性表顺序存储结构的特点它是一种简单 方便的存储方式 它要求线性表的数据元素依次存放在连续的存储单元中 从而利用数据元素的存储顺序表示相应的逻辑顺序 这种存储方式属于静态存储形式 暴露的问题l在做插入或删除元素的操作时 会产生大量的数据元素移动 l对于长度变化较大的线性表 要一次性地分配足够的存储空间 但这些空间常常又得不到充分的利用 l线性表的容量难以扩充 线性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元 可以连续 也可以不连续 存储线性表中的数据元素 为了反映数据元素之间的逻辑关系 对于每个数据元素不仅要表示它的具体内容 还要附加一个表示它的直接后继元素存储位置的信息 假设有一个线性表 a b c d 可用下图2 2所示的形式存储 图2 2线性表链式存储结构示意图 术语表示每个数据元素的两部分信息组合在一起被称为结点 其中表示数据元素内容的部分被称为数据域 data 表示直接后继元素存储地址的部分被称为指针或指针域 next 单链表简化的图2 3描述形式 图2 3单联表结构示意图 其中 head是头指针 它指向单链表中的第一个结点 这是单链表操作的入口点 由于最后一个结点没有直接后继结点 所以 它的指针域放入一个特殊的值NULL NULL值在图示中常用 符号表示 带头结点的单链表为了简化对链表的操作 人们经常在链表的第一个结点之前附加一个结点 并称为头结点 这样可以免去对链表第一个结点的特殊处理 如下图2 4所示 图2 4带头结点的单链表结构示意图 链式存储结构的特点 1 线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致 2 在对线性表操作时 只能通过头指针进入链表 并通过每个结点的指针域向后扫描其余结点 这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等 具有这种特点的存取方式被称为顺序存取方式 在C语言中 实现线性表的链式存储结构的类型定义typedefstrcutnode 结点类型EntryTypeitem structnode next NODE typedefstruct 链表类型NODE head LINK LIST 2 3 2典型操作的算法实现1 初始化链表LintInitList LINK LIST L L head NODE malloc sizeof NODE 为头结点分配存储单元if L head L head next NULL returnOK elsereturnERROR 2 销毁链表LvoidDestoryList LINK LIST L NODE p while L head 依次删除链表中的所有结点p L head L head L head next free p 3 清空链表LvoidClearList LINK LIST L NODE p while L head next p L head next p指向链表中头结点后面的第一个结点L head next p next 删除p结点free p 释放p结点占据的存储空间 4 求链表L的长度intListLength LINK LISTL NODE p intlen for p L head len 0 p next NULL p p next len return len 5 判链表L空否 intIsEmpty LINK LISTL if L head next NULL returnTRUE elsereturnFALSE 6 通过e返回链表L中第i个数据元素的内容voidGetElem LINK LISTL inti EntryType e NODE p intj if iListLength L exitERROR 检测i值的合理性for p L head j 0 j i p p next j 找到第i个结点 e p item 将第i个结点的内容赋给e指针所指向的存储单元中 7 在链表L中检索值为e的数据元素NODE LocateELem LINK LISTL EntryTypee NODE p for p L head next p 8 返回链表L中结点e的直接前驱结点NODE PriorElem LINK LISTL NODE e NODE p if L head next e returnNULL 检测第一个结点for p L head p next 9 返回链表L中结点e的直接后继结点NODE NextElem LINK LISTL NODE e NODE p for p L head next p 10 在链表L中第i个数据元素之前插入数据元素eintListInsert LINK LIST L inti EntryTypee NODE p s intj if iListLength L 1 returnERROR s NODE malloc sizeof NODE if s NULL returnERROR s item e for p L head j 0 p 11 将链表L中第i个数据元素删除 并将其内容保存在e中 intListDelete LINK LIST L inti EntryType e NODE p s intj if iListLength L returnERROR 检查i值的合理性for p L head j 0 jnext j 寻找第i 1个结点s p next 用s指向将要删除的结点 e s item p next s next 删除s指针所指向的结点free s returnOK 2 3 3循环链表若将链表中最后一个结点的next域指向实现循环链表的类型定义与单链表完全相同 它的所有操作也都与单链表类似 只是判断链表结束的条件有所不同 下面我们就列举两个循环链表操作的算法示例 图2 7带头结点的循环链表示意图 1 初始化链表CLintInitList LINK LIST CL CL head NODE malloc sizeof NODE if CL head CL head next CL head returnOK 让next域指向它自身elsereturnERROR 2 在循环链表CL中检索值为e的数据元素NODE LocateELem LINK LISTCL EntryTypee NODE p for p CL head next p CL head 2 3 4双向循环链表在循环链表中 访问结点的特点访问后继结点 只需要向后走一步 而访问前驱结点 就需要转一圈 结论 循环链表并不适用于经常访问前驱结点的情况 解决方法 在需要频繁地同时访问前驱和后继结点的时候 使用双向链表 所谓双向链表 双向链表就是每个结点有两个指针域 一个指向后继结点 另一个指向前驱结点 图2 8 a b 用C语言实现双向循环链表的类型定义 typedefstrcutdu node 双向链表的结点类型EntryTypeitem structdu node prior next DU NODE typedefstruct 双向链表类型DU NODE head DU LINK LIST 1 初始化双向循环链表DLintInitDuList DU LINK LIST DL DL head DU NODE malloc sizeof DU NODE 为头结点分配存储单元if DL head NULL returnERROR DL head next DL head 让头结点的next域指向自身DL head prior DL head 让头结点的prior域指向自身returnOK 2 在双向循环链表DL中 第i个数据元素之前插入数据元素e在一个结点之前插入一个新结点的过程 在双向循环链表中的p结点之前插入s结点应使用下列语句序列 s next p s prior p prior p prior next s p prior s 图2 9 完整的算法 intDuListInsert DU LINK LIST L inti EntryTypee DU NODE p s intj if iListLength DL 1 returnERROR 检测i值的合理性s DU NODE malloc sizeof DU NODE 为新结点分配存储单元if s NULL returnERROR s item e for p L head j 0 p 3 创建双向循环链表DL voidCreate Du Link List DU LINK LIST DL if InitDulist DL ERROR exitERROR scanf d 2 4线性表的应用举例 约瑟夫 Joseph 问题 编号为1 2 n的n个人按顺时针方向围坐在一张圆桌旁 每个人手中持有一个密码 正整数 首先输入一个正整数作为报数上限值m 然后 从第一个人开始按顺时针方向自1开始顺序报数 报到m的人离开桌旁 并将他手中的密码作为新的m值 从顺时针方向的下一个就坐在桌旁的人人开始重新从1报数 如此下去 直至所有人全部离开桌旁为止 假设有7个人 编号从1到7 他们手中的密码分别是3 1 7 2 4 8 4 最初的m 2 通过报数 这7个人离开桌旁的顺序应该是 2 3 5 4 7 6 1 数据结构的分析这个问题的主角是n个人 每个人需要描述的信息有 编号 密码和是否在桌旁的状态 假设有7个人 他们的信息可以表示成下面的形式 顺序存储结构算法描述让n个人围坐在一张圆桌旁 for i 1 i n i 从1开始报数 报到m停止 报到m的人离开桌子 最终的算法实现 defineLIST MAX LENGTH7 definenLIST MAX LENGTHtypedefintEntryType 将EntryType定义为int类型voidJoseph intcode intn 通过一维数组code带入n个人手中的密码 n是开始就坐在桌旁的人数SQ LISTpeople inttemp m m是报数的上限值scanf d 记录当前所报的数目 for i 1 i0 count while count m printf d position 输出当前离开桌旁人的编号GetElem people position 将密码变为负值 链式存储结构使用一个不带头结点的循环单链表结构 结点结构为 图2 10 用C语言定义typedefstruct 循环链表中每个结点的数据域部分的类型intNo 编号intcode 密码 INFO typedefINFOEntryType 算法voidJoseph intcode intn LINK LISTpeople NODE position pre position指向当前报数的结点if InitList position people head 让position指向最后一个结点 以便报数从第一个开始while position next people head position NextElem people position scanf d printf d position item No 离开桌子处理m position item code pre PriorElem people position pre next position next free position position pre printf d position item No 处理最后一个人free position 算法复杂度分析 顺序结构 步骤 1 建立顺序表2 出列时间复杂度分析 出列元素的删除 移动实现 为基本运算 每次最多i 1个元素移动 需要n 1次 n 1 n 2 1 n n 1 2 O n2 算法复杂度分析 链表结构 步骤 1 建立循环链表 2 找循环单链表中的第s个结