Java数据结构与经典算法——高手必会.doc

大O表示法：粗略的量度方法即算法的速度是如何与数据项的个数相关的2排序2优先级队列6队列8栈9链表10单链表12双端链表16有序链表18双向链表20实现二叉树前序遍历迭代器24迭代器27合并搜索算法30希尔排序34快速排序35二叉树37经典算法的Java实现42（1）河内塔问题：42（2）费式数列44（3）巴斯卡（Pascal）三角形44（4）蒙地卡罗法求 PI46（5）最大公因数、最小公倍数47（6）阿姆斯壮数48（7）最大访客数48（8）洗扑克牌（乱数排列）50（9）约瑟夫问题（Josephus Problem）51（10）排列组合53（11）得分排行54（12）选择、插入、气泡排序56（13）快速排序（一）59（14）快速排序（二）61（15）快速排序（三）62（16）合并排序63（17）基数排序64（18）循序查找法（使用卫兵）66（20）插补查找法68（21）费式查找法69（22）稀疏矩阵72（23）多维矩阵转一维矩阵73（24）上三角、下三角、对称矩阵74（25）奇数魔方阵76（26）4N魔方阵77（27）2(2n+1)魔方阵79大O表示法：粗略的量度方法即算法的速度是如何与数据项的个数相关的算法 大O表示法表示的运行时间线性查找 O(N)二分查找 O(logN)无序数组的插入 O(1)有序数组的插入 O(N)无序数组的删除 O(N)有序数组的删除 O(N)O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到)排序public class JWzw /插入排序public void insertArray(Integer in)int tem = 0;int num = 0;int upnum = 0;for (int i = 0; i = 0; j-) num+;if (inj+1 inj) tem = inj+1;inj+1 = inj;inj = tem;upnum+;elsebreak;for (int i = 0; i in.length; i+) System.out.print(ini);if(i in.length - 1)System.out.print(,);System.out.println();System.out.println(插入排序循环次数: + num);System.out.println(移动次数： + upnum);System.out.print(nnn);/选择排序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(inj+1 inj)tem = inj+1;inj + 1 = inj;inj = tem;upnum+;for (int i = 0; i in.length; i+) System.out.print(ini);if(i in.length - 1)System.out.print(,);System.out.println();System.out.println(选择排序循环次数: + num);System.out.println(移动次数： + upnum);System.out.print(nnn);/冒泡排序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(inj+1 ini)tem = inj+1;inj+1 = ini;ini = tem;upnum+;for (int i = 0; i in.length; i+) System.out.print(ini);if(i in.length - 1)System.out.print(,);System.out.println();System.out.println(冒泡排序循环次数: + num);System.out.println(移动次数： + upnum);System.out.print(nnn);/打印乘法口诀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(tn);System.out.print(nnn);/打印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 2);优先级队列class PriorityQueue private long a = null;private int nItems = 0;private int maxSize = 0;public PriorityQueue(int maxSize) a = new longmaxSize; this.maxSize = maxSize; nItems = 0;public void insert(long l) /优先级队列的插入不是队尾,而是选择一个合适的按照某种顺序插入的 /当队列长度为0时，如下 /不为0时,将所有比要插入的数小的数据后移,这样大的数就在队列的头部了 int i = 0; if(nItems = 0) a0 = l; else for(i=nItems-1; i=0; i-) if(l ai) ai+1 = ai; else break; ai+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+; 队列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; 栈public class Stack int arr;int len = 0;public Stack() arr = new int100;public Stack(int n) arr = new intn;public int size() return len + 1;/ 扩大数组public void resize() int b = new intarr.length * 2;System.arraycopy(arr, 0, b, 0, arr.length);arr = b;public void show() for (int i = 0; i = arr.length)resize();arrlen = a;len+;/ 出栈public int pop() if (len = 0) System.out.println();System.out.println(stack is empty!);return -1;int a = arrlen - 1;arrlen - 1 = 0;len-;return a;链表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;单链表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(argi);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 );void reverse() / 倒置该链表for (int i = 0; i = size) return null;Node temp = first;for (int i = 0; i 10)System.out.println(长度超过限制或者缺少参数);else MyLinkList ll = new MyLinkList(arg); / 创建一个链表ll.print(); / 先输出该链表（运行到这一步抛出异常）ll.reverse(); / 倒置该链表ll.print(); / 再输出倒置后的链表String data = new String10;int i;for (i = 0; i ll.size(); i+) datai = ll.get(i); / 将链表中的数据放入数组/ sort(data);/ 按升序排列data中的数据（有没有现成的排序函数？）for (i = 0; i ll.size(); i+) System.out.print(datai + ;); / 输出数组中元素System.out.println();MyStack s = new MyStack(); / 创建堆栈实例sfor (i = 0; i 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 stubFirstLastList theList = new FirstLastList();theList.insertFirst(22); / insert at fronttheList.insertFirst(44);theList.insertFirst(66);theList.insertLast(11); / insert at reartheList.insertLast(33);theList.insertLast(55);theList.displayList(); / display the listtheList.deleteFirst(); / delete first two itemstheList.deleteFirst();theList.displayList(); / display again有序链表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;/ 如果是空表或者要插入的元素最小,则在表头插入keyif (current = first)first = newLink;elseprevious.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 listwhile (current != null) / until end of list,current.display(); / print datacurrent = current.next; / move to next linkSystem.out.println();class SortedListApp public static void main(String args) / create new listSortedList theSortedList = new SortedList();theSortedList.insert(20); / insert 2 itemstheSortedList.insert(40);theSortedList.displayList(); / display listtheSortedList.insert(10); / insert 3 more itemstheSortedList.insert(30);theSortedList.insert(50);theSortedList.displayList(); / display listtheSortedList.remove(); / remove an itemtheSortedList.displayList(); / display list双向链表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=nullif (first.next = null)last = null;else/ 否则,让第二个元素的previous=nullfirst.next.previous = null;/ 删除头指针,则first指向原来的secondfirst = first.next;return temp;public Link deleteLast() / 同上Link temp = last;if (last.previous = null)first = null;elselast.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;elsecurrent.previous.next = current.next;if (current = last)last = last.previous;elsecurrent.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 listDoublyLinked theList = new DoublyLinked();theList.insertFirst(22); / insert at fronttheList.insertFirst(44);theList.insertFirst(66);theList.insertLast(11); / insert at reartheList.insertLast(33);theList.insertLast(55);theList.di