数据结构java版第三版第2章线性表.ppt

詹华蕊 ,数据结构与算法 DATA STRUCTURE AND ARITHMETIC,2,复习回顾,上节课我们学习了： 数据结构中常用的基本概念和术语 算法描述和分析方法 通过上节课的学习，我们对数据、数据元素、数据结构等基本概念，以及算法的描述和算法的时间复杂度分析已经有了一个初步的掌握。,3,1 数据结构的基本概念,什么是数据、数据元素、数据项和关键字？它们之间是怎样的关系？ 什么是数据结构？数据结构概念包括哪三部分？ 数据的逻辑结构主要有哪三种？各有何特点？三者之间存在怎样的联系？ 数据的存储结构主要有哪些？各有何特点？,4,1 数据结构的基本概念,5,2 算法,什么是算法？怎样描述算法？怎样衡量算法的性 能？,6,第二章 线性表,7,本章的重点内容,线性表的相关概念 线性表的顺序存储结构 线性表的链式存储结构 链表应用 顺序表和链表的比较,8,本章的重点内容,线性表的相关概念 线性表的顺序存储结构 线性表的链式存储结构 链表应用 顺序表和链表的比较,9,1、线性表（Linear list）的定义,线性表是指n (n=0)个相同类型的数据元素a0,a1,.an-1所构成的有限且有序的序列，其一般描述为：LinearList=（ a0,a1,an-1） 其中LinearList称为线性表的名称 每个ai（n-1i0）称为线性表的数据元素 表中相邻元素之间存在着顺序关系：将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继 具体n的值称为线性表中包含有数据元素的个数，也称为线性表的长度 当n的值等于0时，表示该线性表是空表,10,线性表的定义,每个数据元素ai(0in-1)只是一个抽象的符号，其具体含义在不同的情况下可以不同。它们可能是一个字母、一个数字、也可以是一条记录等。 例1、26个英文字母组成的字母表 （A，B，C、Z） 例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188）,11,.,.,.,神经衰弱,17,男,790634,张立立,健康,21,男,790633,刘建平,一般,20,女,790632,陈 红,健康,18,男,790631,王小林,健康情况,年龄,性 别,学 号,姓 名,例3、学生健康情况登记表如下：,线性表的定义,12,线性表的定义,线性表的离散定义如下：B=,其中A包含n个结点的集合(a0,a1,an-1)，R是关系的集合(ai-1,ai)|i=0,1,n-1，可见R只有一个关系，即线性关系。,13,线性表的定义,线性表的抽象数据类型定义如下： ADT list 数据对象:Dai|ai元素集合,i=0,1,n-1 n=0 数据关系:R=(ai-1,ai)|ai-1,ai 元素集合,i=0,2,n-1 基本操作：插入，删除，查找等 ADT list,14,从实例及线性表的定义可以看出线性表的特征： 有且仅有一个开始结点(表头结点)a0，它没有直接前驱，只有一个直接后继; 有且仅有一个终端结点(表尾结点)an-1，它没有直接后继，只有一个直接前驱; 其它结点都有一个直接前驱和直接后继； 元素之间为一对一的线性关系。,线性表的特征,线性表是一种典型的线性结构。,15,线性表的主要操作有如下几种： 1 linklist() 初始化：构造一个空的线性表。 2 insert(index,element) 插入：在给定的线性表中，在第index个元素后插入数据元素element。线性表长度加1。 3 remove(index) 删除：在给定的线性表中，删除第index个元素。线性表的长度减1。 4 index(x) 查找定位：对给定的值x，若线性表中存在一个元素ai与之相等，则返回该元素在线性表中的位置的序号i，否则返回Null（空）。,线性表的主要操作,16,5 size() 求长度：对给定的线性表，返回线性表的数据元素的个数。 6 get(index) 存取：对给定的线性表，返回第index（0indexLength(L)-1）个数据元素，否则返回Null。 7 Traverse(L) 遍历：对给定的线性表L，依次输出L的每一个数据元素。 8 Copy(L,C) 复制：将给定的线性表L复制到线性表C中。 9 Merge(A,B,C) 合并：将给定的线性表A和B合并为线性表C。,线性表的主要操作,17,线性表的分类,数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。 线性表有两种存储方式，对应地把线性表分成了两类： 顺序存储结构的顺序表（或称向量存储、一维数组存储） 链式存储结构的链表,18,本章的重点内容,线性表的相关概念 线性表的顺序存储结构 线性表的链式存储结构 链表应用 顺序表和链表的比较,19,2、顺序表（Sequential List）的定义,顺序存储方法： 即用一组连续的存储单元顺序存储线性表中的元素 在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度，然后让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推 顺序表： 用顺序存储方法存储的线性表简称为顺序表,20,顺序表的定义,在程序设计语言中，通常利用一维数组来表示顺序表的数据存储区域，这是因为数组具有如下特点： 数据中的元素间的地址是连续的 数组中所有元素的数据类型是相同的 这与线性表的顺序存储结构(顺序表)是类似的,21,若定义数组An= a0，a1，a2，an-1，假设每一个数组元素占用d个字节，则数组元素A0，A1，A2，An-1的地址分别为Loc(A0)，Loc(A0)+d，Loc(A0)+2d，Loc(A0)+（n-1）d 。其结构如图所示 ：,22,由上可知，数据的存储逻辑位置由数组的下标决定。所以相邻的元素之间地址的计算公式为（假设每个数据元素占有c个存储单元）： LOC（ai）=LOC（a0）+ i*c 对线性表的所有数据元素，假设已知第一个数据元素a0的地址为d0，每个结点占有c个存储单元， 则第(i+1)个数据元素ai的地址为： 线性表的第一个数据元素的位置通常称做起始位置或基地址。 在使用一维数组时，数组的下标起始位置根据给定的问题确定，或者根据实际的高级语言的规定确定。,顺序表的定义,di=d0+i*c,23,顺序表的实现定义: 顺序表可以直接使用一维数组描述为： type arrayname；/type的类型根据实际需要确定/ 该代码只是对应用数组的声明，还没有对该数组分配空间，因此不能访问数组。只有对数组进行初始化并申请内存资源后，才能够对数组中元素进行使用和访问。 arrayname= new typearraysize； 其作用是给名称为arrayname的数组分配arraysize个类型为type大小的空间； 其中arraysize表示数组的长度，它可以是整型的常量和变量；如果arraysize是常量，则分配固定大小的空间，如果是变量，则表示根据参数动态分配数组的空间。,顺序表的定义实现,24,顺序表的基本运算插入操作,插入操作： 线性表的插入是指在表的ai的位置上插入一个值为 x 的新元素，插入后使原表长为 n的表: (a0，a1，. ，ai-1，ai，ai+1，. ，an-1) 成为表长为 n+1 表: (a0，a1，. ， ai-1， x， ai，ai+1，. ，an) i 的取值范围为0=i=n 。,25,顺序表的基本运算插入操作,算法设计： 参数： 顺序表 narray 插入位置 i、 插入元素item 操作步骤： (1) 将aian 顺序向下移动，为新元素让出位置； (2) 将item 置入空出的第i个位置； (3) 修改表长。,26,顺序表的基本运算插入操作,本算法中注意以下问题： (1)顺序表中数据区域有narray.length个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。 (2) 要检验插入位置的有效性，这里 i 的有效范围是：0=i=narray.length。 (3) 注意数据的移动方向。 (4)插入结束后要修改线性表的长度。,27,算法如下： Public class Arrayinsert public static void main(string args) int narray ; if ( inarray.length | i=i;k-) narrayk+1=narrayk; /* 结点移动 */ narrayi=item; /*新元素插入*/ narray.length=narray.length+1; /*修改表长*/ ,28,顺序表的基本运算插入操作,当在顺序存储结构的线性表中某个位置上插入一个数据元素时,其时间消耗主要在移动元素上,而移动元素的个数取决于插入元素的位置.,29,删除运算 ： 线性表的删除运算是指将表中第 i 个元素从线性表中去掉，删除后使原表长为 n 的线性表： (a0，a1，. ，ai-1，ai，ai+1，.，an-1) 成为表长为 n1 的线性表： (a0，a1，. ，ai-1，ai+1，. ，an-1) i 的取值范围为：0=i=n-1 。,顺序表的基本运算删除操作,30,顺序表的基本运算删除操作,顺序表上完成这一运算 的步骤如下： (1) 将ai+1an 顺序向上移动。 (2) 修改表长,图2. 4 顺序表中的删除,31,顺序表的基本运算删除操作,本算法注意以下问题： （1）删除第i个元素，i的取值为 0=i=narray.length-1否则第i个元素不存在，因此，要检查删除位置的有效性。 （2）当表空(narray.length=0)时不能做删除。 （3）删除 ai 之后，该数据已不存在，如果需要，先取出 ai ，再做删除。,32,顺序表的基本运算删除操作,算法如下： Public class arraydelete public static void main(string args) int narray; if ( inarray.length-1 | i0 ) /*检查删除位置的正确性*/ system.out.println(“i not exist”) else if(narray.length=0) /*表是否为空*/ system.out.println(“overflow”); else for(int k=i;knarray.length-1;k+) narrayk=narrayk+1; /*结点移动*/ narray.length=narray.length-1; /*修改表长*/ ,33,顺序表的基本运算删除操作,当在顺序存储结构的线性表中某个位置上删除一个数据元素时,其时间消耗主要在移动元素上,而移动元素的个数取决于删除元素的位置.,34,顺序表的基本运算,考虑线性表的其他基本操作： 求顺序表的长度 置表为空 检查表是否为空 检查表是否为满 查找某个元素是否在表中 取某个位置上的元素 遍历顺序表并输出 求前驱 求后继,35,完整实现的示例,考虑到线性表的运算有插入、删除等运算，即表长是可变的，因此，数组的容量需设计的足够大，设用：dataMaxSize来表示，其中MaxSize是一个根据实际问题定义的足够大的整数，线性表中的数据从 data0 开始依次顺序存放，但当前线性表中的实际元素个数可能未达到MaxSize多个，因此需用一个变量 last 记录当前线性表中最后一个元素在数组中的位置，即 last 起一个指针的作用，始终指向线性表中最后一个元素，因此，表空时last=-1。这种存储思想的具体描述可以是多样的。,36,完整实现的示例,如可以是： Datatype data ; /*存放顺序表的数组*/ int MaxSize; /* 数组的容量*/ int last; /*最后一个元素在数组中的 位置，Last+1为顺序表的长度*/,37,这样表示的顺序表如图所示。表长为 last+1，数据元素分别存放在data0到datalast中。这样使用简单方便，但有时不便管理。,图 线性表的顺序存储示意图,last,data,完整实现的示例,38,完整实现的示例,从结构性上考虑，通常将 data 和 last 封装成一个结构作为顺序表的类型： Class SeqList Public const int MaxSqSize; public datatype data ; /*存放顺序表的数组*/ Public int last; /*顺序表的初始化*/ Public SeqList ( int i); /*插入操作*/ Public int SeqList_Insert ( int i，datatype x); /*删除操作*/ Public int SeqList_Delete ( int i ); /*查找操作*/ Public int SeqList_Location ( datatype x);,39,完整实现的示例,/*顺序表的遍历*/ Public void List_Traverse( ); /*求顺序表的长度*/ Public int List_Length( ); /*判断顺序表是否为空*/ Public bool List_Empty( ); /*判断顺序表是否满*/ Public bool List_Full( ); /*清空顺序表*/ Public viod List_Clear( )； /*求前驱*/ Public datatype List_PriorElem( datatype x ); /*求后继*/ Public datatype List_NextElem(datatype x ); ,40,完整实现的示例,1、初始化操作 SeqList 顺序表的初始化即构造一个空表，因此，将表中 last 指针置为1，表示表中没有数据元素。通常，我们将初始化工作放在构造方法中，算法如下： Public SeqList ( int i) MaxSqSize=i; datatype data=new datatype MaxSqSize; Last = -1; ,41,完整实现的示例,2、插入操作 SeqListInsert(int i,datatype x) int SeqList_Insert ( int i，datatype x) int j; if ( last=MaxSize1) System.out.println(表满); return(-1); /*表空间已满，不能插入*/ if ( ilast+1 ) /*检查插入位置的正确性*/ System.out.println(位置错); return(0); /* 结点移动 */ For ( j=last; j=i-1; j- - ) dataj+1=dataj; datai=x; /*新元素插入*/ last+; /*last仍指向最后元素*/ return (1); /*插入成功，返回*/ ,42,完整实现的示例,3. 删除运算 SeqListDelete(int i) int SeqList_Delete ( int i ) int j; if(ilast)/*检查空表 及删除位置的合法性*/ System.out.println (“ 不存在第i个元素); return(0); for(j=i; j=last; j+) dataj-1=dataj; /*向上移动*/ last- -; return(1); /*删除成功*/ ,43,完整实现的示例,4. 按值查找 SeqList Location 线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素。在顺序表中完成该运算最简单的方法是：从第一个元素 a1 起依次和x比较，直到找到一个与x相等的数据元素，则返回它在顺序表中的存储下标或序号（二者差一）；或者查遍整个表都没有找到与 x 相等的元素，返回-1。 int SeqList_Location ( datatype x) int i=0; while(ilast) return -1; else return i; /*返回的是存储位置*/ ,44,完整实现的示例,5. 求顺序表的长度 Public int List_Length( ) Return last+1; ,45,完整实现的示例,6. 检查顺序表是否为空 Public bool List_Empty( ) If (List_Length( )=0) return TRUE; else return FALSE; ,46,完整实现的示例,7. 检查顺序表是否为满 Public bool List_Full( ) if(List_Length( )=MaxSize) return TRUE; else return FALSE ; ,47,完整实现的示例,8. 清空顺序表 Public viod List_Clear( ) Last=-1; ,48,完整实现的示例,9. 遍历顺序表 Public void List_Traverse( ) if(List_Length( )=0) System.out.println(“顺序表为空“); else System.out.println (“当前顺序表中的元素为: “); for(int i=0;i=last;i+) System.out.println (datai+“ ”); ,49,完整实现的示例,10. 求前驱 Public datatype List_PriorElem( datatype x ) Int i=0; while(iList_Length() ,50,完整实现的示例,11. 求后继 Public datatype List_NextElem(datatype x ) int i=0; while(i List_Length() ,51,顺序表存储结构的优点,线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。 也就是说定位操作可以直接实现。 高级程序设计语言提供的数组数据类型可以直接定义顺序存储结构的线性表，使其程序设计十分方便。,52,但是，顺序存储结构也有一些不便之处，表现在： 数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间。 插入与删除运算的效率很低。为了保持线性表中的数据元素的顺序，在插入操作和删除操作时需移动大量数据。这对于插入和删除操作频繁的线性表、以及每个数据元素所占字节较大的问题将导致系统的运行速度难以提高。 顺序存储结构的线性表的存储空间不便于扩充。当一个线性表分配顺序存储空间后，如果线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到与之连续的可用空间，则会导致运算的失败或中断。,顺序表存储结构的缺点,53,顺序表作业,有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。 算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。,54,本章的重点内容,线性表的相关概念 线性表的顺序存储结构 线性表的链式存储结构 链表应用 顺序表和链表的比较,55,3、线性表的链式存储结构,从线性表的顺序存储结构的讨论中可知，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，这时，可应采用链式存储结构 。 线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。 在链式存储结构方式下，数据元素的存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，数据元素的逻辑次序和物理次序不一定相同。,56,线性表的链式存储结构,采用链式存储结构时，数据元素之间的逻辑关系由指针域来确定。 对线性表中的每一个数据元素，都至少需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域（链域），我们把这种存储单元称为结点。,57,线性表的链式存储结构,下面将介绍几个链表类型的实现： 单链表（singly linked list） 双链表（doubly linked list） 循环链表（circular linked list）,58,线性表的链式存储结构,下面将介绍几个链表类型的实现： 单链表（singly linked list） 双链表（doubly linked list） 循环链表（circular linked list）,59,单链表,单链表是指，在链表中，每一个结点只有一个指针域（链域），链表是单向的，故将这种链表称为单链表。 任意存储单元（结点）存储单向链表的数据元素时，其特点形式如下图所示：,其中data 是数据域，存放数据元素的值；next是指针域，存放相邻的下一个结点的地址。 因为结点是一个独立的对象，所以能够实现独立的结点类。,60,单链表,单链表是由多个元素（结点）组成的 前趋结点和后继结点 链表的存储方式是： 在内存中利用存储单元(可以不连续)来存放元素值及它在内存的地址，由于各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到计算机内存后不一定相邻，从一个元素找下一个元素必须通过地址(指针)才能实现。故不能像顺序表一样可随机访问，而只能按顺序逐个访问。,61,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,170,180,head,头指针,单链表,62,单链表中的结点类实现,考虑：如何实现单链表类？ 成员变量包含哪些？ 构造函数如何定义？ 有哪些常用的操作？,63,单链表中的结点类实现,成员变量： 结点元素是一个自引用的数据，当前结点对象中具有下一个结点元素的对象 构造函数： 构造一个结点元素时，其值被存储到对象中，并且结点元素包括一个指向链表中下一个元素的引用 其他方法： 访问一个类对象的数据时，使用所给方法直接访问（读或写）数据域及引用域,64,单链表中的结点类实现,单链表中结点类描述如下： class Node private Object data; / 存放结点值 private Node next; / 后继结点的引用 / 无参数时的构造函数 public Node() this(null, null); /带一个参数时的构造函数 public Node(Object data) this(data, null); /带两个参数时的构造函数 public Node(Object data, Node next) this.data = data; this.next = next; ,65,我们可以设计一个头结点，指向单链表的第一个元素，其值域可以为列表中元素的个数 如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点： 第一，由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上操作一致，无须进行特殊处理； 第二，无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。 本课开始时未设计头结点，只使用了头指针（指向第一个元素的指针）,头结点,66,单链表的实现,对于单链表来说，整个链表的存取必须是从头指针开始，头指针指示链表中第一个结点的存储位置。 同时由于最后一个数据元素，没有直接后继，则线性链表中最后一个结点的指针为“空”（null）。,67,单链表类的定义实现,class llist implements Node private Node head; /头结点 private Node tail; /尾结点（考虑是否有必要？） protected Node curr;/当前结点（考虑是否有必要？） llist() setup(); private void setup() tail=head=curr=new Node(null); ,head,tail,curr,头结点,68,单链表表头操作,头部插入一个结点（头插入法） 头部删除一个结点（头删法）,69,单链表表头操作,头部插入一个结点（头插入法） 头部删除一个结点（头删法）,70,头部插入一个结点的过程,71,头部插入一个结点的过程,72,头部插入一个结点的过程,may,73,头部插入一个结点的过程,may,74,头部插入一个结点的过程,may,75,头部插入一个结点的过程,may,76,头部插入一个结点,过程： 构造一个新的Node对象 在新对象中加入需要的值 判断是否空表，空表直接插入 如果不是空表，让其引用域指向列表中的第一个元素 head指向新对象,77,if (head = null) /空表插入 head = new Node(x, null); else /头插入 Node q = new Node(x, null); q.next = head; head = q; 即head = new Node(x, head);,头部插入一个结点,78,单链表表头操作,头部插入一个结点（头插入法） 头部删除一个结点（头删法）,79,自己考虑如何实现？,头部删除一个结点,80,头部删除一个结点,过程： 将第一个元素复制到一个临时变量中 将head指向第二个元素 返回原有的第一个元素的值,81,头部删除一个结点的过程,82,头部删除一个结点的过程,83,头部删除一个结点的过程,84,头部删除一个结点的过程,85,头部删除一个结点，并没有显式的释放该结点，释放工作由垃圾收集器负责回收内存。 但在C，或C中，如此，就会导致内存泄漏（memory leak），必须手动释放内存。 注意：在头部删除和插入的操作是相反对称的，我们编程时，应考虑对称性。,单链表表头操作总结,86,垃圾收集器,Java中有个很重要的技术：garbage collector垃圾收集器 在Java中，内存的申请由程序员手动用new分配，但释放是系统自动进行的，垃圾收集器就负责自动回收内存，程序员无需手动释放内存 问题是，收集器怎么知道哪些内存是不再使用的？,87,垃圾收集器,Java中，动态内存的分配是用new分配的，它返回一个指向新对象的引用 引用就象一个线，如风筝的线，由它就可以控制访问风筝，如果一个风筝没有线，那么风筝就飞走了 如果一个风筝没有线，那么这个风筝将无用，我们就可以回收了，并且不会出错（由垃圾收集器实现）,88,单链表表尾操作,尾部插入结点 尾部删除结点,89,单链表表尾操作,尾部插入结点 尾部删除结点,90,尾部插入一个结点的过程,列表不为空的情况：,91,尾部插入一个结点的过程,finger,92,尾部插入一个结点的过程,finger,93,尾部插入一个结点的过程,finger,94,尾部插入一个结点的过程,finger,yes,95,尾部插入一个结点的过程,finger,yes,96,尾部插入一个结点的过程,考虑：如果列表为空，如何操作？ 可否增设一个尾结点（tail）？（思考。）,finger,yes,97,单链表表尾操作,尾部插入结点 尾部删除结点,98,尾部删除一个结点的过程,列表不为空的情况：,99,尾部删除一个结点的过程,finger,previos,100,尾部删除一个结点的过程,finger,previos,101,尾部删除一个结点的过程,finger,previos,102,尾部删除一个结点的过程,on,finger,previos,103,尾部删除一个结点的过程,finger,previos,104,自己考虑如何实现？,尾部删除一个结点的过程,if (p.next!= null) p= p.next; else p.next=null；,105,单链表表尾操作总结,表尾操作都是先从头找到表尾，然后开始操作，这种技术称为链表遍历技术。 需要注意链表为空这种特殊情况，否则程序出错。 编程需要考虑边界条件，软件需要健壮性和正确性。,106,单链表的一个实例,得到单链表的长度 两种方法： 可以返回count值。 可以顺序扫描每个结点，计算结点个数 public int size( ) return count; ,107,单链表的一个实例,public int size( ) int elementCount = 0; SinglyLinkedListElement finger = head; while(finger != null) elementCount +; finger = finger.next( ); return elementCount; 两种方法的实现对用户隐藏，但两种方法的应用环境不同，效率不同,108,单链表中间操作,中间删除一个结点 删除所有结点 中间插入一个结点,109,head ,(a)寻找第i个结点指向其前驱p,(b)删除并释放第i个结点,head ,S,中间删除一个结点的过程,110,中间删除一个结点的过程,若将x删除，删除结点的指针变化如图所示 在此，需要考虑P和S的各种情况：是否为空等,111,删除所有结点,public void clear() head = null; Head停止指向列表，列表第一个结点变成垃圾被回收。 被垃圾引用的结点也是垃圾，也会被回收，这样整个链表都被回收。,112,中间插入一个结点的过程,113,中间插入一个结点的过程,114,中间插入一个结点的过程,若将x插入a和b 之间，插入结点的指针变化如图所示 在此，需要考虑P和S的各种情况,115,中间插入一个结点,public void add(int i, Object o) Assert.pre(0 = i) ,116,while (i 0) previous = finger; finger = finger.next(); i-; SinglyLinkedListElement current = new SinglyLinkedListElement(o,finger); count+; previous.setNext(current); ,中间插入一个结点,117,118,119,单链表课堂思考题,算法要求： 已知：线性表 A、B，分别由单链表 LA , LB 存储，其中数据元素按值非递减有序排列， 要求：将 A ，B 归并为一个新的线性表C , C 的数据元素仍按值非递减排列 。设线性表 C 由单链表 LC 存储。 假设：A=（3，5，8，11），B=（2，6，8，9，11） 预测：合并后 C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 ）,120,用链表可表示为：,头结点,121,算法分析：,算法主要包括：搜索、比较、插入三个操作： 搜索：需要两个指针搜索两个链表； 比较：比较结点数据域中数据的大小； 插入：将两个结点中数据小的结点插入新链表。,122,La,Pa、Pb用于搜索La和Lb， Pc指向新链表当前结点,123,单链表课堂思考题（两个链表的归并）,算法实现： 自己考虑,124,单链表作业,已知单链表H，写一算法将其倒置。即实现如下图的操作。(a)为倒置前，(b)为倒置后。,(a),(b),125,线性表的链式存储结构,几个链表类型的实现： 单链表（singly linked list） 双链表（doubly linked list） 循环链表（circular linked list）,126,双链表,单链表元素无法知道它的前趋结点，只知其后继结点。 我们需要一种新的数据结构，能解决以上的问题。,127,双链表结点,任意存储单元（结点）存储双向链表的数据元素时，其特点形式如下图所示：,128,双链表,每个元素保存了两个引用，一个指向其前趋，一个指向其后继。 双链表中有两条方向不同的链 。,129,双链表示意图,head,双向链表示意图1,130,双链表元素数据结构,在双链表元素中加入了previous引用（指向此元素前面的那个元素） 考虑：有什么不利之处？ 在一个双链表中，两个相邻元素的相互性被记录在两个引用中，因此，当修改其中一个引用时，必须修改另外一个引用。 当构造一个新的双链表的元素时，需要同时设置两个引用，存储空间开销大。,131,双链表节点类,成员变量：包含一个值域，两个引用： public class DoublyLinkedListElement protected Object data; protected DoublyLinkedListElement nextElement; protected DoublyLinkedListElement previousElement;,132,双链表节点类,构造函数 public DoublyLinkedListElement(Object v, DoublyLinkedListElement next, DoublyLinkedListElement previous) data = v; nextElement = next; if (nextElement != null) nextElement.previousElement = this; previousElement = previous; if (previousElement != null) previousElement.nextElement = this; ,133,双链表节点类,其他函数 public DoublyLinkedListElement next() return nextElement; public DoublyLinkedListElement previous() return previousElement; public Object value() return data; ,134,双链表节点类,其他函数 public void setNext(DoublyLinkedListElement next) nextElement = next; public void setPrevious(DoublyLinkedListElement previous) previousElement = previous; public void setValue(Object value) data = value; ,135,双链表类实现,成员变量： 包含一个表元素个数的count域。 包含两个引用域，分别引用表头和表尾元素。 public class DoublyLinkedList extends AbstractList * Number of elements within list. protected int count; * Reference to head of list. protected DoublyLinkedListElement head; * Reference to tail of list. protected DoublyLinkedListElement tail;,136,双链表类实现：构造函数,* Constructs an empty list. * post constructs an empty list public DoublyLinkedList() head = null; tail = null; count = 0; ,137,在head为头指针的双向链表中，在值为Y的结点之后插入值为X的结点，插入结点的指针变化见下图 (若改为在值为Y的结点之前插入值为X的结点，可以作类似分析)。,在双向链表中插入一个结点,图 在双向链表中插入结点（后插入）,138,(a)插入前 （b）插入后 图 在双向链表中插入结点（前插入）,ai-1,ai,在双向链表中插入一个结点,在双向链表的第i个元素前插入一个结点时，可用指针p指向该结点（称p结点），先将新结点的previous指向p结点的前一个结点，其次将p结点的前一个结点的next指向新结点，然后将新结点的next指向p结点，最后将p结点的previous指向新结点。操作过程如下图：,139,在双向链表中插入一个结点,我们在双向链表中进行插入操作时，还需注意下面两种情况： 当在链表中的第一个结点前插入新结点时，新结点的previous应为空，原链表第一个结点的previous应指向新结点，新结点的next应指向原链表的第一个结点。 当在链表的最后一个结点后插入新结点时，新结点的next应为空，原链表的最后一个结点的next应指向新结点，新结点的previous应指向原链表的最后一个结点。 在插入过程中和单向链表的主要的不同点是修改的指针的个数不同： 单向链表修改两个指针 双向链表需要修改四个指针,140,双链表的头部和尾部操作,双链表处理头部和尾部操作时比较相似。 操作时必须考虑边界情况，即表为空的情况。这种情况较为复杂。,141,在双向链表中删除一个结点,在双向链表中删除一个结点时，可用指针p指向该结点（称p结点），然后将p结点的前一个结点的next指向p结点的下一个结点，再将p的下一个结点的previous指向p的上一个结点。如下图：,142,在双向链表中删除一个结点,在删除过程中和单向链表的主要的不同点是修改的指针的个数不同： 单向链表修改一个指针； 双向链表需要修改两个指针。,143,线性表的链式存储结构,几个链表类型的实现： 单链表（singly linked list） 双链表（doubly linked list） 循环链表（circular linked list）,144,循环链表,单链表的最后一个元素的引用为空，没有使用，有点浪费。 我们可以让尾引用指向头部。 这就是循环链表，它可以很方便的访问头和尾 循环链表(Circular Linked List)是另一种形式的链式存储结构。是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，这样从表中任一结点出发都可找到表中其他的结点。 它将单链表的空间优势和双链表的速度优势结合起来,145,循环链表,实现时，循环链表往往只需要指向表尾的指针tail，而无需指向头结点的head指针！ （先思考为什么？） 因为tail的后继即为head所指结点。这样，头尾结点都可在常数时间内找到。,146,循环链表,图,不带头结的单循环链表示意图,tail,147,循环链表,头,a,1,a,2,a,n,head,(b),非空循环链表,图,带头结的单循环链表示意图,(a),空循环链表,头,head,148,头部增加一个元素,tail,149,头部增加一个元素,* Add an element to head of