程序员必备——数据结构入门-阿里云开发者社区

开发者社区> 大数据> 正文

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

简介: 数据结构是计算机存储、组织数据的方式。在这篇笔记中,记录了常见的线性表、栈与队列、树、图、排序和查找算法等知识点,精心选择这些数据结构可以带来更高的程序运行效率。

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

一.课程概述

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

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

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

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

二.基本概念与术语

  • 数据

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

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

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

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

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

    • 逻辑结构
    • 存储结构
    • 数据运算
  • 抽象数据类型(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

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
大数据
使用钉钉扫一扫加入圈子
+ 订阅

大数据计算实践乐园,近距离学习前沿技术

其他文章