程序员必备——数据结构入门

前言:数据结构与算法作为计算机经典的基础理论课程,同时作为计算机类专业考研课程,并且在校招面试时常被提及,其重要性可见一斑。除此之外,学习这门课程有助于我们用编程去解决、思考问题,设计出更简洁、效率更高的代码。

一.课程概述

  • 数据结构课程研究什么?

    • 内存中基本数据组织和数据处理的方法
    • 非数值问题
  • 通过学习数据结构获得什么?

    • 经典数据结构和经典算法的基本原理
  • 学习重点

    • 数据结构的逻辑特性和存储结构设计
    • 数据结构算法设计基本方法和分析方法
    • 利用数据结构解决实际问题

二.基本概念与术语

  • 数据

    • 能输入到计算机中,被程序识别和处理的一切事物的符号化表示
  • 数据元素

    • 数据的基本单位
  • 数据项

    • 构成数据元素的最小单位
  • 存储结构(由想法到算法)

    • 顺序存储结构
    • 链式存储结构
  • 逻辑结构(由问题到想法)

    • 一种逻辑结构可由多种存储结构实现
  • 数据结构

    • 逻辑结构
    • 存储结构
    • 数据运算
  • 抽象数据类型(ADT)

    ADT 抽象数据类型名{
        数据对象的定义
        数据元素之间的逻辑关系定义
        基本运算定义
    }ADT
  • 算法的定义

    • 基于存储结构的运算实现的步骤
    • 满足有穷性确定性可行性
    • 有0个或多个输入,1个或多个输出
  • 什么是好的算法

    • 正确性:对于合法输入,算法能得出正确结果
    • 健壮性:对于非法输入,算法能做出特别处理
    • 可理解性:算法容易理解、实现
    • 高效性:具有较短执行时间并占用较少空间
    • 可修改、可拓展性

三.算法分析

  • 时间复杂度

    • 是算法求解问题规模n的函数,T(n)=F(n),F(n)是基本语句的执行频度
    • 增长率:忽略低次幂和最高次幂系数
  • 分析规则

    • 加法规则:针对并列程序段
    • 乘法规则:针对嵌套程序段
  • 例子

  • 常见的时间复杂度

    O(1)<(log2n)<(n)<(nlog2n)<(n²)<...<(2的n次方)<(n!)
  • 空间复杂度

    • 除去输入输出占用空间,算法临时占用的存储空间
    • S(n)=O(f(n))

完整内容可以访问我的个人博客:数据结构 515code.com

上一篇:【转载】PC端微信设置操作快捷键方法


下一篇:LeetCode-2.两数相加 使用链表加法实现