数据类型1 数据类型介绍数据类型的分类（按照结构划分）：线性结构和非线性结构 线性结构：
非线性结构： 2 数据类型之——稀疏数组2.1 引入实例
2.2 稀疏数组的基本介绍当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组 稀疏数组的处理方式是：
2.3 应用实例使用稀疏数组来保存类似前面的二维数组（棋盘，地图等） 2.4 思路分析
public class SparseArray {
public static void main(String[] args) {
//创建一个棋盘（原始的二维数组11*11）
//0：表示没有棋子，1：表示黑色棋子，2：表示蓝色棋子
int[][] chessArr = new int[11][11];
chessArr[1][2] = 1;
chessArr[2][3] = 2;
chessArr[4][5] = 2;
//输出原始的二维数组
System.out.println('原始的二维数组');
for (int[] row : chessArr) {//对二维数组中的整行遍历
for (int data : row) {
System.out.printf('%d\t', data);
}
System.out.println();
}
//将二维数组转稀疏数组的思想
//1.先遍历二维数组，得到非0数据的个数
int sum = 0;
for (int[] row : chessArr) {
for (int data : row) {
if (data != 0) {
sum++;
}
}
}
System.out.println('sum=' + sum);
//创建对应的稀疏数组
int[][] sparsArr = new int[sum + 1][3];
//给稀疏数组赋值
sparsArr[0][0] = chessArr.length;
sparsArr[0][1] = chessArr[0].length;
sparsArr[0][2] = sum;
//遍历二维数组，将非0的值存放到稀疏数组中
int count = 1;//计数器，用于记录是第几个非零数据
for(int i = 0; i<chessArr.length; i++){
for (int j =0; j<chessArr[0].length;j++){
if (chessArr[i][j]!=0){
sparsArr[count][0] = i;
sparsArr[count][1] = j;
sparsArr[count][2] = chessArr[i][j];
count++;
}
}
}
//输出稀疏数组
System.out.println('稀疏数组');
for (int[]row:sparsArr){
for (int data:row){
System.out.printf('%d\t',data);
}
System.out.println();
}
System.out.println('还原的二维数组');
//将稀疏数组恢复成原始的二维数组
//1.根据sparsArr第一行创建二维数组
int[][] chessArr2 = new int[sparsArr[0][0]][sparsArr[0][1]];
//2.再读取稀疏数组的后几行的数据（从第二行开始），并赋值给新的二维数组即可
for (int i = 1; i<=sparsArr[0][2];i++){
chessArr2[sparsArr[i][0]][sparsArr[i][1]] = sparsArr[i][2];
}
for (int[] row:chessArr2){
for (int data:row){
System.out.printf('%d\t',data);
}
System.out.println();
}
}}3 单向队列3.1 队列介绍
3.2 数组模拟队列
3.3 思路分析我们将数据存入队列的时候称为“addQueue”，addQueue的处理需要有两个步骤
3.4 代码实现import java.util.Scanner;public class ArrayQueueDemo {
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(5);
Scanner s = new Scanner(System.in);
boolean loop = true;
while (loop){
System.out.println('a(add):添加数据');
System.out.println('g(get):得到数据');
System.out.println('s(show):显示数据');
System.out.println('q(quit):退出程序');
char text = s.next().charAt(0);
switch (text){
case 'a':
System.out.println('请输入要添加的数据');
arrayQueue.addQueue(s.nextInt());
break;
case 'g':
try{
System.out.println('得到的数据为');
arrayQueue.getQueue();
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 's':
arrayQueue.show();
break;
case 'q':
s.close();//关闭输入器防止异常
loop = false;
break;
}
}
}}//创建数组队列类class ArrayQueue{
private int maxSize;//表示数组的最大容量
private int front;//头指针
private int rear;//尾指针
private int[] arr;//该数组用于存放数据，模拟队列
//创建数组队列的构造器
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
this.arr = new int[maxSize];
front = -1;//指向队列头部，分析出front是指向队列头的前一个位置
rear = -1;//指向队列尾部，指向队列尾（即队列最后一个数据）
}
//判断队列是否为空
public boolean isEmpty(){
return front == rear;
}
//判断队列是否满了
public boolean isFull(){
return rear == maxSize - 1;
}
//向队列中添加数据
public void addQueue(int n){
//如果满了则输出异常不添加数据
if (isFull()){
System.out.println('错误：队列已满不能再添加');
return;
}
//没满，则指针后移，向指针所指的格子中添加数据
rear++;
arr[rear] = n;
}
//从队列中获得数据
public int getQueue(){
//如果队列是空的，抛出异常
if (isEmpty()){
throw new RuntimeException('队列是空的，不能取出数据');
}
//指针后移返回数据
front++;
return arr[front];
}
//将队列格式化输出
public void show(){
if (isEmpty()){
System.out.println('队列是空的，没有数据');
return;
}
for (int i = 0; i<arr.length;i++){
System.out.printf('arr[%d] = %d\n',i,arr[i]);
}
}}3.5 存在的问题
4 数组模拟队列的改进——环形队列4.1 思路分析
4.2 注意
4.3 代码实现import java.util.Scanner;public class CircleArrayQueueDemo {
public static void main(String[] args) {
CircleArrayQueue circleArrayQueue = new CircleArrayQueue(5);//说明：设置4，但是有效数据最大是3，有一个空间是作为约定的
Scanner s = new Scanner(System.in);
boolean loop = true;
while (loop) {
System.out.println('a(add):添加数据');
System.out.println('g(get):得到数据');
System.out.println('s(show):显示数据');
System.out.println('q(quit):退出程序');
System.out.println('h(head):查看队列的第一个数据');
char text = s.next().charAt(0);
switch (text) {
case 'a':
System.out.println('请输入要添加的数据');
circleArrayQueue.addQueue(s.nextInt());
break;
case 'g':
try {
System.out.println('得到的数据为' + circleArrayQueue.getQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 's':
circleArrayQueue.show();
break;
case 'q':
s.close();//关闭输入器防止异常
loop = false;
break;
case 'h':
circleArrayQueue.headQueue();
break;
}
}
}}//创建数组队列类class CircleArrayQueue {
private int maxSize;//表示数组的最大容量
private int front;//头指针
private int rear;//尾指针
private int[] arr;//该数组用于存放数据，模拟队列
//创建数组队列的构造器
public CircleArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.arr = new int[maxSize];
front = 0;//指向队列头部，即队列的第一个元素
rear = 0;//指向队列尾部，指向队列尾的后一个数据
}
//判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//判断队列是否满了
public boolean isFull() {
//如果尾指针的下一个元素是front，则满了
return (rear + 1) % maxSize == front;
}
//向队列中添加数据
public void addQueue(int n) {
//如果满了则输出异常不添加数据
if (isFull()) {
System.out.println('错误：队列已满不能再添加');
return;
}
//没满，向当前位置所指的格子中添加数据(因为rear所指的格子是空的)
arr[rear] = n;
//指针后移
rear = (rear + 1) % maxSize;//防止出界
}
//从队列中获得数据
public int getQueue() {
//如果队列是空的，抛出异常
if (isEmpty()) {
throw new RuntimeException('队列是空的，不能取出数据');
}
//这里需要分析出front是指向队列的第一个元素
//先输出，再后移front
//1. 先把front对应的值保留到一个临时变量
//2. 将front后移
//3. 将临时变量返回
int temp = arr[front];
front = (front + 1) % maxSize;
return temp;
}
//将队列格式化输出
public void show() {
if (isEmpty()) {
System.out.println('队列是空的，没有数据');
return;
}
//思路：从front开始遍历，遍历多少个元素
for (int i = front; i < front + (rear - front + maxSize) % maxSize; i++) {
System.out.printf('arr[%d] = %d\n', i % maxSize, arr[i % maxSize]);
}
}
//显示队列的头数据，不是取出数据
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException('队列是空的，没有数据');
}
return arr[front];
}}5 单链表5.1 单链表介绍链表是有序的列表，但是它在内存中的存储如下
5.2 链表的创建
5.3 节点的修改通过辅助（指针）遍历链表，发现节点内部编号相等，则与新的节点内容进行互换 5.4 节点的删除
5.5 代码实现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.addByOrder(hero1);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero2);
singleLinkedList.add(hero3);
singleLinkedList.add(hero4);
singleLinkedList.List();
singleLinkedList.delete(hero4);
singleLinkedList.delete(hero3);
singleLinkedList.delete(hero2);
singleLinkedList.delete(hero1);
System.out.println('删除后');
singleLinkedList.List();
}}class SingleLinkedList {
//先初始化一个头结点，头节点不要动，不要存放具体的数值
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已经指向的最后的节点
temp.next = heroNode;
}
public void addByOrder(HeroNode heroNode) {
//因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
//因为单链表，因此我们找到的temp是位于添加位置的前一个结点，否则插入不进去
HeroNode temp = head;//辅助指针，初始值在head
boolean flag = false;//标识：表示该插入的对象是否已经在链表中存在了，默认为false（没有存在）
//遍历，从head开始到链表尾
while (true) {
//如果已经在链表尾
if (temp.next == null) {
break;
}
//如果找到位置，就在temp后面插入
if (temp.next.heroNo > heroNode.heroNo) {//temp的heroNo不大于，但是temp.next大于，说明插入位置在temp和temp.next之间
break;//找到位置，退出循环
}
if (temp.next.heroNo == heroNode.heroNo) {
flag = true;//说明该节点存在
break;
}
//如果以上条件都不满足，将temp后移
temp = temp.next;
}
//此时得到了一个flag值或者一个temp位置
//首先判断flag
if (flag) {
//说明该节点已经存在
System.out.printf('节点%d已经存在，不能再添加\n', heroNode.heroNo);
} else {
//该节点不存在的话，就在temp后面插入新的节点
heroNode.next = temp.next;
temp.next = heroNode;
}
}
//修改节点
public void update(HeroNode newHeroNode) {
//首先确定一下链表是否为空
if (head.next == null) {
System.out.println('链表为空，无法修改');
}
//创建辅助结点来遍历链表
HeroNode temp = head.next;
//创建flag变量，判断该节点是否找到
boolean flag = false;
while (true) {
//如果已经遍历到尾节点，终止
if (temp == null) {
break;
}
if (temp.heroNo == newHeroNode.heroNo) {
//找到该节点
flag = true;
break;
} else {
temp = temp.next;
}
}
//循环结束后通过flag值判断是否修改
if (flag) {
temp.heroName = newHeroNode.heroName;
temp.nickName = newHeroNode.nickName;
//next和no都不用变
} else {
System.out.printf('没有编号为%d的节点,无法修改\n', newHeroNode.heroNo);
}
}
//删除节点
//思路：
//1.head不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
//2.说明我们在比较时，是temp.next.heroNo 和要删除的节点的heroNo比较
public void delete(HeroNode delHeroNode) {
//如果链表为空，无法删除
if (head.next == null) {
System.out.println('链表为空，无法删除\n');
return;
}
//构建辅助节点，帮忙遍历链表
HeroNode temp = head;
//flag表示是否找到该节点的前一位，默认为false
boolean flag = false;
while (true) {
//如果遍历到最后一位，说明该节点不存在，终止循环
if (temp.next == null) {
break;
}
if (temp.next.heroNo == delHeroNode.heroNo) {
//找到了要删除的节点的上一位
flag = true;
break;
} else {
//没有找到，继续往后走
temp = temp.next;
}
}
//循环终止后通过判断flag值决定是否删除节点
if (flag) {
//如果要删除的节点在最后一位，则将上一位的next指向null
/*if (temp.next.next==null){
temp.next = null;
}
else {
//要删除的节点不在最后一位
temp.next = temp.next.next;
}*/
//如果要删除的节点在最后一位，则temp.next.next本身就等于null，以上两种情况可以合并
temp.next = temp.next.next;
} else {
System.out.printf('没有编号为%d的节点，无法删除\n', delHeroNode.heroNo);
}
}
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 heroNo;
public String heroName;
public String nickName;
HeroNode next;
public HeroNode(int heroNo, String heroName, String nickName) {
this.heroNo = heroNo;
this.heroName = heroName;
this.nickName = nickName;
}
//为了显示方法，我们重写toString
public String toString() {
return 'HeroNode [no = ' + heroNo + ', name = ' + heroName + ', nickname = ' + nickName + ']';
}}5.6 单链表面试题5.6.1 求单链表中有效节点的个数韩老师的方法写在了测试类中，为静态方法： /**
*
* @param head 链表的头节点
* @return 返回链表的长度
*/
public static int getLength(HeroNode head){
//空链表
if (head.next == null){
return 0;
}
int result = 0;
//辅助接点遍历，将头节点排除在外
HeroNode cur = head.next;
while (cur!=null){
result++;
cur = cur.next;
}
return result;
}//同时因为head为SingleLinkedList类中的private属性，所以在SingleLinkedList中添加一个getter方法
public HeroNode getHead() {
return head;
}
//==========================我写在了SingleLinkedList类中，为实例方法，不需要参数，可以直接使用对象调用 //方法：获取单链表的节点的个数（如果是带头节点的，需要不统计头节点）
public int getLength2(){
int result = 0;
HeroNode temp = head;
while (true){
if (temp.next == null){
break;
}
temp = temp.next;
result++;
}
return result;
}我感觉在实际情况中，韩老师的方法更对一些，因为SingleLinkedList在实际应用情况下是封装好的，外部是不能够更改内部的，所以应该用外部的方法取实现要求。 5.6.2 查找单链表中的倒数第k个节点思路：
代码示例： /**
*
* @param head 链表的头节点
* @param k
* @return 返回倒数第K个节点
*/
public static HeroNode findLastKNode(HeroNode head, int k){
//如果链表为空，返回null
if (head.next == null){
return null;
}
//找到链表的长度
int length = getLength(head);
//先做一个index校验
if ( k <= 0 || k > length){
return null;
}
//辅助节点帮助遍历
HeroNode cur = head.next;
//遍历K次
for (int i = 0; i < length - k; i++) {
cur = cur.next;
}
return cur;
}5.6.3 从尾到头打印单链表（反向遍历）思路：
|
|
|
