鏈表
鏈表是一種數(shù)據(jù)結(jié)構(gòu),相對于數(shù)組而言,插入和刪除的開銷比較小,而查找的代價較大.以下我們實現(xiàn)雙向鏈表:
public class MyList<T> {
private Node<T> head;
private Node<T> tail;
private int size;
//初始化頭結(jié)點和尾節(jié)點
public MyList(){
head=new Node<T>(null, null, tail);
tail=new Node<T>(null, head, null);
}
//獲得大小
public int size(){
return size;
}
//增加方法
public void add(T x){
this.addBefore(tail, x);
}
public void addBefore(int index,T x){
this.addBefore(this.getNode(index), x);
}
public void addBefore(Node<T> p,T x){
Node<T> newNode=new Node<T>(x, p.prev, p);
newNode.prev.next=newNode;
p.prev=newNode;
size++;
}
//查找方法 效率應(yīng)該高點
public Node<T> getNode(int index){
Node<T> p;
if(index<size()/2){
p=head.next;
for(int i=0;i<index;i++){p=p.next;}
}else{
p=tail;
for(int i=size();i>index;i--){p=p.prev;}
}
return p;
}
//刪除
public T remove(int index){
return remove(this.getNode(index));
}
public T remove(Node<T> p){
p.next.prev=p.prev;
p.prev.next=p.next;
size--;
return p.data;
}
//修改
public void set(int index,T newData){
Node<T> p=this.getNode(index);
p.data=newData;
}
//顯示全部
public void show(){
if(size()>0){
Node<T> p=head.next;
while(p!=tail){
System.out.println(p.data);
p=p.next;
}
}
}
//節(jié)點類
private static class Node<T>{
public T data;
public Node<T> prev;
public Node<T> next;
public Node(T d,Node<T> p,Node<T> n){
data=d;
prev=p;
next=n;
}
}
}
在我寫的這個雙向鏈表中頭節(jié)點head和尾節(jié)點tail是空出來的,不存放任何數(shù)據(jù).若是要改造成雙向循環(huán)鏈表的話就不合適了,比如最后一個元素要next三下越過tail和head才循環(huán)到第一個元素.
于是稍作改造(注意空指針),雙向循環(huán)鏈表:
package com.fredal.structure;
public class MyCList<T> {
private Node<T> head;
private Node<T> tail;
private int size;
// 初始化頭結(jié)點和尾節(jié)點
public MyCList() {
head = new Node<T>(null, tail, tail);
tail = new Node<T>(null, head, head);
// 解決空指針
head.prev = tail;
head.next = tail;
tail.prev = head;
tail.next = head;
}
// 獲得大小
public int size() {
return size;
}
// 增加方法
public void add(T x) {
if (head.data == null) {
head.data = x;
size++;
} else if (tail.data == null) {
tail.data = x;
size++;
} else {
Node<T> p = this.addBefore(head, x);
tail = p;
}
}
public Node<T> addBefore(int index, T x) {
return this.addBefore(this.getNode(index), x);
}
public Node<T> addBefore(Node<T> p, T x) {
Node<T> newNode = new Node<T>(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
size++;
return newNode;
}
// 查找方法 效率應(yīng)該高點
public Node<T> getNode(int index) {
Node<T> p;
if (index < size() / 2) {
p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
} else {
p = tail;
for (int i = size() - 1; i > index; i--) {
p = p.prev;
}
}
return p;
}
// 刪除
public T remove(int index) {
return remove(this.getNode(index));
}
public T remove(Node<T> p) {
p.next.prev = p.prev;
p.prev.next = p.next;
size--;
if (p == head) {
head = p.next;
}
if (p == tail) {
tail = p.prev;
}
return p.data;
}
// 修改
public void set(int index, T newData) {
Node<T> p = this.getNode(index);
p.data = newData;
}
// 顯示全部
public void show() {
if (size() > 0) {
Node<T> p = head;
do {
System.out.println(p.data);
p = p.next;
} while (p != head);
}
}
// 節(jié)點類
private static class Node<T> {
private T data;
private Node<T> prev;
private Node<T> next;
public Node(T d, Node<T> p, Node<T> n) {
data = d;
prev = p;
next = n;
}
}
}
棧
棧Stack是一個表,先進后出,有兩種實現(xiàn)方式:由鏈表或者數(shù)組來實現(xiàn).這里我們選用數(shù)組實現(xiàn)做例子,比較簡單:
package com.fredal.structure;
public class MyStack<T> {
// Java 不支持泛型數(shù)組，如需使用饭玲，請使用Java提供的容器
private Object[] stack;
// 棧的默認初始大小
private static final int INIT_SIZE = 2;
// 棧頂索引
private int index;
public MyStack() {
stack = new Object[INIT_SIZE];
index = -1;
}
/**
* 構(gòu)造方法
*
* @param initSize
* 棧的初始大小
*/
public MyStack(int initSize) {
if (initSize < 0) {
throw new IllegalArgumentException();
}
stack = new Object[initSize];
index = -1;
}
/**
* 出棧操作
*
* @return 棧頂對象
*/
public T pop() {
if (!isEmpty()) {
T temp = peek();
stack[index--] = null;
return temp;
}
return null;
}
/**
* 入棧操作
*
* @param obj
* 等待入棧的對象
*/
public void push(T obj) {
if (isFull()) {
Object[] temp = stack;
// 擴容操作,和arraylist的一樣,如果棧滿，則創(chuàng)建空間為當(dāng)前椄淳保空間兩倍的棧
stack = new Object[2 * stack.length];
System.arraycopy(temp, 0, stack, 0, temp.length);
}
stack[++index] = obj;
}
/**
* 查看棧頂對象
*
* @return 棧頂對象
*/
public T peek() {
if (!isEmpty()) {
return (T) stack[index];
}
return null;
}
/**
* 查看棧是否為空
*
* @return 如果棧為空返回true棘利，否則返回false
*/
public boolean isEmpty() {
return index == -1;
}
/**
* 查看棧是否滿
*
* @return 如果棧滿返回true,否則返回false
*/
public boolean isFull() {
return index >= stack.length - 1;
}
}
應(yīng)用的比較多的一個是檢測平衡符號,這個比較簡單,就是按順序push按順序pop看看是否相同.另外一個是逆波蘭表達式,寫一段代碼,包括中序表達式轉(zhuǎn)化為逆波蘭式,以及逆波蘭式的計算:
package com.fredal.structure;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Nbl {
private static Stack s1 = new Stack();// 逆波蘭表達式的棧
private static Stack s2 = new Stack();// 運算棧
//將字符串轉(zhuǎn)化成中序list
public static List<String> format(String s) {
List<String> ls = new ArrayList<String>();// 存儲中序表達式
int i = 0;
String str;
char c;
do {
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
ls.add("" + c);
i++;
} else {
str = "";
while (i < s.length() && (c = s.charAt(i)) >= 48
&& (c = s.charAt(i)) <= 57) {
str += c;
i++;
}
ls.add(str);
}
} while (i < s.length());
return ls;
}
//將中序表達式轉(zhuǎn)化為逆波蘭式
public static List<String> parse(List<String> ls) {
List<String> lss = new ArrayList<String>();
for (String ss : ls) {
if (ss.matches("\\d+")) {
lss.add(ss);// 不是運算符就加入list
} else if (ss.equals("(")) {
s1.push(ss);//碰到"("直接進棧
} else if(ss.equals(")")){
while(!s1.peek().equals("(")){//將直到"("的符號全彈出
lss.add((String) s1.pop());//加入list
}
s1.pop();//彈出"("
}else{
while(s1.size()!=0&&getValue((String) s1.peek())>=getValue(ss)){//比它優(yōu)先級高的全彈出
lss.add((String) s1.pop());
}
s1.push(ss);
}
}
while(s1.size()!=0){//結(jié)束之后全部彈出
lss.add((String) s1.pop());
}
return lss;
}
//獲取運算符優(yōu)先級
private static int getValue(String s) {
if (s.equals("+")) {
return 1;
} else if (s.equals("-")) {
return 1;
} else if (s.equals("*")) {
return 2;
} else if (s.equals("/")) {
return 2;
}
return 0;
}
// 對逆波蘭表達式進行求值
public static int calculate(List<String> ls) {
for (String s : ls) {
if (s.matches("\\d+")) {
s2.push(s);// 不是運算符就入棧
} else {
int b = Integer.parseInt((String) s2.pop());
int a = Integer.parseInt((String) s2.pop());
if (s.equals("+")) {
a = a + b;
} else if (s.equals("-")) {
a = a - b;
} else if (s.equals("*")) {
a = a * b;
} else if (s.equals("/")) {
a = a / b;
}
s2.push("" + a);
}
}
return Integer.parseInt((String) s2.pop());
}
}
隊列
隊列(queue)也是表,使用隊列時插入在一端進行而刪除在另一端進行.
基本操作是enqueue入隊,在表的末端插入元素.dequeue出隊,刪除并返回表的開頭.
用數(shù)組實現(xiàn)隊列會有潛在問題,就是隊列滿了之后在入隊一次back的下標(biāo)會指向不存在的位置,解決這個問題我們用循環(huán)隊列的方式.
package com.fredal.structure;
public class MyQueue<T> {
private int INITIAL_SIZE=10;
private int capacity;//數(shù)組長度
private Object[] elementData;
private int front=0;
private int back=0;
public MyQueue(){
capacity=INITIAL_SIZE;
elementData=new Object[capacity];
}
//以一個初始化元素來創(chuàng)建循環(huán)隊列
public MyQueue(T element){
this();
elementData[0]=element;
back++;
}
//以指定長度的數(shù)組來創(chuàng)建循環(huán)隊列
public MyQueue(T element,int initSize){
this.capacity=initSize;
elementData=new Object[capacity];
elementData[0]=element;
back++;
}
//判斷循環(huán)隊列是否為空
public boolean isEmpty(){
return back==front&&elementData[back]==null;
}
//獲取循環(huán)隊列的大小
public int length(){
if(isEmpty()){
return 0;
}else{
return back>front?back-front:capacity-(front-back);
}
}
//插入隊列
public void add(T element){
if(back==front&&elementData[front]!=null){
throw new IndexOutOfBoundsException("隊列已滿");
}
elementData[back++]=element;
//back指針到頭就循環(huán)
back=(back==capacity)?0:back;
}
//移出隊列
public T remove(){
if(isEmpty()){
throw new IndexOutOfBoundsException("隊列已空");
}
T oldValue=(T)elementData[front];
elementData[front++]=null;
//如果front到頭 就循環(huán)
front=front==capacity?0:front;
return oldValue;
}
//顯示
public void show(){
if(isEmpty()){
System.out.println("[]");
}else{
if(front<back){
StringBuilder sb=new StringBuilder("[");
for(int i=front;i<back;i++){
sb.append(elementData[i].toString()+",");
}
int len=sb.length();
String s= sb.delete(len-1, len).append("]").toString();
System.out.println(s);
}else{
StringBuilder sb=new StringBuilder("[");
for(int i=front;i<capacity;i++){
sb.append(elementData[i].toString()+",");
}
for(int i=0;i<back;i++){
sb.append(elementData[i].toString()+",");
}
int len=sb.length();
String s= sb.delete(len-1, len).append("]").toString();
System.out.println(s);
}
}
}
}
樹
先說二叉樹,二叉樹表示每個節(jié)點都不能有多于兩個的兒子.二叉樹的一個重要應(yīng)用是二叉排序樹ADT:
package com.fredal.structure;
public class MyTree<T extends Comparable<T>> {
// 節(jié)點類
private static class BNode<T> {
T element;
BNode<T> left;
BNode<T> right;
public BNode(T element) {
this(element, null, null);
}
public BNode(T element, BNode<T> lt, BNode<T> rt) {
this.element = element;
left = lt;
right = rt;
}
}
// 插入節(jié)點之后
public BNode<T> insert(T x, BNode<T> t) {
if (t == null) {
return new BNode<T>(x, null, null);
}
int result = x.compareTo(t.element);
if (result < 0)
t.left = insert(x, t.left);
else if (result > 0)
t.right = insert(x, t.right);
return t;
}
// 刪除
public BNode<T> remove(T x, BNode<T> t) {
if (t == null)
return t;
int result = x.compareTo(t.element);
if (result < 0)
t.left = remove(x, t.left);
else if (result > 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);
} else
// 找到了 一個孩子或沒有孩子
t = (t.left != null) ? t.left : t.right;
return t;
}
// 尋找最小值
public BNode<T> findMin(BNode<T> t) {
if (t == null)
return null;
else if (t.left == null)
return t;
return findMin(t.left);
}
// 尋找最大值
public BNode<T> findMax(BNode<T> t) {
if (t == null)
return null;
else if (t.right == null)
return t;
return findMax(t.right);
}
// 獲得樹的高度
public int getHeight(BNode<T> t) {
int a = 0;
int b = 0;
if (t.left != null)
a = getHeight(t.left);
if (t.right != null)
b = getHeight(t.right);
return (a > b ? a : b) + 1;
}
// 是否包含某個元素
public boolean contains(T x, BNode<T> t) {
if (t == null)
return false;
int result = x.compareTo(t.element);
if (result < 0)
return contains(x, t.left);
else if (result > 0)
return contains(x, t.right);
else
return true;
}
// 顯示 中序遍歷了
public void show(BNode<T> t) {
if (t.left != null)
show(t.left);
System.out.println(t.element);
if (t.right != null)
show(t.right);
}
}
還有一個就是所謂的表達式樹,一個正常的表達式構(gòu)建的表達式樹如果采取中序遍歷就是得到正常的表達式,如果采取后序遍歷呢就會產(chǎn)生上一節(jié)說的那個逆波蘭表達式,也叫后綴表達式.
基本上這個樹的作用就是把后序表達式變成中序表達式,之前那段代碼逆作用..
用后綴表達式構(gòu)建樹,再中序遍歷之
package com.fredal.structure;
import java.util.Stack;
public class ExpTree<T> {
// 節(jié)點類
private static class BNode<T> {
T element;
BNode<T> left;
BNode<T> right;
public BNode(T element) {
this(element, null, null);
}
public BNode(T element, BNode<T> lt, BNode<T> rt) {
this.element = element;
left = lt;
right = rt;
}
}
public BNode<Character> bulid(String exp){
char c;
BNode<Character> newNode,newLeft,newRight;
Stack<BNode<Character>> stack=new Stack<BNode<Character>>();
int i=0;
int len=exp.length();
while(i!=len){
while(exp.charAt(i)==' '||exp.charAt(i)=='\t'){
i++;
}
if(i==len) break;
c=exp.charAt(i);
i++;
if(c=='+'||c=='-'||c=='*'||c=='/'){//碰到運算符就把前兩個彈出來重新構(gòu)建一下樹再入棧
newRight=stack.pop();
newLeft=stack.pop();
newNode=new BNode<Character>(c, newLeft, newRight);
stack.push(newNode);
}else{
newNode=new BNode<Character>(c);//不是運算符直接入棧
stack.push(newNode);
}
}
if(!stack.isEmpty()){
return stack.pop();//彈出整棵樹
}else{
return null;
}
}
//中序輸出
public void show(BNode<T> t){
if(t!=null){
show(t.left);
System.out.print(t.element+" ");
show(t.right);
}
}
}
表達式樹確實是這樣的,中序遍歷也沒錯,不過要變成正常的表達式仍然是不夠的,還需要考慮優(yōu)先級去加括號,偷懶方法當(dāng)然是全部加上括號,這兒不寫了.
然后寫一下多叉樹的實現(xiàn)吧,這兒寫習(xí)慣了就給node外面加了一層包裝類,這樣添加的時候還是比較麻煩的,待優(yōu)化吧.
package com.fredal.structure;
import java.util.ArrayList;
import java.util.List;
public class CTree<T> {
// 節(jié)點類
private static class CNode<T> {
T element;
CNode<T> parent;// 父節(jié)點
List<CNode<T>> children = new ArrayList<CNode<T>>();// 孩子節(jié)點
CNode<T> leftBrother;// 左邊第一個兄弟節(jié)點
CNode<T> rightBrother;// 右邊第一個兄弟節(jié)點
public CNode(T t, CNode<T> parent) {
element = t;
this.parent = parent;
}
}
// 插入
public CNode<T> insert(T x, CNode<T> t) {
CNode<T> newNode = new CNode<T>(x, t);
List<CNode<T>> children = t.children;
if (children.size() == 0) {
children.add(newNode);
} else {
CNode<T> lastNode = children.get(children.size() - 1);
lastNode.rightBrother = newNode;
newNode.leftBrother = lastNode;
children.add(newNode);
}
return newNode;
}
// 得到根節(jié)點
public CNode<T> getRoot(CNode<T> t) {
while (t.parent != null) {
t = t.parent;
}
return t;
}
// 得到父節(jié)點
public CNode<T> getParent(CNode<T> t) {
if (t.parent != null) {
return t.parent;
}
return null;
}
// 得到子節(jié)點
public List<CNode<T>> getChildren(CNode<T> t) {
if (t.children != null) {
return t.children;
}
return null;
}
// 左節(jié)點
public CNode<T> getLeftBrother(CNode<T> t) {
if (t.leftBrother != null) {
return t.leftBrother;
}
return null;
}
// 右節(jié)點
public CNode<T> getRightBrother(CNode<T> t) {
if (t.rightBrother != null) {
return t.rightBrother;
}
return null;
}
// 這個屬于先序遍歷
public void show(CNode<T> t) {
if (t != null) {
System.out.print(t.element + " ");
List<CNode<T>> children = t.children;
for (int i = 0; i < children.size(); i++) {
show(children.get(i));
}
}
}
}
散列
散列也叫哈希,會遇到散列沖突問題,解決沖突最常用的是分離鏈接法,簡單來說就是將散列到同一個值的所有元素都插入到一個鏈表中去,來實現(xiàn)吧.
package com.fredal.structure;
import java.util.LinkedList;
import java.util.List;
public class MyHashTable<T> {
private static final int DEFAULT_SIZE=100;
private int size;
private List<T>[] lists;
public MyHashTable(int size){
this.size=size;
lists=new LinkedList[size];//初始化鏈表數(shù)組
for (int i = 0; i < lists.length; i++) {
lists[i]=new LinkedList<T>();
}
}
public MyHashTable(){
this(DEFAULT_SIZE);
}
private int myHash(T x){
int hashVal=x.hashCode();
hashVal%=lists.length;
if(hashVal<0){
hashVal+=lists.length;
}
return hashVal;
}
//是否包含 使用自帶的就好 ~
public boolean contains(T x){
List<T> list=lists[myHash(x)];
return list.contains(x);
}
//插入方法
public void insert(T x){
List<T> list=lists[myHash(x)];
if(!list.contains(x)){
list.add(x);
size++;
}
}
//移除方法
public void remove(T x){
List<T> list=lists[myHash(x)];
if(list.contains(x)){
list.remove(x);
size--;
}
}
}
這里并沒有考慮再散列,因為場景不復(fù)雜,再散列以后再談.
還有一種散列表叫探測散列表,也以后再說...
堆
堆也叫優(yōu)先隊列,是允許至少下列兩種操作的數(shù)據(jù)結(jié)構(gòu),插入和刪除并返回最小值.插入(insert)相當(dāng)于enqueue(入隊),而刪除最小值(deleteMin)則等價于隊列運算dequeue(出隊).
我們要講的叫二叉堆,除了是一顆完整二叉樹外還要保持其堆序性質(zhì).例如最小二叉堆即,最小元在根上,而任意節(jié)點都小于它的所有后裔.
我們通過代碼模擬二叉堆
package com.fredal.structure;
public class MyHeap<T extends Comparable<? super T>> {
private static final int DEFAULT_CAPACITY=10;
private int currentSize;//堆元素數(shù)量
private T[] array;//堆數(shù)組
public MyHeap(){
this(DEFAULT_CAPACITY);
}
public MyHeap(int capacity){
currentSize=0;
array=(T[]) new Comparable[capacity+1];
}
//對已給定的數(shù)組建堆初始化
public MyHeap(T [] items){
currentSize=items.length;
array=(T[])new Comparable[(currentSize+2)*11/10];
int i=1;
for(T item:items){
array[i++]=item;
}
buildHeap();
}
private void buildHeap() {
for(int i=currentSize/2;i>0;i--){
percolateDown(i);//下濾
}
}
//下濾 保持堆特性
private void percolateDown(int i) {
int child;
T temp =array[i];
for(;i*2<=currentSize;i=child){
child=i*2;
if(child!=currentSize&& array[child+1].compareTo(array[child])<0){
child++;
}
if(array[child].compareTo(temp)<0){
array[i]=array[child];
}else
break;
}
array[i]=temp;
}
//插入操作
public void insert(T x){
if(currentSize==array.length-1){
enlargeArray(array.length*2+1);
}
//上濾操作
int i=++currentSize;
for(array[0]=x;x.compareTo(array[i/2])<0;i/=2){
array[i]=array[i/2];
}
array[i]=x;
}
//擴容操作
private void enlargeArray(int newSize){
T[] old=array;
array=(T[]) new Comparable[newSize];
for(int i=0;i<old.length;i++){
array[i]=old[i];
}
}
//刪除最小值
public T deleteMin(){
if(currentSize==0){
throw new RuntimeException();
}
T min=findMin();
array[1]=array[currentSize--];
//下濾
percolateDown(1);
return min;
}
//尋找最小值
public T findMin() {
if(currentSize==0){
throw new RuntimeException();
}
return array[1];
}
//顯示
public void show(){
for(int i=1;i<=currentSize;i++){
System.out.print(array[i]+" ");
}
}
}
堆的應(yīng)用有許多,堆排序是最重要的之一,我們在后面會講到.
更多文章與相關(guān)下載請看擴展閱讀
