数据结构001

复习

2019年9月17日发布📑

编程遇到的实际问题

字符串替换问题

五子棋问题

- 二维数组
- 稀疏数组

约瑟夫问题(丢手帕问题) 单项环形链表

修路问题 树(加权值) + 普里姆算法

最短路径问题 图 + 弗洛伊德算法

汉诺塔 分治算法

八皇后 回溯法

线性结构与非线性结构

顺序存储和链式存储

线性结构常见的有: 数组、队列、链表和栈。

非线性结构包括: 二维数组,多维数组,广义表,树结构,图结构

稀疏数组,当一个数组中大部分元素为0,或者为同一个值的数组是,可以使用稀疏数组来保存这个数组。

  1. 记录数组一共有几行几列,有多少个不同的值
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模。

二维数组 转 稀疏数组的思路, 之后稀疏数组还要恢复到二维数组。