一 線性結(jié)構(gòu)
數(shù)據(jù)元素之間存在一對一的線性關系
順序存儲結(jié)構(gòu)
順序表中的存儲元素是連續(xù)的
鏈式存儲結(jié)構(gòu)
鏈表中的存儲元素不一定是連續(xù)的，元素節(jié)點中存放數(shù)據(jù)元素以及相鄰元素的地址信息
二 非線性結(jié)構(gòu)
非線性結(jié)構(gòu)包括：二維數(shù)組，多維數(shù)組，廣義表勋颖，樹結(jié)構(gòu)耘擂，圖結(jié)構(gòu)
三 稀疏數(shù)組
當一個數(shù)組中大部分元素為０摇庙，或者為同一個值的數(shù)組時旱物，可以使用稀疏數(shù)組來保存該數(shù)組。
稀疏數(shù)組的處理方法是:
- 記錄數(shù)組一共有
幾行幾列卫袒，有多少個不同的值
把具有不同值的元素的行列及值記錄在一個小規(guī)模的數(shù)組中宵呛，從而縮小程序的規(guī)模
image.png
image.png
實戰(zhàn)
- 使用稀疏數(shù)組，來保留類似前面的
二維數(shù)組(棋盤夕凝、地圖等等) - 把稀疏數(shù)組
存盤宝穗，并且可以從新恢復原來的二維數(shù)組數(shù) -
整體思路分析
image.png
思路
二維數(shù)組轉(zhuǎn)稀疏數(shù)組
- 遍歷原始數(shù)組，得到
有效數(shù)據(jù)的個數(shù)sum - 創(chuàng)建一個稀疏數(shù)組
int[sum+1][3]（如果值只有0码秉，1逮矛；則可以省略第三列。第一行可以放默認值,規(guī)則自定義）转砖。這里放第一行二維數(shù)組的行列數(shù)以及sum - 將二維數(shù)組的有效數(shù)據(jù)依次記錄
稀疏數(shù)組還原二維數(shù)組
- 根據(jù)第一行
創(chuàng)建一個默認值的二維數(shù)組 - 從第二行開始遍歷须鼎，
還原有效數(shù)值
代碼
/**
* 獲得一個原始二維數(shù)組
* @return
*/
public int[][] getOriginArray(){
int[][] origin = new int[10][12];
origin[2][8] = 1;
origin[9][11] = 90;
origin[8][5] = 123;
origin[6][6] = 99;
origin[7][4] = 6;
origin[3][1] = 618;
origin[5][9] = 111;
return origin;
}
/**
* 轉(zhuǎn)換成稀疏數(shù)組
* @param origin
* @return
*/
public int[][] tranSparseArray(int[][] origin){
int sum = 0;
int rows = origin.length;
int columns = origin[0].length;
for(int i=0;i<rows;i++){
int[] row= origin[i];
for(int j=0;j<columns;j++){
if(row[j]!=0){
sum++;
}
}
}
int[][] sparseArray = new int[sum+1][3];
sparseArray[0][0] = sum;
sparseArray[0][1] = rows;
sparseArray[0][2] = columns;
int index = 1;
for(int i=0;i<rows;i++){
int[] row= origin[i];
for(int j=0;j<columns;j++){
if(row[j]!=0){
sparseArray[index][0] = i;
sparseArray[index][1] = j;
sparseArray[index][2] = row[j];
index ++;
}
}
}
return sparseArray;
}
/**
* 稀疏數(shù)組還原
* @param sparseArray
* @return
*/
public int[][] recovery(int[][] sparseArray){
int rows = sparseArray[0][1];
int columns = sparseArray[0][2];
int[][] orgins = new int[rows][columns];
for(int index=1;index<sparseArray.length;index++){
int row = sparseArray[index][0];
int column = sparseArray[index][1];
int value = sparseArray[index][2];
orgins[row][column] = value;
}
return orgins;
}
工具方法
/**
* 打印二維數(shù)組
* @param array
*/
public static void printTwoDimArray(int[][] array){
for(int i = 0;i<array.length;i++){
System.out.print("[");
for(int j=0;j<array[i].length;j++){
System.out.print("\t"+array[i][j]);
}
System.out.println("\t"+"]");
}
}
測試
@Test
public void test() {
int[][] origin = getOriginArray();
ArrayUtils.printTwoDimArray(origin);
System.out.println("-----------");
int[][] sparseArray = tranSparseArray(origin);
ArrayUtils.printTwoDimArray(sparseArray);
System.out.println("-----------");
int[][] recoverys = recovery(sparseArray);
ArrayUtils.printTwoDimArray(recoverys);
}
四 隊列
隊列是一個有序列表，可以用數(shù)組或是鏈表來實現(xiàn)
遵循先入先出的原則
數(shù)組實現(xiàn)
- 隊列本身是有序列表府蔗，若使用數(shù)組的結(jié)構(gòu)來存儲隊列的數(shù)據(jù)晋控，則隊列數(shù)組的聲明如下圖, 其中
maxSize是該隊列的最大容量 - 因為隊列的
輸出、輸入是分別從前后端來處理姓赤，因此需要兩個變量front及rear分別記錄隊列前后端的下標赡译，front會隨著數(shù)據(jù)輸出而改變，而rear則是隨著數(shù)據(jù)輸入而改變不铆，如圖所示:
我的定義和圖不同蝌焚，front（rear）指向下一個要取（加）得元素得前一個下標
image.png
思路
- 取數(shù)據(jù)后狂男，front+1综看；加數(shù)據(jù)后品腹，rear+1（
rear總是大于等于front） - 封裝一個數(shù)據(jù)機構(gòu)
- 當
front=maxSize-1時岖食，隊列滿了
代碼
package com.zyc;
import org.junit.Test;
/**
* @author zhuyc
* @create 2019-07-13 16:25
*/
public class ArrayQueue {
private int front;//下一個坐標就是要取得元素坐標
private int rear;//下一個坐標就是增加元素得坐標
private int maxSize;
private int[] array;
public ArrayQueue(int maxSize){
front = -1;
rear = -1;
this.maxSize = maxSize;
array = new int[maxSize];
}
public boolean isFull(){
return rear == maxSize-1;
}
public boolean isEmpty(){
return front==rear;//一樣表示放的都取出來了
}
public void push(int value){
if(isFull()){
throw new RuntimeException("隊列已滿");
}
array[++rear] = value;
}
public int pop(){
if(isEmpty()){
throw new RuntimeException("空隊列");
}
return array[++front];
}
public void showValidQueue(){
if(isEmpty()){
System.out.println("空隊列");
}else{
for(int i = front;i<rear;i++){
System.out.printf("數(shù)組[%d]=%d",i+1,array[i+1]);
}
System.out.println();
}
}
public void showQueue(){
if(isEmpty()){
System.out.println("空隊列");
}else{
for(int i = 0;i<maxSize;i++){
System.out.printf("數(shù)組[%d]=%d",i,array[i]);
}
System.out.println();
}
}
public int head(){
if(isEmpty()){
throw new RuntimeException("空隊列");
}
int index = front +1;
return array[index];
}
}
測試
@org.junit.Test
public void test(){
ArrayQueue queue = new ArrayQueue(10);
queue.push(23);
queue.push(28);
queue.push(1);
queue.push(3);
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
System.out.println(queue.pop());
System.out.println(queue.head());
System.out.println(queue.pop());
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
}
數(shù)組模擬環(huán)形隊列
上面的隊列的空間是不可復用，下面我們要進行優(yōu)化
思路分析
- front和rear對maxSize取模后的值范圍
[0,maxSize-1]正好是數(shù)組的有效下標范圍 -
rear-front<maxSize,否則就超出了容量(這樣就處理了覆蓋的問題) - 取下標時我們需要對
front(rear)取模 - 當front和rear
同時超過maxSize時舞吭，作一次重置操作(兩者都等于取模后的值泡垃，這樣可以避免無限增長) - 當maxSize=2的n次方時，可以用
&maxSize-1操作代替取模
代碼
package com.zyc;
import org.junit.Test;
/**
* @author zhuyc
* @create 2019-07-13 16:25
*/
public class ArrayQueue {
private int front;//下一個坐標就是要取得元素坐標
private int rear;//下一個坐標就是增加元素得坐標
private int maxSize;
private int[] array;
public ArrayQueue(int maxSize){
front = -1;
rear = -1;
this.maxSize = maxSize;
array = new int[maxSize];
}
public boolean isFull(){
return rear-front==maxSize;
}
public boolean isEmpty(){
return front==rear;//一樣表示放的都取出來了
}
public void push(int value){
if(isFull()){
throw new RuntimeException("隊列已滿");
}
int index = ++rear%maxSize;
array[index] = value;
}
public int pop(){
if(isEmpty()){
throw new RuntimeException("空隊列");
}
if(front==maxSize){//重置
front = front%maxSize;
rear = rear%maxSize;
}
int index = ++front%maxSize;
return array[index];
}
public void showValidQueue(){
if(isEmpty()){
System.out.println("空隊列");
}else{
for(int i = front;i<rear;i++){
int index = (i+1)%maxSize;
System.out.printf("數(shù)組[%d]=%d",index,array[index]);
}
System.out.println();
}
}
public void showQueue(){
if(isEmpty()){
System.out.println("空隊列");
}else{
for(int i = 0;i<maxSize;i++){
System.out.printf("數(shù)組[%d]=%d",i,array[i]);
}
System.out.println();
}
}
public int head(){
if(isEmpty()){
throw new RuntimeException("空隊列");
}
int index = (front +1)%maxSize;
return array[index];
}
}
測試
@Test
public void testArrayQueue2(){
ArrayQueue queue = new ArrayQueue(4);
queue.push(1);
queue.push(2);
queue.push(3);
queue.push(4);
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
System.out.println(queue.pop());
System.out.println(queue.head());
System.out.println(queue.pop());
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
queue.push(5);
queue.push(6);
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
queue.push(7);
queue.push(8);
queue.push(9);
queue.push(10);
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
queue.push(11);
System.out.println(queue.pop());
System.out.println("end");
}
