Java实现的基础数据结构
0，常用的基础数据结构
文章图片
图1 基础数据结构&相关特性
文章图片
图2 Java自带的类集框架&继承关系图
1，数组【Array】
特点：长度固定、查找方便【直接使用index查找即可】、增加、删除麻烦。
文章图片
图3 数组【查找直接使用index指针即可直接查询】
文章图片
图4 数组添加【需要重新创建新数组对象并产生垃圾空间】
文章图片
图5 数组删除【需要重新创建新数组并且产生垃圾空间】
①创建实例化数组对象
1 public classDemo1_Array {2 public static voidmain(String[] args) {3 String [] array=new String[5];
//需要初始化长度
4 array[0]="hello";
5 array[1]="world";
6 array[4]="Mufasa";
7 //array[5]="right or not";
//ArrayIndexOutOfBoundsException
8 for(String str:array){9 System.out.print(str+"、");
//hello、world、null、null、Mufasa、
10 }11 }12 }
②对实例化数组进行扩容【利用Java反射机制】
1 public classDemo1_Array2 {2 public static voidmain(String[] args) {3 String [] array={"hello","world",null,null,"Mufasa"};
//实例化&赋值
4 array = (String[])resizeArray(array,10);
5 for(String str:array){6 System.out.print(str+"、");
//hello、world、null、null、Mufasa、
7 }8 }9
10 private static Object resizeArray(Object oldArray, int newSize) {//数组扩容！！！真麻烦，还利用反射机制来实现
11 int oldSize = java.lang.reflect.Array.getLength(oldArray);
//获取旧数组长度,向上转型！！！12 //int oldSize =oldArray.length;
//无法在此使用，因为array内容的是不定类型
13 Class elementType = oldArray.getClass().getComponentType();
//获取对象类别
14 Object newArray = java.lang.reflect.Array.newInstance(elementType,newSize);
//利用Java的反射机制实例化新数组
15 int preserveLength = Math.min(oldSize, newSize);
//判断是否需要copy数据
16 if (preserveLength > 0)17 System.arraycopy(oldArray, 0, newArray, 0, preserveLength);
18 return newArray;
//oldArray切断索引成为垃圾由Runtime.getRuntime().gc();
回收处理
19 }20 }
③数组删除与增添，本质上是创建新的数值并且copy数值【需要私有反射实例化新数组，这里需要进一步优化】
1 public classDemo1_Array4 {2 public static voidmain(String[] args) {3 String [] array=new String[5];
//需要初始化长度
4 array[0]="hello";
5 array[1]="world";
6 array[4]="Mufasa";
7 array=drop(array,3);
8 for(String str:array){9 System.out.print(str+"、");
//hello、world、null、null、Mufasa、
10 }11
12 }13 public static String[] drop(Object[] oldArray,int index){//删除指定位置上的元素
14 int size=java.lang.reflect.Array.getLength(oldArray);
15 if(index<0 || index>size) {16 throw new RuntimeException("删除索引范围有误");
17 }else{18 Class elementType = oldArray.getClass().getComponentType();
//获取对象类别
19 Object newArray = java.lang.reflect.Array.newInstance(elementType,size-1);
20 String[] newStringArray=(String[])newArray;
21 int counter=0;
22 for(int i=0;
i
④数组添加元素，本质也是创建新数组长度+1拷贝，index后移、赋值
1 public classDemo1_Array5 {2 public static voidmain(String[] args) {3 String [] array=new String[5];
//需要初始化长度
4 array[0]="hello";
5 array[1]="world";
6 array[4]="Mufasa";
7 array=add(array,3,"添加字符串");
8 for(String str:array){9 System.out.print(str+"、");
//hello、world、null、null、Mufasa、
10 }11
12 }13 public static String[] add(Object[] oldArray,int index,String str){//删除指定位置上的元素
14 int size=java.lang.reflect.Array.getLength(oldArray);
15 if(index<0 || index>size) {16 throw new RuntimeException("添加索引范围有误");
17 }else{18 Class elementType = oldArray.getClass().getComponentType();
//获取对象类别
19 Object newArray = java.lang.reflect.Array.newInstance(elementType,size+1);
20 String[] newStringArray=(String[])newArray;
21 int counter=0;
22 for(int i=0;
i
备注：当然也可以直接使用Java自带的类集框架中的ArrayList、Vector
1 importjava.util.ArrayList;
2 importjava.util.List;
3
4 public classDemo1_Array6 {5 public static voidmain(String[] args) {6 List array=new ArrayList<>();
//需要初始化长度
7 array.add("hello");
8 array.add("world");
9 //array.set(2,"Mufasa");
10 array.add("扩容！");
11 System.out.println(array.size());
12 for(String str:array){13 System.out.print(str+"、");
//hello、world、null、null、Mufasa、
14 }15 }16 }
Vector中方法使用sychronized修饰符，线程安全【与ArrayList的区别】；
2，链表【Linked List】
使用Node节点进行设计，功能：基本的setter、getter、add、getSize、remove等功能。
文章图片
图6 链表
文章图片
图7 链表增加【不用重新创建对象，不产生垃圾空间】
文章图片
图8 链表删除【①断开②重新建立链接】
1 classNode{2 private String str=null;
3 private Node nextNode=null;
4 publicNode(String str){5 this.str=str;
6 }7 public void add(Node nextNode){//先遍历到最后一个再添加
8 Node indexNode=this.nextNode;
9 while(true){10 if(indexNode.hasNext()==false){11 break;
12 }13 indexNode=indexNode.getNextNode();
14 }15 indexNode.setNextNode(nextNode);
16 }17 /*
18 public void add(Node nextNode,int index){//方法重载,指定位点上添加元素19 if(index==0){20 String str_mid=this.str;
21 this.str=nextNode.getStr();
22 this.nextNode.setStr(str_mid);
23 this.nextNode.setNextNode();
24 }25 Node indexNode=this.nextNode;
26 int size=1;
27 while(true){28 if(indexNode.hasNext()==false || size==index){29 break;
30 }31 size++;
//放在后面0开始32 indexNode=indexNode.getNextNode();
33 System.out.println("size:"+size+",元素："+indexNode.getStr());
34 }35 if(size
42
43 public intgetSize(){44 int size=0;
45 Node indexNode=this.nextNode;
46 while(true){47 size++;
48 if(indexNode.hasNext()==false){49 break;
50 }51 indexNode=indexNode.getNextNode();
52 }53 returnsize;
54 }55 public voidsetNextNode(Node nextNode) {56 this.nextNode =nextNode;
57 }58
59 publicNode getNextNode() {60 return this.nextNode;
61 }62
63 publicString getStr() {64 returnstr;
65 }66 public voidsetStr(String str){67 this.str=str;
68 }69 public booleanhasNext(){70 if(nextNode!=null){71 return true;
72 }else{73 return false;
74 }75 }76 }77
78 public classDemo2_LinkedList {79 public static voidmain(String[] args) {80 String[] array={"begin","1","2","3","4","5"};
81 Node rootNode=null;
82 Node indexNode=null;
83 boolean flag=true;
84 for(String str:array){85 if(flag){86 rootNode=newNode(str);
87 indexNode=rootNode;
88 flag=false;
89 }else{90 indexNode.setNextNode(newNode(str));
91 indexNode=indexNode.getNextNode();
92 }93 }94 rootNode.add(new Node("添加元素"),2);
95 indexNode=rootNode;
96 //System.out.println(rootNode.getSize());
97 while(true){98 System.out.println(indexNode.getStr());
99 if(indexNode.hasNext()==false){100 break;
101 }102 indexNode=indexNode.getNextNode();
103 }104 }105 }
3，栈【Stack】
先进后出的一种数据结构，解决方法：①双向链表，略；②数组后续遍历；
使用Vector数组构建Stack
1 importjava.util.List;
2 importjava.util.Vector;
3
4 class Stack_m{//使用泛型
5 private List stack=new Vector();
6 public voidpush(T t){7 stack.add(t);
8 }9 publicT pop(){10 int size=stack.size();
11 T mid;
12 mid=stack.get(size-1);
13 stack.remove(size-1);
14 returnmid;
15 }16 }17 public classDemo3_Stack {18 public static voidmain(String[] args) {19 Stack_m stack_m=newStack_m();
20 stack_m.push("hello");
21 stack_m.push("world");
22 stack_m.push("Mufasa");
23 stack_m.push("最后一个push");
24 for(int i=0;
i<4;
i++){25 System.out.println(stack_m.pop());
26 }27 }28 }
4，队列【Queue】
通用：先进先出，一端输入另一端输出；特殊：优先队列。
使用Vector实现通用队列
1 importjava.util.List;
2 importjava.util.Vector;
3
4 class Queue_m{5 private List stack=new Vector();
6 public voidadd(T t){7 stack.add(t);
8 }9 publicT offer(){10 int size=stack.size();
11 T mid;
12 mid=stack.get(0);
13 stack.remove(0);
14 returnmid;
15 }16 }17 public classDemo4_Queue {18 public static voidmain(String[] args) {19 Queue_m queue_m=newQueue_m();
20 queue_m.add("hello");
21 queue_m.add("world");
22 queue_m.add("Mufasa");
23 queue_m.add("最后一个push");
24 for(int i=0;
i<4;
i++){25 System.out.println(queue_m.offer());
26 }27 }28 }
使用Vector实现优先队列PriorityQueue【待：泛型这个还没处理好】
1 importjava.util.List;
2 importjava.util.Vector;
3
4 class Queue_m1{5 private List queue=new Vector();
6 public voidadd(T t){7 int index=0;
8 for(T temp:queue){9 }10 queue.add(t);
11 }12 publicT offer(){13 int size=queue.size();
14 T mid;
15 mid=queue.get(0);
16 queue.remove(0);
17 returnmid;
18 }19 //private boolean compareTo(T t1,T t2){//需要覆写compareTo20 //if()21 //return22 //}
23 }24
25 public classDemo4_PriorityQueue {26 public static voidmain(String[] args) {27 Queue_m queue_m=newQueue_m();
28 queue_m.add("hello");
29 queue_m.add("world");
30 queue_m.add("Mufasa");
31 queue_m.add("最后一个push");
32 for(int i=0;
i<4;
i++){33 System.out.println(queue_m.offer());
34 }35 }36 }
5，图【Graph】
图数据结构有两种表现形式：①邻接矩阵形式；②邻接表形式；
1 importjava.util.LinkedList;
2 importjava.util.Vector;
3
4 class Graph_m1{//有两种类型，类型1：邻接矩阵形式
5 private Vector> graph=new Vector>();
//叠加Vector，【行】为Vector，【列】为元素
6 private VectormidVector;
7 publicGraph_m1(){}8 public void add(Vector midVector){//方法重载
9 this.graph.add(midVector);
10 }11 public void add(int index1,Vector midVector){//方法重载
12 this.graph.add(index1,midVector);
13 }14 public void add(int index1, int t){//方法重载
15 midVector=graph.get(index1);
16 midVector.add(t);
17 graph.set(index1,midVector);
18 }19 public void add(int index1, int index2, int t){//方法重载
20 midVector=graph.get(index1);
21 midVector.add(index2,t);
22 graph.set(index1,midVector);
23 }24 public void set(int index1, int index2, intt){25 midVector=graph.get(index1);
26 midVector.set(index2,t);
27 graph.set(index1,midVector);
28 }29 public int get(int index1,intindex2){30 midVector=graph.get(index1);
31 returnmidVector.get(index2);
32 }33 public voidgetAll(){34 for(Vectortemp:graph){35 for(Integer temp1:temp){36 System.out.print(temp1+",");
37 }38 System.out.println("");
39 }40 }41 }42 class Graph_m2{//形式2：邻接表形式
43 private LinkedList> graph =new LinkedList>();
44 private LinkedListmidLinkedList;
45 //set，get，getAll方法
46 public void add(LinkedListmidLinkedList){47 this.graph.add(midLinkedList);
48 }49 public void add(int index1,LinkedListmidLinkedList){50 this.graph.add(index1,midLinkedList);
51 }52
53 public voidgetAll(){54 for(LinkedList temp:this.graph){55 for(T temp1:temp){56 System.out.print(temp1+",");
57 }58 System.out.println();
59 }60 }61 }62 public classDemo5_Graph {63 public static voidmain(String[] args) {64 Graph_m2 graph=newGraph_m2();
65 LinkedListlinkedList;
66 for(int i=0;
i<3;
i++){67 linkedList=new LinkedList();
68 for(int j=0;
j<5;
j++){69 linkedList.add(j+i);
70 }71 graph.add(linkedList);
72 }73 graph.getAll();
74 }75 }
6，树【Tree】
可以简单理解为一种特殊的不包含圈的单向图【发散型】。具体有：普通树、二叉树【最常用】、堆【heap】、哈夫曼树。
这里暂时只考虑二叉树的结构。
文章图片
图xx 二叉树
通用二叉树实现代码【使用Node】
1 classBinTree{2 privateString str;
3 privateBinTree leftTree;
4 privateBinTree rightTree;
5 publicBinTree(String str){6 this.str=str;
7 }8
9 public voidsetStr(String str) {10 this.str =str;
11 }12
13 public voidsetLeftTree(BinTree leftTree) {14 this.leftTree =leftTree;
15 }16
17 public voidsetRightTree(BinTree rightTree) {18 this.rightTree =rightTree;
19 }20
21 publicString getStr() {22 returnstr;
23 }24
25 publicBinTree getLeftTree() {26 returnleftTree;
27 }28
29 publicBinTree getRightTree() {30 returnrightTree;
31 }32
33 }34
35 public classDemo6_Tree {36 public static voidmain(String[] args) {37 BinTree rootTree=new BinTree("a");
38 rootTree.setLeftTree(new BinTree("b"));
39 rootTree.setRightTree(new BinTree("c"));
40
41 BinTree midTree=null;
42 midTree=rootTree.getLeftTree();
43 midTree.setLeftTree(new BinTree("d"));
44 midTree.setRightTree(new BinTree("e"));
45
46 midTree=rootTree.getRightTree();
47 midTree.setLeftTree(new BinTree("f"));
48 midTree.setRightTree(new BinTree("g"));
49 }50 }
7，堆【Heap】
文章图片
借用Java类集中的ArrayList实现Heap
1 importjava.util.ArrayList;
2
3 classHeap_m{4 private ArrayList arryList=new ArrayList();
5 private boolean type;
//true表示最大堆，false表示最小堆
6 private Integer mid_i;
//只是负责数据交换
7 public Heap_m(booleantype){8 this.type=type;
9 }10
11 public void add(inti){12 arryList.add(i);
13 shiftUp(this.arryList.size()-1);
14 }15 public int deletRoot(){//删除根节点并返回其值
16 int mid_root=this.arryList.get(0);
17 this.mid_i=this.arryList.get(this.arryList.size()-1);
18 this.arryList.remove(this.arryList.size()-1);
19 this.arryList.set(0,this.mid_i);
20 shiftDown(0);
21 returnmid_root;
22 }23 public int delet(int index){//删除指定index节点，并返回其值
24 if(index<0 || index>this.arryList.size()-1){25 throw new IndexOutOfBoundsException("删除节点index范围有误");
26 }27 int mid_value=https://www.it610.com/article/this.arryList.get(index);
28 this.mid_i=this.arryList.get(this.arryList.size()-1);
29 this.arryList.remove(this.arryList.size()-1);
30 this.arryList.set(index,this.mid_i);
31 shiftDown(index);
32 returnmid_value;
33 }34
35 private void shiftUp(int index){//添加数据的时候进行操作
36 if(type){//最大堆
37 if((index-1)/2!=-1){38 if(this.arryList.get((index - 1) / 2)
43 }44 }45 }else {//最小堆
46 if((index-1)/2!=-1){47 if(this.arryList.get((index - 1) / 2) >this.arryList.get(index)){48 mid_i=this.arryList.get((index - 1) / 2);
49 this.arryList.set((index - 1) / 2,this.arryList.get(index));
50 this.arryList.set(index,mid_i);
51 shiftUp((index - 1) / 2);
//递归调用
52 }53 }54 }55 }56
57 private void shiftDown(int index){//删除数据的时候进行操作
58 if(type){//最大堆
59 if(index*2+1 < this.arryList.size()){60 if(this.arryList.get(2*index+1) >this.arryList.get(index)){61 mid_i=this.arryList.get(2*index+1);
62 this.arryList.set(2*index+1,this.arryList.get(index));
63 this.arryList.set(index,mid_i);
64 shiftDown(2*index+1);
//递归调用
65 }66 }67 }else {//最小堆
68 if(index*2+1 < this.arryList.size()){69 if(this.arryList.get(2*index+1)
74 }75 }76 }77 }78
79 public ArrayListgetHeap_m() {80 return this.arryList;
81 }82 }83 public classDemo7_Heap {84 public static voidmain(String[] args) {85 //Heap_m heap_m=new Heap_m(true);
86 Heap_m heap_m=new Heap_m(false);
87 heap_m.add(5);
88 heap_m.add(10);
89 heap_m.add(1);
90 heap_m.add(7);
91 heap_m.add(2);
92 System.out.println(heap_m.getHeap_m());
93 System.out.println(heap_m.deletRoot());
94 System.out.println(heap_m.getHeap_m());
95 heap_m.delet(-1);
96 }97 }
8，散列表【Hash】
特点：仅支持插入、查找、删除
文章图片
文章图片
文章图片
文章图片
文章图片
拉链型HashTable
1 class HashTable_linked{//拉链型hashtable
2 privateNode[] values;
3 private intj;
4 public HashTable_linked(){//默认16长度，2的冥次方
5 this.values=new Node[16];
6 }7 public HashTable_linked(int length){//手动设置数据槽容量
8 this.values=newNode[length];
9 }10 public void insert(intkey,String value){11 this.j=hashCode(key);
12 if(this.values[j]==null){//为空就添加root节点
13 this.values[j]=newNode(value);
14 }else{15 this.values[j].add(newNode(value));
16 }17 }18 public Object search(int key){//通过key搜索某个元素
19 this.j=hashCode(key);
20 if(this.values[this.j]!=null){21 return this.values[this.j];
22 }else{23 return null;
24 }25 }26 private int hashCode(int key){//除余法散列函数h(k)=k%m
27 return key%this.values.length;
28 }29 }30
31 public classDemo8_HashTable {32 public static void main(String[] args) {//拉链型HashTable
33 HashTable_linked hashTable=new HashTable_linked(10);
34 hashTable.insert(11,"你好");
35 hashTable.insert(39,"世界");
36 hashTable.insert(22,"权利的游戏");
37 hashTable.insert(211,"努力奋斗");
38 hashTable.insert(211,"努力奋斗+1");
39 Node node=(Node)hashTable.search(211);
40 System.out.println(node.getStr());
41 System.out.println(node.getNextNode().getStr());
42 System.out.println(node.getNextNode().getNextNode().getStr());
43 }44 }
链表Node数据结构：
1 classNode{2 private String str=null;
3 private Node nextNode=null;
4 publicNode(String str){5 this.str=str;
6 }7 public void add(Node nextNode){//先遍历到最后一个再添加
8 Node indexNode=this;
//当前对象
9 while(true){10 if(indexNode.hasNext()==false){11 break;
12 }13 indexNode=indexNode.getNextNode();
14 }15 indexNode.setNextNode(nextNode);
16 }17 /*
18 public void add(Node nextNode,int index){//方法重载,指定位点上添加元素19 if(index==0){20 String str_mid=this.str;
21 this.str=nextNode.getStr();
22 this.nextNode.setStr(str_mid);
23 this.nextNode.setNextNode();
24 }25 Node indexNode=this.nextNode;
26 int size=1;
27 while(true){28 if(indexNode.hasNext()==false || size==index){29 break;
30 }31 size++;
//放在后面0开始32 indexNode=indexNode.getNextNode();
33 System.out.println("size:"+size+",元素："+indexNode.getStr());
34 }35 if(size
42
43 public intgetSize(){44 int size=0;
45 Node indexNode=this.nextNode;
46 while(true){47 size++;
48 if(indexNode.hasNext()==false){49 break;
50 }51 indexNode=indexNode.getNextNode();
52 }53 returnsize;
54 }55 public voidsetNextNode(Node nextNode) {56 this.nextNode =nextNode;
57 }58
59 publicNode getNextNode() {60 return this.nextNode;
61 }62
【java|java 基础数据结构_Java实现的基础数据结构】63 publicString getStr() {64 returnstr;
65 }66 public voidsetStr(String str){67 this.str=str;
68 }69 public booleanhasNext(){70 if(nextNode!=null){71 return true;
72 }else{73 return false;
74 }75 }76 }
推荐阅读
- 笔记|咖啡汪对敖丙老哥Java后端面试心得体会————阿里一面
- java|java 反射的概念
- 面试笔试|2022春招华为笔试题-（2）
- java|咸鱼疯传5W次，字节最新春招面试题泄露
- 数据挖掘分类算法--KNN
- 人工智能|收藏 | 计算机顶会论文投稿指南
- Java|docker化你的java应用（上）
- python|「薅羊毛」青龙定时面板——京东活动
- k8s|实战（本地存储-2022.3.1(更新版)）