数据结构一：绪论

（一）数据结构的基本概念

1.相关名词

【1】数据

1.信息的载体，描述客观事物

2.能被输入到计算机中

3.能被计算机程序识别和处理的符号的集合。

【2】数据元素

1.数据的一个“个体”

2.数据的基本单位

3.有时候也被称为元素、结点、顶点、记录等，这时候用于完整描述一个对象。ex：一条学生记录

【3】数据项

1.组成数据元素具有特定意义不可分割的最小单位

2.数据元素是数据项的集合

3.比如说在学生信息表中的一条学生记录（数据元素）中这个学生的学号或者性别这些都是数据项

【4】数据对象

1.具有相同性质的数据元素的集合

2.是数据的一个子集

【5】数据结构：通过抽象方法研究一组具有特定关系的数据的存储和处理，主要研究三个方面（三要素）：逻辑结构、存储结构和数据运算。

2.数据结构的三要素=逻辑结构+存储结构+数据运算

【1】逻辑结构

  有2种划分方式:1.按照线性和非线性分 2.按照结构分

1.线性和非线性

（1）线性：线性表、栈和队列、字符串、数组和广义表

（2）非线性：树和图

2.结构分（4种）

（1）集合结构：在同一个集合中，它们之间无关系

（2）线性结构：任意一个元素之间有且仅有一个前驱和后继，1对1

（3）树形结构：有一个前驱多个后继，1对多

（4）图形结构：有多个前驱多个后继，多对多

【2】存储结构（存储的逻辑结构4种）：顺序、链式、索引、散列（哈希）

*索引：类似课本目录，每页都有页码i，检索时利用结点（页）的顺序号i确定位置

*散列：也称哈希存储，用哈希函数将数据元素按照关键字和唯一的存储位置关联

【3】数据运算：插入、删除、查找、修改、排序等

（二）算法和算法分析

1.算法的基本概念

1.指令的有限序列

2.可以用自然语言描述

3.算法具有5个重要特性：有穷、确定、可行、输入输出

*有穷：步骤和执行时间有限

*确定：有确切含义、无二义、只有唯一的一条执行路径（对于相同的输入有唯一的执行结果）

*可行：执行有限次实现

*输入：0或多个

*输出：1或多个（最少1个结果）

4.算法和程序是两个不同的概念（区别）

*执行时间：算法步骤有限（有穷性），程序无限次执行

*语言描述：程序必须用规定语言，算法无限制可自然语言。

5.算法的基本目标：正确、易读、健壮、高效率

*健壮：当环境发生变化（非法输入）时候可以适当做出反应或者处理，不会产生不正确的结果

*高效率：较高的时间（用时少）和空间性能（占用空间少）

6.算法的评价方法：事前分析、事后统计

2.算法的时间和空间性能分析

【1】时间复杂度

1.T（N）表示该算法时间耗费，N为求解问题的规模

2.当N趋向于无穷时候，仅考虑数量级（阶），就是算法的渐进时间复杂度，用大o表示法

3.大o表示法就是忽略系数，类似数学的“抓大头”

4.语句频度：重复执行的次数

【2】用大o表示法求解算法的渐进时间复杂度（有6类）

1. 常量阶 O(1)：算法的执行时间不随输入数据的规模n变化，即无论输入数据有多大，算法的执行时间都是固定的。这类算法通常只包含基本操作，如赋值、比较等。

2. 对数阶 O（log n)：算法的执行时间随输入数据的规模n的对数增长。这类算法通常涉及到二分搜索或树结构的深度遍历。

3. 线性阶 O(n)：算法的执行时间随输入数据的规模n线性增长。这类算法通常涉及到对数据的顺序访问，如数组或列表的遍历。

4. 平方阶 O(n^2)：算法的执行时间随输入数据的规模n的平方增长。这类算法通常涉及到两层嵌套循环，如矩阵的乘法或对数组的每个元素进行比较。

5. 线性对数阶 O(n log n)：算法的执行时间是输入数据的规模n与对数的乘积。这类算法通常涉及到排序操作，如快速排序或归并排序。

6. 立方阶 O(n^3)：算法的执行时间随输入数据的规模n的立方增长。这类算法通常涉及到三层嵌套循环，如矩阵乘法的直接实现。