从零开始的数据结构——绪论
前言
数据结构是数据元素按照一种或多种特定关系组合而成的集合。是我们日常开发过程中需要学习的必不可少的一门学科。
本文主要记录一些数据结构的基本概念和术语。主要信息来源于清华大学出版社出版的《数据结构（C语言版）》。
基本概念和术语
- 数据：输入到计算机能被计算机程序处Ï理的符号的总称
- 数据元素：数据基本单位，由多个数据项组成
- 数据项：数据项是数据不可分割的最小单位
- 数据对象：性质相同的数据元素的集合
- 数据结构：相互之间存在一种或多种特定关系的数据元素的集合
- 原子类型：属原子类型的变量的值是不可分解的
- 固定聚合类型：由确定数目的成分按某种结构组成
- 可变聚合类型：相较于固定聚合类型，可变聚合类型的数目不确定
算法和算法分析
算法是对特定问题求解步骤的一种描述，是指令的优先序列。每个算法具有下列五个重要特性
- 有穷性：算法需要在有穷时间内完成
- 确定性：相同的输入只能获得相同的输出
- 可行性：能通过有限次操作获得结果
- 输入：一个算法可以有一个或多个数据，是数据集合
- 输出：一个算法可以有一个或多个输出
算法设计要求
- 正确性
- 不含语法错误
- 对于一切合法输入都能获得符合规格的结果
- 可读性：易于开发者阅读
- 健壮性：针对错误输入能提供异常信息等处理方式
- 效率与低存储量需求
算法效率的度量
算法效率的度量分为两个方面：时间度量、空间度量。
算法的时间效率取决于如下几个因素：
- 依据的算法选用何种策略
- 问题的规模、例如求100以内还是1000以内的素数
- 书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越低
- 编译程序所产生的机器代码的质量
- 机器执行指令的速度