数据结构单链表

1、链式存储结构的实现,表(List)的链式存储结构单链表,单链表部分操作的实现,小结和作业,复习顺序存储结构的实现,顺序存储结构,用一组地址连续的存储单元依次存放线性表中的数据元素,a0 a1 ai-1 ai an-1,线性表的起始地址(基地址),ublic class MyArrayList private AnyType theItems; /存储空间基址 private int theSize; /表的大小 private static final int DEFAULT_CAPACITY = 10; /数组容量 成员方法 ,线性表顺序存储结构的实现,线性表顺序存储结构的实现,构造函数My

2、ArrayList( ),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,t

3、heSize,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,a6a5 a5a4 a4a3 a3a2,ak = ak+1,k=(theSize-

4、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,ublic void add(int idx,AnyType x) throws LocateException /在顺序表的第idx个位置之前插入新的数据元素x if (idxtheSize-1) throw new LocateException(idx); if( theItems.length = size( ) ) ensur

5、eCapacity( 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,remo

6、ve,逻辑结构的变化, ,(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,a2a3 a3a4 a4a5,ak-1 = ak,k=i +1 theSize-1,6,theSize,5,theSize,remove移动,remove,ublic AnyType remove( int idx ) throw LocateException /删除表中的第idx个位置上的数

7、据元素 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,链式存储结构的实现,

8、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

9、 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、单链表类,链式存储结构的实现,ublic class SingleLinkedList private int theSize; /表的大小 private Node firstNode; /第一个节点 成员方法 ,链式存储结构

10、的实现,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 =n

11、ull;,theSize=0;,get,原型： public AnyType get( int idx ),作用： 返回第idx个数据元素的值,public AnyType get( int idx ) return getNode( idx ).data; ,get(3),=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 siz

12、e() ) 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 Any

13、Type 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( ),

14、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个节

15、点。,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

16、=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

17、=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(in

18、t idx),作用： 删除第idx个节点,aidx,aidx+1,(a0, , ai-1, ai, ai+1, , an), ,(a1, , ai-1, ai+1, , an),逻辑结构的变化：,存储结构的变化：,q=p.next p.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、id

19、x=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=firstNode firstNode=null=p.next;,如何判断只有一个数据元素？,theSize=1或者 firstNode.next = = null,3、表中只有一个元素,remove的边界问题,public boolean remove( int idx) No

20、de 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是否在单链表中，如果在返回其所在 的位置，否则返回

21、-1,.data与x进行比较,ublic 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 tru