《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 4-4線性表-鏈?zhǔn)降恼n堂例子

課堂練習(xí)增加方法CArrayList<T>toCArrayList()a0a1a2headNodesize=3a0a1a2Object[]listElemintsize=3課堂練習(xí)增加方法voidaddLast(Tx):將x作為隊(duì)尾，不允許使用size

//加入x作為隊(duì)尾，不允許使用size

public

voidaddLast(Tx){

if(head==null){

head=newNode<>(x,null);

size++;

return; } Node<T>p;

for(p=head;p.next!=null;p=p.next) ;//循環(huán)后，p引用表尾結(jié)點(diǎn)

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

size++; }課堂練習(xí)

publicCArrayList<T>toCArrayList(){...... }

publicCArrayList<T>toCArrayList(){ CArrayList<T>sl=newCArrayList<>(size);......

return

sl; }課堂練習(xí)

publicCArrayList<T>toCArrayList(){ CArrayList<T>sl=newCArrayList<>(size);

int

index=0;

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

sl.add(index++,p.data);

return

sl; }課堂練習(xí)a0a1a3heada0a2heada2刪除奇數(shù)位置的數(shù)據(jù)：

public

voidremoveOdd(){ Node<T>p=head;

while(p!=null&&p.next!=null){//利用了運(yùn)算&&的熔斷機(jī)制 Node<T>q=p.next;

p.next=q.next;

p=p.next;

q.data=null;

q.next=null; } }課堂練習(xí)122head12head1刪除重復(fù)的數(shù)據(jù)：思路：1、利用原有的結(jié)點(diǎn)建立一個(gè)“新鏈表”，只包含第1個(gè)結(jié)點(diǎn)1head2、原表的第2、3、4....結(jié)點(diǎn)與新表從頭至尾每個(gè)結(jié)點(diǎn)比較，如果沒有相同的，加入新表的尾；否則，“丟棄”該結(jié)點(diǎn)。

public

voidremoveRepeat(){

if(head==null)return; Node<T>p=head.next;//從第2個(gè)結(jié)點(diǎn)開始

head.next=null;//新鏈表包含第1個(gè)結(jié)點(diǎn)

while(p!=null){//判斷第2，3，4，...是否與前面的結(jié)點(diǎn)相同 Node<T>q=head; Node<T>r=q;//記錄查找后新鏈表的最后1個(gè)結(jié)點(diǎn)

while(q!=null&&!q.data.equals(p.data)){

r=q;

q=q.next; }課堂練習(xí)

if(q==null){

r.next=p;//沒有與p相同的數(shù)據(jù)，將p鏈入新鏈表的尾

p=p.next;

r.next.next=null;//新鏈表的最后1個(gè)結(jié)點(diǎn)的next=null }

else{//有與p相同的，刪除p Node<T>s=p;

p=p.next;

s.data=null;

s.next=null; } } }課堂練習(xí)課堂練習(xí)不允許利用size字段，找中間結(jié)點(diǎn)12head534p12head43pp課堂練習(xí)

publicNode<T>mid1(){

if(head==null)

return

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

while(q!=null){

p=p.next;

q=q.next;

q=q!=null?q.next:null; }

return

p; }

publicNode<T>mid(){ Node<T>p=head; Node<T>q=head;

while(q!=null&&q.next!=null){

p=p.next;

q=q.next.next;