Java教程
Java数据结构与算法
本文主要是介绍Java数据结构与算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
目录
数据结构
线性结构
非线性结构
稀疏数组和队列
基本介绍
二维数组 转 稀疏数组的思路
稀疏数组 转 原始的二维数组的思路
稀疏数组的代码实现
运行结果
队列
数组模拟队列
代码实现
运行结果
问题分析并优化
思路分析
数组模拟环形队列实现
运行结果
单链表介绍和内存布局
链表(Linked List)介绍
小结
单链表的应用实例
head节点
添加(创建)
遍历
单链表创建和遍历的分析实现
运行结果
单链表按顺序插入节点
单链表的节点的修改
完整代码
运行结果
数据结构
数据结构包括 线性结构和非线性结构
线性结构
1)线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
2)线性结构有两种不同的存储结构，即顺序存储结构(数组)和链式存储结构(链表)。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的
3)链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
4)线性结构常见的有 数组、队列、链表和栈。
非线性结构
非线性结构包括： 二维数组、多维数组、广义表，树结构，图结构。
稀疏数组和队列
基本介绍
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
1)记录数组一共有几行几列，有多少个不同的值
2)把具有不同值得的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
二维数组 转 稀疏数组的思路
1.遍历 原始的二维数组，得到有效数据的个数
2.根据sum 就可以创建稀疏数组sparseArr int[sum+1][3]
3.将二维数组的有效数据数据存入到稀疏数组
稀疏数组 转 原始的二维数组的思路
1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2=int[11][11]
2.在读取稀疏数组后几行的数据，并赋给 原始的二维数组即可。
稀疏数组的代码实现
package com.atguigu.sparsearray;
public class SparseArray {
public static void main(String[] args) {
//创建一个原始的二维数组11*11
//0:表示没有棋子，1表示黑子 2表蓝子
int chessArr1[][]=new int[11][11];
chessArr1[1][2]=1;
chessArr1[2][3]=2;
chessArr1[4][5]=2;
//输出原始的二维数组
System.out.println("原始的二维数组~~");
for (int[] row:chessArr1) {
for(int data:row) {
System.out.printf("%d\t",data);
}
System.out.println();
}
//将二维数组 转 稀疏数组的思路
//1.先遍历二维数组 得到非0数据的个数
int sum=0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j <11; j++) {
if (chessArr1[i][j]!=0) {
sum++;
}
}
}
//2.创建对应的稀疏函数
int sparseArr[][]=new int[sum+1][3];
//给稀疏数组赋值
sparseArr[0][0]=11;
sparseArr[0][1]=11;
sparseArr[0][2]=11;
//遍历二维数组，将非0的值存放到sparseArr中
int count=0;//count用于记录是第几个非0数据
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr1[i][j]!=0) {
count++;
sparseArr[count][0]=i;
sparseArr[count][1]=j;
sparseArr[count][2]=chessArr1[i][j];
}
}
}
//输出稀疏数组的形式
System.out.println();
System.out.println("得到稀疏数组为~~~");
for (int i = 0; i < sparseArr.length; i++) {
System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
}
System.out.println();
//将稀疏数组-->恢复成 原始的二维数组
/*
* 1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的chessArr1=int
* 2.在读取稀疏数组后几行的数据，并赋给原始的二维数组即可。
* */
//1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
int chessArr2[][]=new int[sparseArr[0][0]][sparseArr[0][1]];
//2.在读取稀疏数组后几行的数据(从第二行开始)，并赋给原始的二维数组即可。
for (int i = 0; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
}
//输出恢复后的二维数组
System.out.println();
System.out.println("恢复后的二维数组");
for (int[] row:chessArr1) {
for (int data:row) {
System.out.printf("%d\t",data);
}
System.out.println();
}
}
}
运行结果
队列
队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即:先存入队列的数据，要先取出。后存入的要后取出。
示意图：(使用数组模拟队列示意图)
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如上图，其中maxSize是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变。
数组模拟队列
当我们将数据存入队列时称为"addQueue",addQueue的处理需要有两个步骤:思路分析
1)将尾指针往后移:rear+1,当front==rear【空】
2)若尾指针rear小于队列的最大下标maxSize-1,则将数据存入rear所指的数组元素中，否则无法存入数据。rear==maxSize-1[队列满]
class ArrayQueue(arrMaxSize:int){
maxSize:int=arrMaxSize
val array=new Array[int](arrMaxSize)
val front:int=-1;
val rear:int=-1;
}
//初始化
val queue=new ArrayQueue(3);
1.rear是队列最后[含]
2.front是队列最前元素[不含]
代码实现
package queue;
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
//测试一把
//创建一个队列
ArrayQueue queue=new ArrayQueue(3);
char key=' ';//接收用户输入
Scanner scanner=new Scanner(System.in);
boolean loop=true;
//输出一个菜单
while (loop) {
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列取出数据");
System.out.println("h(head):查看队列头的数据");
key=scanner.next().charAt(0);//接收一个字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("输出一个数");
int value=scanner.nextInt();
queue.addQueue(value);
break;
case 'g'://取出数据
try {
int res=queue.getQueue();
System.out.printf("取出数据是%d\n",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h'://查看队列头的数据
try {
int res=queue.headQueue();
System.out.printf("队列头的数据是%d\n",res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e'://退出
scanner.close();
loop=false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
//使用数组模拟队列-编写一个ArrayQueue类
class ArrayQueue{
private int maxSize;//表示数组的最大容量
private int front;//队列头
private int rear;//队列尾
private int[] arr;//该数据用于存放数据，模拟队列
//创建队列的构造器
public ArrayQueue(int arrMaxSize) {
maxSize=arrMaxSize;
arr=new int[maxSize];
front=-1;//指向队列头部，分析出front是指向队列头的前一个位置
rear=-1;//指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
}
//判断队列是否满
public boolean isFull() {
return rear==maxSize-1;
}
//判断队列是否为空
public boolean isEmpty() {
return rear==front;
}
//添加数据到队列
public void addQueue(int n) {
//判断队列是否满
if (isFull()) {
System.out.println("队列满，不能加入数据~");
return;
}
rear++;//让rear后移
arr[rear]=n;
}
//获取队列的数据，出队列
public int getQueue() {
//判断队列是否空
if (isEmpty()) {
//通过抛出异常
throw new RuntimeException("队列空,不能取数据");
}
front++;//front后移
return arr[front];
}
//显示队列的所有数据
public void showQueue() {
//遍历
if (isEmpty()) {
System.out.println("队列空的,没有数据~~");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n",i,arr[i]);
}
}
//显示队列的头数据，注意不是取出数据
public int headQueue() {
//判断
if (isEmpty()) {
throw new RuntimeException("队列空的，没有数据~~");
}
return arr[front+1];
}
}
运行结果
问题分析并优化
1)目前数组使用一次就不能用，没有达到复用的效果
2)将这个数组使用算法，改进成一个环形的队列 取模:%
思路分析
1.front变量的含义做一个调整:front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素
2.rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定。rear的初始值=0
3.当队列满时，条件是(rear+1)%=front【满】
4.对队列为空的条件，rear==front空
5.当我们这样分析，队列中有效的数据的个数(rear+maxSize-front)%maxSize//rear=1 front=0
6.我们就可以在原来的队列上修改得到，一个环形队列
数组模拟环形队列实现
package queue;
import java.util.Scanner;
public class CircleArrayQueueDemo {
public static void main(String[] args) {
//测试一把
//创建一个环形队列
CircleArray queue=new CircleArray(4);//说明设置4，其队列的有效数据最大是3
char key=' ';//接收用户输入
Scanner scanner=new Scanner(System.in);
boolean loop=true;
//输出一个菜单
while (loop) {
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列取出数据");
System.out.println("h(head):查看队列头的数据");
key=scanner.next().charAt(0);//接收一个字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("输出一个数");
int value=scanner.nextInt();
queue.addQueue(value);
break;
case 'g'://取出数据
try {
int res=queue.getQueue();
System.out.printf("取出数据是%d\n",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h'://查看队列头的数据
try {
int res=queue.headQueue();
System.out.printf("队列头的数据是%d\n",res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e'://退出
scanner.close();
loop=false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
class CircleArray{
private int maxSize;//表示数组的最大容量
//front变量的含义做一个调整:front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素
//rear的初始值=0
private int front;//队列头
//rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定。
//rear的初始值=0
private int rear;//队列尾
private int[] arr;//该数据用于存放数据，模拟队列
public CircleArray(int arrMaxSize) {
maxSize=arrMaxSize;
arr=new int[maxSize];
}
//判断队列是否满
public boolean isFull() {
return (rear+1)%maxSize==front;
}
//判断队列是否为空
public boolean isEmpty() {
return rear==front;
}
//添加数据到队列
public void addQueue(int n) {
//判断队列是否满
if (isFull()) {
System.out.println("队列满，不能加入数据~");
return;
}
//直接将数据加入
arr[rear]=n;
//将rear后移，这里必须考虑取模
rear=(rear+1)%maxSize;
}
//获取队列的数据，出队列
public int getQueue() {
//判断队列是否空
if (isEmpty()) {
//通过抛出异常
throw new RuntimeException("队列空,不能取数据");
}
//这里需要分析出front是指向队列的第一个元素
//1.先把front对应的值保留到一个临时变量
//2.将front后移
//3.将临时保存的变量返回
int value=arr[front];
front=(front+1)%maxSize;
return value;
}
//显示队列所有的数据
public void showQueue() {
//遍历
if (isEmpty()) {
System.out.println("队列空的，没有数据~~");
return;
}
//思路：从front开始遍历，遍历多少个元素
//动脑筋
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}
//求出当前队列有效数据的个数
public int size() {
//rear=1
//front=0
//maxSize=3
return (rear+maxSize-front)%maxSize;
}
//显示队列的头数据，注意不是取出数据
public int headQueue() {
//判断
if (isEmpty()) {
throw new RuntimeException("队列空的，没有数据~~");
}
return arr[front];
}
}
运行结果
单链表介绍和内存布局
链表(Linked List)介绍
链表是有序的列表，但是它在内存中是存储如下
小结
1)链表是以节点的方式来存储，是链式存储
2)每个节点包含data域，next域:指向下一个节点
3)如图:发现链表的各个节点不一定是连续存放
4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
单链表的应用实例
head节点
1.不存放具体的数据
2.作用就是表示单链表头next
添加(创建)
1.先创建一个head头节点，作用就是表示单链表的头
2.后面我们每添加一个节点，就直接加入到链表的最后
遍历
1.通过一个辅助变量遍历，帮助遍历整个链表
单链表创建和遍历的分析实现
package linkedlist;
public class SingleLinkedListDemo {
public static void main(String[] args) {
//进行测试
//先创建节点
HeroNode hero1=new HeroNode(1, "宋江", "及时雨");
HeroNode hero2=new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3=new HeroNode(3, "吴用", "智多星");
HeroNode hero4=new HeroNode(4, "林冲", "豹子头");
//创建要给链表
SingleLinkedList singleLinkedList=new SingleLinkedList();
//加入
singleLinkedList.add(hero1);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
singleLinkedList.add(hero4);
//显示一把
singleLinkedList.list();
}
}
//定义SingleLinkedList 管理我们的英雄
class SingleLinkedList{
//先初始化一个头节点，头节点不要动,不存放具体的数据
private HeroNode head=new HeroNode(0, "","");
//添加节点到单向链表
//思路，当不考虑编号顺序时
//1.找到当前链表的最后节点
//2.将最后这个节点的next指向新的节点
public void add(HeroNode heroNode) {
//因为head节点不能动，因此我们需要一个辅助遍历temp
HeroNode temp=head;
//遍历链表，找到最后
while (true) {
//找到链表的最后
if (temp.next==null) {
break;
}
//如果没有找到最后，将将temp后移
temp=temp.next;
}
//当退出while循环时，temp就指向了链表的最后
//将最后这个节点的next 指向 新的节点
temp.next=heroNode;
}
//显示链表[遍历]
public void list() {
//判断链表是否为空
if (head.next==null) {
System.out.println("链表为空");
return;
}
//因为头节点，不能动，因此我们需要一个辅助变量来遍历
HeroNode temp=head.next;
while (true) {
//判断是否到链表最后
if (temp==null) {
break;
}
//输出节点的信息
System.out.println(temp);
//将temp后移，一定小心
temp=temp.next;
}
}
}
//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
public int no;
public String name;
public String nickname;
public HeroNode next;//指向下一个节点
//构造器
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
//为了显示方法，我们重新toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" +nickname + "]";
}
}
运行结果
单链表按顺序插入节点
需要按照编号的顺序添加
1.首先找到新添加的节点的位置，是通过辅助变量(指针)
2.新的节点 next=temp.next
3.将temp.next=新的节点
//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
//(如果有这个排名，则添加失败，并给出提示)
public void addByOrder(HeroNode heroNode) {
//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
//因为是单链表，因此我们找的temp是位于添加位置的前一个节点，否则插入不了
HeroNode temp=head;
boolean flag=false;//标志添加的编号是否存在，默认为false
while (true) {
if (temp.next==null) {//说明temp已经在链表的最后
break;//
}
if (temp.next.no>heroNode.no) {//位置找到，就在temp的后面插入
break;
}else if(temp.next.no==heroNode.no){//说明希望添加的heroNode的编号已然存在
flag=true;
break;
}
temp=temp.next;//后移，遍历当前链表
}
//判断flag的值
if (flag) {//不能添加，说明编号存在
System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入\n",heroNode.no);
}else {
//插入到链表中，temp的后面
heroNode.next=temp.next;
temp.next=heroNode;
}
}
//修改节点的信息，根据no编号来修改，即no编号不能改
//说明
//1.根据newHeroNode的no来修改即可
public void update(HeroNode newHeroNode) {
//判断是否空
if (head.next==null) {
System.out.println("链表为空~");
return;
}
//修改节点的信息，根据no编号
//定义一个辅助变量
HeroNode temp=head.next;
boolean flag=false;//表示是否找到该节点
while (true) {
if (temp==null) {
break;
}
if (temp.no==newHeroNode.no) {
//找到
flag=true;
break;
}
temp=temp.next;
}
//根据flag判断是否找到要修改的节点
if (flag) {
temp.name=newHeroNode.name;
temp.nickname=newHeroNode.nickname;
}else {//没有找到
System.out.printf("没有找到 编号$d的节点，不能修改\n",newHeroNode.no);
}
}
//加入按照顺序编号的顺序 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4);; singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero3);
单链表的节点的修改
//测试修改节点的代码 HeroNode newHeroNode=new HeroNode(2, "小卢", "玉麒麟~~"); singleLinkedList.update(newHeroNode);
完整代码
package linkedlist;
public class SingleLinkedListDemo {
public static void main(String[] args) {
//进行测试
//先创建节点
HeroNode hero1=new HeroNode(1, "宋江", "及时雨");
HeroNode hero2=new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3=new HeroNode(3, "吴用", "智多星");
HeroNode hero4=new HeroNode(4, "林冲", "豹子头");
//创建要给链表
SingleLinkedList singleLinkedList=new SingleLinkedList();
//加入
// singleLinkedList.add(hero1);
// singleLinkedList.add(hero2);
// singleLinkedList.add(hero3);
// singleLinkedList.add(hero4);
//加入按照顺序编号的顺序
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);;
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
//测试修改节点的代码
HeroNode newHeroNode=new HeroNode(2, "小卢", "玉麒麟~~");
singleLinkedList.update(newHeroNode);
//显示一把
singleLinkedList.list();
}
}
//定义SingleLinkedList 管理我们的英雄
class SingleLinkedList{
//先初始化一个头节点，头节点不要动,不存放具体的数据
private HeroNode head=new HeroNode(0, "","");
//添加节点到单向链表
//思路，当不考虑编号顺序时
//1.找到当前链表的最后节点
//2.将最后这个节点的next指向新的节点
public void add(HeroNode heroNode) {
//因为head节点不能动，因此我们需要一个辅助遍历temp
HeroNode temp=head;
//遍历链表，找到最后
while (true) {
//找到链表的最后
if (temp.next==null) {
break;
}
//如果没有找到最后，将将temp后移
temp=temp.next;
}
//当退出while循环时，temp就指向了链表的最后
//将最后这个节点的next 指向 新的节点
temp.next=heroNode;
}
//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
//(如果有这个排名，则添加失败，并给出提示)
public void addByOrder(HeroNode heroNode) {
//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
//因为是单链表，因此我们找的temp是位于添加位置的前一个节点，否则插入不了
HeroNode temp=head;
boolean flag=false;//标志添加的编号是否存在，默认为false
while (true) {
if (temp.next==null) {//说明temp已经在链表的最后
break;//
}
if (temp.next.no>heroNode.no) {//位置找到，就在temp的后面插入
break;
}else if(temp.next.no==heroNode.no){//说明希望添加的heroNode的编号已然存在
flag=true;
break;
}
temp=temp.next;//后移，遍历当前链表
}
//判断flag的值
if (flag) {//不能添加，说明编号存在
System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入\n",heroNode.no);
}else {
//插入到链表中，temp的后面
heroNode.next=temp.next;
temp.next=heroNode;
}
}
//修改节点的信息，根据no编号来修改，即no编号不能改
//说明
//1.根据newHeroNode的no来修改即可
public void update(HeroNode newHeroNode) {
//判断是否空
if (head.next==null) {
System.out.println("链表为空~");
return;
}
//修改节点的信息，根据no编号
//定义一个辅助变量
HeroNode temp=head.next;
boolean flag=false;//表示是否找到该节点
while (true) {
if (temp==null) {
break;
}
if (temp.no==newHeroNode.no) {
//找到
flag=true;
break;
}
temp=temp.next;
}
//根据flag判断是否找到要修改的节点
if (flag) {
temp.name=newHeroNode.name;
temp.nickname=newHeroNode.nickname;
}else {//没有找到
System.out.printf("没有找到 编号$d的节点，不能修改\n",newHeroNode.no);
}
}
//显示链表[遍历]
public void list() {
//判断链表是否为空
if (head.next==null) {
System.out.println("链表为空");
return;
}
//因为头节点，不能动，因此我们需要一个辅助变量来遍历
HeroNode temp=head.next;
while (true) {
//判断是否到链表最后
if (temp==null) {
break;
}
//输出节点的信息
System.out.println(temp);
//将temp后移，一定小心
temp=temp.next;
}
}
}
//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
public int no;
public String name;
public String nickname;
public HeroNode next;//指向下一个节点
//构造器
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
//为了显示方法，我们重新toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" +nickname + "]";
}
}
运行结果
这篇关于Java数据结构与算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
栏目导航
