现在的位置: 首页 > 综合 > 正文

Java数据结构和算法–链表

2012年06月28日 ⁄ 综合 ⁄ 共 10254字 ⁄ 字号 评论关闭

 (1)简单链表

Java代码 复制代码
  1. package ChapterFive;   
  2.   
  3. class Link<E> {   
  4.   
  5.     public E data;   
  6.   
  7.     public Link<E> next;   
  8.   
  9.     public Link(E data) {   
  10.         this.data = data;   
  11.     }   
  12. }   
  13.   
  14. class LinkList<E> {   
  15.   
  16.     public Link<E> first;   
  17.     //链表中数据项的个数   
  18.     public int size;   
  19.   
  20.     public LinkList() {   
  21.         first = null;   
  22.         size = 0;   
  23.     }   
  24.     //在表头插入新的数据   
  25.     public void insertFirst(E value) {   
  26.         Link<E> link = new Link<E>(value);   
  27.         link.next = first;   
  28.         first = link;   
  29.         size++;   
  30.     }   
  31.     //判断链表是否为空   
  32.     public boolean isEmpty() {   
  33.         return size == 0;   
  34.     }   
  35.     //删除表头   
  36.     public Link<E> deleteFirst() {   
  37.         Link<E> temp = first;   
  38.         first = first.next;   
  39.         size--;   
  40.         return temp;   
  41.     }   
  42.     //输出链表中的所有数据   
  43.     public void display() {   
  44.         Link<E> curr = first;   
  45.         while (curr != null) {   
  46.             System.out.print(curr.data + " ");   
  47.             curr = curr.next;   
  48.         }   
  49.         System.out.println();   
  50.     }   
  51.     //返回链表中数据项的个数   
  52.     public int size() {   
  53.         return size;   
  54.     }   
  55.     //获取从头至尾的第i个数据项   
  56.     public Link<E> get(int i) {   
  57.         if (i > size() - 1 || i < 0)   
  58.             try {   
  59.                 throw new IndexOutOfBoundsException();   
  60.             } catch (Exception e) {   
  61.                 e.printStackTrace();   
  62.             }   
  63.         Link<E> curr = first;   
  64.         for (int n = 0; n < size(); n++) {   
  65.             if (n == i)   
  66.                 return curr;   
  67.             else  
  68.                 curr = curr.next;   
  69.         }   
  70.         return null;   
  71.     }   
  72.     //输出从头至尾的第i个数据项   
  73.     public void remove(int i) {   
  74.         if (i == 0)   
  75.             deleteFirst();   
  76.         else if (i == size() - 1)   
  77.             get(i - 1).next = null;   
  78.         else {   
  79.             get(i - 1).next = get(i + 1);   
  80.         }   
  81.         size--;   
  82.     }   
  83. }   
  84.   
  85. public class Link_list {   
  86.     public static void main(String[] args) {   
  87.         LinkList<Long> ll = new LinkList<Long>();   
  88.         for (int i = 0; i < 10; i++) {   
  89.             Long value = (long) (Math.random() * 100);   
  90.             ll.insertFirst(value);   
  91.         }   
  92.         ll.display();   
  93.         while (!ll.isEmpty()) {   
  94.             ll.deleteFirst();   
  95.             ll.display();   
  96.         }   
  97.         System.out.println("Ok");   
  98.     }   
  99. }  

(2)链栈

Java代码 复制代码
  1. package ChapterFive;   
  2.   
  3. class LinkStack<E> {   
  4.   
  5.     LinkList<E> linkList;   
  6.   
  7.     int size;   
  8.   
  9.     public LinkStack() {   
  10.         size = 0;   
  11.         linkList = new LinkList<E>();   
  12.     }   
  13.     //入栈   
  14.     public void push(E value) {   
  15.         linkList.insertFirst(value);   
  16.         size++;   
  17.     }   
  18.     //出栈   
  19.     public Link<E> pop() {   
  20.         size--;   
  21.         return linkList.deleteFirst();   
  22.     }   
  23.     //返回栈顶元素   
  24.     public Link<E> top() {   
  25.         return linkList.first;   
  26.     }   
  27.     //判断栈是否为空   
  28.     public boolean isEmpty() {   
  29.         return size == 0;   
  30.     }   
  31.     //显示栈中的全部数据   
  32.     public void display() {   
  33.         linkList.display();   
  34.     }   
  35. }   
  36.   
  37. public class Link_stack {   
  38.     public static void main(String[] args) {   
  39.         LinkStack<Long> ls = new LinkStack<Long>();   
  40.         for (int i = 0; i < 10; i++) {   
  41.             Long value = new Long((long) (Math.random() * 100));   
  42.             ls.push(value);   
  43.         }   
  44.         while (!ls.isEmpty()) {   
  45.             ls.pop();   
  46.             ls.display();   
  47.         }   
  48.         System.out.println("Ok");   
  49.     }   
  50. }  

(3)有序表

