数据结构线性表ppt课件.ppt

数据结构 第2章线性表 线性结构是最常用 最简单的一种数据结构 而线性表是一种典型的线性结构 其基本特点是线性表中的数据元素是有序且是有限的 线性结构基本特征 存在一个唯一的被称为 第一个 的数据元素 存在一个唯一的被称为 最后一个 的数据元素 除第一个元素外 每个元素均有唯一一个直接前驱 除最后一个元素外 每个元素均有唯一一个直接后继 线性结构 主要内容 2 1线性表抽象数据类型2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 4线性表的应用 多项式的表示及运算 2 1线性表抽象数据类型 线性表的定义 线性表是指n n 0 个类型相同的数据元素a0 a1 an 1组成的有限序列 其一般描述为 LinearList a0 a1 an 1 其中LinearList称为线性表的名称每个ai n 1 i 0 称为线性表的数据元素 可以是整数 浮点数 字符或类表中相邻元素之间存在着顺序关系 将ai 1称为ai的前驱 Predecessor ai 1称为ai的后继 Successor a0没有前驱元素 an 1没有后继元素具体n的值称为线性表中包含有数据元素的个数 也称为线性表的长度 Length 当n的值等于0时 表示该线性表是空表 2 1线性表抽象数据类型 线性表的定义 线性表的定义中每个数据元素ai的含义在不同情况下各不相同 它们可能是一个字母 一个数字 也可以是一条记录等 一般情况下 在线性表中每个ai描述的是一组相同属性的数据 例如 英文字母表 A B C Z 是一个长度为26的线性表 其中的每一个字母就是一个数据元素某公司2015年每月产值表 400 420 500 600 650 单位 万元 是一个长度为12的线性表 其中的每一个数值就是一个数据元素在一些复杂的线性表中 每一个数据元素又可以由若干个数据项组成 在这种情况下 通常将数据元素称为记录 record 比如学生信息记录 线性表的离散 数学 定义如下 B 其中A包含n个结点的集合 a0 a1 an 1 R是关系的集合 ai 1 ai i 1 2 n 1 可见R只有一种类型的关系 即线性关系 2 1线性表抽象数据类型 线性表的定义 2 1线性表抽象数据类型 线性表的特征 从线性表的定义可以看出线性表的特征 有且仅有一个开始结点 表头结点 a0 它没有直接前驱 只有一个直接后继 有且仅有一个终端结点 表尾结点 an 1 它没有直接后继 只有一个直接前驱 其它结点都有一个直接前驱和直接后继 元素之间为一对一的线性关系 线性表的抽象数据类型定义如下 ADTLinearList 数据对象 D ai ai 元素集合 i 0 1 2 n 1n 1 数据关系 R ai 1 ai 元素集合 i 1 2 n 1 基本操作 插入 删除 查找等 ADTlist 2 1线性表抽象数据类型 线性表的抽象数据类型 线性表的基本操作求长度 求线性表的数据元素个数 访问 对线性表中指定位置的数据元素进行存取 替换等操作 插入 在线性表指定位置上 插入一个新的数据元素 插入后仍为一个线性表 删除 删除线性表指定位置的数据元素 同时保证更改后的线性表仍然具有线性表的连续性 复制 重新复制一个线性表 合并 将两个或两个以上的线性表合并起来 形成一个新的线性表 查找 在线性表中查找满足某种条件的数据元素 排序 对线性表中的数据元素按关键字值 以递增或递减的次序进行排列 遍历 按次序访问线性表中的所有数据元素 并且每个数据元素恰好访问一次 2 1线性表抽象数据类型 线性表的抽象数据类型 2 1线性表抽象数据类型 线性表的抽象数据类型 声明线性表抽象数据类型ADTList 线性表抽象数据类型 数据元素的数据类型为T booleanisEmpty 判断线性表是否为空intsize 返回线性表长度Tget inti 返回第i个元素voidset inti Tx 设置第i个元素为xStringtoString 所有元素的描述字符串intinsert inti Tx 插入x作为第i个元素 2 1线性表抽象数据类型 线性表的抽象数据类型 intinsert Tx 在线性表最后插入x元素Tremove inti 删除第i个元素voidclear 删除所有元素intsearch Tkey 查找与key相等元素booleancontains Tkey 判断是否包含key元素intinsertDifferent Tx 插入不重复元素Tremove Tkey 删除与key相等元素booleanequals Objectobj 比较是否相等voidaddAll Listlist 添加list所有元素 2 1线性表抽象数据类型 线性表的分类 线性表有两种存储方式 对应地把线性表分成了两类 顺序存储结构的顺序表 或称向量存储 一维数组存储 链式存储结构的链表线性表的实现 publicclassSeqList 顺序表类publicclassSinglyLinkedList 单链表类 线性表的存储结构 2 1线性表抽象数据类型 线性表的分类 2 2线性表的顺序存储和实现 线性表的顺序存储结构 数组 是实现顺序存储结构的基础 数组 Array 存储具有相同数据类型的元素集合 一维数组占用一块内存空间 每个存储单元的地址是连续的 计算第i个元素地址所需时间复杂度是一个常量 与元素序号i无关 存取任何一个元素的时间复杂度是O 1 的数据结构称为随机存取结构 因此 数组是随机存取结构 2 2线性表的顺序存储和实现 线性表的顺序存储结构 数组的特点 通过下标识别元素 下标是其存储单元序号 表示元素在数组中的位置N维数组有n个下标数组地址和容量不能更改 2 2线性表的顺序存储和实现 顺序表 顺序表定义 顺序存储方法 即用一组连续的内存单元依次存放线性表中的数据元素 元素在内存的物理存储次序与它们在线性表中的逻辑次序相同 在内存中开辟一片连续存储空间 但该连续存储空间的大小要大于或等于顺序表的长度 然后让线性表中第一个元素存放在连续存储空间第一个位置 第二个元素紧跟着第一个之后 其余依此类推顺序表定义 用顺序存储方法存储的线性表简称为顺序表 SequentialList 2 2线性表的顺序存储和实现 顺序表 顺序表定义 在程序设计语言中 通常利用一维数组来表示顺序表的数据存储区域 这是因为数组具有如下特点 数据中的元素间的地址是连续的数组中所有元素的数据类型是相同的这与线性表的顺序存储结构 顺序表 是类似的考虑 数组存储有什么缺点 2 2线性表的顺序存储和实现 顺序表 顺序表定义 采用一维数组存储数据元素 数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序 顺序表是随机存取结构 2 2线性表的顺序存储和实现 顺序表 顺序表定义 若定义数组A n a0 a1 a2 an 1 假设每一个数组元素占用d个字节 则数组元素A 0 A 1 A 2 A n 1 的地址分别为Loc A 0 Loc A 0 d Loc A 0 2d Loc A 0 n 1 d 其结构如图所示 2 2线性表的顺序存储和实现 顺序表 顺序表定义 由上可知 数据的存储逻辑位置由数组的下标决定 所以相邻的元素之间地址的计算公式为 假设每个数据元素占有d个存储单元 LOC ai LOC ai 1 d对线性表的所有数据元素 假设已知第一个数据元素a0的地址为LOC a0 每个结点占有d个存储单元 则第i个数据元素ai的地址为 LOC ai LOC a0 i d线性表的第一个数据元素的位置通常称做起始位置或基地址 在使用一维数组时 数组的下标起始位置根据给定的问题确定 或者根据实际的高级语言的规定确定 2 2线性表的顺序存储和实现 顺序表 顺序表的实现 顺序表的实现定义 顺序表可以直接使用一维数组描述为 typearrayname type的类型根据实际需要确定 该代码只是对应用数组的声明 还没有对该数组分配空间 因此不能访问数组 只有对数组进行初始化并申请内存资源后 才能够对数组中元素进行使用和访问arrayname newtype arraysize 其作用是给名称为arrayname的数组分配arraysize个类型为type大小的空间其中arraysize表示数组的长度 它可以是整型的常量和变量 如果arraysize是常量 则分配固定大小的空间 如果是变量 则表示根据参数动态分配数组的空间 2 2线性表的顺序存储和实现 顺序表 顺序表的实现 书上P18定义的顺序表 顺序表类 实现ADTList声明的方法 T表示数据元素 的数据类型publicclassSeqListextendsObject 顺序表类 publicclassSeqListextendsMyAbstractList 继承抽象列表类 protectedObject element 对象数组 保护成员protectedintn 顺序表元素个数 长度 2 2线性表的顺序存储和实现 顺序表 顺序表的实现 P18书上定义的顺序表注意 n类声明为实现线性表接口ADTList的泛型类 T表示线性表元素的数据类型 当声明SeqList类的一个对象并创建实例时 指定泛型参数T为一个确定的类 如SeqListlist newSeqList 泛型T的实际参数必须是类 不能是基本数据类型成员变量是保护类型数据元素不能是空对象 null 注意回忆理解Java类是引用数据类型 与基本数据类型相区别 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 初始化操作 由构造函数实现 创建顺序表对象为其分配内存空间 另外 还需要设定当前顺序表的长度算法如下 注意书上P20下对Java语言构造函数的解释 1 构造 存取publicSeqList intlength 构造容量为length的空表 this element newObject length 申请数组的存储空间 元素为null 若length 0 Java抛出异常java lang NegativeArraySizeExceptionthis n 0 publicSeqList 创建默认容量的空表 构造方法重载 this 64 调用本类已声明的指定参数列表的构造方法 初始化操作 由构造函数实现 publicSeqList T values 构造顺序表 由values数组提供元素 忽略其中空对象 this values length 创建容量为values length的空表 若values null 用空对象调用方法 Java抛出空对象异常NullPointerExceptionfor inti 0 i values length i 复制数组元素 O n this element i values i 对象引用赋值this n element length 也可this insert values i 尾插入 this n 暂且不用 因为还没有讲到 也可for Tx values 数组逐元循环 this insert x 尾插入 this n 1 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 Stringvalues A B C D E SeqListlista newSeqList values lista引用顺序表实例 元素是String对象 泛型类与创建实例 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 释放操作 由析构函数实现 Java类不需要声明析构方法 判断顺序表的空与满 顺序表为空 n 0 顺序表为满 n element length算法如下 publicbooleanisEmpty 判断顺序表是否空 若空返回true O 1 returnthis n 0 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 返回顺序表的长度 n是长度算法如下 publicintsize 返回顺序表元素个数 O 1 returnthis n 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 获得 get 顺序表的第i个数据元素值 需要注意i的有效性 然后根据数组的下标从0开始 来考虑到底返回哪一个元素算法如下 存取操作publicTget inti 返回第i个元素 0 i 0 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 设置 set 顺序表的第i个数据元素值为x 需要注意x的有效性 考虑如下 1 如果x已经是被赋值的元素 如何处理2 如果x还没有被赋值 如何处理 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 设置 set 顺序表的第i个数据元素值 算法如下 设置第i个元素为x 0 i 0 抛出序号越界异常 toString 采用字符串形式描述对象的属性值 遍历 返回顺序表所有元素的描述字符串 形式为 覆盖Object类的 toString 方法1 注意P21下的解释 运行时多态 publicStringtoString Stringstr this getClass getName 返回类名 Stringstr if this n 0 str this element 0 toString 执行T类的toString 方法 运行时多态for inti 1 i this n i str this element i toString 执行T类的toString 方法 运行时多态returnstr 空表返回 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 toString 采用字符串形式描述对象的属性值 遍历 返回顺序表所有元素的描述字符串 形式为 覆盖Object类的 toString 方法2 可行 效率同上publicStringtoString Stringstr if this n 0 for inti 0 i this n 1 i str this get i toString str this get this n 1 toString 单独追加最后一个元素 不加逗号 returnstr 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 isEmpty size get i set i x 方法 时间复杂度为O 1 为什么 toString 方法需要遍历顺序表 时间复杂度为O n 为什么 操作的效率分析 插入操作 线性表的插入是指在表的第i个位置上插入一个值为x的新元素 插入后使原表长为n的表 a0 a1 ai 1 ai ai 1 an 1 成为表长为n 1表 a0 a1 ai 1 x ai ai 1 an 1 i的取值范围为0 i n 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 插入操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 插入操作算法设计 参数 插入位置i插入元素x操作步骤 书上例子中先对i值进行修正 也可以直接报错 将ai an 1顺序向下移动 为新元素让出位置将x置入空出的第i个位置修改表长 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 插入操作算法设计 注意 当插入一个元素时 如果数组element已满 为了能使插入操作正常进行 insert 方法创建一个容量为原数组两倍的新数组 并将原数组中的元素复制到新数组中若使用new申请存储空间失败 java虚拟机将产生内存溢出 并终止程序边界的取值方法实现 intinsert inti Tx 插入x作为第i个元素intinsert Tx 尾插入x元素 重载 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 插入操作若数组满 则扩充顺序表的数组容量 插入操作数组扩容 理解对象引用赋值 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 插入操作 插入x作为第i个元素 x null 返回x序号 若x null 抛出空对象异常 O n 对序号i采取容错措施 若in 插入x在最后publicintinsert inti Tx if x null thrownewNullPointerException x null 抛出空对象异常if ithis n i this n 插入在最后Object source this element 数组变量引用赋值 source也引用element数组if this n element length 若数组满 则扩充顺序表的数组容量 this element newObject source length 2 重新申请一个容量更大的数组for intj 0 j i j 从i开始至表尾的元素向后移动 次序从后向前this element j 1 source j this element i x this n returni 返回x序号 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 插入操作publicintinsert Tx 顺序表尾插入x元素 返回x序号 成员方法重载 returnthis insert this n x 插入操作中 this n加1 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 插入操作 当在顺序存储结构的线性表中某个位置上插入一个数据元素时 其时间消耗主要在移动元素上 而移动元素的个数取决于插入或者删除元素的位置考虑 时间复杂度 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 删除操作 线性表的删除运算是指将表中第i个元素从线性表中去掉 删除后使原表长为n的线性表 a0 a1 ai 1 ai ai 1 an 1 成为表长为n 1的线性表 a0 a1 ai 1 ai 1 an 1 i的取值范围为 0 i n 1 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 删除操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 顺序表上完成这一运算的步骤如下 找到要删除的位置i依次将ai 1 an 1顺序向上移动修改表长方法实现 Tremove inti 返回删除第i 0 i n 个元素voidclear 删除线性表所有元素 删除操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 本算法注意以下问题 删除第i个元素 i的取值为0 i element length 1否则第i个元素不存在 因此 要检查删除位置的有效性 当表空 element length 0 时不能做删除 删除ai之后 该数据已不存在 如果需要 先取出ai 再做删除 删除操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 顺序表的删除操作publicTremove inti 删除第i个元素 0 i0 抛出序号越界异常 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 publicvoidclear 删除线性表所有元素 this n 0 设置长度为0 未释放数组空间 删除操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 当在顺序存储结构的线性表中某个位置上删除一个数据元素时 其时间消耗主要在移动元素上 而移动元素的个数取决于插入或者删除元素的位置 考虑 时间复杂度 删除元素平均移动次数 n 1 2时间复杂度为O n 删除操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 例2 1 求解约瑟夫环问题 约瑟夫环 Josephus 问题 1 古代某法官要判决N个犯人的死刑 他有一条荒唐的法律 将犯人站成一个圆圈 从第S个人开始数起 每数到第D个犯人 就拉出来处决 然后再数D个 数到的在处决 直到剩下的最后一个可赦免 2 设编号为1 2 n的n个人围坐一圈 约定编号为k 1 k n 的人从1开始报数 数到m的那个人出列 他的下一位又从1开始报数 数到m的那个人出列 依次类推 知道所有人出列为止 由此产生一个出队编号的序列 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 使用顺序表求解Josephus环number 5start 0distance 2时的执行示意图如何设计算法 例2 1 求解约瑟夫环问题 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 注意 泛型的实际参数只能是类 不能是基本类型char int等 importdataStructure 声明导入指定包中的类或接口publicclassJosephus 例2 1 求解Josephus环问题 创建Josephus环并求解 参数指定环长度 起始位置 计数publicJosephus intnumber intstart intdistance System out print Josephus number start distance SeqListlist newSeqList number 创建顺序表实例 元素类型是字符串 构造方法参数指定顺序表容量 省略 时取默认值for inti 0 i number i list insert char A i 顺序表尾插入 O 1 char类型 转化为string类型System out println list toString 输出顺序表的描述字符串 O n 例2 1 求解约瑟夫环问题 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 inti start 计数起始位置while list size 1 多于一个元素时循环 计数O 1 i i distance 1 list size 按循环方式对顺序表进行遍历System out print 删除 list remove i toString 删除i位置对象 O n System out println list toString System out println 被赦免者是 list get 0 toString get 0 获得元素 O 1 例2 1 求解约瑟夫环问题 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 publicstaticvoidmain Stringargs 例2 1 求解Josephus环问题 newJosephus 5 0 2 例2 1 求解约瑟夫环问题 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 程序运行结果如下 Josephus 5 0 2 A B C D E 删除B A C D E 删除D A C E 删除A C E 删除E C 被赦免者是CJosephus 5 0 2 SeqList A B C D E 删除B SeqList A C D E 删除D SeqList A C E 删除A SeqList C E 删除E SeqList C 被赦免者是C 例2 1 求解约瑟夫环问题 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 查找操作 顺序查找算法 顺序查找首次出现的与key相等元素 返回元素序号i 查找不成功返回 1 若key null Java抛出空对象异常NullPointerExceptionpublicintsearch Tkey for inti 0 i this n i if key equals this element i 执行T类的equals Object 方法 运行时多态returni return 1 空表或未找到时 booleancontains Tkey 包含 returnthis search key 1 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 插入不重复元素 查找不成功时 尾插入intinsertDifferent Tx returnthis search x 1 this insert x 1 Tremove Tkey 删除首个与key相等元素 returnthis remove this search key 先查找 再调用remove i 若查找不成功 返回 1 则不删除 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 查找操作 Object类publicbooleanequals Objectobj return this obj 若两个对象引用同一个实例 返回true Object类中equals Object 函数比较两个是对象是否引用同一个实例 其他类继承Object类时会覆盖equals Object 方法 例如 publicfinalclassIntegerextendsNumberimplementsComparable privatefinalintvalue publicbooleanequals Objectobj 覆盖Object类的方法 if objinstanceofInteger returnvalue Integer obj intValue 比较两个Integer对象的值returnfalse 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 查找操作 考虑线性表的其他基本操作 置表为空遍历顺序表并输出求前驱求后继复制合并排序 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 顺序表的静态特性很好 动态特性很差 具体说明如下 顺序表元素的物理存储顺序直接反映线性表元素的逻辑顺序 顺序表是一种随机存取结构 get set 方法时间复杂度是O 1 插入和删除操作效率很低 O n 2 2线性表的顺序存储和实现 小结 顺序表 顺序表的基本操作 顺序表的浅拷贝与深拷贝 自学 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 比较相等操作 习题2 5SeqList类以下声明有什么错误 为什么 publicbooleanequals Objectobj 比较两个顺序表是否相等 覆盖 returnthis n list n 注意 1 使用 比较两个对象时 比较的是两个对象的内存地址 所以不相等即使它们内容相等 但是不同对象的内存地址也是不相同的 2 两个线性表相等是指 它们各对应元素相等并且长度相同 使用equal 函数 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 习题解答2 5 比较相等操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 比较相等操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 SeqList类声明覆盖publicbooleanequals Objectobj if this obj 引用同一个实例returntrue if objinstanceofSeqList 若obj引用顺序表实例 SeqList是所有SeqList的父类 SeqListlist SeqList obj if this n list n 比较长度 for inti 0 i this n i 比较所有元素if this get i equals list get i 运行时多态returnfalse returntrue returnfalse 比较相等操作 2 2线性表的顺序存储和实现 顺序表 顺序表的基本操作 线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出 因此顺序存储结构的线性表是可以随机存取其中的任意元素 也就是说定位操作可以直接实现 高级程序设计语言提供的数组数据类型可以直接定义顺序存储结构的线性表 使其程序设计十分方便 2 2线性表的顺序存储和实现 顺序表 顺序表的存储结构优点 但是 顺序存储结构也有一些不便之处 表现在 数据元素最大个数需预先确定 使得高级程序设计语言编译系统需预先分配相应的存储空间 插入与删除运算的效率很低 为了保持线性表中的数据元素的顺序 在插入操作和删除操作时需移动大量数据 这对于插入和删除操作频繁的线性表 以及每个数据元素所占字节较大的问题将导致系统的运行速度难以提高 顺序存储结构的线性表的存储空间不便于扩充 当一个线性表分配顺序存储空间后 如果线性表的存储空间已满 但还需要插入新的元素 则会发生 上溢 错误 在这种情况下 如果在原线性表的存储空间后找不到与之连续的可用空间 则会导致运算的失败或中断 2 2线性表的顺序存储和实现 顺序表 顺序表的存储结构缺点 从线性表的顺序存储结构的讨论中可知 对于大的线性表 特别是元素变动频繁的大线性表不宜采用顺序存储结构 而应采用链式存储结构 线性表的链式存储结构就是用若干地址分散的存储单元 可以是不连续的 存储线性表的数据元素 采用链式存储结构表示的线性表称为线性链表在链式存储结构方式下 存储数据元素的结点空间可以不连续 各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致 逻辑上相邻的数据元素在物理位置上不一定相邻 而数据元素之间的逻辑关系由指针域 地址域 来确定 2 3线性表的链式存储和实现 线性表的链式存储结构 对线性表中的每一个结点 都至少需用两部分来存储 一部分用于存放数据元素值 称为数据域 另一部分用于存放直接前驱或直接后继结点的地址 指针 称为地址域 指针域 我们把这种存储单元称为结点 用结点来存储线性表中的每一个数据元素 2 3线性表的链式存储和实现 线性表的链式存储结构 结点 线性表的链式存储结构L a1 a2 an 示意图 单链表 其中 a 为非空表 b 为空表 2 3线性表的链式存储和实现 线性表的链式存储结构 带头结点链表 2 3线性表的链式存储和实现 线性表的链式存储结构 不带头结点 带头指针 链表 下面将介绍几个线性链表 linearlinkedlist 类型的实现 单链表 singlylinkedlist 双链表 doublylinkedlist 循环链表 circularlinkedlist 2 3线性表的链式存储和实现 线性表的链式存储结构 链表分类 每个结点只有一个地址域的线性链表称为单链表任意存储单元 结点 存储单向链表的数据元素时 其形式如下图所示 其中data是数据域 存放数据元素的值 next是地址域 存放相邻的下一个结点的地址单向链表是指结点中的指针域只有一个沿着同一个方向表示的链式存储结构 因为结点是一个独立的对象 所以能够实现独立的结点类 2 3线性表的链式存储和实现 单链表 单链表是由多个元素 结点 组成的前驱结点和后继结点链表的存贮方式是 在内存中利用存贮单元 可以不连续 来存放元素值及相关元素在内存中的地址 各个元素的存放顺序及位置都可以以任意顺序进行 原来相邻的元素存放到计算机内存后不一定相邻 从一个元素找下一个元素必须通过地址 指针 才能实现 故不能像顺序表一样可随机访问 而只能按顺序访问 2 3线性表的链式存储和实现 单链表 a 2 180 a 4 170 a 6 NULL a 1 110 a 5 140 a 3 130 150 地址 data 域 next 域 110 120 130 140 150 160 170 180 head 头指针 head 2 3线性表的链式存储和实现 单链表 考虑 如何实现单链表类 关键在于结点如何实现单链表结点类 成员变量包含哪些 构造函数如何定义 有哪些常用的操作 2 3线性表的链式存储和实现 单链表 单链表的类实现 成员变量 结点元素是一个自引用的数据 当前结点对象中具有下一个结点元素的对象构造方法 构造一个结点元素时 其值被存储到对象中 并且结点元素包括一个指向链表中下一个元素的引用其他方法 访问一个类对象的数据时 使用所给方法直接访问 读或写 数据域及引用域 2 3线性表的链式存储和实现 单链表 单链表的结点类实现 1 单链表结点类publicclassNode 单链表结点类 T指定结点的元素类型 publicTdata 数据域 存储数据元素publicNodenext 地址域 引用后继结点publicNode Tdata Nodenext 构造结点 data指定数据元素 next指定后继结点 this data data T对象引用赋值this next next Node对象引用赋值 publicNode this null null 2 3线性表的链式存储和实现 单链表 单链表的结点类实现 publicStringtoString 返回结点数据域的描述字符串 returnthis data toString 教材没有写 没有直接调用publicbooleanequals Objectobj 比较两个结点值是否相等 覆盖Object类的equals obj 方法 returnobj this objinstanceofNode 2 3线性表的链式存储和实现 单链表 单链表的结点类实现 注意 Node有两个成员变量 data表示结点的数据域 保存数据元素本身 数据类型是T next表示结点的地址域 保存后继结点的地址Node类中成员变量next的数据类型是Node类自己 Node类是 自引用的类 自引用的类 Self referentialClass 是指一个类声明包含引用当前类实例的成员变量 2 3线性表的链式存储和实现 单链表 单链表的结点类实现 注意 一个Node类的实例只表示链表中的一个结点 如何将两个结点链接起来 成员变量设计为共有 合适否 其他方法需要否 比如直接访问 读或写 数据域及引用域 单链表的头指针如何设定 2 3线性表的链式存储和实现 单链表 单链表的结点类实现 一个Node类的实例只表示链表中的一个结点 如何将两个结点链接起来 通过next域将两个结点链接起来语句如下 Nodep q p newNode A null q newNode B null p next q 所以若干结点通过next链指定相互之间的顺序关系 形成一条单链表 2 3线性表的链式存储和实现 单链表 单链表的结点类实现 成员变量设计为公有 合适否 便于访问 更改结点间的链接关系 根据封装性 应该设置为private或protected 2 3线性表的链式存储和实现 单链表 单链表的结点类实现 其他方法需要否 比如直接访问 读或写 数据域及引用域 如果将Node类的data和next封装成私有成员 则必须提供一组公有的getData getNext setData setNext 等方法 2 3线性表的链式存储和实现 单链表 单链表的结点类实现 单链表的头指针如何设定 单链表的头指针head也是一个结点引用 声明如下 Nodehead null 当head null时 表示空单链表 2 3线性表的链式存储和实现 单链表 单链表的结点类实现 对于单链表来说 整个链表的存取必须是从头指针开始 头指针指示链表中第0个 起始 结点的存储位置 同时由于最后一个数据元素 没有直接后继 则线性链表中最后一个结点的指针为 空 null 2 3线性表的链式存储和实现 单链表 单链表的实现 开始时单链表为空表建立单链表时依次在链表尾部插入一个新建的结点考虑 如何实现关键的尾部插入 插入的第一个结点是否单独处理 结论 需要使用new创建Node类型的对象 并依次链入链表的尾部 注意参数的值是什么需要对第一个结点单独处理插入结点作为链表结点的初始化来看待 所以利用构造函数实现 建立单链表 2 3线性表的链式存储和实现 单链表 单链表的实现 设rear指向原链表的最后一个结点 q指向新创建的结点 则将q结点链在rear结点之后的语句是 rear next q rear q 需要考虑开始为空的特殊情况 建立单链表 2 3线性表的链式存储和实现 单链表 单链表的实现 其他需要考虑的问题 rear可否作为SingLinkedList类的保护成员存在假设插入的元素为随机数 建立单链表 2 3线性表的链式存储和实现 单链表 单链表的实现 实现过程 产生随机数新建以随机数为元素的结点 并把新结点链入到第一个位置修改rear产生随机数新建以随机数为元素的结点q把q放到结点的尾部修改rear循环4 7步 建立单链表 2 3线性表的链式存储和实现 单链表 单链表的实现 单链表的遍历操作 遍历单链表是指从第0个结点开始 沿着结点的next链 依次访问单链表中的每个结点 并且每个结点只访问一次 2 3线性表的链式存储和实现 单链表 单链表的实现 遍历单链表操作不能改变头指针head 因此需要声明一个变量p指向当前访问结点p从head指向的结点 第0个 引用结点 开始访问 再沿着next链到达后继结点 逐个访问 直到最后一个结点 完成一次遍历 单链表的遍历操作 2 3线性表的链式存储和实现 单链表 单链表的实现 单链表的遍历操作Nodep head while p null p data toString 执行访问p结点的相关操作p p next 单链表的遍历操作 2 3线性表的链式存储和实现 单链表 单链表的实现 如果语句p p next写成p next p p next p 使p next指向p结点自己 改变了结点间的链接关系 遍历算法死循环 单链表的遍历操作 思考 2 3线性表的链式存储和实现 单链表 单链表的实现 在单链表中插入新的结点 根据插入位置的不同 分四种情况 空表插入头插入尾插入中间插入关键 插入结点时 只要改变结点间的链接关系 不需要移动数据元素 插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 假定链表为空 head null 插入一个结点 链表只有一个结点语句如下 head newNode x null 空表插入 2 3线性表的链式存储和实现 单链表 单链表的实现 head 头插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 head q 头插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 may head q 头插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 may head q 头插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 may head q 头插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 过程 构造一个新的Node对象p在新对象中加入需要的值x让其指针域指向列表中的第一个元素head指向新对象p 头插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 若单链表非空 head null 则在head结点之前插入值为x的结点的关键语句如下 Nodep newNode x null p next head head p 考虑 空表插入和头插入有何相似之处 结论 空表插入和头插入的合并结果head newNode x head 头插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 链表不为空的情况 head 尾插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 p head 尾插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 p head 尾插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 p head 尾插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 p yes head q 尾插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 p yes q head 尾插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 考虑 如果链表为空 如何操作 可否增设一个尾结点 rear 尾插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 实现过程 到达链表尾部构造一个新的Node对象p在新对象中加入需要的值让最后一个结点的指针域指向新对象p 尾插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 关键语句如下 Nodep newNode x null front next p 尾插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 若将x插入a和b之间 插入结点的指针变化如图所示 q a b x p 插入结点时的指针修改 中间插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 基于上图 关键语句如下 Nodep newNode x null p next front next front next p 中间插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 考虑 单链表的插入是否需要移到大量元素对于单链表很方便访问结点的后继结点对于单链表访问结点的前驱结点很不方便 如何实现 中间插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 考虑 中间插入和尾插入有何相似之处 结论 中间插入和尾插入的合并实现设front指向单链表中的某个结点 在front结点后插入值为x结点的语句如下 Nodep newNode x null p next front next p的后继是front的后继front next p p作为front的后继即 front next newNode x front next 中间插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 思考 图 c 中 如果 两句次序颠倒 将会怎样 Nodep newNode x null front next p p next front next 会出现错误 丢失后续链表 中间插入结点 2 3线性表的链式存储和实现 单链表 单链表的实现 在单链表中删除已有的结点 根据删除位置的不同 分四种情况 只有一个结点的链表删除头部删除中间删除尾部删除关键 删除单链表中的指定结点 通过改变结点的next域 就可以改变结点间的链接关系 不需要移动元素 Java的资源回收机制将自动释放不再使用的对象 收回其占用的资源 删除结点 2 3线性表的链式存储和实现 单链表 单链表的实现 删除结点 2 3线性表的链式存储和实现 单链表 单链表的实现 删除结点 2 3线性表的链式存储和实现 单链表 单链表的实现 删除单结点链表 只要使链表的引用head为空即可 head null 删除结点 单结点链表 2 3线性表的链式存储和实现 单链表 单链表的实现 head 头删除 2 3线性表的链式存储和实现 单链表 单链表的实现 head 头删除 2 3线性表的链式存储和实现 单链表 单链表的实现 head 头删除 2 3线性表的链式存储和实现 单链表 单链表的实现 操作过程 将第一个元素复制到一个临时变量中将head指向第二个元素返回原有的第一个元素的值 头删除 2 3线性表的链式存储和实现 单链表 单链表的实现 删除单链表head指向的结点 使head引用其后继结点 关键语句如下 head head next 考虑 一个结点的删除和头删除有何相似之处 结论 一个结点的删除和头删除的合并head head next 头删除 2 3线性表的链式存储和实现 单链表 单链表的实现 列表不为空的情况 head 尾删除 2 3线性表的链式存储和实现 单链表 单链表的实现 finger previos head 尾删除 2 3线性表的链式存储和实现 单链表 单链表的实现 finger previos head 尾删除 2 3线性表的链式存储和实现 单链表 单链表的实现 finger previos head 尾删除 2 3线性表的链式存储和实现 单链表 单链表的实现 on finger previos head 尾删除 2 3线性表的链式存储和实现 单链表 单链表的实现 自己考虑如何实现 尾删除 2 3线性表的链式存储和实现 单链表 单链表的实现 表尾操作都是先从