概述

经典算法问题举例

1、问题1：字符串匹配问题

问题描述：判断str1是否包含str2, 如果存在返回第一次出现的位置，如果没有返回-1

str1 = "你好你好啊"
str2 = "你好啊"

思路：

• 暴力匹配: 简单，效率低
• KMP算法: 《部分匹配表》

2、问题2：汉诺塔游戏

要求：

1. 将A塔的圆盘全部移动到C塔
2. 规定：
   • 小圆盘上不能放大圆盘；
   • 三根柱子之间一次只能移动一个圆盘

    1
    2
    3
    A塔      B塔     C塔

思路： 分值算法

3、问题3：八皇后问题 8x8的格子国际象棋上摆放八个皇后，不能相互攻击 即：任意两个皇后都不能处于同一行、同一列、同一斜线 问：一共多少中摆法

思路： 回溯(su)算法

4、问题4：马踏棋盘（骑士周游问题） 将马随机放在国际象棋8X8棋盘，马按照走棋规则（马走日）进行移动，要求每个方格只能进入一次，走遍棋盘全部64个方格

思路： 图的深度优先优化遍历算法DFS+贪心算法优化

数据结构和算法的概述

算法是程序的灵魂，优秀的程序可以在海量数据计算时，依然保持高速计算

程序 = 数据结构 + 算法

实际编程中遇到的问题

• 修路问题 最小生成树（普利姆算法）
• 最短路径问题 弗洛伊德算法
• 汉诺塔问题 分治算法
• 八皇后问题 回溯法

线性结构和非线性结构

数据结构

• 线性结构
  • 顺序存储结构
  • 链式存储结构
• 非线性结构

1、线性结构

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

2、非线性结构 1）非线性结构包括: 二维数组，多维数组，广义表，树结构，图结构