Java实现的基础数据结构

0，常用的基础数据结构

图1 基础数据结构&相关特性

图2 Java自带的类集框架&继承关系图

1，数组【Array】

　　特点：长度固定、查找方便【直接使用index查找即可】、增加、删除麻烦。

图3 数组【查找直接使用index指针即可直接查询】

图4 数组添加【需要重新创建新数组对象并产生垃圾空间】

图5 数组删除【需要重新创建新数组并且产生垃圾空间】

　　①创建实例化数组对象

 public class Demo1_Array {

     public static void main(String[] args) {

         String [] array=new String[5];//需要初始化长度

         array[0]="hello";

         array[1]="world";

         array[4]="Mufasa";

 //        array[5]="right or not";//ArrayIndexOutOfBoundsException

         for(String str:array){

             System.out.print(str+"、");//hello、world、null、null、Mufasa、

         }

     }

 }

　　②对实例化数组进行扩容【利用Java反射机制】

 public class Demo1_Array2 {

     public static void main(String[] args) {

         String [] array={"hello","world",null,null,"Mufasa"};//实例化&赋值

         array = (String[])resizeArray(array,10);

         for(String str:array){

             System.out.print(str+"、");//hello、world、null、null、Mufasa、

         }

     }

     private static Object resizeArray(Object oldArray, int newSize) {//数组扩容！！！真麻烦，还利用反射机制来实现

         int oldSize = java.lang.reflect.Array.getLength(oldArray);//获取旧数组长度,向上转型！！！

 //        int oldSize =oldArray.length;//无法在此使用，因为array内容的是不定类型

         Class elementType = oldArray.getClass().getComponentType();//获取对象类别

         Object newArray = java.lang.reflect.Array.newInstance(elementType,newSize);//利用Java的反射机制实例化新数组

         int preserveLength = Math.min(oldSize, newSize);//判断是否需要copy数据

         if (preserveLength > 0)

             System.arraycopy(oldArray, 0, newArray, 0, preserveLength);

         return newArray;//oldArray切断索引成为垃圾由Runtime.getRuntime().gc();回收处理

     }

 }

　　③数组删除与增添，本质上是创建新的数值并且copy数值【需要私有反射实例化新数组，这里需要进一步优化】

 public class Demo1_Array4 {

     public static void main(String[] args) {

         String [] array=new String[5];//需要初始化长度

         array[0]="hello";

         array[1]="world";

         array[4]="Mufasa";

         array=drop(array,3);

         for(String str:array){

             System.out.print(str+"、");//hello、world、null、null、Mufasa、

         }

     }

     public static String[] drop(Object[] oldArray,int index){//删除指定位置上的元素

         int size= java.lang.reflect.Array.getLength(oldArray);

         if(index<0 || index>size) {

             throw new RuntimeException("删除索引范围有误");

         }else {

             Class elementType = oldArray.getClass().getComponentType();//获取对象类别

             Object newArray = java.lang.reflect.Array.newInstance(elementType,size-1);

             String[] newStringArray=(String[])newArray;

             int counter=0;

             for(int i=0;i<oldArray.length;i++){

                 if(i!=index){

                     newStringArray[counter]= (String) oldArray[i];

                     counter++;

                 }else {

                     continue;

                 }

             }

             return newStringArray;

         }

     }

 }

　　④数组添加元素，本质也是创建新数组长度+1拷贝，index后移、赋值

 public class Demo1_Array5 {

     public static void main(String[] args) {

         String [] array=new String[5];//需要初始化长度

         array[0]="hello";

         array[1]="world";

         array[4]="Mufasa";

         array=add(array,3,"添加字符串");

         for(String str:array){

             System.out.print(str+"、");//hello、world、null、null、Mufasa、

         }

     }

     public static String[] add(Object[] oldArray,int index,String str){//删除指定位置上的元素

         int size= java.lang.reflect.Array.getLength(oldArray);

         if(index<0 || index>size) {

             throw new RuntimeException("添加索引范围有误");

         }else {

             Class elementType = oldArray.getClass().getComponentType();//获取对象类别

             Object newArray = java.lang.reflect.Array.newInstance(elementType,size+1);

             String[] newStringArray=(String[])newArray;

             int counter=0;

             for(int i=0;i<oldArray.length;i++){

                 if(i!=index){

                     newStringArray[counter]= (String) oldArray[i];

                     counter++;

                 }else {

                     newStringArray[counter]= (String) oldArray[i];

                     counter++;

                     newStringArray[counter]=str;

                     counter++;

                 }

             }

             return newStringArray;

         }

     }

 }

