《数据结构》 (java版) 课件 4-3线性表表-链式

主要内容Node(结点)类单(向)链表：用引用变量表示后继关系的线性表实现方式性能分析带头结点的单(向)链表循环单(向)链表双向链表：用引用变量表示前驱和后继关系的线性表实现方式双向循环链表Node类privatestaticclassNode<T>{//嵌套类 Tdata; Node<T>next; ...}Node类对象之间的引用关系∧Node对象简称结点privatestaticclassNode<T>{//嵌套类 Tdata; Node<T>next; ...}线性表的链式描述a0a1a2a3使用结点存储(引用)数据结点之间的引用关系与线性表数据之间的先后关系一致线性表的链式描述4个数据=>4个结点，结点的字段data引用数据对象。若数据之间有先后关系，对应的结点之间有引用关系。SinglyLinkedList(单向链表)：由字段next可找到后继结点a0a1a2a3∧结点的相关约定结点的编号：1、2、3结点的命名：用存储的数据命名，结点a0、结点a1。首结点、尾结点前驱结点、后继结点a0a1a2a3∧CLinkedListpublic

classCLinkedList<T>implementsIList<T>,Iterable<T>,Cloneable{ privateNode<T>first; private

int

size;...

private

static

classNode<T>{//嵌套类

Tdata;

Node<T>next;

Node(Tdata,Node<T>next){

this.data=data;

this.next=next; } }}CLinkedList是使用单链表实现的线性表。CLinkedList对象firstNode对象size=3a0a1a2CLinkedList的对象∧firstsize=3a0a1a2∧简明画法/* CLinkedList(){

first=null; size=0; }*/构造器构造器构建空表。字段size=0，并且字段first=null判断线性表是否为空表，判断size==0，或first==nullfirst=∧size=0p=p.next;Node<T>p=first;pp=p.next;通过字段next可以找到后继结点。找后继结点first∧a0a1a2p=p.next;

=

∧

p=p.next;Node<T>p=first;pp=p.next;pp形象的表示：p跑向下一个结点找后继结点first∧a0a1a2p=p.next;pfor(Node<T>p=first;p!=null;p=p.next){

…//

处理数据}遍历链表：从头至尾，依次“访问”各个数据课堂练习first∧a0a1a2

private

classItrimplementsIterator<T>{

privateNode<T>cursor;

publicItr(){

cursor=first; }

public

booleanhasNext(){

return

cursor!=null; }

publicTnext(){ Tdata=cursor.data;

cursor=cursor.next;

return

data; } }迭代器first∧a0a1a2

public

intindexOf(Tx){

int

index=0;

for(Node<T>p=first;p!=null;p=p.next{if(p.data.equals(x))//这种表达方式数据不能为null

return

index;

index++ }

return-1; }first∧a0a1a2intindexOf(Tx)

public

intindexOf(Tx){

int

index=0;

for(Node<T>p=first;p!=null;p=p.next){if(x.equals(p.data))//这种表达方式x不能为null

return

index; ++index; }

return-1; }intindexOf(Tx)

public

intindexOf1(Tx){

if(x==null){

int

index=0;

for(Node<T>p=first;p!=null;p=p.next){

if(p.data==null)

return

index; ++index; } }else{

int

index=0;

for(Node<T>p=first;p!=null;p=p.next){

if(x.equals(p.data))

return

index; ++index; } }

return-1; }x可以是null，数据中也可以有nullintindexOf(Tx)first∧a0a1a2Tget(intindex)编号为index的数据存储于第index+1个结点。如何找到第index+1个结点？index=0:p所指的就是，执行0次p=p.nextindex=1:执行1次p=p.nextindex=2:执行2次p=p.nextp=first需要执行index次找后继结点的操作：p=p.next。 Node<T>p=first;

for(int

i=0;i<index;i++)

p=p.next;Tget(intindex)first∧a0a1a2循环结束后，p引用了第index+1个结点，它存储的是编号为index的数据。

publicTget(int

index){ rangeCheck(index); Node<T>p=first;

for(int

i=0;i<index;i++)

p=p.next;

return

p.data; }Tget(intindex) Node<T>p=first;

for(int

i=0;i<index-1;i++)

p=p.next;first∧a0a1a2下面的循环结束后：p引用了第几个结点？它是第index+1个结点的？课堂练习abcepqabceqp∧为结点加入新的后继结点∧∧新创建一个结点(用q引用它)，将它作为结点p的后继结点：abcepqq.next=p.next;p.next=q;或者：p.next=newNode<T>(e,p.next);

为结点加入新的后继结点∧∧q=new

Node<>(e,null);创建结点，存储x。将新结点加入链表，它的前驱结点是第index个结点，后继结点是前驱结点的后继结点。首先使p引用前驱结点，然后利用上面介绍的操作即可。注意：首结点没有前驱结点，需要特殊处理。voidadd(intindex,Tx)

public

voidadd(int

index,Tx){ rangeCheckForAdd(index);

if(index==0){//没有前驱结点:空表或加入的数据编号为index

first=newNode<T>(x,first);//加入后作为第1个结点 }else{ Node<T>p=first;

for(int

i=0;i<index-1;i++)

p=p.next;

p.next=newNode<T>(x,p.next); } ++size; }voidadd(intindex,Tx)acdbq.next=p.next;qpq=p;p=p.next;帮助GC：p.next=null;p.data=null;p删除结点的后继结点∧删除结点p的后继结点：找到第index+1个结点的前驱结点利用上面介绍的操作即可。注意：首结点没有前驱结点，需要特殊处理。Tremove(intindex)

publicTremove(int

index){ rangeCheck(index);//空表会抛异常 Node<T>p=first;

if(index==0){//没有前驱结点

first=first.next; }else{//有前驱结点

for(int

i=0;i<index-1;i++)

p=p.next; Node<T>q=p;

p=p.next;

q.next=p.next; }

//p指向待删除结点 Tvalue=p.data;

p.data=null;//帮助GC

p.next=null; --size;

return

value; }Tremove(intindex)voidclear()first=

public

voidclear(){

while(first!=null){//不断的删除第1个结点 Node<T>q=first;//q引用待删除的结点

first=first.next;//下一个结点

q.data=null;//帮助GC

q.next=null; }

size=0; }qfirsta0a1a2a0a1a2∧∧Node<T>pre=null;for(Node<T>p=first;p!=null;pre=p,p=p.next){….if(p.data….)}如果是空表，则pre=null，没有前驱结点如果满足条件的结点是第1个结点，

则pre=null，没有前驱结点prefirsta0a1a2p根据某条件找前驱结点∧ Node<T>p=null;//c的前驱结点 Node<T>c=first; Node<T>q;//q的后继结点

while(c!=null){//可替换成其他条件

q=cur.next;//记住c的后继结点 …处理c引用的结点

p=c;//准备处理下一个结点

c=q; }pfirsta0a1a3cqa2注意：表头(a0)和表尾(a3)结点的特殊性找前驱和后继结点∧a0a1a2firstsizefirstsize

@SuppressWarnings("unchecked")

privateCLinkedList<T>superClone(){

try{

return

(CLinkedList<T>)super.clone();}catch(CloneNotSupportedExceptione){

throw

newInternalError(e);}}Objectclone()∧

publicObjectclone(){ CLinkedList<T>v=superClone();

if(v.first==null)//空表

return

v;

//复制this的链表，赋予v

v.first=newNode<>(first.data,null);

for(Node<T>p=first.next,q=v.first;p!=null;p=p.next,q=q.next)

q.next=newNode<>(p.data,null);

return

v; } }pfirsta0a1a2qv.firsta0a1a2Objectclone()∧∧∧∧pqpq

public

booleanequals(Objectobj){

if(this==obj)

return

true;

if(obj

instanceofCLinkedList<?>){ CLinkedList<?>rhd=(CLinkedList<?>)obj;

if(this.size!=rhd.size)

return

false;

for(Node<?>p=first,q=rhd.first;p!=null;p=p.next,q=q.next){

if(!p.data.equals(q.data))

return

false; }

return

true; }

return

false; }equalsrhd.first∧b0b1b2first∧a0a1a2pqpppqqqisEmpty:O(1)size:O(1)indexOf:主要操作是找后继结点和比较。位置0123n

-

1移动次数0123n

-

1比较次数1234n查找成功：最少0次，最多n

-

1次。等概率的平均：O(n)查找不成功：移动n

-

1次，比较n次，O(n)算法复杂性分析add:主要操作是找后继结点，O(n)remove:主要操作是找后继结点，O(n)get:主要操作是找后继结点，O(n)算法复杂性分析......01234......length-1顺序存储和链式存储的区别first∧顺序的get和set:O(1)随机存取；链式的get和set:O(n)顺序存取add和remove的时间复杂度都是O(n)，但：顺序的add、remove的主要操作是复制数据：listElem[i]=listElem[i+1]，需要读、写内存链式的add、remove的主要操作是找后继结点：

p

=

p.next，需要读内存,写内存，p可以优化为使用寄存器，但需要注意内存体系结构的影响顺序存储和链式存储的区别如果要逐一读取表中的所有数据：顺序存储：for+get链式存储:使用迭代器顺序存储需要一次申请内存，必要时申请更大的内存，适合能预知数据量的场合。链式存储只在需要时申请内存，不需要时释放内存，适合动态数据集(变化较大的数据集）但是，需要更多的存储空间(一个结点比一个数据元素占用更大的存储空间)。顺序存储和链式存储的区别add和remove需要对编号0做特殊处理，原因是编号为0的结点没有前驱结点，一种解决方案是增加1个冗余结点“头结点”，使编号为0的结点也有前驱结点。头结点firstfirsta0a1a2注意：头结点不存储数据，但也可以根据需要，存储特殊的数据加入头结点的目的是为了解决add和remove方法需要判断index为0的情形带头结点的单(向)链表∧∧public

classLinkedListWithfirstNode<T>implementsIlist<T>{

privateNode<T>first;

int

size; LinkedListWithfirstNode(){

first=newNode<>(null,null);//头结点 }

private

static

classNode<T>{ Tdata; Node<T>next; Node(Tdata,Node<T>next){

this.data=data;

this.next=next; } }带头结点的单(向)链表空表：first∧∧

publicTget(int

index){ rangCheck(index); Node<T>p=first.next;//注意：开始的位置

//index次

for(int

i=0;i<index;i++)

p=p.next;

return

p.data; }get

public

voidadd(int

index,Tx){//对比CLinkedList rangeCheckForAdd(index);

//找前驱结点 Node<T>p=first;

//注意：开始的位置

for(int

i=0;i<index;i++)

p=p.next;

p.next=newNode<>(x,p.next); ++size; }add

publicTremove(int

index){//对比CLinkedList rangeCheck(index); Node<T>p=first;

//找到index的前驱

for(int

i=0;i<index;i++)

p=p.next;//循环结束后，p引用待删除结点的前驱 Node<T>q=p.next;//q引用待删除结点

p.next=q.next;//将待删除结点从链表中移除 Tvalue=q.data;

q.data=null;//帮助GC

q.next=null; --size;

return

value; }removefirst

public

voidclear(){

//不断删除first引用结点的后继结点，直到剩下头结点

while(first.next!=null){ Node<T>q=first.next;//q引用待删除结点

first.next=q.next;//将q引用的结点从链表中移除

q.data=null;//帮助GC

q.next=null; }

size=0; }clear∧a0a1a2firstfirst形式一：带头结点的单(向)循环链表构造器：public

classCircularLinkedListWithfirstNode<T>implementsIlist<T>,Cloneable{

privateNode<T>first;

int

size; CircularLinkedListWithfirstNode(){

first=newNode<>(null,null);

first.next=first;//循环 }a0a1a2firstfirst如何实现遍历？开始结点：p=first.next结束条件：p!=first带头结点的单(向)循环链表a0a1a2tailtail形式二：如何实现遍历？开始结点：p=tail.next.next结束条件：p!=tail.next带头结点的单(向)循环链表课堂练习因为要求tail始终引用尾结点，如果删除的结点是尾结点就需要对此进行特殊处理，应该如何处理？a0a1a2tail一、作用：方便定位一个结点的前驱结点和后继结点二、结点的形式aifirstlasta2