多種數(shù)據(jù)結(jié)構(gòu)的Java實現(xiàn)

moonboat 2009-02-11

展開全文

多種數(shù)據(jù)結(jié)構(gòu)的Java實現(xiàn)

class Node {
  Object item; Node next;
    Node (Object v) {
     item = v; next = null;
  }
}

頭指針，空尾指針
初始化：head = null;
在x后插入t：
if ( x == null)
{ head = t; head.next = null; }
else { t.next = x.next; x.next = t; }
移走x之后的結(jié)點：t = x.next; x.next = t.next;
循環(huán)遍歷：for ( t = head; t != null; t = t.next )

檢查鏈表是否為空：if ( head == null )
空頭結(jié)點，空尾指針
初始化：head = new Node(); head.next = null;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的結(jié)點：t = x.next; x.next = t.next;
循環(huán)遍歷：for ( t = head.next; t != null; t = t.next )
檢查鏈表是否為空：if ( head.next == null )
空頭結(jié)點，空尾結(jié)點
初始化：head = new Node(); z = new Node(); head.next = z; z.next = z;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的結(jié)點：t = x.next; x.next = t.next;
循環(huán)遍歷：for ( t = head.next; t != z; t = t.next )
檢查鏈表是否為空：if ( head.next == z )
循環(huán)鏈表
第一次插入：head.next = head;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的結(jié)點：t = x.next; x.next = t.next;
循環(huán)遍歷：t = head; do { t = t.next; } while ( t != head );
檢查是否只有一個數(shù)據(jù)項：if ( head.next == head )

堆棧

數(shù)組實現(xiàn)

class Stack {
  private Object[] s;
  private int n;
  Stack ( int maxN ) {
    s = new Object[maxN]; n = 0;
  }
  boolean isEmpty() { return ( n == 0 ); }
  void push ( Object item ) { s[n++] = item; }
  Object pop() {
    Object t = s[--n]; s[n] = null; return t;
  }
}

鏈表實現(xiàn)
class Stack {
  private Node head;
  private class Node {
    Object item; Node next;
    Node ( Object item, Node next ) {
      this.item = item; this.next = next;
    }
  }
  Stack ( Object maxN ) { head = null; }
  boolean isEmpty() { return ( head ==null ); }
  void push ( Object item ) { head = new Node(item, head); }
  Object pop() {
    Object v = head.item;
    Node t = head.next;
    head = t;
    return v;
  }
}

FIFO隊列的鏈表實現(xiàn)

class Queue {
  private class Node {
    Object item; Node next;
    Node ( Object item ) {
      this.item = item; this.next = null;
    }
  }
  Private Node head, tail;
  Queue ( Object max ) { head = null; tail = null; }
  boolean isEmpty() { return ( head ==null ); }
  void put ( Object item ) {
    Node t = tail;
    tail = new Node(item);
    if ( empty() )
      head = tail;
    else t.next = tail
  }
  Object get() {
    Object v = head.item;
    Node t = head.next;
    head = t;
    return v;
  }
}