@前言
迎来了本学期的重头专业课——数据结构与算法分析。
这次我们的老师是来自英国威尔士亚伯大学（Aberystwyth University）的Fred Long教授！！！老师曾以访问学者的身份来到CMU！！！！！！有六本著作！！
@知识点随笔
【新思想】
java中操作的都是引用！！！
即便是实例化，其实也是新建了一个引用！
操作引用很方便，很少直接操作本体！
【LinkedList的AddToFront方法传递的变量】
应该是传递对象，而不是节点。传对象好一些。
【上下层之间没有大小关系】
【AVL是实现平衡树的一种原则，另外还有红黑树等等】
【平衡树的目的：避免因为不规则的插入，没有及时调整，导致二叉树的时间复杂度急剧上升】
【AVL的目的：原本的绝对平衡二叉树过于严格，应用价值不大，AVL树允许左右深度相差1】
【平衡因素的改变仅限于新节点到根节点的路径上】
【泛型】可能就是增强代码的重用性
【在格式基础上可以实现固定任意的T类】
【如何理解泛型的作用】
1.多用于集合，便于控制集合内的元素类型固定唯一
2.另，可以当做参数来理解，即一套体系可以让不同的类适用
【B树】
·牢记各个树的性质！
·对于任给的一串数字，有可能有多种B树
【对java泛型的补充理解】
泛型的操作对象是集合！Collection
为什么不规定泛型时输出需要强制转化~
因为不规定泛型时，编译器默认泛型是Object
1、泛型的类型参数只能是类类型（包括自定义类），不能是简单类型。
2、同一种泛型可以对应多个版本（因为参数类型是不确定的），不同版本的泛型类实例是不兼容的。
3、泛型的类型参数可以有多个。
4、泛型的参数类型可以使用extends语句，例如。习惯上成为“有界类型”。
5、泛型的参数类型还可以是通配符类型。例如Class
public class BoundedStack {private Person[] list;private int firstFree = 0;private static final int DEFAULT_MAXIMUM = 10;// 2 Constructorspublic BoundedStack() {list = new Person[DEFAULT_MAXIMUM];}public BoundedStack(int size) {list = new Person[size];}// push method, which can add a new element at the endpublic void push(Person element) {if (firstFree == list.length) {throw new StackOverflowError();}list[firstFree] = element;firstFree++;}// pop method to peek and delete the top itempublic Person pop() {Person temp;temp = peek();this.list[firstFree - 1] = null;this.firstFree--;return temp;}// isEmpty method to determine whether the stack is emptypublic boolean isEmpty() {return firstFree == 0;}// peek method to return the top itempublic Person peek() {return this.list[firstFree - 1];}// depth method to get the number of the items in the stackpublic int depth() {return this.firstFree;}// overwrite toStringpublic String toString(Person[] list) {String tempString = "";for (int i = 0; i < this.firstFree; i++)tempString += ("Name: " + list[i].getName() + " Number: " + list[i].getNum());return tempString;}// compare two stackspublic boolean equals(BoundedStack comparedStack) {if (this.firstFree != comparedStack.firstFree)return false;else {for (int i = 0; i < this.firstFree; i++) {if (this.list[i] != comparedStack.list[i])return false;}}return true;}// main method to test BoundedStack classpublic static void main(String args[]) {Person raven = new Person("Raven", 1);//Problem: using the same constructorPerson messi = new Person("Messi", 2);Person neymar = new Person("Neymar", 3);Person mars = new Person("Mars", 4);BoundedStack myStack = new BoundedStack();myStack.push(raven);myStack.push(messi);myStack.push(neymar);myStack.push(mars);System.out.println(myStack.toString(myStack.list));System.out.println("The depth is: " + myStack.depth());System.out.println("The top element is: " + myStack.peek().getName());myStack.pop();System.out.println(myStack.toString(myStack.list));System.out.println("Now, the depth is: " + myStack.depth());System.out.println("Now, The top element is: " + myStack.peek().getName());System.out.println("Equal Test");BoundedStack testStack=new BoundedStack();System.out.println(myStack.equals(testStack));testStack=myStack;System.out.println(myStack.equals(testStack));System.out.println("Over");}}// Other classes/*class Person {private String name;private int num;public Person(String name, int num) {this.name = name;this.num = num;}public String getName() {return this.name;}public int getNum() {return this.num;}}*/
2.队列
@SuppressWarnings("hiding")public class BoundedQueue<Person> {private Person[] list;private static final int DEFAULT_MAXIMUM = 10;private int front = 0;private int back = -1;private int length = 0;public BoundedQueue() {this(DEFAULT_MAXIMUM);}@SuppressWarnings("unchecked")public BoundedQueue(int size) {list = (Person[]) new Object[size];}public void insert(Person tempPerson) throws Exception {if (this.length > list.length)throw new Exception("Queue is full!");if (back == list.length - 1)back = -1;list[++back] = tempPerson;length++;}public Person remove() throws Exception {if (this.length == 0)throw new Exception("Queue is empty!");Person tmp = list[front++];if (front == list.length)front = 0;length--;return tmp;}public Person getFront() throws Exception {if (this.length == 0)throw new Exception("Queue is empty!");return list[front];}/*public boolean equals() {}*/public int length() {return this.length;}public boolean isEmpty() {return (length == 0);}public boolean isFull() {return (length == list.length);}}
3.单向链表
/*** @author Raven Xu**/public class MyLinkedList<E> {private Node<E> first = new Node<E>();//private int length;public boolean isEmpty() {return first.getNext() == null;}public void addToFront(E temp) {Node<E> addedNode = new Node<E>();addedNode.setData(temp);addedNode.setNext(first.getNext());first.setNext(addedNode);}public void removeFromFront() {try {first.setNext(first.getNext().getNext());} catch (NullPointerException e) {throw e;}}public String toString() {StringBuilder tempString = new StringBuilder();for (Node<E> current = first.getNext(); current != null; current = current.getNext()) {tempString.append(current.getData() + "\n");}return tempString.toString();}public int length() {int tempLength = 0;for (Node<E> current = first.getNext(); current != null; current = current.getNext()) {tempLength++;}return tempLength;}public void addToBack(E temp) {Node<E> addedNode = new Node<E>(temp);Node<E> tempNode = new Node<E>();tempNode.setNext(first.getNext());while (tempNode.getNext() != null)tempNode=tempNode.getNext();tempNode.setNext(addedNode);}public void removeFromBack() {Node<E> tempNode = new Node<E>();tempNode.setNext(first.getNext());while (tempNode.getNext().getNext() != null)tempNode=tempNode.getNext();tempNode.setNext(null);}public Node<E> find(E element) {Node<E> current = first.getNext();while ((current != null) && !current.getData().equals(element)) {current = current.getNext();}return current;}public boolean equals(Object obj) {// Deal with the "obvious" casesif (obj == null)return false;if (obj == this)return true;if (!(obj instanceof MyLinkedList))return false;@SuppressWarnings("unchecked")MyLinkedList<E> otherList = (MyLinkedList<E>) obj;if (this.length() != otherList.length())return false;Node<E> current1 = this.getFront(); // the front node of this listNode<E> current2 = otherList.getFront();while (current1 != null) {if (!(current1.getData().equals(current2.getData()))) // assume equalsreturn false; // is definedcurrent1 = current1.getNext(); // method in Node classcurrent2 = current2.getNext(); // method in Node class}return true;}public Node<E> getFront() {return first.getNext();}public Node<E> getBack() {Node<E> tempNode = new Node<E>();tempNode.setNext(first.getNext());while (tempNode.getNext() != null)tempNode=tempNode.getNext();return tempNode;}@SuppressWarnings("hiding")private class Node<E> {private E data;private Node<E> next;public Node() {}public Node(E theData) {data=theData;}// @return the datapublic E getData() {return data;}// @param data the data to setpublic void setData(E data) {this.data = data;}// @return the nextpublic Node<E> getNext() {return next;}// @param next the next to setpublic void setNext(Node<E> next) {this.next = next;}public String toString() {return data.toString();}}//Test my LinkedListpublic static void main(String args[]) {MyLinkedList<Person> personList = new MyLinkedList<Person>();Person raven = new Person("Raven", 1);Person messi = new Person("Messi", 2);Person neymar = new Person("Neymar", 3);Person mars = new Person("Mars", 4);System.out.println("*****addtoFront Test*****");personList.addToFront(raven);personList.addToFront(messi);System.out.println(personList);System.out.println("*****addtoBack Test*****");personList.addToBack(neymar);personList.addToBack(mars);System.out.println(personList);System.out.println("*****getFront and getBack Test*****");System.out.println("Front: "+personList.getFront().toString()+"\n"+"Back: "+personList.getBack().toString());System.out.println("*****equals Test*****");MyLinkedList<Person> list = personList;System.out.println(list.equals(personList));System.out.println("*****length Test*****");System.out.println("List length: "+personList.length());System.out.println("*****find Test*****");System.out.println(personList.find(raven));System.out.println("*****removeFromFront and removeFromBack Test*****");personList.removeFromFront();personList.removeFromBack();System.out.println(personList);}}/*class LinkedListItr<E> implements java.util.Iterator<E> {private Node<E> currentPosition;public LinkedListItr(Node<E> firstNode) {currentPosition = firstNode.getNext();}public boolean hasNext() {return currentPosition != null;}public E next() {E returnedObject = currentPosition.getData();currentPosition = currentPosition.getNext();return returnedObject;}public void remove() {throw new UnsupportedOperationException("The linked list has no remove method.");}}*/
4.双向链表
/** @author Raven**/public class DoubleLinkedList<E> {private Node<E> first = new Node<E>();private Node<E> end = new Node<E>();private int theSize;private int modCount = 0;public DoubleLinkedList() {doClear();}public void Clear() {doClear();}private void doClear() {first = new Node<E>(null, null, null);end = new Node<E>(null, first, null);first.next = end;theSize = 0;modCount++;}public int size() {return theSize;}public boolean isEmpty() {return size()==0;}public boolean add(E x) {add(size(), x);return true;}public void add(int idx, E x) {addBefore(getNode(idx, 0, size()),x);}public E get(int idx) {return getNode(idx).data;}public E set(int idx, E newVal) {Node<E> p = getNode(idx);E oldVal= p.data;p.data=newVal;return oldVal;}public E remove(int idx) {return remove(getNode(idx));}private void addBefore(Node<E> p, E x) {Node<E> newNode = new Node<>(x, p.prev, p);newNode.prev.next = newNode;p.prev=newNode;theSize++;modCount++;}private E remove(Node<E> p) {p.next.prev=p.prev;p.prev.next=p.next;theSize--;modCount++;return p.data;}private Node<E> getNode(int idx){return getNode(idx, 0 ,size()-1);}private Node<E> getNode(int idx, int lower, int upper){Node<E> p;if(idx<lower||idx>upper)throw new IndexOutOfBoundsException();if(idx<size()/2) {p=first.next;for(int i=0;i<idx;i++)p=p.next;}else {p=end;for(int i=size();i>idx;i--)p=p.prev;}return p;}public String toString() {StringBuilder tempString = new StringBuilder();for (Node<E> current = first.getNext(); current != null; current = current.getNext()) {tempString.append(current.getData() + "\n");}return tempString.toString();}private static class Node<E> {private E data;private Node<E> prev;private Node<E> next;public Node() {}@SuppressWarnings("unused")public Node(E theData) {data = theData;}public Node(E theData, Node<E> thePrev, Node<E> theNext) {data = theData;prev = thePrev;next = theNext;}// @return the datapublic E getData() {return data;}// @param data the data to set@SuppressWarnings("unused")public void setData(E data) {this.data = data;}// @return the nextpublic Node<E> getNext() {return next;}// @param next the next to set@SuppressWarnings("unused")public void setNext(Node<E> next) {this.next = next;}// @return the previous node@SuppressWarnings("unused")public Node<E> getPrev() {return prev;}// @param next the next to set@SuppressWarnings("unused")public void setPrev(Node<E> prev) {this.prev = prev;}public String toString() {return data.toString();}}public static void main(String args[]) {DoubleLinkedList<Person> personList2 = new DoubleLinkedList<Person>();Person raven = new Person("Raven", 1);Person messi = new Person("Messi", 2);Person neymar = new Person("Neymar", 3);Person mars = new Person("Mars", 4);personList2.add(raven);personList2.add(messi);personList2.add(neymar);personList2.add(mars);System.out.println("Add Test");System.out.println(personList2.toString());}}
5.二叉搜索树
/*** @author Raven**/public class BinarySearchTree<E extends Comparable<E>> {/** The Binary root */private BinaryNode<E> root = null;// interfacespublic BinarySearchTree() {root = null;}public void makeEmpty() {root = null;}public boolean isEmpty() {return root == null;}public boolean contains(E x) {return contains(x, root);}/*public E findMin() {if (isEmpty())throw new UnderflowException();return findMin(root).element;}public E findMax() {if (isEmpty())throw new UnderflowException();return findMax(root).element;}*/public void insert(E x) {root = insert(x, root);}public void remove(E x) {root = remove(x, root);}// real methodspublic void printTree() {}private boolean contains(E x, BinaryNode<E> t) {if (t == null)return false;int compareResult = pareTo(t.element);if (compareResult < 0)return contains(x, t.left);else if (compareResult > 0)return contains(x, t.right);elsereturn true; // Match}/*** Internal method to find the smallest item in a subtree.(We use two methods to implement findMin and findMax)* @param t the node that roots the subtree.* @return node containing the smallest item.*/public BinaryNode<E> findMin(BinaryNode<E> t) {if (t == null)return null;else if (t.left==null) //it means that t has a left subtree, and there are some nodes are smaller than it.return t;return findMin(t.left);}/*** Internal method to find the largest item in a subtree.(We use two methods to implement findMin and findMax)* @param t the node that roots the subtree.* @return node containing the largest item.*/public BinaryNode<E> findMax(BinaryNode<E> t) {if (t != null)while (t.getRight() != null)t = t.getRight();return t;}/*** Internal method to insert a subtree.* @param x the item to insert.* @param t the node that roots the subtree.* @return the new root of the subtree.*/private BinaryNode<E> insert(E x, BinaryNode<E> t) {if (t == null)return new BinaryNode<>(x, null, null);int compareResult = pareTo(t.getElement());if (compareResult < 0)t.left = insert(x, t.left);else if (compareResult > 0)t.right = insert(x, t.right);else;return t;}/*** Internal method to remove from a subtree.* @param x the item to remove.* @param t the node that roots the subtree.* @return the new root of the subtree.*/private BinaryNode<E> remove(E x, BinaryNode<E> t) {if (t == null)return t; // Item not found; do nothingint compareResult = pareTo(t.getElement());if (compareResult < 0)t.left = remove(x, t.left);else if (compareResult > 0)t.right = remove(x, t.right);else if (t.left != null && t.right != null) {t.element = findMin(t.right).element;t.right = remove(t.element, t.right);} elset = (t.left != null) ? t.left : t.right;return t;}private static class BinaryNode<E> {private E element;private BinaryNode<E> left;private BinaryNode<E> right;// Constructors@SuppressWarnings("unused")public BinaryNode(E theElement) {this(theElement, null, null);}public BinaryNode(E theElement, BinaryNode<E> lt, BinaryNode<E> rt) {element = theElement;left = lt;right = rt;}public E getElement() {return element;}@SuppressWarnings("unused")public BinaryNode<E> getLeft() {return left;}public BinaryNode<E> getRight() {return right;}}public static void main(String args[]) {}}
