数据结构总结：逻辑结构、存储结构和时间复杂度

数据结构期末复习总结宣贯.pdf 数据结构是计算机科学的基础，是计算机科学与技术的核心内容。数据结构是指计算机中存储、组织和处理数据的方式和方法。它是计算机科学与技术的核心内容，涉及到计算机科学与技术的方方面面。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。例如，在整数这个集合中，10这个数就可称是一个数据元素。 数据结构的定义包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。逻辑结构是指数据在计算机中的组织方式，包括线性结构、树形结构、复杂结构等。存储结构是指数据在计算机中的存储方式，包括顺序表示、链接表示、散列表示、索引表示等。对数据的操作是指对数据的各种操作，包括插入、删除、查找、排序等。 时间复杂度和渐近时间复杂度是衡量算法性能的重要指标。时间复杂度是指某个算法的时间耗费，它是该算法所求解问题规模n的函数。渐近时间复杂度是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。通常，我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 线性表是最基本的数据结构之一。线性表的逻辑结构特征是很容易理解的，如其名，它的逻辑结构特征就好象是一条线，上面打了一个个结，很形象的。如果这条线上面有结，那么它就是非空表，只能有一个开始结点，有且只能有一个终端结点，其它的结前后所相邻的也只能是一个结点（直接前趋和直接后继）。关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。 线性表的逻辑结构和存储结构之间的关系。在计算机中，如何把线性表的结点存放到存储单元中，就有许多方法，最简单的方法就是按顺序存储。就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。在顺序表中实现的基本运算主要讨论了插入和删除两种运算。对于顺序表的插入和删除运算，其平均时间复杂度均为O(n)。 线性表的链式存储结构是另外一种常见的存储结构。它与顺序表不同，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。在链表中，插入和删除运算的时间复杂度也为O(n)。 数据结构是计算机科学与技术的核心内容，涉及到计算机科学与技术的方方面面。理解数据结构的概念和原理是计算机科学与技术的基础，掌握数据结构的知识是计算机科学与技术的必备条件。