408计算机考研-101-数据结构-基本概念

数据结构

数据结构(Data Structure)是计算机存储、组织数据的方式。

数据结构分为逻辑结构和物理结构(存储结构)

逻辑结构

逻辑结构是指数据之间的相互关系和组织方式。

按照数据元素之间的关系不同，可以分为以下4种：

• 集合结构
• 线性接口
• 树结构
• 图结构
  

其中集合、树、图属于非线性结构。按照线性和非线性可以分为如下关系：

在C语言中，数组是一种有序且类型相同的数据元素集合，数组的逻辑结构可以表示为线性结构，其中每个元素都有一个唯一的下标来表示其位置。
而数组的物理结构可以根据存储方式分为顺序存储结构和链式存储结构。在顺序存储结构中，数组元素在内存中是连续存储的，每个元素占据固定的内存空间；而在链式存储结构中，数组元素通过指针来连接，每个元素可以存储在任意的内存位置上。
因此，可以说数组在C语言中既是一种逻辑结构，表示数据元素之间的关系，又是一种物理结构，表示数据元素在计算机内存中的存储方式。

物理结构(存储结构)

物理结构是指数据元素在计算机内存中的存储关系。

• 顺序存储
• 链式存储
• 索引存储
• 散列存储

算法

算法(Algorithm)是对特定问题求解步骤的一种描述。它的表现形式是计算机指令的有限序列，执行这些指令就能解决特定的问题。

• 算法的基本特性:
  • 有穷性：一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
  • 确定性：算法的每一步都必须是确定的，即给定初始输入，算法的每一步都有唯一的结果。
  • 可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
  • 输入：一个算法有零个或多个输入。
  • 输出：一个算法有一个或多个输出。
• 评价算法优劣的基本标准：
  • 正确性：在合理的数据输入下，能够在有限的运行时间内得到正确的结果。
  • 可读性：首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法易于隐藏错误，且难于调试和修改。
  • 健壮性：当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。
  • 高效性：高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

时间复杂度

为了客观地反映一个算法的执行时间，可以只用算法中的“基本语句”的执行次数来度量算法的工作量。所谓“基本语句”指的是算法中重复执行次数和算法的执行时间成正比的语句，它对算法运行时间的贡献最大。通常，算法的执行时间是随问题规模增长而增长的，因此对算法的评价通常只需考虑其随问题规模增长的趋势。这种情况下，我们只需要考虑当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶。

常见的渐进时间复杂度：
$$O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(!n)<O(n^n)$$
计算时间复杂度时可以按照以下步骤进行：

1. 确定基本操作：找出算法中的基本操作，即最常执行的操作。
2. 计算执行次数：分析代码的循环、递归等结构，确定每个基本操作的执行次数。
3. 求时间复杂度：根据执行次数公式，计算出时间复杂度。

空间复杂度

一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需分析该算法在实现时所需要的辅助空间就可以了。

常见的渐进空间复杂度：
$$O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(!n)<O(n^n)$$
计算空间复杂度时可以按照以下步骤进行：

1. 确定变量空间：找出算法中占用空间的变量，包括输入、输出等。
2. 计算变量空间大小：分析代码执行过程中的变量空间使用情况，确定每个变量占用的空间大小。
3. 求空间复杂度：求出所有变量空间大小的和，得到空间复杂度。

参考资料

• 《王道数据结构》
• 《数据结构 C语言版》第二版 严蔚敏