数据结构(牛小飞)2表-单链表.ppt

链式存储结构的实现,表(List)的链式存储结构单链表,单链表部分操作的实现,小结和作业,复习顺序存储结构的实现,顺序存储结构,用一组地址连续的存储单元依次存放线性表中的数据元素,a0 a1 ai-1 ai an-1,线性表的起始地址(基地址),public class MyArrayList private AnyType theItems;/存储空间基址 private int theSize;/表的大小 private static final int DEFAULT_CAPACITY=10;/数组容量 成员方法,线性表顺序存储结构的实现,线性表顺序存储结构的实现,构造函数MyArrayList(),get(int idx),set(int idx,AnyType newVal),add(AnyType x)、add(int idx,AnyType x),remove(int idx),add,原型：public void add(int idx,AnyType x),作用：把x插入线性表，作为第idx个数据元素，即在顺序表的第idx个位置之前插入新的 数据元素x。,逻辑结构的变化,(a0,aidx-1,aidx,an-1)(a0,aidx-1,x,aidx,an-1),add,存储结构的变化,add(2,x),6,theSize,7,theSize,add,过程：1、判断i的合法性2、移动3、赋值4、theSize+,add,add合法性,A,10,一般的0itheSize,如果theItems.length=theSize?,增加存储容量,if(idxtheSize)throw new LocateException(idx);if(theItems.length=theSize)ensureCapacity(size()*2+1);/增加存储容量,add移动,6,theSize,7,theSize,a6a5a5a4a4a3a3a2,ak=ak+1,k=(theSize-1)idx,add移动,for(int i=theSize-1;i=idx;i-)theItemsi+1=theItems i;theItemsidx=x;,add(4,66),theSize-1,0,87,56,42,66,42,56,87,add,public void add(int idx,AnyType x)throws LocateException/在顺序表的第idx个位置之前插入新的数据元素x if(idxtheSize-1)throw new LocateException(idx);if(theItems.length=size()ensureCapacity(size()*2+1);/增加存储容量 for(int i=theSize-1;i=idx;i-)theItems i+1=theItems i;theItems idx=x;theSize+;,add,1、在什么情况下，移动次数最小，最小移动次数是多少？,2、在什么情况下，移动次数最多，最多移动次数是多少？,3、在插入0theSize-1每个位置的概率相同的情况下，移动次数的期望值是多少？,原型：public AnyType remove(int idx),作用：删除表中的第idx个位置上的数据元素,remove,remove,逻辑结构的变化,(a1,ai-1,ai,ai+1,an)(a1,ai-1,ai+1,an),存储结构的变化,remove(2),6,theSize,5,theSize,remove,过程：1、判断i的合法性2、取值3、移动4、theSize-,remove,a2a3a3a4a4a5,ak-1=ak,k=i+1 theSize-1,6,theSize,5,theSize,remove移动,remove,public AnyType remove(int idx)throw LocateException/删除表中的第idx个位置上的数据元素 if(idxtheSize)throw new LocateException(idx);AnyType removedItem=theItems idx;for(int i=idx+1;i theSize-1;i+)theItems i-1=theItems i;theSize-;return removedItem;,1、在什么情况下，移动次数最小，最小移动次数是多少？,2、在什么情况下，移动次数最多，最多移动次数是多少？,3、在删除0theSize-1每个位置的概率相同的情况下，移动次数的期望值是多少？,remove,链式存储结构的实现,1、每个数据元素使用一个节点表示,2、每个数据元素在物理存储空间可以不相邻,3、数据元素之间的线性关系由指针链接保证,1、节点类：,private class Node,public AnyType data;public Node next;,public Node(AnyType d,Node n),this.data=d;this.next=n;,public Node(AnyType d),this.data=d;this.next=null;,public Node(),this.data=null;this.next=null;,链式存储结构的实现,Node p,q;p=new Node(12);q=new Node(13);p.next=q;,Node q=new Node(13);Node p=new Node(12,q);,链式存储结构的实现,null,null,Node firstNode=null;,当firstNode=null时，表示空链表。,null,firstNode,链式存储结构的实现,L,2、单链表类,链式存储结构的实现,public class SingleLinkedList private int theSize;/表的大小 private Node firstNode;/第一个节点 成员方法,链式存储结构的实现,2、单链表类,单链表部分操作的实现,构造函数SingleLinkedList(),get(int idx),set(int idx,AnyType newVal),add(AnyType x)、add(int idx,AnyType x),remove(int idx),merge函数,contains(AnyType x,SingleLinkedList La),构造函数SingleLinkedList,public SingleLinkedListt(),原型:public SingleLinkedList(),作用:形成一个空表,this.firstNode=null;,theSize=0;,get,原型：public AnyType get(int idx),作用：返回第idx个数据元素的值,public AnyType get(int idx)return getNode(idx).data;,get(3),p=firstNode,定位到aidx需要移动idx次指针,p=p.next,get(0),get,get,private Node getNode(int idx),p=firstNode;,for(int i=0;i idx;i+)p=p.next;,return p;,if(idx size()throw new IndexOutOfBoundsException(getNode index:+idx+;size:+size();,Node p;,1、在什么情况下，移动指针的次数最少,2、在什么情况下，移动指针的次数最多，如何改善？,get,set,原型：public AnyType set(int idx,AnyType newVal),作用：给表中第idx个数据元素赋新值newVal，返 回赋值前的数据元素的值。,getNode(2),set(2,x),set,p.data=x,p=firstNode,x,set,public AnyType set(int idx,AnyType newVal),for(int i=0;i idx;i+)p=p.next;,AnyType oldVal=p.data;p.data=newVal;,if(idx size()/抛出异常,Node p=firstNode;,return oldVal；,add,原型：public boolean add(AnyType x),作用：将x插入到链表。,默认为最后一个节点，即add(size(),x),add,public boolean add(AnyType x)add(size(),x);return true;,add,原型：public boolean add(int idx,AnyType x),作用：将x插入到链表，作为第idx个节点,逻辑结构的变化,(a0,aidx-1,aidx,an-1)(a0,aidx-1,e,aidx,an-1),存储结构的变化,过程 1、建立一个含有数据元素x的新节点。2、找到第idx-1个节点3、调整，将新节点插入到链表中。,add,过程 1、建立一个含有数据元素x的新节点。,add,Node newNode=new Node(x),newNode,过程 2、找到第idx-1个节点。,add,Node p=getNode(idx-1),过程 3、调整，将新节点插入到链表中。,add,newNode,newNode.next=p.next,p.next=newNode,add,public void add(int idx,AnyType x),Node p=getNode(idx-1);newNode.next=p.next;p.next=newNode;theSize+;,Node newNode=new Node(x);,1、idx=0,2、idx=theSize,3、空表,add的边界问题,1、idx=0时,newNode.next=p.next;,p.next=newNode;,a0,a1,a2,p,x,newNode,add的边界问题,L,newNode.next=firstNode,firstNode=newNode;,a0,a1,a2,L,x,newNode,如果 idx=0，则过程如下：,add的边界问题,firstNode,2、firstNode=null，即为空表，不能插入,p=firstNode,p,newNode.next=p.next;,p.next=newNode;,add的边界问题,firstNode,add的边界问题,2、firstNode=null时的操作过程为：,newNode.next=firstNode,firstNode=newNode;,add,public void add(int idx,AnyType x),Node p=getNode(idx-1);newNode.next=p.next;p.next=newNode;theSize+;,Node newNode=new Node(x);,if(this.firstNode=null|idx=0)newNode.next=firstNode;firstNode=newNode;theSize+;else,remove,原型：public boolean remove(int idx),作用：删除第idx个节点,aidx,aidx+1,(a0,ai-1,ai,ai+1,an),(a1,ai-1,ai+1,an),逻辑结构的变化：,存储结构的变化：,q=p.nextp.next=q.next;return true;,aidx+1,p,q,remove,p=getNode(idx-1),public boolean remove(int idx)Node p=getNode(idx-1),q;q=p.next;p.next=q.next;theSize-;return true;,remove,2、idx=0,4、idx=theSize-1,1、空表,3、表中只有一个元素,remove的边界问题,q=p.next;p.next=q.next;,无法进行删除操作,a1,a2,L,2、idx=0时的操作过程为：,p=firstNode;,firstNode=p.next;,remove的边界问题,a0,L,p,p=firstNodefirstNode=null=p.next;,如何判断只有一个数据元素？,theSize=1或者firstNode.next=null,3、表中只有一个元素,remove的边界问题,public boolean remove(int idx)Node p=getNode(idx-1),q;q=p.next;p.next=q.next;theSize-;return true;,remove,if(firstNode=null)return false;/空表if(idx=0|firstNode.next=null)/只有一个数据元素，或idx=0 Node p=this.firstNode;firstNode=p.next;theSize-;else,contains,原型：public int contains(AnyType x),作用：测试值x是否在单链表中，如果在返回其所在 的位置，否则返回-1,p.data与x进行比较,public int contains(AnyType x)int idx=0;if(firstNode=null)return-1;/空表 Node p=firstNode;while(p.data!=x)return idx;,contains,idx+;p=p.next;,if(p=null)return-1;,merge,原型：public boolean merge(SingleLinkedList La,SingleLinkedList Lb),作用：把Lb的数据元素插入到La的表尾,a0,a1,a2,La,b0,b1,Lb,m=Lb.get(i);La.add(m);,public boolean merge(SingleLinkedList La,SingleLinkedList Lb)for(int i=0;iLb.theSize;i+)return true;,if(code!=true)return false;,AnyType m=(AnyType)Lb.get(i);,boolean code=La.add(m);,merge,作用：把两个有序表合并成一个新的有序表,La:a1 a2 a3 am,Lb:b1 b2 b3 bn,Lc:c1 c2 c3 cm+nci=aj or ci=bk,原型:public boolean mergeSort(SingleLinkedList La,SingleLinkedList Lb,SingleLinkedList Lc),merge（讨论）,merge（讨论）,public void mergeSort(SingleLinkedList La,SingleLinkedList Lb,SingleLinkedList Lc),Node pa=La.firstNode,pb=Lb.firstNode,tmp;,while(pa!=null&pb!=null)/合并if(pareTo(pb.data)0)else,tmp=pa;pa=pa.next;,tmp=pb;pb=pb.next;,Lc.add(tmp.data);,merge（讨论）,while(pa!=null),Lc.add(pa.data);pa=pa.next;,while(pb!=null),Lc.add(pb.data);pb=pb.next;,小结和作业,逻辑结构,链式存储结构,主要操作的实现：构造函数、get、set、add、remove、contains、merge,1、每个元素用一个节点表示，节点有数据域和指针域,2、元素之间的逻辑关系用指针维护,3、头节点,小结和作业,p73,3.4,