Java数据结构算法实现

289434497 贡献于2012-08-11

作者 微软用户  创建于2008-12-05 09:31:00   修改者微软用户  修改于2008-12-09 05:39:00字数26708

文档摘要:大O表示法:粗略的量度方法即算法的速度是如何与数据项的个数相关的算法大O表示法表示的运行时间线性查找O(N)二分查找O(logN)无序数组的插入O(1)有序数组的插入O(N)无序数组的删除O(N)有序数组的删除O(N)O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到)排序
关键词:

1. 大O表示法:粗略的量度方法即算法的速度是如何与数据项的个数相关的 算法 大O表示法表示的运行时间 线性查找 O(N) 二分查找 O(logN) 无序数组的插入 O(1) 有序数组的插入 O(N) 无序数组的删除 O(N) 有序数组的删除 O(N) O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到) 2. 排序 public class JWzw { //插入排序 public void insertArray(Integer []in){ int tem = 0; int num = 0; int upnum = 0; for (int i = 0; i < in.length; i++) { for (int j = i - 1; j >= 0; j--) { num++; if (in[j+1] < in[j]) { tem = in[j+1]; in[j+1] = in[j]; in[j] = tem; upnum++; } else { break; } } } for (int i = 0; i < in.length; i++) { System.out.print(in[i]); if(i < in.length - 1) { System.out.print(","); } } System.out.println(); System.out.println("插入排序循环次数:" + num); System.out.println("移动次数:" + upnum); System.out.print("\n\n\n"); } //选择排序 public void chooseArray(Integer []in){ int tem = 0; int num = 0; int upnum = 0; for(int i = 0;i < in.length;i++) { for(int j = i;j < in.length - 1;j++){ num++; if(in[j+1] < in[j]){ tem = in[j+1]; in[j + 1] = in[j]; in[j] = tem; upnum++; } } } for (int i = 0; i < in.length; i++) { System.out.print(in[i]); if(i < in.length - 1) { System.out.print(","); } } System.out.println(); System.out.println("选择排序循环次数:" + num); System.out.println("移动次数:" + upnum); System.out.print("\n\n\n"); } //冒泡排序 public void efferArray(Integer []in){ int tem = 0; int num = 0; int upnum = 0; for(int i = 0;i < in.length;i++){ for(int j = i;j < in.length - 1;j++) { num++; if(in[j+1] < in[i]){ tem = in[j+1]; in[j+1] = in[i]; in[i] = tem; upnum++; } } } for (int i = 0; i < in.length; i++) { System.out.print(in[i]); if(i < in.length - 1) { System.out.print(","); } } System.out.println(); System.out.println("冒泡排序循环次数:" + num); System.out.println("移动次数:" + upnum); System.out.print("\n\n\n"); } //打印乘法口诀 public void printMulti(){ for (int j = 1; j < 10; j++) { for (int i = 1; i <= j; i++) { System.out.print(i + " * " + j + " = " + j * i + "\t"); } System.out.print("\t\n"); } System.out.print("\n\n\n"); } //打印N * 1 + N * 2 + N * 3 =num的所有组合 public void printNumAssemble(int num){ for (int i = 0; i < num + 1; i++) { for (int j = 0; j < num / 2 +1; j++) { for (int in = 0; in < num / 3 + 1; in++) { if (i * 1 + j * 2 + in * 3 == num) { System.out.println("小马" + i + ",\t中马" + j + ",\t大马" + in); } } } } } /** * @param args */ public static void main(String[] args) { JWzw jwzw = new JWzw(); int num = 3; jwzw.printMulti();//打印乘法口诀 jwzw.printNumAssemble(100);//打印N * 1 + N * 2 + N * 3 =num的所有组合 Integer in[] = {8,89,5,84,3,45,12,33,77,98,456,878,654,213,897}; jwzw.efferArray(in);//冒泡排序 Integer in1[] = {8,89,5,84,3,45,12,33,77,98,456,878,654,213,897}; jwzw.insertArray(in1);//插入排序 Integer in2[] = {8,89,5,84,3,45,12,33,77,98,456,878,654,213,897}; jwzw.chooseArray(in2);//选择排序 //int i = num++; //System.out.println(i); System.out.println(1000>>2); } } 3. 优先级队列 class PriorityQueue { private long[] a = null; private int nItems = 0; private int maxSize = 0; public PriorityQueue(int maxSize) { a = new long[maxSize]; this.maxSize = maxSize; nItems = 0; } public void insert(long l) { //优先级队列的插入不是队尾,而是选择一个合适的按照某种顺序插入的 //当队列长度为0时,如下 //不为0时,将所有比要插入的数小的数据后移,这样大的数就在队列的头部了 int i = 0; if(nItems == 0) { a[0] = l; } else { for(i=nItems-1; i>=0; i--) { if(l < a[i]) a[i+1] = a[i]; else break; } a[i+1] = l; } nItems++; } public long remove() { //移出的是数组最上端的数,这样减少数组元素的移动 return a[--nItems]; } public boolean isEmpty() { return (nItems == 0); } public boolean isFull() { return (nItems == maxSize); } public int size() { return nItems; } } public class duilie {// 队列体类 private duilie s; private String data; duilie(String data) { this.data = data; } public String getData() { return data; } public void setData(String data) { this.data = data; } public duilie getS() { return s; } public void setS(duilie s) { this.s = s; } } public class duiliecz {// 队列操作类 /** * @param args */ private int i = 0;// 队列长 private duilie top = new duilie("");// 队列头 private duilie end = new duilie("");// 队列尾 public void add(String s) {// 添加队列 duilie m = new duilie(s); if (i != 0) { m.setS(top.getS()); top.setS(m); } else { top.setS(m); end.setS(m); } i++; } 4. 队列  public void del() {// 删除队尾 if (i == 0) { return; } else if (i == 1) { top.setS(null); end.setS(null); } else { duilie top1 = new duilie("");// 队列底查找用缓存 top1.setS(top.getS()); while (!top1.getS().getS().equals(end.getS())) { top1.setS(top1.getS().getS()); } end.setS(top1.getS()); } i--; } public static void main(String[] args) { // TODO Auto-generated method stub duiliecz m = new duiliecz(); m.add("1"); m.add("2"); m.add("3"); m.add("4"); for (int n = 0; n < 4; n++) { m.del(); } } public int getI() { return i; } public duilie getEnd() { return end; } public duilie getTop() { return top; } } 5. 栈 public class Stack { int[] arr; int len = 0; public Stack() { arr = new int[100]; } public Stack(int n) { arr = new int[n]; } public int size() { return len + 1; } // 扩大数组 public void resize() { int[] b = new int[arr.length * 2]; System.arraycopy(arr, 0, b, 0, arr.length); arr = b; } public void show() { for (int i = 0; i < len; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // 进栈 public void push(int a) { if (len >= arr.length) resize(); arr[len] = a; len++; } // 出栈 public int pop() { if (len == 0) { System.out.println(); System.out.println("stack is empty!"); return -1; } int a = arr[len - 1]; arr[len - 1] = 0; len--; return a; } } 6. 链表 class Node { Object data; Node next; public Node(Object data) { setData(data); } public void setData(Object data) { this.data = data; } public Object getData() { return data; } } class Link { Node head; int size = 0; public void add(Object data) { Node n = new Node(data); if (head == null) { head = n; } else { Node current = head; while (true) { if (current.next == null) { break; } current = current.next; } current.next = n; } size++; } public void show() { Node current = head; if (current != null) { while (true) { System.out.println(current); if (current == null) { break; } current = current.next; } } else { System.out.println("link is empty"); } } public Object get(int index) { // .... } public int size() { return size; } } 7. 单链表 class Node // 节点类,单链表上的节点 { String data; // 数据域,存放String类的数据 Node next; // 指向下一个节点 Node(String data) { this.data = data; // 构造函数 } String get() { return data; // 返回数据 } } class MyLinkList // 链表类 { Node first; // 头节点 int size; // 链表长度 MyLinkList(String arg[]) { // Node first = new Node("head");//生成头节点 first = new Node("head"); // J.F. 这里不需要定义局部变量 first // 如果定义了局部变量,那成员变量 first 就一直没有用上 // 所以,它一直为空 size = 0; Node p = first; for (int i = 0; i < arg.length; i++) // 将arg数组中的元素分别放入链表中 { Node q = new Node(arg[i]); q.next = p.next; // 每一个节点存放一个arg数组中的元素 p.next = q; p = p.next; size++; } } MyLinkList() // 无参数构造函数 { // Node first = new Node("head"); first = new Node("head"); // J.F. 这里犯了和上一个构造方法同样的错误 size = 0; } int size() // 返回链表长度 { return size; } void insert(Node a, int index) // 将节点a 插入链表中的第index个位置 { Node temp = first; for (int i = 0; i < index; i++) { temp = temp.next;// 找到插入节点的前一节点 } a.next = temp.next; // 插入节点 temp.next = a; size++; } Node del(int index) // 删除第index个节点,并返回该值 { Node temp = first; for (int i = 0; i < index; i++) { temp = temp.next;// 找到被删除节点的前一节点 } Node node = temp.next; temp.next = node.next; size--; // 删除该节点,链表长度减一 return node; } void print() // 在屏幕上输出该链表(这段程序总是出错,不知道错在哪里) { Node temp = first; for (int i = 1; i < size; i++) // 将各个节点分别在屏幕上输出 { temp = temp.next; System.out.print(temp.get() + "->"); } } void reverse() // 倒置该链表 { for (int i = 0; i < size; i++) { insert(del(size - 1), 0); // 将最后一个节点插入到最前 // J.F. 最后一个节点的 index 应该是 size - 1 // 因为第一个节点的 index 是 0 } } String get(int index) // 查找第index个节点,返回其值 { if (index >= size) { return null; } Node temp = first; for (int i = 0; i < index; i++) { temp = temp.next;// 找到被查找节点的前一节点 } return temp.next.get(); } } class MyStack // 堆栈类,用单链表实现 { MyLinkList tmp; Node temp; MyStack() { // MyLinkList tmp = new MyLinkList(); tmp = new MyLinkList(); // J.F. 和 MyLinkList 构造方法同样的错误 } void push(String a) // 压栈,即往链表首部插入一个节点 { Node temp = new Node(a); tmp.insert(temp, 0); } String pop() // 出栈,将链表第一个节点删除 { Node a = tmp.del(0); return a.get(); } int size() { return tmp.size(); } boolean empty() // 判断堆栈是否为空 { if (tmp.size() == 0) return false; else return true; } } public class MyLinkListTest // 测试程序部分 { public static void main(String arg[]) // 程序入口 { if ((arg.length == 0) || (arg.length > 10)) System.out.println("长度超过限制或者缺少参数"); else { MyLinkList ll = new MyLinkList(arg); // 创建一个链表 ll.print(); // 先输出该链表(运行到这一步抛出异常) ll.reverse(); // 倒置该链表 ll.print(); // 再输出倒置后的链表 String data[] = new String[10]; int i; for (i = 0; i < ll.size(); i++) { data[i] = ll.get(i); // 将链表中的数据放入数组 } // sort(data);// 按升序排列data中的数据(有没有现成的排序函数?) for (i = 0; i < ll.size(); i++) { System.out.print(data[i] + ";"); // 输出数组中元素 } System.out.println(); MyStack s = new MyStack(); // 创建堆栈实例s for (i = 0; i < ll.size(); i++) { s.push(data[i]); // 将数组元素压栈 } while (!s.empty()) { System.out.print(s.pop() + ";"); // 再将堆栈里的元素弹出 } } } } 8. 双端链表 class Link { public int iData = 0; public Link next = null; public Link(int iData) { this.iData = iData; } public void display() { System.out.print(iData + " "); } } class FirstLastList { private Link first = null; private Link last = null; public FirstLastList() { first = null; last = null; } public void insertFirst(int key) { Link newLink = new Link(key); if (this.isEmpty()) last = newLink; newLink.next = first; first = newLink; } public void insertLast(int key) { Link newLink = new Link(key); if (this.isEmpty()) first = newLink; else last.next = newLink; last = newLink; } public Link deleteFirst() { Link temp = first; if (first.next == null) last = null; first = first.next; return temp; } public boolean isEmpty() { return (first == null); } public void displayList() { System.out.print("List (first-->last): "); Link current = first; while (current != null) { current.display(); current = current.next; } System.out.println(""); } } class FirstLastListApp { public static void main(String[] args) { // TODO Auto-generated method stub FirstLastList theList = new FirstLastList(); theList.insertFirst(22); // insert at front theList.insertFirst(44); theList.insertFirst(66); theList.insertLast(11); // insert at rear theList.insertLast(33); theList.insertLast(55); theList.displayList(); // display the list theList.deleteFirst(); // delete first two items theList.deleteFirst(); theList.displayList(); // display again } } 9. 有序链表 package arithmetic; class Link { public int iData = 0; public Link next = null; public Link(int iData) { this.iData = iData; } public void display() { System.out.print(iData + " "); } } class SortedList { private Link first = null; public SortedList() { first = null; } public void insert(int key) { Link newLink = new Link(key); Link previous = null; Link current = first; // while的第一个条件是没有到达链表的尾端,第二个是按顺序找到一个合适的位置 while (current != null && key > current.iData) { previous = current; current = current.next; } // 如果是空表或者要插入的元素最小,则在表头插入key if (current == first) first = newLink; else previous.next = newLink; newLink.next = current; } /** * 删除表头的节点 * * @return 要删除的节点 */ public Link remove() { Link temp = first; first = first.next; return temp; } public boolean isEmpty() { return (first == null); } public void displayList() { System.out.print("List (first-->last): "); Link current = first; // start at beginning of list while (current != null) // until end of list, { current.display(); // print data current = current.next; // move to next link } System.out.println(""); } } class SortedListApp { public static void main(String[] args) { // create new list SortedList theSortedList = new SortedList(); theSortedList.insert(20); // insert 2 items theSortedList.insert(40); theSortedList.displayList(); // display list theSortedList.insert(10); // insert 3 more items theSortedList.insert(30); theSortedList.insert(50); theSortedList.displayList(); // display list theSortedList.remove(); // remove an item theSortedList.displayList(); // display list } } 10. 双向链表 class Link { // 双向链表,有两个指针,一个向前,一个向后 public int iData = 0; public Link previous = null; public Link next = null; public Link(int iData) { this.iData = iData; } public void display() { System.out.print(iData + " "); } } class DoublyLinked { // 分别指向链表的表头和表尾 private Link first = null; private Link last = null; public boolean isEmpty() { return first == null; } /** * 在表头插入数据 * * @param 要插入的节点的数据 */ public void insertFirst(int key) { Link newLink = new Link(key); // 如果开始链表为空,则插入第一个数据后,last也指向第一个数据 if (this.isEmpty()) last = newLink; else {// 表不为空的情况 first.previous = newLink; newLink.next = first; } // 无论怎样,插入后都的让first重新指向第一个节点 first = newLink; } public void insertLast(int key) {// 在尾端插入数据,同上 Link newLink = new Link(key); if (this.isEmpty()) first = newLink; else { last.next = newLink; newLink.previous = last; } last = newLink; } /** * 在指定的节点后插入数据 * * @param key * 指定的节点的值 * @param iData * 要插入的数据 * @return 是否插入成功 */ public boolean insertAfter(int key, int iData) { Link newLink = new Link(key); Link current = first; // 从first开始遍历,看能否找到以key为关键字的节点 while (current.iData != key) { current = current.next; // 若能找到就跳出循环,否则返回false,插入失败 if (current == null) return false; } // 如果插入点在last的位置 if (current == last) { last = newLink; } else {// 非last位置,交换各个next和previous的指针 newLink.next = current.next; current.next.previous = newLink; } current.next = newLink; newLink.previous = current; return true; } /** * 删除表头的节点 * * @return */ public Link deleteFirst() { Link temp = first; // 如果表中只有一个元素,删除后则为空表,所以last=null if (first.next == null) last = null; else // 否则,让第二个元素的previous=null first.next.previous = null; // 删除头指针,则first指向原来的second first = first.next; return temp; } public Link deleteLast() {// 同上 Link temp = last; if (last.previous == null) first = null; else last.previous.next = null; last = last.previous; return temp; } public Link deleteKey(int key) { Link current = first; // 遍历整个链表查找对应的key,如果查到跳出循环,否则... while (current.iData != key) { current = current.next; // ...否则遍历到表尾,说明不存在此key,返回null,删除失败 if (current == null) return null; } if (current == first) first = first.next; else current.previous.next = current.next; if (current == last) last = last.previous; else current.next.previous = current.previous; return current; } public void displayForward() { Link current = first; while (current != null) { current.display(); current = current.next; } System.out.println(); } public void displayBackward() { Link current = last; while (current != null) { current.display(); current = current.previous; } System.out.println(); } } class DoublyLinkedApp { public static void main(String[] args) { // make a new list DoublyLinked theList = new DoublyLinked(); theList.insertFirst(22); // insert at front theList.insertFirst(44); theList.insertFirst(66); theList.insertLast(11); // insert at rear theList.insertLast(33); theList.insertLast(55); theList.displayForward(); // display list forward theList.displayBackward(); // display list backward theList.deleteFirst(); // delete first item theList.deleteLast(); // delete last item theList.deleteKey(11); // delete item with key 11 theList.displayForward(); // display list forward theList.insertAfter(22, 77); // insert 77 after 22 theList.insertAfter(33, 88); // insert 88 after 33 theList.displayForward(); // display list forward } } 11. 实现二叉树前序遍历迭代器 class TreeNode 这个类用来声明树的结点,其中有左子树、右子树和自身的内容。   class MyTree 这个类用来声明一棵树,传入根结点。这里设计的比较简单   class TreeEum 这个类是树的迭代器,通过MyTree类的方法获取,这里主要就是设计它了。代码如下:   //TreeNode类,使用了泛型,由于比较简单,考试.大提示不作解释   class TreeNode   {   E node;   private TreeNode left;   private TreeNode right;   public TreeNode(E e)   {   this(e,null,null);   }   public TreeNode(E e,TreeNode left,TreeNode right)   {   this.node=e;   this.left=left;   this.right=right;   }   public TreeNode left()   {   return left;   }   public TreeNode right()   {   return right;   }   }   // MyTree类,没什么功能,传入根结点构造,getEnumerator()方法获取迭代器。   class MyTree   {   TreeNode root;   public MyTree(TreeNode root)   {   this.root=root;   }   public TreeEnum getEnumerator()   {   return new TreeEnum(root);   }   }   // 这个类为迭代器,有详细解释,相信各位能看懂。在栈中用了两次泛型。   import java.util.Stack;   public class TreeEnum   {   private TreeNode root;   private Stack> store;/* 保存遍历左子树但未遍历右子树的结点 */   private TreeNode next;   public TreeEnum(TreeNode root)   {   this.root=root;   store=new Stack>();   next=root;   }   public TreeNode next()   {   TreeNode current=next;   if(next!=null)   {   /* 如果当前结点的左子树不为空,则遍历左子树,并标记当前结点未遍历右子树 */   if(next.left()!=null)   {   store.push(next);   next=next.left();   }   // 如果当前结点的左子树为空,则遍历右子树   else if(next.right()!=null)   {   next=next.right();   }   /* 如果当前结点为叶子,则找未遍历右子树的结点并且遍历它的右子树 */   else{   if(!store.empty())/* 判断是否还有结点的右子树未遍历 */   {   TreeNode tmp=store.pop();   /* 如果有未遍历右子树的结点,但它的右子树为空,且还有结点的右子树未遍历, */   /* 则一直往上取,直到取到未遍历右子树且右子树不为空的结点,遍历它的右子树. */   while((tmp.right()==null)&&!store.empty())   {   tmp=store.pop();   }   next=tmp.right();   }   else   {   /* 如果没有哪个结点右子树未遍历,则表示没有下一个结点了,设置next为null */   next=null;   }   }   }   return current;   }   public boolean hasMoreElement()   {   return next!=null;   }   }   下面写个测试类,不作解释,相信大家看得懂   public class TreeReader{   public static void main(String[] args)   {   TreeNode n1=new TreeNode("n1");   TreeNode n2=new TreeNode("n2");   TreeNode n3=new TreeNode("n3");   TreeNode n4=new TreeNode("n4");   TreeNode n5=new TreeNode("n5");   TreeNode n6=new TreeNode("n6",null,n1);   TreeNode n7=new TreeNode("n7",n2,null);   TreeNode n8=new TreeNode("n8",n7,null);   TreeNode n9=new TreeNode("n9",null,n5);   TreeNode n10=new TreeNode("n10",n4,n9);   TreeNode n11=new TreeNode("n11",n6,n8);   TreeNode n12=new TreeNode("n12",n3,n10);   TreeNode root=new TreeNode("root",n11,n12);   MyTree tree=new MyTree(root);   TreeEnum eum=tree.getEnumerator();   while(eum.hasMoreElement())   {   System.out.print(eum.next().node+"--");   }   System.out.println("end");   }   } 12. 迭代器 package TreeIterator; public interface Iterator { public boolean hasNext(); public Object next(); } 这个接口我们有2个方法,hasNext()是否还有下一条数据,next返回具体的Object 这里也就是树。 我们先不必要忙着做他的实现类,我们现在要来做的是这个容器(不是JAVA中容器,与arraylist什么的无关),正所谓树的容器是什么,是山也! 我们想想山应该具有什么呢!? 首先它要有种植树的功能,这里可以看作添加树。我们可以想像山的功能是和树相互关联的,那么他们之间是什么关系呢,我们给他们一 种聚合的关系,聚合的关系大家可以参考UML图,我在这里给出它的一种程序表现形式。 package TreeIterator; public class Hall { Tree[] tree ; // 这里可以看作是聚合关系 private int index; // 指向Tree[]的标签 public Hall(int maxNumber) { tree = new Tree[maxNumber]; index = 0; } public void add(Tree tree) { this.tree[index]=tree; index++; } public Iterator connectIterator() { return new TreeIterator(this); } } 这里我们定义的山可以抽象出Hall类来,Tree[] tree 可以看作是山和树之间的一种聚合关系。add方法就是添加树。问题来了,山 和树有了关系,那么山和迭代器有什么关系呢。它们之间肯定有一种关系。我们有了这个容器(山),就要把这个容器来实现迭代的方法:hasNext()和Next().恩这里我们可以看 出,山和迭代器之间也是一种关联关系。我们就把它看成是一种聚合关系(TIP:聚合关系一种特殊的关联关系)。我们可以通过一个connectIterator方法来链接山和迭代器,接下来 我们要去做一个具体的迭代类,这个具体的类中间有了hasNext()和Next()的具体实现方法 package TreeIterator; public class TreeIterator implements Iterator{ private int last=0; private Hall hall; public TreeIterator(Hall hall) { this.hall=hall; } public boolean hasNext(){ if(last 0){ return num + RecursionNum(num - 1); } Else{ return 0; } } } 15. 归并排序 /** * 归并排序,要求待排序的数组必须实现Comparable接口 */ public class MergeSort implements SortStrategy { private Comparable[] bridge; /** * 利用归并排序算法对数组obj进行排序 */ public void sort(Comparable[] obj) { if (obj == null) { throw new NullPointerException("The param can not be null!"); } bridge = new Comparable[obj.length]; // 初始化中间数组 mergeSort(obj, 0, obj.length - 1); // 归并排序 bridge = null; } /** * 将下标从left到right的数组进行归并排序 * * @param obj * 要排序的数组的句柄 * @param left * 要排序的数组的第一个元素下标 * @param right * 要排序的数组的最后一个元素的下标 */ private void mergeSort(Comparable[] obj, int left, int right) { if (left < right) { int center = (left + right) / 2; mergeSort(obj, left, center); mergeSort(obj, center + 1, right); merge(obj, left, center, right); } } /** * 将两个对象数组进行归并,并使归并后为升序。归并前两个数组分别有序 * * @param obj * 对象数组的句柄 * @param left * 左数组的第一个元素的下标 * @param center * 左数组的最后一个元素的下标 * @param right * 右数组的最后一个元素的下标 */ private void merge(Comparable[] obj, int left, int center, int right) { int mid = center + 1; int third = left; int tmp = left; while (left <= center && mid <= right) { // 从两个数组中取出小的放入中间数组 if (obj[left].compareTo(obj[mid]) <= 0) { bridge[third++] = obj[left++]; } else bridge[third++] = obj[mid++]; } // 剩余部分依次置入中间数组 while (mid <= right) { bridge[third++] = obj[mid++]; } while (left <= center) { bridge[third++] = obj[left++]; } // 将中间数组的内容拷贝回原数组 copy(obj, tmp, right); } /** * 将中间数组bridge中的内容拷贝到原数组中 * * @param obj * 原数组的句柄 * @param left * 要拷贝的第一个元素的下标 * @param right * 要拷贝的最后一个元素的下标 */ private void copy(Comparable[] obj, int left, int right) { while (left <= right) { obj[left] = bridge[left]; left++; } } } 16. 希尔排序 间隔序列:h = 3 * h + 1,h=(h-1)/3 public class ShellSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub ShellSort ss = new ShellSort(); int num[] = { 546, 87, 21, 3124, 65, 2, 9, 3, 213, 54, 98, 23, 6, 4, 7, 8, 123, 872, 61, 5, 8954}; ss.shellArray(num); for (int i = 0; i < num.length; i++) { System.out.println(num[i]); } } public void shellArray(int[] num) { int i = 1; int tem, in; for (; i < num.length / 3;) { i = 3 * i + 1; } for (; i >= 1;) { for (int j = i; j < num.length; j++) { tem = num[j]; in = j; while (in > i - 1 && num[in - i] >= tem) { num[in] = num[in - i]; in = in - i; } num[in] = tem; } i = (i - 1) / 3; } } } 17. 快速排序 class QuickSort { private int[] data; QuickSort(int[] data) { this.data = data; } public void quickSort() { recQuickSort(data, 0, data.length - 1); } private void recQuickSort(int[] data, int low, int high) { // 设置两个滑标 int lowCursor = low + 1; int highCursor = high; // 交换时的临时变量 int temp = 0; // 比较枢值,设为数组的第一个值 int medi = data[low]; while (true) { // 从低端开始查找,确定大于数 data[low] 所在的位置 while (lowCursor < high && data[lowCursor] < medi) { lowCursor++; } // 从高端开始查找,确定小于数 data[low] 所在的位置。这里要使用 >= 判断确定小于值 while (highCursor > low && data[highCursor] >= medi) { highCursor--; } // 两游标位置出现越界,退出循环 if (lowCursor >= highCursor) { break; } // 交换 data[highCursor] 和 data[lowCursor] 位置数据 temp = data[highCursor]; data[highCursor] = data[lowCursor]; data[lowCursor] = temp; } // 由 while 循环退出条件可知:lowCursor > highCursor // 当前 lowCursor 指向右侧大于 data[low]的第一个位置; // 而 highCursor 指向左侧小于 data[low]的第一个位置,所以需要交换 data[low] 和 // data[highCursor]的值 data[low] = data[highCursor]; data[highCursor] = medi; // 递归运算左半部分 if (low < highCursor) { recQuickSort(data, low, highCursor); } // 递归运算右半部分 if (lowCursor < high) { recQuickSort(data, lowCursor, high); } } public void display() { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] data = new int[] { 43, 12, 32, 55, 33, 67, 54, 65, 43, 22, 66, 98, 74 }; QuickSort sort = new QuickSort(data); sort.display(); sort.quickSort(); sort.display(); } } 18. 二叉树 //******************************************************************************************************// //*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******// //******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********// //******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**// //*******************************CopyRight By phoenix*******************************************// //************************************Jan 12,2008*************************************************// //****************************************************************************************************// public class BinTree { public final static int MAX = 40; BinTree[] elements = new BinTree[MAX];// 层次遍历时保存各个节点 int front;// 层次遍历时队首 int rear;// 层次遍历时队尾 private Object data; // 数据元数 private BinTree left, right; // 指向左,右孩子结点的链 public BinTree() { } public BinTree(Object data) { // 构造有值结点 this.data = data; left = right = null; } public BinTree(Object data, BinTree left, BinTree right) { // 构造有值结点 this.data = data; this.left = left; this.right = right; } public String toString() { return data.toString(); } // 前序遍历二叉树 public static void preOrder(BinTree parent) { if (parent == null) return; System.out.print(parent.data + " "); preOrder(parent.left); preOrder(parent.right); } // 中序遍历二叉树 public void inOrder(BinTree parent) { if (parent == null) return; inOrder(parent.left); System.out.print(parent.data + " "); inOrder(parent.right); } // 后序遍历二叉树 public void postOrder(BinTree parent) { if (parent == null) return; postOrder(parent.left); postOrder(parent.right); System.out.print(parent.data + " "); } // 层次遍历二叉树 public void LayerOrder(BinTree parent) { elements[0] = parent; front = 0; rear = 1; while (front < rear) { try { if (elements[front].data != null) { System.out.print(elements[front].data + " "); if (elements[front].left != null) elements[rear++] = elements[front].left; if (elements[front].right != null) elements[rear++] = elements[front].right; front++; } } catch (Exception e) { break; } } } // 返回树的叶节点个数 public int leaves() { if (this == null) return 0; if (left == null && right == null) return 1; return (left == null ? 0 : left.leaves()) + (right == null ? 0 : right.leaves()); } // 结果返回树的高度 public int height() { int heightOfTree; if (this == null) return -1; int leftHeight = (left == null ? 0 : left.height()); int rightHeight = (right == null ? 0 : right.height()); heightOfTree = leftHeight < rightHeight ? rightHeight : leftHeight; return 1 + heightOfTree; } // 如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层 public int level(Object object) { int levelInTree; if (this == null) return -1; if (object == data) return 1;// 规定根节点为第一层 int leftLevel = (left == null ? -1 : left.level(object)); int rightLevel = (right == null ? -1 : right.level(object)); if (leftLevel < 0 && rightLevel < 0) return -1; levelInTree = leftLevel < rightLevel ? rightLevel : leftLevel; return 1 + levelInTree; } // 将树中的每个节点的孩子对换位置 public void reflect() { if (this == null) return; if (left != null) left.reflect(); if (right != null) right.reflect(); BinTree temp = left; left = right; right = temp; } // 将树中的所有节点移走,并输出移走的节点 public void defoliate() { if (this == null) return; // 若本节点是叶节点,则将其移走 if (left == null && right == null) { System.out.print(this + " "); data = null; return; } // 移走左子树若其存在 if (left != null) { left.defoliate(); left = null; } // 移走本节点,放在中间表示中跟移走... // innerNode += this + " "; data = null; // 移走右子树若其存在 if (right != null) { right.defoliate(); right = null; } } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub BinTree e = new BinTree("E"); BinTree g = new BinTree("G"); BinTree h = new BinTree("H"); BinTree i = new BinTree("I"); BinTree d = new BinTree("D", null, g); BinTree f = new BinTree("F", h, i); BinTree b = new BinTree("B", d, e); BinTree c = new BinTree("C", f, null); BinTree tree = new BinTree("A", b, c); System.out.println("前序遍历二叉树结果: "); tree.preOrder(tree); System.out.println(); System.out.println("中序遍历二叉树结果: "); tree.inOrder(tree); System.out.println(); System.out.println("后序遍历二叉树结果: "); tree.postOrder(tree); System.out.println(); System.out.println("层次遍历二叉树结果: "); tree.LayerOrder(tree); System.out.println(); System.out.println("F所在的层次: " + tree.level("F")); System.out.println("这棵二叉树的高度: " + tree.height()); System.out.println("--------------------------------------"); tree.reflect(); System.out.println("交换每个节点的孩子节点后......"); System.out.println("前序遍历二叉树结果: "); tree.preOrder(tree); System.out.println(); System.out.println("中序遍历二叉树结果: "); tree.inOrder(tree); System.out.println(); System.out.println("后序遍历二叉树结果: "); tree.postOrder(tree); System.out.println(); System.out.println("层次遍历二叉树结果: "); tree.LayerOrder(tree); System.out.println(); System.out.println("F所在的层次: " + tree.level("F")); System.out.println("这棵二叉树的高度: " + tree.height()); } }

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 5 人已下载

下载文档