第 1 章 -- 绪论

第一章： 绪论

1.1 数据结构的基本概念

1.1.1基本概念和术语

1.数据

$\quad$信息的载体，描述客观事物属性的数、字符等能输入到计算机中并被计算机处理的集合。

2.数据元素

$\quad$ 是数据的基本单位，通常作为一个整体进行考虑。但注意数据元素可以被拆分为若干个数据项。比如一条学生记录是一个数据元素，身份证号、性别、姓名都是一个数据项。

3.数据对象

4.数据类型

5.数据结构

$\quad $ 数据结构包括 逻辑结构、物理结构、数据的运算。

1.1.2 数据结构的三要素

1.逻辑结构

$\quad $ 线性结构：一般线性表、受限线性表（队列、栈、串）、线性表的推广（数组）

$\quad$ 非线性结构：集合、树形结构（二叉树）、图结构（有向图、无向图）

2.存储结构

$\quad$ 顺序存储：相邻存储

$\quad$ 链式存储：借助指针来连接元素存储的顺序关系

$\quad$ 索引存储：用索引表来进行检索。 优点：检索速度快。

$\quad$ 散列存储：又称哈希存储。优点：检索、增删结点都很快。 对于散列函数的依赖较大。

3.数据的运算

$\quad$ 包括对于数据运算的定义和实现。

1.2 算法和算法评价

1.2.1 算法的基本概念

$\quad$ 算法的五大特性： 有穷性、确定性、可行性、输入（可以有0个输入）、输出（一定要有 ）。

$\quad$ 好的算法： 正确性、可读性、健壮性、效率与低存储量需求。

1.2.2 算法效率的度量

1.时间复杂度

$\quad$ 通常使用O(n) 来表示一个算法的时间复杂度。

2.空间复杂度

$\quad$ 一般是问题规模n的函数。