数据结构（基础知识）

基础概念：

数据：数据是信息的载体，是描述客观事物属性的数，字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合

数据元素：是数据的基本单位，在程序中常作为一个整体来考虑

数据对象：是具有相同构成的数据元素的集合，是数据的一个子集。

三者之间的关系：

数据由若干数据元素构成，而数据元素可由多个数据项构成

数据项：是数据不可再分的最小标识单位

数据元素描述的是个体，数据对象描述的是一个整体

数据结构：是互相有关联的数据元素的集合，元素之间的关系称为结构

DS=(D,R);DS=(D,S);

D是数据元素的有限集，R或S是D上关系的有限集

数据结构三要素

数据结构三要素：逻辑结构，存储结构，数据的运算

1.逻辑结构（重点）

由于数据结构中的关系描述了数据元素之间逻辑上的联系，因此也称这些关系为数据的逻辑结构，它与数据的存储无关，是独立于计算机的。

数据的逻辑结构可以把数据结构分为线性结构（线性表，栈，队列，数组）和非线性结构（集合树，图）。

2.存储结构（重点）

数据结构在计算机中的表示称为数据的存储结构或物理结构，包括数据元素的表示和关系的表示

数据的存储结构主要包括：顺序存储，链式存储，索引存储和散列存储。（简答）

（1）顺序存储：

逻辑上相邻的两个元素的物理位置也相邻。

优点：能够随机存取。

缺点：插入删除需要移动大量的元素，不方便。

（2）链式存储：

逻辑上相邻的两个元素的物理位置不一定相邻，每个结点用一个指针来找到下一个结点的位置。

优点：插入和删除很方便

缺点：随机读取时不方便，需要从第一个结点开始遍历

（3）索引存储：

在存储时，还附加建立索引表，索引表中的每一项称为索引项，索引项的一般形式是（关键字，地址）

优点：检索速度快

缺点：索引表占用存储空间，并且插入和删除一个数据时，对应的索引项也要插入和删除，会耗费较多的时间

（4）哈希存储：

通过函数，根据数据的元素的关键字计算该元素的地址

优点：检索、增加和删除结点的操作比较快

缺点：可能会出现元素存储单元的冲突，解决冲突又需要增加时间和空间的开销

3.数据的运算

施加在数据上的运算包括运算的定义和实现。

数据元素四种基本类型（简答）

1.集合

数据结构中的数据元素之间除了“同属于一个集合”的关系外，无其他关系。

2.线性结构（包括线性表，栈和队列）

数据结构中的数据元素之间存在1对1的关系。

3.树型结构

数据结构中的数据元素之间存在1对多的关系。

4.网状结构

数据结构中的数据元素之间存在多对多的关系。

4.抽象数据类型

数据对象，数据对象上关系的集合和对数据对象的基本操作的集合。

ADT = 或者ADT =

这里的D为数据 R或者S是D的关系 P是对D的基本操作集

算法的特点（简答）

（1）有穷性：能在有限的步内和有限时间内执行结束

（2）确定性：对于相同的输入执行相同路径，每条指令理解起来不会产生二义性。

（3）可行性：每条指令所表示的操作可由以实现操作的有限次运算来完成

（4）有输入：有大于等于0个来自某一特定集合的输入

（5）有输出：有大于等于1个同输入有特定关系的输出

算法的评价：正确性，可读性，健壮性，效率和存储量要求

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

算法的开销有两种方法：事后分析发和事前分析估算法

时间复杂度：一个语句的频度是指该语句在算法中被重复执行的次数

空间复杂度：该算法所消费的存储空间