数据结构_基础结构
程序员文章站
2022-03-24 17:27:38
...
链表
链表是一种数据结构,相对于数组而言,插入和删除的开销比较小,而查找的代价较大.以下我们实现双向链表:
public class MyList<T> {
private Node<T> head;
private Node<T> tail;
private int size;
//初始化头结点和尾节点
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++;
}
//查找方法 效率应该高点
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;
}
}
}
//节点类
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;
}
}
}
在我写的这个双向链表中头节点head和尾节点tail是空出来的,不存放任何数据.若是要改造成双向循环链表的话就不合适了,比如最后一个元素要next三下越过tail和head才循环到第一个元素.
于是稍作改造(注意空指针),双向循环链表:
package com.fredal.structure;
public class MyCList<T> {
private Node<T> head;
private Node<T> tail;
private int size;
// 初始化头结点和尾节点
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;
}
// 查找方法 效率应该高点
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);
}
}
// 节点类
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是一个表,先进后出,有两种实现方式:由链表或者数组来实现.这里我们选用数组实现做例子,比较简单:
package com.fredal.structure;
public class MyStack<T> {
// Java 不支持泛型数组，如需使用，请使用Java提供的容器
private Object[] stack;
// 栈的默认初始大小
private static final int INIT_SIZE = 2;
// 栈顶索引
private int index;
public MyStack() {
stack = new Object[INIT_SIZE];
index = -1;
}
/**
* 构造方法
*
* @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的一样,如果栈满，则创建空间为当前栈空间两倍的栈
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;
}
}
应用的比较多的一个是检测平衡符号,这个比较简单,就是按顺序push按顺序pop看看是否相同.另外一个是逆波兰表达式,写一段代码,包括中序表达式转化为逆波兰式,以及逆波兰式的计算:
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();// 运算栈
//将字符串转化成中序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;
}
//将中序表达式转化为逆波兰式
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)){//比它优先级高的全弹出
lss.add((String) s1.pop());
}
s1.push(ss);
}
}
while(s1.size()!=0){//结束之后全部弹出
lss.add((String) s1.pop());
}
return lss;
}
//获取运算符优先级
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出队,删除并返回表的开头.
用数组实现队列会有潜在问题,就是队列满了之后在入队一次back的下标会指向不存在的位置,解决这个问题我们用循环队列的方式.
package com.fredal.structure;
public class MyQueue<T> {
private int INITIAL_SIZE=10;
private int capacity;//数组长度
private Object[] elementData;
private int front=0;
private int back=0;
public MyQueue(){
capacity=INITIAL_SIZE;
elementData=new Object[capacity];
}
//以一个初始化元素来创建循环队列
public MyQueue(T element){
this();
elementData[0]=element;
back++;
}
//以指定长度的数组来创建循环队列
public MyQueue(T element,int initSize){
this.capacity=initSize;
elementData=new Object[capacity];
elementData[0]=element;
back++;
}
//判断循环队列是否为空
public boolean isEmpty(){
return back==front&&elementData[back]==null;
}
//获取循环队列的大小
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指针到头就循环
back=(back==capacity)?0:back;
}
//移出队列
public T remove(){
if(isEmpty()){
throw new IndexOutOfBoundsException("队列已空");
}
T oldValue=(T)elementData[front];
elementData[front++]=null;
//如果front到头 就循环
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);
}
}
}
}
树
先说二叉树,二叉树表示每个节点都不能有多于两个的儿子.二叉树的一个重要应用是二叉排序树ADT:
package com.fredal.structure;
public class MyTree<T extends Comparable<T>> {
// 节点类
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<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);
}
}
还有一个就是所谓的表达式树,一个正常的表达式构建的表达式树如果采取中序遍历就是得到正常的表达式,如果采取后序遍历呢就会产生上一节说的那个逆波兰表达式,也叫后缀表达式.
基本上这个树的作用就是把后序表达式变成中序表达式,之前那段代码逆作用..
用后缀表达式构建树,再中序遍历之
package com.fredal.structure;
import java.util.Stack;
public class ExpTree<T> {
// 节点类
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=='/'){//碰到运算符就把前两个弹出来重新构建一下树再入栈
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);
}
}
}
表达式树确实是这样的,中序遍历也没错,不过要变成正常的表达式仍然是不够的,还需要考虑优先级去加括号,偷懒方法当然是全部加上括号,这儿不写了.
然后写一下多叉树的实现吧,这儿写习惯了就给node外面加了一层包装类,这样添加的时候还是比较麻烦的,待优化吧.
package com.fredal.structure;
import java.util.ArrayList;
import java.util.List;
public class CTree<T> {
// 节点类
private static class CNode<T> {
T element;
CNode<T> parent;// 父节点
List<CNode<T>> children = new ArrayList<CNode<T>>();// 孩子节点
CNode<T> leftBrother;// 左边第一个兄弟节点
CNode<T> rightBrother;// 右边第一个兄弟节点
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;
}
// 得到根节点
public CNode<T> getRoot(CNode<T> t) {
while (t.parent != null) {
t = t.parent;
}
return t;
}
// 得到父节点
public CNode<T> getParent(CNode<T> t) {
if (t.parent != null) {
return t.parent;
}
return null;
}
// 得到子节点
public List<CNode<T>> getChildren(CNode<T> t) {
if (t.children != null) {
return t.children;
}
return null;
}
// 左节点
public CNode<T> getLeftBrother(CNode<T> t) {
if (t.leftBrother != null) {
return t.leftBrother;
}
return null;
}
// 右节点
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));
}
}
}
}
散列
散列也叫哈希,会遇到散列冲突问题,解决冲突最常用的是分离链接法,简单来说就是将散列到同一个值的所有元素都插入到一个链表中去,来实现吧.
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];//初始化链表数组
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--;
}
}
}
这里并没有考虑再散列,因为场景不复杂,再散列以后再谈.
还有一种散列表叫探测散列表,也以后再说...
堆
堆也叫优先队列,是允许至少下列两种操作的数据结构,插入和删除并返回最小值.插入(insert)相当于enqueue(入队),而删除最小值(deleteMin)则等价于队列运算dequeue(出队).
我们要讲的叫二叉堆,除了是一颗完整二叉树外还要保持其堆序性质.例如最小二叉堆即,最小元在根上,而任意节点都小于它的所有后裔.
我们通过代码模拟二叉堆
package com.fredal.structure;
public class MyHeap<T extends Comparable<? super T>> {
private static final int DEFAULT_CAPACITY=10;
private int currentSize;//堆元素数量
private T[] array;//堆数组
public MyHeap(){
this(DEFAULT_CAPACITY);
}
public MyHeap(int capacity){
currentSize=0;
array=(T[]) new Comparable[capacity+1];
}
//对已给定的数组建堆初始化
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]+" ");
}
}
}
堆的应用有许多,堆排序是最重要的之一,我们在后面会讲到.
更多文章与相关下载请看扩展阅读