数据结构和算法基础

巩固基础，砥砺前行 。
只有不断重复，才能做到超越自己。
能坚持把简单的事情做到极致，也是不容易的。

数据结构和算法

程序= 数据结构+算法
数据结构是算法的基础

问题1：字符串匹配问题。str1 是否完全包含 str2

1）暴力匹配
2）KMP算法

问题2：汉诺塔游戏

问题3：8皇后问题

问题4：骑士周游

问题5：写出单链表表示的字符串类以及字符串节点类的定义，并依次实现他的构造函数、以及计算字符串的长度、串赋值、判断两串相等、求子串、两串拼接、求子串在串中的位置等成员函数

问题6：使用二维数组保存棋盘上的数据，如何判断输赢？完成存盘退出和继续上局的功能

棋盘 二维数组->稀疏数组->写入文件
读取文件->稀疏数组->棋盘

问题7：约瑟夫问题（丢手帕），编号为 1，2，3，4……n的人围成一圈，约定编号为K（1<=K<=n）的人从1开始报数,数到m的那个人出列，然后从m的下一位又开始报数，数到m的那个人又出列，依次类推，直到所有人都出列为止，由此产生的一个出队的编号的序列

问题8：修路问题

问题9：最短路劲

稀疏数组和队列

将棋盘上的数据存储下来，可以使用二维数组来存储，没有棋子的可以使用默认的0，因此记录了很多没有意义的数据
–>优化：可以使用稀疏数组来存储

稀疏数组
记录数组有多少行 多少列;
把具体的有数据的行列以及数据记录下来，缩小程序的规模

棋盘数据存储和恢复：
使用稀疏数组来保留二维数组中有效的数据;
将稀疏数组存盘,同时将稀疏数组恢复为二维数组;

代码实现

package com.ttzz.a3;public class SparseArray {// 这是一个10*10的棋盘private static final int ROW_COL = 10;private static final int BLACK = 1;private static final int WHITE = 2;public static void main(String[] args) {int[][] aa = new int[ROW_COL][ROW_COL];
//		 System.out.println("棋盘：");
//		 printArray(aa);// 棋盘填充数据aa[3][4] = BLACK;aa[7][5] = BLACK;aa[3][2] = BLACK;aa[5][1] = BLACK;aa[6][6] = WHITE;aa[8][3] = WHITE;aa[1][1] = WHITE;aa[4][0] = WHITE;
//		 printArray(aa);int size = 0;// 有效数据for (int i = 0; i < ROW_COL; i++) {for (int j = 0; j < ROW_COL; j++) {if(aa[i][j]!=0) {size++;
//					System.out.println(aa[i][j]);}}}
//		System.out.println("size="+size);int bb[][] = new int[size+1][3];bb[0][0] = ROW_COL;bb[0][1] = ROW_COL;bb[0][2] = size;int count = 0;for (int i = 0; i < ROW_COL; i++) {for (int j = 0; j < ROW_COL; j++) {if(aa[i][j]!=0) {count++;
//					System.out.println(count+","+i+","+j+","+aa[i][j]);bb[count][0] = i;bb[count][1] = j;bb[count][2] = aa[i][j];}}}
//		printArray(bb);//将稀疏数组转为数组int cc[][] = new int[bb[0][0]][bb[0][1]];
//		printArray(cc);for (int i = 1; i < bb.length; i++) {for (int j = 0; j < bb[i].length; j++) {System.out.println(i+","+j+","+bb[i][j]); cc[bb[i][0]][bb[i][1]] = bb[i][2];}}printArray(cc);}public static void printArray(int[][] item) {for (int i = 0; i < item.length; i++) {for (int j = 0; j < item[i].length; j++) {System.out.printf("%d\t", item[i][j]);}System.out.println();}}}

数据结构和算法-(排序算法-冒泡排序)

1.概念：什么是稳定排序和非稳定性排序？

相同元素排序中之后，顺序和之前的顺序一样，则为稳定排序，否则为非稳定性排序。道听途说，不足为惧。都是抄的，天下文章一大抄，先抄了再说。

2. 冒泡排序代码实现

2.1 普通版本

​public static void sort1(int arr[]) {for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr.length-i-1; j++) {int item = 0;if(arr[j]>arr[j+1]) {item = arr[j];arr[j] = arr[j+1];arr[j+1] = item;}}}}​

2.2 优化版本 某一步之后，后面的代码有序了，后面的代码就不排序了。

​
public static void sort2(int arr[]) {for (int i = 0; i < arr.length; i++) {boolean iscontinue = true; for (int j = 0; j < arr.length-i-1; j++) {int item = 0;if(arr[j]>arr[j+1]) {item = arr[j];arr[j] = arr[j+1];arr[j+1] = item;iscontinue = false;}}if(iscontinue) {break;}}}​

2.3 优化版2

​
public static void sort3(int arr[]) {int sortborder = arr.length-1;//表示比较的边界int lastcomindex = 0; //最后一次比较的位置for (int i = 0; i < arr.length; i++) {boolean iscontinue = true; for (int j = 0; j < sortborder; j++) {int item = 0;if(arr[j]>arr[j+1]) {item = arr[j];arr[j] = arr[j+1];arr[j+1] = item;iscontinue = false;lastcomindex = j;}}sortborder = lastcomindex;if(iscontinue) {break;}}}​

使用Java实现的栈

package aa.datastructure;import java.util.Arrays;/***  栈*/
public class MyStack<E> {private Object[] data = null;private int length = 0; // 栈的容量private int top = -1; // 栈顶的指针MyStack() {}MyStack(int initSize){if(initSize>=0) {this.length = initSize;data = new Object[initSize];top = -1;}else {throw new RuntimeException("初始容量不能小于0"+initSize);}}public boolean push(E e) {if(top == length-1) {throw new RuntimeException("栈已经达到最大值");}else {data[++top] = e;return true;}}public E pop() {if(top == -1) {throw new RuntimeException("空栈");}else {return (E) data[top--];}}public E peek() {if(top == -1) {throw new RuntimeException("空栈");}else {return (E) data[top];}}public static void main(String[] args) {MyStack sm = new MyStack(3);for (int i = 0; i < 3; i++) {sm.push(i);}System.out.println(Arrays.toString(sm.data));for (int i = 0; i < 3; i++) {System.out.println(sm.peek());}for (int i = 0; i < 3; i++) {System.out.println(sm.pop());}}}

使用Java实现的队列

package aa.datastructure;import java.util.Arrays;/** 队列*/
public class MyQueue<E> {private int length;//容量private Object[] data;private int front;//头private int rear;MyQueue(){}MyQueue(int initSize){if(initSize>=0) {length = initSize;data = new Object[initSize];front = rear = 0;}else {throw new RuntimeException("队列初始化大小不能小于0");}}public boolean add(E e) {if(rear == length) {throw new RuntimeException("队列满了");}else {data[rear++] = e;return true;}}public E pool() {if(front == rear) {throw new RuntimeException("空队列");}else {E value = (E) data[front];data[front++] = null;return value;}}public E peek() {if(front == rear) {throw new RuntimeException("空队列");}else {E value = (E) data[front];return value;}}public static void main(String[] args) {MyQueue mq = new MyQueue(10);for (int i = 0; i < 5; i++) {mq.add(i);}System.out.println(Arrays.toString(mq.data));for(int i = 0; i < 5; i++) {System.out.println(mq.pool());}for(int i = 0; i < 5; i++) {System.out.println(mq.peek());}}}

【临渊羡鱼不如退而结网】