【408数据结构】第一章 绪论

第一章 绪论

1.数据结构基本概念及三要素

一.数据结构基本概念

1.数据

信息的载体，能被客观事物描述的数字，字符以及能被计算机程序识别和处理的符号的集合

2.数据元素

数据的基本单位，一个数据元素可由若干个数据项（构成数据元素的最小不可分割的最小单位）组成。例如：学生记录是一个数据元素；姓名，班级，学号等则是组成学生记录的数据项。

3.数据对象

数据的一个子集，具有相同性质的数据元素的集合。

4.数据类型

1. 原子类型（其值不可再分）
2. 结构类型（其值可再分解成若干成分的数据类型）
3. 抽象数据类型

二.数据结构三要素

逻辑结构，存储结构，数据运算

1.逻辑结构

可细分为线性结构和非线性结构。
线性结构：一般线性表，栈和队列，串，数组。
非线性结构：集合，树形结构（一般树，二叉树），图状网状结构（有向，无向）
逻辑结构元素间的的关系：线性结构（一对一），树形结构（一对多），图状结构（多对多）。

2.存储结构

也称物理结构，主要有顺序存储，链式存储，索引存储，散列存储。

2.算法和算法的评价

一.算法基本概念

算法是对特定问题求解步骤的一种描述，他是指令的有限序列，一个算法还具有五个重要特性：

1. 有穷性（总是在执行有穷次步骤后结束，每一步都在有穷时间内结束）
2. 确定性（每条指令有确切的含义，相同的输入只能得出相同的输出）
3. 可行性（算法中描述的操作可以通过实现基本的运算执行有限次结束）
4. 输入（可以有零个或多个）
5. 输出（可以有一个或多个）

好的算法应该具有：

1. 正确性
2. 可读性
3. 健壮性（输入非法数据可进行处理）
4. 高效率（算法执行时间）与低存储量需求（执行算法所需的存储空间）

二.算法效率的度量

算法的效率度量是通过时间复杂度和空间复杂度来描述的

1.时间复杂度

语句在算法中执行的频率

时间复杂度计算方法可以参考该博主的博客：时间复杂度计算方法详解

2.空间复杂度

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。