　　备注：当然也可以直接使用Java自带的类集框架中的ArrayList、Vector

 import java.util.ArrayList;

 import java.util.List;

 public class Demo1_Array6 {

     public static void main(String[] args) {

         List<String> array=new ArrayList<>();//需要初始化长度

         array.add("hello");

         array.add("world");

 //        array.set(2,"Mufasa");

         array.add("扩容！");

         System.out.println(array.size());

         for(String str:array){

             System.out.print(str+"、");//hello、world、null、null、Mufasa、

         }

     }

 }

　　Vector中方法使用sychronized修饰符，线程安全【与ArrayList的区别】；

2，链表【Linked List】

　　使用Node节点进行设计，功能：基本的setter、getter、add、getSize、remove等功能。

图6 链表

图7 链表增加【不用重新创建对象，不产生垃圾空间】

图8 链表删除【①断开②重新建立链接】

 class Node{

     private String str=null;

     private Node nextNode=null;

     public Node(String str){

         this.str=str;

     }

     public void add(Node nextNode){//先遍历到最后一个再添加

         Node indexNode=this.nextNode;

         while(true){

             if(indexNode.hasNext()==false){

                 break;

             }

             indexNode=indexNode.getNextNode();

         }

         indexNode.setNextNode(nextNode);

     }

     /*

     public void add(Node nextNode,int index){//方法重载,指定位点上添加元素

         if(index==0){

             String str_mid=this.str;

             this.str=nextNode.getStr();

             this.nextNode.setStr(str_mid);

             this.nextNode.setNextNode();

         }

         Node indexNode=this.nextNode;

         int size=1;

         while(true){

             if(indexNode.hasNext()==false || size==index){

                 break;

             }

             size++;//放在后面0开始

             indexNode=indexNode.getNextNode();

             System.out.println("size:"+size+",元素："+indexNode.getStr());

         }

         if(size<index){

             throw new RuntimeException("添加元素索引超出范围");

         }else {

             nextNode.setNextNode(indexNode.getNextNode());//先在新节点后加入

             indexNode.setNextNode(nextNode);//后在前面节点加入新节点

         }

     }*/

     public int getSize(){

         int size=0;

         Node indexNode=this.nextNode;

         while(true){

             size++;

             if(indexNode.hasNext()==false){

                 break;

             }

             indexNode=indexNode.getNextNode();

         }

         return size;

     }

     public void setNextNode(Node nextNode) {

         this.nextNode = nextNode;

     }

     public Node getNextNode() {

         return this.nextNode;

     }

     public String getStr() {

         return str;

     }

     public void setStr(String str){

         this.str=str;

     }

     public boolean hasNext(){

         if(nextNode!=null){

             return true;

         }else {

             return false;

         }

     }

 }

 public class Demo2_LinkedList {

     public static void main(String[] args) {

         String[] array={"begin","1","2","3","4","5"};

         Node rootNode=null;

         Node indexNode=null;

         boolean flag=true;

         for(String str:array){

             if(flag){

                 rootNode=new Node(str);

                 indexNode=rootNode;

                 flag=false;

             }else {

                 indexNode.setNextNode(new Node(str));

                 indexNode=indexNode.getNextNode();

             }

         }

         rootNode.add(new Node("添加元素"),2);

         indexNode=rootNode;

 //        System.out.println(rootNode.getSize());

         while(true){

             System.out.println(indexNode.getStr());

             if(indexNode.hasNext()==false){

                 break;

             }

             indexNode=indexNode.getNextNode();

         }

     }

 }

3，栈【Stack】

　　先进后出的一种数据结构，解决方法：①双向链表，略；②数组后续遍历；

　　使用Vector数组构建Stack

 import java.util.List;

 import java.util.Vector;

 class Stack_m<T>{//使用泛型

     private List<T> stack=new Vector<T>();

     public void push(T t){

         stack.add(t);

     }

     public T pop(){

         int size=stack.size();

         T mid;

         mid=stack.get(size-1);

         stack.remove(size-1);

         return mid;

     }

 }

 public class Demo3_Stack {

     public static void main(String[] args) {

         Stack_m stack_m=new Stack_m();

         stack_m.push("hello");

         stack_m.push("world");

         stack_m.push("Mufasa");

         stack_m.push("最后一个push");

         for(int i=0;i<4;i++){

             System.out.println(stack_m.pop());

         }

     }

 }

