数据结构考纲概论.pdf

数据结构知识总结 1. 线性结构 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小 标识单位。 ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·原子类型：由语言提供。 ·结构类型：由用户借助于描述机制定义，是导出类型。 算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出。 算法设计的要求：正确性、可读性、健壮性、高效性、低存储量 时间复杂度是某个算法的时间耗费，它是该算法所求解问题规模n 的函数。一般指算法 的执行次数。 О（1）表示实践复杂性为常数 常见的时间复杂性及其比较： О（1） О（㏒㏒n ） О（㏒n ） О（n ） О （n ㏒ n ） О（n2 ） О（n3 ） О（2n ） 空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模 n 的函数。 算法的时间复杂度和空间复杂度合称算法复杂度。通常使用时间复杂度较高。 1.1 数组 1. 1.1.1 数组的概念 数组是一种扩展的线性数据结构。线性表、栈、队列、串的数据元素都是不可再分的原 子类型，而数组中的数据元素是可以再分的。数组可以分为一维数组和多维数组，一维数组 中的元素是由原子构成的，多维数组中的元素又是一个线性表。因此，数组是一种特殊的线 性表。 数组是由 n 个相同数据类型的数据元素(a0,a1,a2,…an-1)组成的有限序列。其中，这 n 个数据元素占用一块地址连续的存储空间。数组中的数据元素可以是原子类型的，如整型、 字符型、浮点型等，这种类型的数组称为一维数组；也可以是一个线性表，这种类型的数组 称为二维数组。二维数组可以看成是线性表的线性表。 特殊矩阵的压缩存储 在许多科学与工程计算中会经常遇到矩阵运算的问题，在高级语言中，通常使用二维数 组来存储矩阵。然而，在矩阵的运算中，往往在阶数很高的矩阵中存在许多相同的元素或值 为零的元素。为了节省空间，需要将这些矩阵进行压缩存储。 对称矩阵的压缩存储 如果一个 n 阶的矩阵 A 中的元素满足性质 aij=aji(0≤i,j≤n-1) ，则称这种矩阵为 n 阶对 称矩阵。 由于对称矩阵中的元素关于主对角线对称，因此，在对矩阵存储时，可以只存储对称矩 阵中的上三角或者下三角的元素，使得对称的元素共享一个存储单元。 稀疏矩阵的三元组表示 为了实现压缩存储，可以只存储稀疏矩阵的非零的元素。在存储稀疏矩阵中的非零元素 时，还必须存储非零元素对应的行和列的位置(i,j) 。也就是说存储一个非零元素需要存储元 素的行号、列号和元素值，即通过存储(i,j,aij)唯一确定一个非零的元素。 稀疏矩阵的十字链表表示与实现 采用三元组顺序表在进行两个稀疏矩阵的相加和相乘运算时，需要移动大量的元素，算 法的时间复杂度也大大增加。因此，本节来学习稀疏矩阵的另一种存储结构链式存储。 1.1.2 数组的应用 数组一般用顺序存储的方式表示。 存储的方式有： ·行优先顺序，也就是把数组逐行依次排列。PASCAL 、C ·列优先顺序，就是把数组逐列依次排列。FORTRAN 地址的计算方法： ·按行优先顺序排列的数组：LOCa （ij ）=LOCa （11）+ （（i-1 ）*n+ （j-1 ））*d. ·按列优先顺序排列的数组：LOCa （ij ）=LOCa （11）+ （（j-1 ）*n+ （i-1 ））*d. 矩阵的压缩存储：为多个相同的非零元素分配一个存储空间；对零元素不分配空间。