imicola 课程考核
课程考核

课程考核

724 字 · 约 2 分钟

对于课程考核,本课程按照下面划分

方式 分数
平时表现 20%
作业 20%
实验 10%
期末考试 50%

绪论

数据结构研究什么?

  • 非数值计算问题的操作对象
  • 对象之间的关系
  • 在计算机中的表示和实现

数据结构的用法

  • 通过预先分析问题来确定必须达到的 性能目标
  • 挑选出恰当的数据结构

基本概念与术语

数据结构:

  • 定义: 由某一数据结构的集合及该集合所有数据元素之间的关系构成

数据结构的逻辑结构:

  • 数据的逻辑结构从逻辑关系上描述数据,只指向数据之间的逻辑关系
  • 可以看作是从具体问题中抽象出来的数学模型
  • 其可以分为: 线性结构,树状结构,图

数据的存储结构

从底层上而言,其储存结构可以分为顺序存储结构与链式存储结构

抽象数据模型

数据类型:

  • 定义:一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称
  • 例如:C语言中有如下数据类型
    • char int float double 等
  • 构造数据类型由 不同成员 构成
  • 基本的数据类型可以看作是计算机中已实现的数据类型

抽象数据类型

  • 是指一个数学模型以及定义在这个数学模型上的一组操作
  • 特性
    • 抽象: 通过外部接口访问其功能
    • 封装: 将实现细节与外部特性分离

一个简单的实例 三元组

template <typename T1, typename T2, typename T3>
class ppair
{
private:
public:
    T1 _first;
    T2 _second;
    T3 _third;
    ppair(const T1 &a, const T2 &b, const T3 &c)
    {
        _first = a;
        _second = b;
        _third = c;
    }
};
cpp

算法与算法分析

算法是为了解决某类问题而规定的一个有限长的操作序列,为了度量算法的效率,我们通常使用复杂度来评估

时间复杂度

一个算法的时间复杂度只和其问题的规模有关系,在计算时间复杂度的时候我们通常只关心规模最大的子问题,即对于O(F)O(F),FF是一个多项式,我们只关心幂次最高的项并且忽略常数

例如:

O(42n2+2log⁡n+18079n)⟹O(n2)O(42n^{2}+ 2\log n +18079n) \Longrightarrow O(n^{2})

空间复杂度

与时间复杂度类似,空间复杂度也是只关心最大规模子问题所占用的空间规模