Java代码 复制代码
  1. package ChapterFive;   
  2.   
  3. class SortedLink {   
  4.   
  5.     public Link<Long> first;   
  6.   
  7.     int size;   
  8.   
  9.     public SortedLink() {   
  10.         first = null;   
  11.         size = 0;   
  12.     }   
  13.     //向有序链表中插入数据   
  14.     public void insert(long value) {   
  15.         Link<Long> newLink = new Link<Long>(value);   
  16.         Link<Long> previous = null;   
  17.         Link<Long> curr = first;   
  18.         while (curr != null && (value > curr.data)) {   
  19.             previous = curr;   
  20.             curr = curr.next;   
  21.         }   
  22.         if (previous == null)// 链表为空(在表头插入)   
  23.             first = newLink;   
  24.         else  
  25.             previous.next = newLink;//插入新的节点   
  26.         newLink.next = curr;   
  27.         size++;   
  28.     }   
  29.     //删除第一个节点   
  30.     public Link<Long> remove() {   
  31.         Link<Long> temp = first;   
  32.         first = first.next;   
  33.         size--;   
  34.         return temp;   
  35.     }   
  36.     //判断链表是否为空   
  37.     public boolean isEmpty() {   
  38.         return size == 0;   
  39.     }   
  40.     //输出链表的所有数据   
  41.     public void display() {   
  42.         Link<Long> curr = first;   
  43.         while (curr != null) {   
  44.             System.out.print(curr.data + " ");   
  45.             curr = curr.next;   
  46.         }   
  47.         System.out.println();   
  48.     }   
  49. }   
  50.   
  51. public class SortedLinkApp {   
  52.     public static void main(String[] args) {   
  53.         SortedLink sl = new SortedLink();   
  54.         for (int i = 0; i < 10; i++) {   
  55.             sl.insert((long) (Math.random() * 100));   
  56.         }   
  57.         while (!sl.isEmpty()) {   
  58.             sl.remove();   
  59.             sl.display();   
  60.         }   
  61.     }   
  62. }  

(4)双向链表

Java代码 复制代码
  1. package ChapterFive;   
  2.   
  3. class DoubleLink<E> {   
  4.   
  5.     public Link<E> first;   
  6.   
  7.     public Link<E> last;   
  8.   
  9.     int size;   
  10.   
  11.     @SuppressWarnings("hiding")   
  12.     class Link<E> {   
  13.         public E data;   
  14.   
  15.         public Link<E> next;// 链表的下一项   
  16.   
  17.         public Link<E> previous;// 链表的前一项   
  18.   
  19.         public Link(E value) {   
  20.             this.data = value;   
  21.         }   
  22.     }   
  23.   
  24.     public DoubleLink() {   
  25.         first = null;   
  26.         last = null;   
  27.         size = 0;   
  28.     }   
  29.   
  30.     // 在链表的首部插入一项   
  31.     public void insertFirst(E value) {   
  32.         Link<E> newLink = new Link<E>(value);   
  33.         if (isEmpty())// 如果链表为空则first == last   
  34.             last = newLink;   
  35.         else  
  36.             first.previous = newLink;// 确定原first与newLink的前后关系   
  37.         newLink.next = first;   
  38.         first = newLink;// 设置新的first值   
  39.         size++;   
  40.     }   
  41.   
  42.     // 在链表的尾部插入一项   
  43.     public void insertLast(E value) {   
  44.         Link<E> newLink = new Link<E>(value);   
  45.         if (isEmpty())// 如果链表为空则last == first   
  46.             first = newLink;   
  47.         else {   
  48.             last.next = newLink;// 确定原last与newLink的前后关系   
  49.             newLink.previous = last;   
  50.         }   
  51.         last = newLink;// 设置新的last值   
  52.         size++;   
  53.     }   
  54.   
  55.     // 删除双向链表的表头   
  56.     public Link<E> deleteFirst() {   
  57.         Link<E> temp = first;   
  58.         if (first.next == null)// 链表中只有一项数据   
  59.             last = null;   
  60.         else  
  61.             first.next.previous = null;// 销毁原链表的头部   
  62.         first = first.next;   
  63.         size--;   
  64.         return temp;   
  65.     }   
  66.   
  67.     // 删除链表的最后一项   
  68.     public Link<E> deleteLast() {   
  69.         Link<E> temp = last;   
  70.         if (first.next == null)// 链表中只有一项数据   
  71.             first = null;   
  72.         else  
  73.             last.previous.next = null;// 销毁原链表的尾部   
  74.         last = last.previous;   
  75.         size--;   
  76.         return temp;   
  77.     }   
  78.   
  79.     // 判断链表是否为空   
  80.     public boolean isEmpty() {   
  81.         return size == 0;   
  82.     }   
  83.   
  84.     // 输出链表中的所有数据项   
  85.     public void display() {   
  86.         Link<E> curr = first;   
  87.         while (curr != null) {   
  88.             System.out.print(curr.data + " ");   
  89.             curr = curr.next;   
  90.         }   
  91.         System.out.println();   
  92.     }   
  93. }   
  94.   
  95. public class DoubleLinkApp {   
  96.     public static void main(String[] args) {   
  97.         DoubleLink<Integer> dl = new DoubleLink<Integer>();   
  98.         for (int i = 0; i < 5; i++) {   
  99.             dl.insertFirst((int) (Math.random() * 100));   
  100.         }   
  101.         for (int i = 0; i < 5; i++) {   
  102.             dl.insertLast((int) (Math.random() * 100));   
  103.         }   
  104.         dl.display();   
  105.         while (!dl.isEmpty()) {   
  106.             dl.deleteFirst();   
  107.             dl.deleteLast();   
  108.             dl.display();   
  109.         }   
  110.         System.out.println("Ok");   
  111.     }   
  112. }  

抱歉!评论已关闭.