4，队列【Queue】

　　通用：先进先出，一端输入另一端输出；特殊：优先队列。

　　使用Vector实现通用队列

 import java.util.List;

 import java.util.Vector;

 class Queue_m<T>{

     private List<T> stack=new Vector<T>();

     public void add(T t){

         stack.add(t);

     }

     public T offer(){

         int size=stack.size();

         T mid;

         mid=stack.get(0);

         stack.remove(0);

         return mid;

     }

 }

 public class Demo4_Queue {

     public static void main(String[] args) {

         Queue_m queue_m=new Queue_m();

         queue_m.add("hello");

         queue_m.add("world");

         queue_m.add("Mufasa");

         queue_m.add("最后一个push");

         for(int i=0;i<4;i++){

             System.out.println(queue_m.offer());

         }

     }

 }

　　使用Vector实现优先队列PriorityQueue【待：泛型这个还没处理好】

 import java.util.List;

 import java.util.Vector;

 class Queue_m1<T>{

     private List<T> queue=new Vector<T>();

     public void add(T t){

         int index=0;

         for(T temp:queue){

         }

             queue.add(t);

     }

     public T offer(){

         int size=queue.size();

         T mid;

         mid=queue.get(0);

         queue.remove(0);

         return mid;

     }

 //    private boolean compareTo(T t1,T t2){//需要覆写compareTo

 //        if()

 //        return

 //    }

 }

 public class Demo4_PriorityQueue {

     public static void main(String[] args) {

         Queue_m queue_m=new Queue_m();

         queue_m.add("hello");

         queue_m.add("world");

         queue_m.add("Mufasa");

         queue_m.add("最后一个push");

         for(int i=0;i<4;i++){

             System.out.println(queue_m.offer());

         }

     }

 }

5，图【Graph】

　　图数据结构有两种表现形式：①邻接矩阵形式；②邻接表形式；

 import java.util.LinkedList;

 import java.util.Vector;

 class Graph_m1{//有两种类型，类型1：邻接矩阵形式

     private Vector<Vector<Integer>> graph=new Vector<Vector<Integer>>();//叠加Vector，【行】为Vector，【列】为元素

     private Vector<Integer> midVector;

     public Graph_m1(){}

     public void add(Vector<Integer> midVector){//方法重载

         this.graph.add(midVector);

     }

     public void add(int index1,Vector<Integer> midVector){//方法重载

         this.graph.add(index1,midVector);

     }

     public void add(int index1, int t){//方法重载

         midVector=graph.get(index1);

         midVector.add(t);

         graph.set(index1,midVector);

     }

     public void add(int index1, int index2, int t){//方法重载

         midVector=graph.get(index1);

         midVector.add(index2,t);

         graph.set(index1,midVector);

     }

     public void set(int index1, int index2, int t){

         midVector=graph.get(index1);

         midVector.set(index2,t);

         graph.set(index1,midVector);

     }

     public int get(int index1,int index2){

         midVector=graph.get(index1);

         return midVector.get(index2);

     }

     public void getAll(){

         for(Vector<Integer> temp:graph){

             for(Integer temp1:temp){

                 System.out.print(temp1+",");

             }

             System.out.println("");

         }

     }

 }

 class Graph_m2<T>{//形式2：邻接表形式

     private LinkedList<LinkedList<T>> graph =new LinkedList<LinkedList<T>>();

     private LinkedList<T> midLinkedList;

     //set，get，getAll方法

     public void add(LinkedList<T> midLinkedList){

         this.graph.add(midLinkedList);

     }

     public void add(int index1,LinkedList<T> midLinkedList){

         this.graph.add(index1,midLinkedList);

     }

     public void getAll(){

         for(LinkedList<T> temp:this.graph){

             for(T temp1:temp){

                 System.out.print(temp1+",");

             }

             System.out.println();

         }

     }

 }

 public class Demo5_Graph {

     public static void main(String[] args) {

         Graph_m2 graph=new Graph_m2();

         LinkedList<Integer> linkedList;

         for(int i=0;i<3;i++){

             linkedList=new LinkedList<Integer>();

             for(int j=0;j<5;j++){

                 linkedList.add(j+i);

             }

             graph.add(linkedList);

         }

         graph.getAll();

     }

 }

6，树【Tree】

