一.数据结构的分型
数据结构包括线性结构和非线性结构
线性结构:
1.线性结构是最常见的数据结构,其特点是数据元素之间一对一的线性关系
2.线性结构有两种不同的存储结构(数组)和链式存储结构(链表),顺序存储的线性表称为顺序表,顺序表中存储的元素是连续的
3.链式存储的表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
4.线性结构常见的有:数组,队列,链表和栈
非线性结构:
包括二维数组,多维数组,广义表,图结构,树结构
二.稀疏数组
当一个数组中大部分元素为0或者同一个值的时候,可以使用稀疏数组来保存该数据
稀疏数组的处理方式:
1.记录数组中一共有几行几列,有多少个不同的值
2.把具有不同值的元素的行列及其值记录在一个小规模的数组中,从而缩小数据的规模
二维数组转稀疏数组
1.遍历原始的二维数组,得到有效数据的个数
2.根据有效数据的个数就可以创建相应的稀疏数组
3.将二维数组的有效数据填入到稀疏数组中
public static int[][] convertSparseArray(int[][] chaseArr){
/*
*
* 1.遍历原始的二维数组,得到有效数据的个数sum
* 2.根据sum来创建稀疏数组
* 3.将二维数组的有效数据存入到稀疏数组
* */
int sum = 0;
for (int i = 0; i < chaseArr.length; i++) {
for (int j = 0; j < chaseArr[i].length; j++) {
if (chaseArr[i][j] != 0){
sum++;
}
}
}
//创建稀疏数组
int[][] sparseArray = new int[sum+1][3]; //二维数组转稀疏数组
// 给稀疏数组赋值
sparseArray[0][0] = chaseArr.length; // 原二维数组的行
sparseArray[0][1] = chaseArr[0].length; // 原二维数组的列
sparseArray[0][2] = sum; // 原二维数组有效数据的个数
int count = 0;
for (int i = 0; i < chaseArr.length; i++) {
for (int j = 0; j < chaseArr[i].length; j++) {
if(chaseArr[i][j] != 0){
count++;
sparseArray[count][0] = i; // 获取有效值所在的行
sparseArray[count][1] = j; // 获取有效值所在的列
sparseArray[count][2] = chaseArr[i][j]; // 获取原数组中的有效值
}
}
}
return sparseArray;
}
稀疏数组还原成二维数组
1.先读取稀疏数组的第一行,根据第一行创建原始的二维数组
2.根据有效值,根据行列,传进二维数组
public static int[][] convertOriArrar(int[][] sparseArr){
/*
* 稀疏数组转二维数组
* 1.先读取稀疏数组的第一行,根据第一行创建原始的二维数组
* 2.在读取稀疏数组的后几行数据,并赋给原始的二维数组即可
* */
int row = sparseArr[0][0];
int col = sparseArr[0][1];
int[][] chaseArr = new int[row][col];
for (int i = 1; i < sparseArr.length; i++) {
chaseArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
return chaseArr;
}
完整版:
public class SparseArray {
/*从二维数组转变为稀疏数组,在由稀疏数组转变成二维数组*/
public static void main(String[] args) {
// 棋盘,1表示黑色,2表示白色
int[][] chaseArr = new int[11][11];
chaseArr[1][2] = 1;
chaseArr[2][3] = 2;
showArr(convertSparseArray(chaseArr));
int[][] sparseArr = convertSparseArray(chaseArr);
showArr(convertOriArrar(sparseArr));
}
public static int[][] convertOriArrar(int[][] sparseArr){
/*
* 稀疏数组转二维数组
* 1.先读取稀疏数组的第一行,根据第一行创建原始的二维数组
* 2.在读取稀疏数组的后几行数据,并赋给原始的二维数组即可
* */
int row = sparseArr[0][0];
int col = sparseArr[0][1];
int[][] chaseArr = new int[row][col];
for (int i = 1; i < sparseArr.length; i++) {
chaseArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
return chaseArr;
}
public static int[][] convertSparseArray(int[][] chaseArr){
/*
*
* 1.遍历原始的二维数组,得到有效数据的个数sum
* 2.根据sum来创建稀疏数组
* 3.将二维数组的有效数据存入到稀疏数组
* */
int sum = 0;
for (int i = 0; i < chaseArr.length; i++) {
for (int j = 0; j < chaseArr[i].length; j++) {
if (chaseArr[i][j] != 0){
sum++;
}
}
}
//创建稀疏数组
int[][] sparseArray = new int[sum+1][3]; //二维数组转稀疏数组
// 给稀疏数组赋值
sparseArray[0][0] = chaseArr.length; // 原二维数组的行
sparseArray[0][1] = chaseArr[0].length; // 原二维数组的列
sparseArray[0][2] = sum; // 原二维数组有效数据的个数
int count = 0;
for (int i = 0; i < chaseArr.length; i++) {
for (int j = 0; j < chaseArr[i].length; j++) {
if(chaseArr[i][j] != 0){
count++;
sparseArray[count][0] = i; // 获取有效值所在的行
sparseArray[count][1] = j; // 获取有效值所在的列
sparseArray[count][2] = chaseArr[i][j]; // 获取原数组中的有效值
}
}
}
return sparseArray;
}
public static void showArr(int[][] arr){
for (int[] row : arr) {
for (int i : row) {
System.out.printf("%d\t",i);
}
System.out.println();
}
}
}
三.队列
1.队列是一个有序的列表,可以用数组或链表来实现
2.遵循先进先出的原则
3.数组模拟队列思路
队列本身是一个有序的列表,若使用数组的结构来存储队列,则队列数组的声明如下图,其中maxSize是队列的最大容量
因为队列的输出,输入分别从前后端来处理,因此需要front和rear两个变量分别记录队列前后端的下标,front会随着输出而改变,rear会随着输入而改变
示意图:
class ArrayQueue{
//模拟数组队列的实现类
private int maxSize;
private int front; // 指向头部的指针,指向第一个元素的前一个位置
private int rear; // 指向尾部的指针,指向队列的最后一个元素
private int[] arr;
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
front = -1;
rear = -1;
arr = new int[maxSize];
}
/*判断队列是否为空*/
public boolean isEmpty(){
return front == rear;
}
/*判断队列是否已满*/
public boolean isFull(){
return rear == maxSize-1;
}
/*添加元素到队列中*/
public void addElement(int e){
if(isFull()){
System.out.println("队列已满,不能添加元素");
return;
}
rear++; // 尾部指针后移
arr[rear] = e; //添加元素到队列中
}
/*获取队列中的元素*/
public int getElement(){
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]);
}
}
/*打印队列的头部元素*/
public int getHeadElement(){
if (isEmpty()){
throw new RuntimeException("队列为空,没有数据");
}
return arr[front+1];
}
}
public static void main(String[] args) {
testArrayQueue();//测试代码
}
public static void testArrayQueue(){
// 初始化队列的元素,3个
ArrayQueue queue = new ArrayQueue(3);
boolean loop = true;
char key = ' ';
Scanner scanner = new Scanner(System.in);
while (loop){
System.out.println("请输入队列的操作,s(show)\te(exit)\ta(add)\tg(get)\th(head)");
//获取用户的输入操作
key = scanner.next().charAt(0);
switch (key){
case 's':
queue.show();
break;
case 'a':
int value = scanner.nextInt();
queue.addElement(value);
break;
case 'g':
int res = queue.getElement();
System.out.println("取出的数是:"+res);
break;
case 'h':
int head = queue.getHeadElement();
System.out.println("队列的头元素是:"+head);
break;
case 'e':
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出");
}
执行结果:
队列无法复用,只能用一次,不能再次使用
4.改进
使用环形队列(通过取模的方式来实现)
5.思路
front指向队列中的第一个元素,arr[front]就是队列的第一个元素,初始值是0
rear指向队列的最后一个元素,arr[rear],就是队列的最后一个元素,需要预留出约定的空间
队列满时的条件:(rear+1)%maxSize == front
队列为空的条件: front == rear
队列中的有效个数:(rear+maxSize-front)%maxSize
class CircleArray{
/*
* 1.front指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素,front的初始值是0
* 2.rear指向队列的最后一个元素的后一个位置,要预留出一个空间作为约定
* 3.当队列满的时候(rear+1)%maxSize == front
* 4.队列中的有效的数据个数(rear+maxSize-front)%maxSize
*
* */
private int maxSize;
private int front;
private int rear;
private int[] arr;
public CircleArray(int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
}
/*判断队列是否为空*/
public boolean isEmpty(){
return front == rear;
}
/*判断队列是否已满*/
public boolean isFull(){
return (rear+1) % maxSize == front;
}
/*添加元素*/
public void addElement(int e){
if (isFull()){
System.out.println("队列已满,不能在添加元素");
return;
}
arr[rear] = e;// 直接加入数据
rear = (rear +1)%maxSize; //取模来实现环形例rear=1,maxSize=3
}
/*获取队列元素*/
public int getElement(){
if (isEmpty()){
throw new RuntimeException("队列为空,不能获取元素");
}
int v = arr[front]; // 把front对应的值保存到临时变量中
front = (front+1)%maxSize; // front指针取模,后移
return v; // 将临时变量返回
}
/*打印输出队列*/
public void show(){
if (isEmpty()){
System.out.println("队列为空,没有数据");
return;
}
// 从front开始遍历,遍历队列中的有效元素的个数
for (int i = front; i < front+size(); i++) {
System.out.printf("arr[%d]=%d\n",(i%maxSize),arr[i%maxSize]);
}
}
/*查看队列的第一个元素*/
public int getHeadElement(){
if (isEmpty()){
throw new RuntimeException("队列为空,不能打印队列");
}
return arr[front];
}
public int size(){
//例如: rear=2,front=1,maxSize=3 带入 有效的元素个数为1
return (rear+maxSize-front)%maxSize;
}
}
public static void main(String[] args) {
testCircleQueue();
}
public static void testCircleQueue(){
CircleArray circle = new CircleArray(4);
boolean loop =true;
char key = ' ';
Scanner scanner = new Scanner(System.in);
while (loop){
System.out.println("请输入队列的操作,s(show)\te(exit)\ta(add)\tg(get)\th(head)");
key = scanner.next().charAt(0);
switch (key){
case 's':
circle.show();
break;
case 'a':
circle.addElement(scanner.nextInt());
break;
case 'g':
System.out.println("取出的队列元素是:"+circle.getElement());
break;
case 'h':
System.out.println("队列的头部元素是:"+circle.getHeadElement());
break;
case 'e':
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出");
}
运行结果:
可以实现队列的复用