Java数据结构和算法笔记

Java数据结构和算法第0讲 综述参考教材：Java数据结构和算法（第二版），美 Robert lafore1. 数据结构的特性数据结构优点缺点数组插入快；如果知道下标，可以非常快地存取查找慢，删除慢，大小固定有序数组比无序的数组查找快删除和插入慢，大小固定栈提供后进先出方式的存取存取其他项很慢队列提供先进先出方式的存取存取其他项很慢链表插入快，删除快查找慢二叉树查找、插入、删除都快（如果树保持平衡）删除算法复杂红-黑树查找、插入、删除都快；树总是平衡的算法复杂2-3-4树查找、插入、删除都快；树总是平衡的；类似的树对磁盘存储有用算法复杂哈希表如果关键字已知，则存储极快；插入快删除慢，如果不知道关键字则存储很慢，对存储空间使用不充分堆插入、删除快；对大数据项的存取很快对其他数据项存取慢图对现实世界建模有些算法慢且复杂2. 经典算法总结查找算法：线性查找和二分查找排序算法：用表展示第一讲 数组1. Java中数组的基础知识1） 创建数组在Java中把数组当作对象来对待，因此在创建数组时必须使用new操作符：int intArr = new int10;一旦创建数组，数组大小便不可改变。2） 访问数组数据项数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0： intArr0 = 123;3） 数组的初始化当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的null对象。 int intArr = 1, 2, 3, 4, 5;等效于下面使用new来创建数组并初始化：int intArr = new int5;intArr0 = 1;intArr1 = 2;intArr2 = 3;intArr3 = 4;intArr4 = 5;2. 面向对象编程方式1） 使用自定义的类封装数组MyArray类：public class MyArray private long arr;private int size;/记录数组的有效长度public MyArray() arr = new long10;public MyArray(int maxSize) arr = new longmaxSize;/向数组中插入数据public void insert(long element) arrsize = element;size+;/显示数组中的数据public void show() for(int i=0; isize; i+) if(i=0) System.out.print( + arri + , ); else if(i=size-1) System.out.println(arri + ); else System.out.print(arri + , );/根据值查找索引（出现该值的第一个位置）：线性查找public int queryByValue(long element) int i;for(i=0; i= size | index = size | index 0) throw new ArrayIndexOutOfBoundsException(); else /当size=maxSize，删除最后一个数时，不会执行forfor(int i=index; i= size | index 0) throw new ArrayIndexOutOfBoundsException(); else arrindex = value;2） 添加类方法实现数据操作测试MyArray类方法：public void testMyArray() throws Exception MyArray myArray = new MyArray();myArray.insert(123);myArray.insert(456);myArray.insert(789);myArray.show();/123, 456, 789System.out.println(myArray.queryByValue(111);/-1System.out.println(myArray.queryByIndex(2);/789myArray.delete(2);myArray.show();/123, 456myArray.update(0, 0);myArray.show();/0, 4563. 有序数组1） 有序数组简介以及其优点有序数组是一种数组元素按一定的顺序排列的数组，从而方便使用二分查找来查找数组中特定的元素。有序数组提高了查询的效率，但并没有提高删除和插入元素的效率。2） 构建有序数组将2.1中自定义的类封装数组MyArray的insert方法改为如下：/向有序数组中插入数据，按大小从前往后排列public void insert(long element) int i;for(i=0; isize; i+) / find where it goesif(elementi; j-) / move bigger ones uparrj = arrj-1;arri = element;size+;得到有序数组的类封装MyOrderedArray类，测试该类中的insert方法： public void testMyOrderedArray() throws Exception MyOrderedArray myOrderedArray = new MyOrderedArray();myOrderedArray.insert(999);myOrderedArray.insert(555);myOrderedArray.insert(777);myOrderedArray.show();/555, 777, 9994. 查找算法1） 线性查找在查找过程中，将要查找的数一个一个地与数组中的数据项比较，直到找到要找的数。在2.1中自定义的类封装数组MyArray的queryByValue方法，使用的就是线性查找。2） 二分查找二分查找（又称折半查找），即不断将有序数组进行对半分割，每次拿中间位置的数和要查找的数进行比较：如果要查找的数中间数，则表明该数在数组的后半段；如果要查的数=中间数，则返回中间数。在有序数组的类封装类MyOrderedArray中添加binarySearch方法 /根据值二分查找索引（前提：有序）public int binarySearch(long value) int middle = 0;int left = 0;int right = size - 1;while(true) middle = (left + right) / 2;if(arrmiddle = value) return middle;/ found it else if(left right) return -1;/ cant found it else / divide rangeif(arrmiddle value) right = middle - 1;/in lower half else left = middle + 1;/ in upper half测试该二分查找方法： public void testMyOrderedArray() throws Exception MyOrderedArray myOrderedArray = new MyOrderedArray();myOrderedArray.insert(999);myOrderedArray.insert(555);myOrderedArray.insert(777);myOrderedArray.insert(333);System.out.println(myOrderedArray.binarySearch(333);/0第二讲 简单排序本讲提到的排序算法都假定了数组作为数据存储结构，本讲所有算法的时间复杂度都是。在大多数情况下，假设当数据量比较小或基本上有序时，插入排序算法是三种简单排序算法中最好的选择，是应用最多的。对于更大数据量的排序来说，后面讲到的快速排序通常是最快的方法。1. 冒泡排序1） 基本思想在要排序的一组数中，对当前还未排好序的范围内的全部数，自下而上对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。2） 算法实现冒泡排序的Java代码：/ bubble sortpublic static void bubbleSort(long arr) long temp;for(int i=0; ii; j-) /inner loop (backward)if(arrj arrj-1) / swap themtemp = arrj;arrj = arrj-1;arrj-1 = temp;测试冒泡排序及输出结果： public void testBubbleSort() throws Exception long arr = 79, 91, 13, 52, 34;Sort.bubbleSort(arr);System.out.println(Arrays.toString(arr);/13, 34, 52, 79, 912. 选择排序1） 基本思想在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。与冒泡排序相比，选择排序将必要的交换次数从O(N*N)减少到O(N)，但比较次数仍然保持为O(N*N)。2） 算法实现选择排序的Java代码：/ select sortpublic static void selectSort(long arr) long temp;for(int i=0; iarr.length-1; i+) /outer loopint k = i; / location of minimumfor(int j=i+1; jarr.length; j+) /inner loopif(arrj =2个数已经是排好顺序的（局部有序），现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。在插入排序中，一组数据仅仅是局部有序的；而冒泡排序和选择排序，一组数据项在某个时刻是完全有序的。2） 算法实现插入排序的Java代码：/ insert sortpublic static void insertSort(long arr) long temp;for(int i=1; i=1 & arrj-1temp) / until one is smallerarrj = arrj-1; / shift item rightj-; / go left one positionarrj = temp; / insert marked item测试插入排序以及输出结果：public void testInsertSort() throws Exception long arr = 79, 91, 13, 52, 34, 34;Sort.insertSort(arr);System.out.println(Arrays.toString(arr); /13, 34, 34, 52, 79, 91第三讲 栈和队列栈和队列都是抽象数据类型（abstract data type，ADT），它们既可以用数组实现，又可以用链表实现。1. 栈1） 栈模型栈（Stack，又LIFO：后进先出）是一种只能在固定的一端进行插入和删除的数据结构。栈只允许访问一个数据项：即最后插入的数据项，移除这个数据项后才能访问倒数第二个插入的数据项，以此类推。栈可以用数组来实现，也可以用链表来实现。2） 栈的数组实现栈的Java代码：public class MyStack private long arr; /底层使用数组实现private int top;public MyStack() arr = new long10;top = -1;public MyStack(int maxSize) arr = new longmaxSize;top = -1;/ put item on top of stackpublic void push(long value) arr+top = value;/ take item from top of stackpublic long pop() return arrtop-;/ peek at top of stack public long peek() return arrtop;/ ture if stack is emptypublic boolean isEmpty() return (top = -1);/ ture if stack is fullpublic boolean isFull() return (top = arr.length-1);测试栈的特性：public void testMyStack() throws Exception MyStack myStack = new MyStack(4);myStack.push(12);myStack.push(34);myStack.push(56);myStack.push(78);System.out.println(myStack.isFull(); / truewhile(!myStack.isEmpty() System.out.print(myStack.pop(); /78, 56, 34, 12if(!myStack.isEmpty() System.out.print(, );System.out.println();System.out.println(myStack.isFull(); / false2. 队列1） 队列模型队列（Queue，又FIFO：先进先出）是一种插入时在一端进行而删除时在另一端进行的数据结构。为解决顺序队列假溢出问题，而采用循环队列：即让队头、队尾指针在达到尾端时，又绕回到开头。2） 队列的数组实现队列的Java代码：public class MyQueue private long arr;private int size;private int front;private int rear;public MyQueue() arr = new long10;size = 0;front = 0;rear = -1;public MyQueue(int maxSize) arr = new longmaxSize;size = 0;front = 0;rear = -1;/ put item at rear of queuepublic void insert(long value) if(isEmpty() / throw exception if queue is fullthrow new ArrayIndexOutOfBoundsException(); if(rear = arr.length-1) /deal with wraparound (环绕式处理)rear = -1;arr+rear = value; / increment rear and insertsize+; / increment size/ take item from front of queuepublic long remove() long value = arrfront+; / get value and increment frontif(front = arr.length) / deal with wraparoundfront = 0;size-; / one less itemreturn value;/ peek at front of queuepublic long peek() return arrfront;/ true if queue is emptypublic boolean isEmpty() return (size = 0);/ true if queue is fullpublic boolean isFull() return (size = arr.length);测试队列的特性：public void testMyQueue() throws Exception MyQueue myQueue = new MyQueue(4);myQueue.insert(12);myQueue.insert(34);myQueue.insert(56);myQueue.insert(78);System.out.println(myQueue.isFull(); / truewhile(!myQueue.isEmpty() System.out.print(myQueue.remove(); /12, 34, 56, 78if(!myQueue.isEmpty() System.out.print(, );System.out.println();System.out.println(myQueue.isEmpty(); / truemyQueue.insert(99);System.out.println(myQueue.peek(); / 99第四讲 链表1. 链结点一个链结点（Link，或称结点）是某个类的对象，该对象中包含对下一个链结点引用的字段（通常叫next）。而链表本身的对象中有一个字段指向对第一个链结点的引用。Link类的定义：public class Link public long data; / data itempublic Link next; / next link in listpublic Link(long data) this.data = data;public void displayLink() / display ourselfSystem.out.print(data + - );2. 单链表（LinkList）LinkList类显示了一个单链表，该链表可以进行的操作有：l 在链表头插入一个数据（insertFirst）：设置新添加的结点的next设为原来的头结点，再将新添加的结点设为头结点。l 在链表头删除一个数据（deleteFirst）：将第二个结点设为头结点。l 遍历链表显示所有数据（displayList）：使用临时指针current，从头结点开始，沿着链表先前移动，依次遍历每个节点。LinkList类：public class LinkList private Link first; / reference to first link on listpublic LinkList() this.first = null;/ insert at start of listpublic void insertFirst(long value) Link newLink = new Link(value);newLink.next = first; / newLink - old firstfirst = newLink; / first - newLink/ delete first itempublic Link deleteFirst() if(first = null) return null;Link temp = first; first = first.next; / delete it: first - old nextreturn temp; / return deleted linkpublic void displayList() Link current = first; / start at beginning of listwhile(current != null) / until end of listcurrent.displayLink();current = current.next; / move list to next linkSystem.out.println();测试LinkList类的方法：public void testLinkList() throws Exception LinkList linkList = new LinkList();linkList.insertFirst(88);linkList.insertFirst(66);linkList.insertFirst(44);linkList.insertFirst(22);linkList.displayList(); /22- 44- 66- 88-linkList.deleteFirst();linkList.displayList(); /44- 66- 88-3. 查找和删除指定链结点此外，还能对指定的结点值进行查找和删除：l 查找指定结点（find）：类似于之前的displayList方法。l 删除指定结点（delete）：在删除指定结点时，必须把前一个结点和后一个结点连接在一起，所以需要一个临时指针（previous）来保存对前一个结点的引用。向LinkList类中添加查找（find）和删除（delete）方法：/ find link with given keypublic Link find(long key) Link current = first; / start at firstwhile(current.data != key) if(current.next = null) / didnt find itreturn null; else / go to next linkcurrent = current.next;return current;/ delete link with given keypublic Link delete(long key) Link current = first; / search for expected linkLink previous = first;while(current.data != key) if(current.next = null) return null; / didnt find it else previous = current;current = current.next; / go to next link/ find itif(current = first) / if first link, change firstfirst = first.next; else / otherwise, bypass itprevious.next = current.next;return current;测试添加的find和delete方法：public void testLinkList() throws Exception LinkList linkList = new LinkList();linkList.insertFirst(88);linkList.insertFirst(66);linkList.insertFirst(44);linkList.insertFirst(22);linkList.displayList(); /22- 44- 66- 88-linkList.find(44).displayLink(); / 44-System.out.println();linkList.delete(44).displayLink(); / 44-System.out.println();linkList.displayList(); /22- 66- 88-第五讲 双端链表和双向链表1. 双端链表链表中保存着对最后一个链结点的引用l 从头部进行插入（insertFirst）：要对链表进行判断，如果链表为空，则设置尾结点为新添加的结点。l 从尾部进行插入（insertLast）：如果链表为空，则直接设置头结点为新添加的结点，否则设置尾结点的后一个节点为新添加的结点。l 从头部进行删除（deleteFirst）：判断头结点是否有下一个结点，如果没有则设置尾结点为null。双端链表FirstLastList类：public class FirstLastList private Link first; / reference to first linkprivate Link last; / reference to last linkpublic FirstLastList() this.first = null;this.last = null;public boolean isEmpty() / true if no linksreturn first = null;/ insert at front of listpublic void insertFirst(long value) Link newLink = new Link(value);if(isEmpty() / if empty listlast = newLink; / newLink old firstfirst = newLink; / first - newLink/ insert at end of listpublic void insertLast(long value) Link newLink = new Link(value);if(isEmpty() / if empty listfirst = newLink; / first - newLink else last.next = newLink; / old last - newLinklast = newLink; / newLink - last/ delete first linkpublic Link deleteFirst() Link temp = first;if(first.next = null) / if only one itemlast = null; / null old nextreturn temp;public void displayList() Link current = first; / start at beginning of listwhile(current != null) / until end of listcurrent.displayLink();current = current.next; / move list to next linkSystem.out.println();测试FirstLastList类及输出结果：public void testFirstLastList() throws Exception FirstLastList list = new FirstLastList();list.insertLast(24);list.insertFirst(13);list.insertFirst(5);list.insertLast(46);list.displayList(); /5- 13- 24- 46-list.deleteFirst();list.displayList(); /13- 24- 46-2. 双向链表双向链表既允许向后遍历，也允许向前遍历整个链表。即每个节点除了保存了对下一个节点的引用，同时后保存了对前一个节点的引用。l 从头部进行插入（insertFirst）：要对链表进行判断，如果为空，则设置尾结点为新添加的结点；如果不为空，还需要设置头结点的前一个结点为新添加的结点。l 从尾部进行插入（insertLast）：如果链表为空，则直接设置头结点为新添加的结点，否则设置尾节点的后一个结点为新添加的结点。同时设置新添加的结点的前一个结点为尾结点。l 从头部进行删除（deleteFirst）：判断头结点是否有下一个结点，如果没有则设置尾结点为null；否则设置头结点的下一个结点的previous为null。l 从尾部进行删除（deleteLast）：如果头结点后没有其他结点，则设置头结点为null。否则设置尾结点的前一个结点的next为null。设置尾结点为其前一个结点。l 在指定结点后插入（insertAfter）：l 删除指定结点（deleteKey）：不再需要在使用一个临时的指针域指向前一个结点。双向链表的链接点Link类的定义：public class DoubleLink public long data; / data itempublic DoubleLink next; / next link in listpublic DoubleLink previous; / previous link in listpublic DoubleLink(long data) this.data = data;public void displayLink() / display ourselfSystem.out.print(data + );双向链表DoublyLinkedList类：public class DoublyLinkedList private DoubleLink first; / reference to first linkprivate DoubleLink last; / reference to last linkpublic DoublyLinkedList() this.first = null;this.last = null;public boolean isEmpty() / true if no linksreturn first = null;/ insert at front of listpublic void insertFirst(long value) DoubleLink newLink = new DoubleLink(value);if(isEmpty() / if empty listlast = newLink; / newLink - last else first.previous = newLink;