01-简述

1. 几个经典算法题

• 字符串匹配 —— KMP算法(部分匹配表)
• 汉诺塔 —— 分治算法
• 八皇后 —— 回溯算法
• 马踏棋盘(骑士周游) —— 图的深度优先遍历算法(DFS) + 贪心算法优化

2. 数据结构和算法的关系

2.1 数据结构

• 解决存储问题
• 把现实生活中大量而复杂的问题以特定的数据类型(事物) 和特定的存储结构(事物的关系) 保存到存储器中
• 数据的存储 = 数据的存储 + 数据关系的存储

2.2 算法

• 在存储结构的基础上实现某个功能而执行的操作，这个相应的操作也叫做 [算法] // 算法就是对数据的操作
• 广义 | 狭义 上的算法
  • 狭义的算法：与数据的存储方式密切相关
  • 广义的算法：与数据的存储方式无关

2.3 关系

• 程序 = 数据结构 + 算法（= 数据的存储 + 数据的操作 + 可以被计算机执行的语言）
• 数据结构是算法的基础

3. 看几个实际编程中遇到的问题

• 试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等 7 个成员函数 → 数据结构：单链表
• 五子棋程序：如何判断游戏的输赢，并可以完成 {存盘退出} 和 {继续上局} 的功能
  • 存盘退出：棋盘 → 二维数组 → 稀疏数组 → 写入文件
  • 继续上局：读取文件 → 稀疏数组 → 二维数组 → 棋盘
• 约瑟夫问题(丢手帕问题)：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列 → 单向环形链表
• 修路问题
  • 最小生成树
  • 普利姆算法
• 最短路径问题
  • 图
  • 弗洛伊德算法

4. 数据结构

4.1 线性结构

• 有 2 种不同的存储结构
  • 顺序存储结构：逻辑关系上相邻的两个元素在物理位置上也相邻。
  • 链式存储结构：一组任意的存储单元(离散存储)；数据元素之间通过指针连接（即每个数据除了存储其本身的信息外，还需要存储一个指向其直接后继的指针）。
• 常见的线性结构
  • 数组
  • 链表
  • 队列
  • 栈

4.2 非线性结构

• 二维数组、多维数组
• 广义表
• 树 结构
• 图 结构