2019数据结构（牛小飞）3 表带头节点的单链表和循环单链表ppt课件.ppt

《2019数据结构（牛小飞）3 表带头节点的单链表和循环单链表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、带头节点的单链表表的链式存储结构—带头节点单链表和循环单链表部分操作的实现小结和作业复习循环单链表顺序存储和链式存储的区别复习单链表：部分成员方法：构造函数、get、set、add、remove、getSize、contains、mergeLa4a0a1a2a3最基本的动作：从左到右移动指针p=p.next带头节点的单链表逻辑形态a0a1a2L空链表L头节点分析：与前面的单链表相比，必须有一个头节点publicclassSheadLinkedList>{privateinttheSize

2、;//表的大小privateNodeheadNode;//头节点……成员方法}带头节点的单链表类带头节点的单链表存储结构的实现部分操作的实现构造函数SheadLinkedList()get(intidx)set(intidx,AnyTypenewVal)add(AnyTypex)、add(intidx,AnyTypex)remove(intidx)getSize()其他方法（讨论）SheadLinkedListheadheadpublicSheadLinkedList(){//构造带头节点的单链表Nodep=newNode

3、Type>();p.next=headNode;//p.next=null;headNode=p;theSize=0;}get1、p指向第一个2、重复p=p.next操作idx次3、p指向了第i个元素a0a1a2Lp1、p指向头节点2、重复p=p.next操作idx+1次3、p指向了第idx个元素pa0a1a2LgetpublicAnyTypeget(intidx){returngetNode(idx).data;}getgetprivateNodegetNode(intidx){}p=headNode;//指向头节点for(inti=0;i

4、x+1;i++)p=p.next;returnp;if(idx<0

5、

6、idx>getSize())thrownewIndexOutOfBoundsException("getNodeindex:"+idx+";size:"+size());Nodep;getNode(1);set(1,x)setp.data=x;p=headNode;a0a1a2Lppset(idx,x)getNode(idx);p.data=x;setpublicAnyTypeset(intidx,AnyTypenewVal){}for(inti=0;i

7、p.next;AnyTypeoldVal=p.data;p.data=newVal;if(idx<0

8、

9、idx>getSize())//抛出异常Nodep=headNode;returnoldVal1、idx=02、idx=theSize-13、空表1、重新修改操作2、OK3、重新修改操作add表用SingleLinkedList实现时的边界情况adda0a1a2LpxnewNodea0a1a2Lp头节点idx=0,i-1=?a0的前驱是谁？publicbooleanadd(AnyTypex){add(size(),x);returntrue;}a

10、ddaddpublicvoidadd(intidx,AnyTypex){NodenewNode=newNode(x);theSize++;}newNode.next=p.next;p.next=newNode;Nodep=this.headNode;;intj=0;while(j

11、t循环idx次后，p指向欲删除节点的前一个节点，q指向要删除的节点。removea0LpqqpremovepublicAnyTyperemove(intidx){}q=p.next;e=q.data;p.next=q.next;theSize--;returne;AnyTypee;intj=0;Nodep=this.headNode;,q;while(j>{pr