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

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

一.课程概述

• 数据结构课程研究什么？
  • 内存中基本数据组织和数据处理的方法
  • 非数值问题
• 通过学习数据结构获得什么？
  • 经典数据结构和经典算法的基本原理
• 学习重点
  • 数据结构的逻辑特性和存储结构设计
  • 数据结构算法设计基本方法和分析方法
  • 利用数据结构解决实际问题

二.基本概念与术语

• 数据
• 能输入到计算机中，被程序识别和处理的一切事物的符号化表示
• 数据元素
• 数据的基本单位
• 数据项
• 构成数据元素的最小单位
• 存储结构（由想法到算法）
• 顺序存储结构
• 链式存储结构
• 逻辑结构（由问题到想法）
• 一种逻辑结构可由多种存储结构实现
• 数据结构
• 逻辑结构
• 存储结构
• 数据运算
• 抽象数据类型（ADT）

ADT 抽象数据类型名{

数据对象的定义

数据元素之间的逻辑关系定义

基本运算定义

}ADT

• 算法的定义
• 基于存储结构的运算实现的步骤
• 满足有穷性、确定性、可行性
• 有0个或多个输入，1个或多个输出
• 什么是好的算法
• 正确性：对于合法输入，算法能得出正确结果
• 健壮性：对于非法输入，算法能做出特别处理
• 可理解性：算法容易理解、实现
• 高效性：具有较短执行时间并占用较少空间
• 可修改、可拓展性

三.算法分析

• 时间复杂度
• 是算法求解问题规模n的函数，T(n)=F(n)，F(n)是基本语句的执行频度
• 增长率：忽略低次幂和最高次幂系数
• 分析规则
• 加法规则：针对并列程序段
• 乘法规则：针对嵌套程序段
• 例子

++x; //复杂度O(1)

for(i=1;i<=n;++i)

++x; //复杂度O(n)

for(i=1;i<=n;++i)

for(j=1;j<=n;++j)

++x; //复杂度O(n²)

• 常见的时间复杂度

O(1)<(log2n)<(n)<(nlog2n)<(n²)<...<(2的n次方)<(n!)

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

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