数据结构与算法（c 描述）-z6尊龙旗舰厅

讲解第1章的内容 18—26页

讲解第2章的内容27--36页

重点:

1、掌握算法复杂度的计算【难点、重点】

2、线性表的逻辑结构

3、线性表的存储结构-顺序结构

4、线性表顺序存储结构的实现【重点】

练习内容:

25页习题2:分析以下各程序段，并用大o记号表示其执行时间。

师说:

具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。那么，什么是线性表呢?
线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿起来，再存储到物理空间中”。

如图 1 所示，这是一组具有“一对一”关系的数据，我们接下来采用线性表将其储存到物理空间中。首先，用“一根线儿”把它们按照顺序“串”起来，如图 2 所示:

图 2 中，左侧是“串”起来的数据，右侧是空闲的物理空间。把这“一串儿”数据放置到物理空间，我们可以选择以下两种方式，如图 3 所示。

图 3 两种线性存储结构

图 3a) 是多数人想到的存储方式，而图 3b) 却少有人想到。我们知道，数据存储的成功与否，取决于是否能将数据完整地复原成它本来的样子。如果把图 3a) 和图 3b) 线的一头扯起，你会发现数据的位置依旧没有发生改变（和图 1 一样）。因此可以认定，这两种存储方式都是正确的。

将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。

虽然线性结构是最简单且最广泛的一种数据结构，但往往简单中也可以设计出巧妙的算法，腾讯公司2014年的一道面试题:“快速找到未知长度单链表的中间节点”；2021年某公司春招的一道面试题“为什么redis字典一般不用线性表实现?”等等，大家可以自己思考一下，你会如何完成，然后百度一下其他人的思路，对比一下。

面试会出哪些经典算法题?

推荐阅读: