@TOC21_08_16王道计算机考研 数据结构（一）
一、 数据结构有什么用？
（1）将现实生活中的问题信息化。
（2）处理信息，创造价值。
相关课程：计算机组成原理，C语言，计算机网络，操作系统。
基本概念
（1）数据元素和数据项
数据的基本单位：数据元素
一个数据元素可由多个数据项组成，数据项是数据不可分割的最小单位。（数据项和数据元素都是由实际应用决定的）
（2）数据结构和数据对象
数据结构：存在一种或多种特定关系的数据元素集合。具有三要素：逻辑结构、物理结构和数据的运算。
数据对象：具有相同性质的数据元素的集合
（3）数据结构三要素
①逻辑结构：集合、线性结构（具有一对一关系，元素的前驱和后继）、树型结构（一对多结构）和图状结构（多对多关系）。
②存储结构：顺序存储（相邻元素的物理位置也要相邻）、链式存储（物理位置可以不相邻）、索引存储（需要构建索引表）和散列存储（哈希存储，直接根据关键字计算存储地址）。
ps:数据的存储结构会影响存储空间分配的方便程度、数据运算速度。
③数据的运算：包括数据的定义和实现。
数据的定义：指运算的功能，针对逻辑结构。
数据的实现：指运算的具体操作，针对存储结构。
（4）数据类型：一个值的集合和定义在此集合上的一组操作的总称。
原子类型：布尔类型、int类型
结构类型：如struct
抽象数据类型ADT：抽象数据组织和其相关的操作。
二、算法
（1）基本概念
算法是解决问题的操作步骤。
特性：有穷的（程序可以无穷）、确定的、可行的、有输入和输出的。
（2）时间复杂度（所用时间与问题规模n的关系）
不能只用事后时间统计，应该事前预估时间开销T(n)。
初级：计算程序中每个语句的执行次数。
中级：直接选最高阶为T(n)。
高级：顺序执行的代码只影响常数项，可以忽略。对于循环语句，只需要分析循环中的一个基本操作的执行次数和n的关系。对于多层嵌套循环：只需观察最深层循环的执行次数。
PS：对于输入数据不定影响输出的情况，应计最坏时间复杂度和平均复杂度。
（3）空间复杂度（内存开销S(n)和问题规模n的关系）
程序运行时的内存需求：将代码装入内存，存放数据（局部变量和参数）
PS：只需关注存储空间大小和问题规模n相关的变量。
