面向对象的数组
import java.lang.reflect.Array;
import java.util.Arrays;
public class myArray {
private int[] elements;
public myArray(){
elements = new int[0];
}
//获取数组长度的方法
public void size(){
System.out.println(elements.length);
}
//给数组添加元素
public void add(int element){
//创建一个新的数组
int [] newArray = new int[elements.length+1];
//把原元素复制进入新的数组中
for (int i = 0;i<elements.length;i++){
newArray[i] = elements[i];
}
newArray[elements.length] = element;
elements = newArray;
}
public void show(){
System.out.println(Arrays.toString(elements));
}
//向数组中插入元素
public void insert(int index,int element){
int[] newArr = new int[elements.length+1];
for (int i = 0;i<elements.length;i++)
{
if (i<index){
newArr[i] = elements[i];
}
else{
newArr[i+1] = elements[i];
}
}
newArr[index] = element;
elements = newArr;
}
//删除数组中的某个下标的元素
public void delete(int index){
if(index<0 || index >= elements.length)
throw new RuntimeException("数组越界");
int[] newArr = new int[elements.length-1];
//复制原数组元素到新数组
for (int i = 0;i < newArr.length;i++){
if (i<index)
newArr[i] = elements[i];
else{
newArr[i] = elements[i+1];
}
}
elements = newArr;
}
//获取某个下标的元素
public int get(int index){
if(index < 0||index >= elements.length)
throw new RuntimeException("下标不存在");
return elements[index];
}}
这部分就是对数组的各个功能的实现，自己定义功能的实现。
算是java版本的数据结构的入门吧。
查找算法
线性查找
线性查找的优势在查找的数组不需要有顺序
缺点在于查找的效率低
二分查找
二分查找的优势在于，空间复杂度低，查找的效率更加高效
缺点在于查找的数组必须是有顺序的。
public class TestBinarySearch {
public static void main(String[] args) {
int[] arr = new int[] {1,2,3,4,5,6,7,8,9};
int target = 6;
int begin = 0;
int end = arr.length-1;
int mid = (begin+end)/2;
//记录目标元素
int index = -1;
while(true){
if (arr[mid] == target){
index = mid;
break;
}
else{
if (arr[mid]>target){
end = mid-1;
}
else{
begin = mid+1;
}
}
mid = (begin + end)/2;
}
System.out.println("index:"+index);
}}
栈
栈的结构是先进后出的模式进行的
我们需要的就是利用这样模式来进行我们的一些相关的计算或者存储
java代码的具体实现方法也是按照先进后出这个原则来进行
public class myStack {
//栈的底层我们用数组来存储数据
int[] elements;
public myStack(){
elements = new int[0];
}
//压入栈操作
public void push(int element){
int[] newArr = new int[elements.length+1];
for (int i = 0;i < elements.length;i++){
newArr[i] = elements[i];
}
newArr[elements.length] = element;
elements = newArr;
}
//出栈操作(实际上是删除的一种形式)
public int pop(){
if (elements.length == 0){
throw new RuntimeException("栈为空");
}
//取出数组的最后一个元素
int element = elements[elements.length-1];
int[] newArr = new int[elements.length-1];
for (int i = 0;i<newArr.length;i++){
newArr[i] = elements[i];
}
elements = newArr;
return element;
}}
入栈和出栈的操作有点类似于操作数组的添加和删除环节
只是注意是先进后出就可以。
队列
队列就好比一个管道，一边进另一边出去
比较容易理解
public class MyQueue {
int[] elements;
public MyQueue(){
elements = new int[0];
}
//入队操作(操作类似于数组的添加)
public void add(int element){
int[] newArr = new int[elements.length+1];
for (int i = 0;i < elements.length;i++){
newArr[i] = elements[i];
}
newArr[elements.length] = element;
elements = newArr;
}
//出队操作
public int pull(){
int element = elements[0];
int[] newArr = new int[elements.length-1];
for (int i= 0;i < newArr.length;i++){
newArr[i] = elements[i+1];
}
elements = newArr;
return element;
}
//判断队列是否为空
public boolean isEmpty(){
return elements.length == 0;
}
}
单链表
java版本的单链表不同于C/C++的单链表，在C语言中存在指针的概念，利用指针来进行链表的创建
在java中我们只能借助类来创建单链表，思想是差不多的但是这里我们就没有指针的思想，而是对象的思想来进行的。
public class Node {
int data;
//下一个节点
Node next;
public Node(int data){
this.data = data;
}
//为节点追加节点,目的在于连接到链表的洗后一个节点上去
public void append(Node node){
//当前节点
Node currentNode = this;
while(true){
Node nextNode = currentNode.next;
if(nextNode == null){
break;
}
//赋给当前节点
currentNode = nextNode;
}
//白需要追加的节点加在当前节点的下一个节点
currentNode.next = node;
}
//提取下一个节点
public Node next(){
return this.next;
}
//获取节点中的数据
public int getData(){
return this.data;
}
}
单链表节点的删除
这一小节还是要好好的研究一下，在java中想要删除某个节点和C语言中思想是差不都的，但是具体的实现方法可能需要我Java学习一下泛型有办法实现C语言那种删除。这个点有待学习。
单链表的插入
//插入一个节点
public void after(Node node){
Node nextNext = next;
this.next = node;
//把下下个节点设置为新节点的下个节点
node.next = nextNext;
}
这个插入只是基础版本的插入，还没有限制插入不合法的情况，这个的学习有点像是学习java jdk的开发，很是不错，可以了解java函数封装性吧
循环链表
循环链表的添加操作只需要修改这个便可以实现循环操作
Node next = this;
这个部分的讲解和学习不同于C/C++中的循环链表，，这个应该是基础功能的循环链表
双链表
循环双链表
package demo03;
public class DoubleNode {
//创建上一个节点
DoubleNode pre = this;
//创建下一个节点
DoubleNode next = this;
//存储我们的数据
int data;
public DoubleNode(int data){
this.data = data;
}
//增加节点
public void after(DoubleNode node){
//记录当前节点的下一个
DoubleNode nextNext = this.next;
//当前节点的下一个节点为新节点
this.next = node;
//新节点的上一个节点为当前节点
node.pre = this;
//让原来的下一个节点作为新节点的下一个节点
node.next = nextNext;
//让原来的下一个节点的删一个节点指向新节点
nextNext.pre = node;
}
//获取下一个节点
public DoubleNode next(){
return this.next;
}
//获取上一个节点
public DoubleNode pre(){
return this.pre;
}
//获取节点数据
public int getData(){
return this.data;
}}
循环双链表理解起来和C、C++中是相似的，但是java中条理更加清晰，便于理解。
递归
递归很占用内存，所以不太适合计算量比较大程序，尽量不要采用递归的算法来解决大数据的计算，不然计算的时间会很长。
斐波那契
public static int Febonacci(int i){
if (i == 1 || i == 2)
return 1;
else{
return Febonacci(i-1) + Febonacci(i-2);
}
当i的值太大的时候，这个函数计算的时间就非常的长
汉罗塔问题
汉诺塔问题确实很奇妙，是使用递归解决问题的一个好例子，但是理解起来需要有小技巧
总体都是分为两个部分
最大的一个盘子为一部分
其上的所有为一个部分
使用递归的算法解决这个问题就比较的容易
package demo03;
public class TestHannuo {
public static void main(String[] args) {
hannuo(5,'A','B','C');
}
//汉诺塔问题
/**
*
* @param n 代表盘子的数量
* @param from 开始的位置
* @param in 中间柱子
* @param to 目标柱子
*/
public static void hannuo(int n,char from,char in,char to){
if(n == 1){
System.out.println("第1个盘子从"+from+"移到"+to);
}
else{
//移动上面所有盘子到中间位置
hannuo(n-1,from,to,in);
//移动下面的盘子
System.out.println("第"+n+"个盘子从"+from+"移到"+to);
//把上面所有盘子从中间位置移动到目标位置
hannuo(n-1,in,from,to);
}
}}