数据结构与算法知识点整理
程序员文章站
2022-03-25 21:25:56
...
开篇:几个经典的算法题
八皇后问题
在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转,和对角线对称变换的摆法看成一类,共有42类。计算机发明后,有多种计算机语言可以编程解决此问题。
使用回溯算法解决:
public class Queen {
private int[] column; //同栏是否有皇后,1表示有
private int[] rup; //右上至左下是否有皇后
private int[] lup; //左上至右下是否有皇后
private int[] queen; //解答
private int num; //解答编号
public Queen() {
column = new int[8+1];
rup = new int[(2*8)+1];
lup = new int[(2*8)+1];
for (int i = 1; i <= 8; i++)
column[i] = 0;
for (int i = 1; i <= (2*8); i++)
rup[i] = lup[i] = 0; //初始定义全部无皇后
queen = new int[8+1];
}
public void backtrack(int i) {
if (i > 8) {
showAnswer();
} else {
for (int j = 1; j <= 8; j++) {
if ((column[j] == 0) && (rup[i+j] == 0) && (lup[i-j+8] == 0)) {
//若无皇后
queen[i] = j; //设定为占用
column[j] = rup[i+j] = lup[i-j+8] = 1;
backtrack(i+1); //循环调用
column[j] = rup[i+j] = lup[i-j+8] = 0;
}
}
}
}
protected void showAnswer() {
num++;
System.out.println("\n解答" + num);
for (int y = 1; y <= 8; y++) {
for (int x = 1; x <= 8; x++) {
if(queen[y]==x) {
System.out.print("Q");
} else {
System.out.print(".");
}
}
System.out.println();
}
}
public static void main(String[] args) {
Queen queen = new Queen();
queen.backtrack(1);
}
}
马踏棋盘
(1)马踏棋盘算法也被称为骑士周游问题
(2)将马随机放在国际象棋的8×8棋盘Board[0~7][0~7]的某个方格中,马按走棋规则(马走日字)进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格
线性结构和非线性结构
线性结构
- 线性结构有两种不同的存储结构,即顺序存储结构(数组)和链式存储结构(链表)。顺序表中的存储元素是连续的。
- 链式存储的线性表是链表,链表中的存储元素不一定是连续的。
- 常见的线性结构:数组、队列、链表和栈
非线性结构
非线性结构包括:二维数组、多维数组、广义表、树结构、图结构