您申请加入课程:数据结构与算法(C++描述)
需要验证您的身份,请输入课程密码:
您的学号:
班级选择:
课程密码:
  • 创建者

    Creator

    潘家辉
  • 活跃度

    Activeness

  • 访问量

    Visits

    211997

教学公告

22软工 第2周安排
[作者: 杨桂芝  发布时间:2023-09-12 19:54:53  浏览次数:593次]

讲解第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字典一般不用线性表实现?”等等,大家可以自己思考一下,你会如何完成,然后百度一下其他人的思路,对比一下。



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

https://www.zhihu.com/question/34814570

推荐阅读:

学习线性表,高深又烧脑?莫怕,手把手教你终结烦恼!(线性表:顺序存储结构)


相关课程

扫一扫二维码,快速加入本课程!

放大二维码 查看使用方法
关闭