　　可以简单理解为一种特殊的不包含圈的单向图【发散型】。具体有：普通树、二叉树【最常用】、堆【heap】、哈夫曼树。

　　这里暂时只考虑二叉树的结构。

图xx 二叉树

通用二叉树实现代码【使用Node】

 class BinTree{

     private String str;

     private BinTree leftTree;

     private BinTree rightTree;

     public BinTree(String str){

         this.str=str;

     }

     public void setStr(String str) {

         this.str = str;

     }

     public void setLeftTree(BinTree leftTree) {

         this.leftTree = leftTree;

     }

     public void setRightTree(BinTree rightTree) {

         this.rightTree = rightTree;

     }

     public String getStr() {

         return str;

     }

     public BinTree getLeftTree() {

         return leftTree;

     }

     public BinTree getRightTree() {

         return rightTree;

     }

 }

 public class Demo6_Tree {

     public static void main(String[] args) {

         BinTree rootTree=new BinTree("a");

         rootTree.setLeftTree(new BinTree("b"));

         rootTree.setRightTree(new BinTree("c"));

         BinTree midTree=null;

         midTree=rootTree.getLeftTree();

         midTree.setLeftTree(new BinTree("d"));

         midTree.setRightTree(new BinTree("e"));

         midTree=rootTree.getRightTree();

         midTree.setLeftTree(new BinTree("f"));

         midTree.setRightTree(new BinTree("g"));

     }

 }

7，堆【Heap】

借用Java类集中的ArrayList实现Heap

 import java.util.ArrayList;

 class Heap_m{

     private ArrayList<Integer> arryList=new ArrayList<Integer>();

     private boolean type;//true表示最大堆，false表示最小堆

     private Integer mid_i;//只是负责数据交换

     public Heap_m(boolean type){

         this.type=type;

     }

     public void add(int i){

         arryList.add(i);

         shiftUp(this.arryList.size()-1);

     }

     public int deletRoot(){//删除根节点并返回其值

         int mid_root=this.arryList.get(0);

         this.mid_i=this.arryList.get(this.arryList.size()-1);

         this.arryList.remove(this.arryList.size()-1);

         this.arryList.set(0,this.mid_i);

         shiftDown(0);

         return mid_root;

     }

     public int delet(int index){//删除指定index节点，并返回其值

         if(index<0 || index>this.arryList.size()-1){

             throw new IndexOutOfBoundsException("删除节点index范围有误");

         }

         int mid_value=this.arryList.get(index);

         this.mid_i=this.arryList.get(this.arryList.size()-1);

         this.arryList.remove(this.arryList.size()-1);

         this.arryList.set(index,this.mid_i);

         shiftDown(index);

         return mid_value;

     }

     private void shiftUp(int index){//添加数据的时候进行操作

         if(type){//最大堆

             if((index-1)/2!=-1){

                 if(this.arryList.get((index - 1) / 2) <this.arryList.get(index)){

                     mid_i=this.arryList.get((index - 1) / 2);

                     this.arryList.set((index - 1) / 2,this.arryList.get(index));

                     this.arryList.set(index,mid_i);

                     shiftUp((index - 1) / 2);//递归调用

                 }

             }

         }else {//最小堆

             if((index-1)/2!=-1){

                 if(this.arryList.get((index - 1) / 2) >this.arryList.get(index)){

                     mid_i=this.arryList.get((index - 1) / 2);

                     this.arryList.set((index - 1) / 2,this.arryList.get(index));

                     this.arryList.set(index,mid_i);

                     shiftUp((index - 1) / 2);//递归调用

                 }

             }

         }

     }

     private void shiftDown(int index){//删除数据的时候进行操作

         if(type){//最大堆

             if(index*2+1 < this.arryList.size()){

                 if(this.arryList.get(2*index+1) >this.arryList.get(index)){

                     mid_i=this.arryList.get(2*index+1);

                     this.arryList.set(2*index+1,this.arryList.get(index));

                     this.arryList.set(index,mid_i);

                     shiftDown(2*index+1);//递归调用

                 }

             }

         }else {//最小堆

             if(index*2+1 < this.arryList.size()){

                 if(this.arryList.get(2*index+1) <this.arryList.get(index)){

                     mid_i=this.arryList.get(2*index+1);

                     this.arryList.set(2*index+1,this.arryList.get(index));

                     this.arryList.set(index,mid_i);

                     shiftDown(2*index+1);//递归调用

                 }

             }

         }

     }

     public ArrayList<Integer> getHeap_m() {

         return this.arryList;

     }

 }

 public class Demo7_Heap {

     public static void main(String[] args) {

 //        Heap_m heap_m=new Heap_m(true);

         Heap_m heap_m=new Heap_m(false);

         heap_m.add(5);

         heap_m.add(10);

         heap_m.add(1);

         heap_m.add(7);

         heap_m.add(2);

         System.out.println(heap_m.getHeap_m());

         System.out.println(heap_m.deletRoot());

         System.out.println(heap_m.getHeap_m());

         heap_m.delet(-1);

     }

 }

8，散列表【Hash】

　　特点：仅支持插入、查找、删除

拉链型HashTable

 class HashTable_linked{//拉链型hashtable

     private Node[] values;

     private int j;

     public HashTable_linked(){//默认16长度，2的冥次方

         this.values=new Node[16];

     }

     public HashTable_linked(int length){//手动设置数据槽容量

         this.values=new Node[length];

     }

     public void insert(int key,String value){

         this.j=hashCode(key);

         if(this.values[j]==null){//为空就添加root节点

             this.values[j]=new Node(value);

         }else {

             this.values[j].add(new Node(value));

         }

     }

     public Object search(int key){//通过key搜索某个元素

         this.j=hashCode(key);

         if(this.values[this.j]!=null){

             return this.values[this.j];

         }else{

             return null;

         }

     }

     private int hashCode(int key){//除余法散列函数h(k)=k%m

         return key%this.values.length;

     }

 }

 public class Demo8_HashTable {

     public static void main(String[] args) {//拉链型HashTable

         HashTable_linked hashTable=new HashTable_linked(10);

         hashTable.insert(11,"你好");

         hashTable.insert(39,"世界");

         hashTable.insert(22,"权利的游戏");

         hashTable.insert(211,"努力奋斗");

         hashTable.insert(211,"努力奋斗+1");

         Node node=(Node)hashTable.search(211);

         System.out.println(node.getStr());

         System.out.println(node.getNextNode().getStr());

         System.out.println(node.getNextNode().getNextNode().getStr());

     }

 }

链表Node数据结构：

 class Node{

     private String str=null;

     private Node nextNode=null;

     public Node(String str){

         this.str=str;

     }

     public void add(Node nextNode){//先遍历到最后一个再添加

         Node indexNode=this;//当前对象

         while(true){

             if(indexNode.hasNext()==false){

                 break;

             }

             indexNode=indexNode.getNextNode();

         }

         indexNode.setNextNode(nextNode);

     }

     /*

     public void add(Node nextNode,int index){//方法重载,指定位点上添加元素

         if(index==0){

             String str_mid=this.str;

             this.str=nextNode.getStr();

             this.nextNode.setStr(str_mid);

             this.nextNode.setNextNode();

         }

         Node indexNode=this.nextNode;

         int size=1;

         while(true){

             if(indexNode.hasNext()==false || size==index){

                 break;

             }

             size++;//放在后面0开始

             indexNode=indexNode.getNextNode();

             System.out.println("size:"+size+",元素："+indexNode.getStr());

         }

         if(size<index){

             throw new RuntimeException("添加元素索引超出范围");

         }else {

             nextNode.setNextNode(indexNode.getNextNode());//先在新节点后加入

             indexNode.setNextNode(nextNode);//后在前面节点加入新节点

         }

     }*/

     public int getSize(){

         int size=0;

         Node indexNode=this.nextNode;

         while(true){

             size++;

             if(indexNode.hasNext()==false){

                 break;

             }

             indexNode=indexNode.getNextNode();

         }

         return size;

     }

     public void setNextNode(Node nextNode) {

         this.nextNode = nextNode;

     }

     public Node getNextNode() {

         return this.nextNode;

     }

     public String getStr() {

         return str;

     }

     public void setStr(String str){

         this.str=str;

     }

     public boolean hasNext(){

         if(nextNode!=null){

             return true;

         }else {

             return false;

         }

     }

 }

巴特西

Java实现的基础数据结构

Java实现的基础数据结构

0，常用的基础数据结构

1，数组【Array】

备注：当然也可以直接使用Java自带的类集框架中的ArrayList、Vector

2，链表【Linked List】

3，栈【Stack】

4，队列【Queue】

5，图【Graph】

6，树【Tree】

7，堆【Heap】

8，散列表【Hash】

最新文章

热门文章