数据结构知识点总结（1）

概论

1：数据的结构直接影响算法的选择和效率。

2：数据->数据元素（元素，结点，记录）数据的基本单位->数据项（字段，域）数据不可分割的最小单位

3：数据类型：原子数据类型：值不可分（整型，字符型，实型）和结构数据类型：值可分解（数组类型，结构类型）用户自己定义的

4：数据结构：逻辑结构，物理结构：存储结构（数据结构在计算机中的表示），运算特征。

逻辑结构：集合，线性结构（一对一），树型结构（一对多），图状结构（多对多）

运算：插入，删除，查找，排序。

数据结构定义：按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储表示方法把它们存储在

计算机的存储器中，并在这些数据上定义了一个运算的集合。

数据的4种基本存储方法：

顺序存储方法：逻辑上相邻的节点存储在物理位置相邻的存储单位中，结点之间的逻辑关系由存储单元的邻接关系来体现。

该方法主要应用于线性的数据结构。

链接存储方法：不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附加的指针来表示的。

索引存储方法：存储结点信息的同时，建立附加的索引表。索引表中的每一项称为索引项。索引项的一般形式：（关键字，地址）

散列存储方法：根据结点的关键字直接计算出该结点的存储地址。

例子：线性结构+顺序存储方法+栈=顺序栈，线性结构+链接存储方法+队列=链队列。

5：算法特性：有穷性，确定性，可行性，输入，输出。

6：算法好坏的判断依据：正确性，健壮性，可读性，执行耗费时间，执行耗费空间。

7：常用函数关系排序：c

8：算法是通过数据结构求解问题的步骤，程序是用数据类型描述的算法。

9：数据结构：

基础数据结构：

线性结构：线性表，栈，队列，串

非线性结构：数组，广义表，树，二叉树，图

应用数据结构：查找，内部排序，外部排序，文件。

图一为数据结构考试大纲

图二是根据考试大纲总结的应知应会