第二章线性表-1.pptVIP

  1. 1、本文档共14页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第二章线性表-1

第二章 线性表 2.1 线性表的抽象数据类型 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 目的:实现线性表抽象数据类型。 要求:掌握两种存储结构实现线性表。 重点:顺序表类,单链表类。 难点:单链表,双链表。 2.1 线性表的抽象数据类型 1、线性表的定义 线性表是由n(n?0)个类型相同的数据元素a0, a1,…,an-1组成的有限序列。 LinearList=(a0, a1,…,an-1) n为线性表的元素个数,称为线性表长度。若n=0,则LinearList为空表。 若n0,则a0没有前驱元素, an-1没有后继元素 ai(0in-1)有且仅有一个直接前驱元素ai-1和一个直接后继元素ai+1 。 2.1 线性表的抽象数据类型 2、线性表的操作 2.2 线性表的顺序表示和实现 1 .线性表的顺序存储结构 定义:用一组连续的内存单元依次存放线性表的数据元素。用这种方法存储的线性表简称顺序表(sequential list)。 元素地址计算方法 c—一个元素占用的存储单元个数 Loc(ai)—线性表第i个元素的地址,该元素所占的第一个存储单元 Loc (a0)—称为线性表的起始位置或基地址 线性表的顺序存储结构示意图 2 .顺序表的插入和删除操作 线性表的插入 分析:线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素,就是要使长度为n的线性表 (a0,…,ai-1,ai,…,an-1) 变为长度为n+1的线性表 (a0,…,ai-1,e,ai,…,an-1) 线性表插入前后的状况 2 .顺序表的插入和删除操作 线性表的删除 分析:线性表的删除操作是指将表的第i个数据元素删除,使长度为n的线性表 (a0,…,ai-1,ai,ai+1,…,an-1) 变为长度为n-1的线性表 (a0,…,ai-1, ai+1,…,an-1) 需将第i+1至第n-1共(n-i-1)个元素前移 3. 顺序表类 4. 顺序表操作的效率分析 如果在各位置插入元素的概率相同,则有 【例2.1】 使用顺序表类求解约瑟夫环问题。//Josephus.java 古代某法官要判决n个犯人的死刑,他有一条荒唐的法律,将犯人站成一个圆圈,从第s个人开始数起,每数到第d个犯人,就拉出来处决,然后再从下一个开始数d个,数到的人再处决,……,直到剩下最后一个犯人予以赦免。 n=5,s=1,d=2执行过程 * * public interface LListE { //线性表接口 boolean isEmpty(); //判断线性表是否为空 int length(); //返回线性表长度 E get(int index); //返回序号为index的对象 E set(int index, E element); //设置序号为index对象为element,返回原对象 boolean add(int index, E element); //插入element对象,插入后对象序号为index boolean add(E element); //在线性表表尾插入element对象 E remove(int index); //移去序号为index的对象,返回被移去对象 void clear(); //清空线性表 } 特点: 实现逻辑上相邻—物理地址相邻 实现随机存取,存取任何一个元素的时间复杂度为O(1 可用一维数组实现 Loc(a0)+i*c ai i Loc(a0)+(i-1)*c ai-1 i-1 Loc(a0)+(n-1)*c an-1 n-1 … … … Loc(a0)+(i+1)*c ai+1 i+1 … … … Loc(a0)+c a1 1 Loc(a0) a0 0 存储地址 数据元素 index 插入25 插入后 数据元素 12 13 28 30 序号 21 24 42 77 0 1 4 5 2 3 6 7 n=8 数据元素 12 13 28 30 21 24 42 77 0 1 4 5 2 3 6 7 8 25 n=9 数据元素 12 13 28 30 21 24 42 77 0 1 4 5 2 3 6 7 8 数据元素 12 13 28 30 21 24 42 77 0 1 4 5 2 3 6 7 8 28 28 28 28 25 28 30 42 77 25 第4至第7个元素后移 第7至第4个元素后移 数据元素 a0 a1 ai ai+1 an-1 0 1 i

文档评论(0)

asd522513656 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档