一、经典算法题举例

1.1 字符串匹配

字符串A="hello world",字符串B="llo",判断A是否包含B,如果包含则返回B在A中第一次出现的位置。

暴力匹配

简单,效率低

KMP算法

部分匹配表

1.2 汉诺塔

image.png
将A塔的所有圆盘移动到C塔,小圆盘上不能放大圆盘,一次只能移动一个圆盘。

1.3 八皇后问题

在8X8的国际象棋盘上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处在同一行、同一列或同一斜线上,问有多少种摆法。(92种)

分治算法

1.4 马踏棋盘/骑士周游

将马随机放在8X8的国际象棋盘上,马走日字,要求每个方格只进一次,走遍棋盘上全部64个方格。

深度遍历
贪心算法

二、数据结构与算法的关系

  1. 数据结构是一门研究组织数据方式的学科,数据结构是算法的基础。
  2. 程序=数据结构+算法。

三、数据结构分类

3.1 线性结构

  1. 数据元素之间存在一对一的线性。
  2. 线性结构有两种不同的的存储结构,顺序存储(顺序表)和链式存储(链表)。
  3. 顺序表中的元素是连续的,链表中的存储元素不一定是连续的,元素节点中存放着数据元素以及相邻元素的地址信息。
  4. 线性结构常见的有:数组、链表、队列、栈

3.2 非线性结构

二维数组、多维数组、广义表、树、图

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议