数据结构复习：串与数组知识点详解

"这份数据结构复习资料涵盖了第4到第5章的内容，主要涉及串和数组，包括串的模式匹配、数组的存储布局以及广义表的操作等知识点。" 在数据结构中，串是一种基本的数据类型，用于表示一系列字符的序列。在本复习资料中，区分了空串和空白串的概念：空串是指不含任何字符的串，而空白串是由一个或多个空格字符组成的串。此外，介绍了字符串长度的计算方法，如在示例中，字符串"S=“A;/document/Mary.doc”"的长度为20，字符"/"的位置为3。 串的模式匹配是数据结构中的一个重要概念，它涉及到在一个主串（目标串）中查找一个子串（模式）。例如，当目标串为"T=“abccdcdccbaa”"，模式为"P=“cdcc”"时，第6次匹配成功。古典（朴素）匹配算法在最坏情况下需要比较的字符总次数为(n-m+1)*m，其中n为主串长度，m为子串长度。 数组是另一种基础数据结构，复习资料讨论了二维数组的存储方式。在给定的例子中，一个6行8列的数组A，每个元素占用6个字节，起始地址为1000。数组的体积（存储量）为288B，末尾元素A57的第一个字节地址为1282。根据存储方式的不同，无论是按行存储还是按列存储，都能计算出特定元素的地址。 数组的存储布局中，考研题目涉及到了以列序为主序的存储方式。例如，数组a[1...60, 1...70]，基地址为2048，每个元素占2个存储单元，元素a[32,58]的存储地址可以通过列优先公式计算得出，为8950。 复习资料还提到了稀疏矩阵的存储，通常通过三元素组表来表示，每个结点包含非零元素的行下标、列下标和值。这有助于节省存储空间，特别是在处理大部分元素为零的大矩阵时。 最后，复习资料中展示了广义表的一些基本操作，如GetHead和GetTail，它们用于获取列表的头元素或尾元素。例如，广义表((a,b),(c,d))的头元素是(a,b)，其尾元素是(c,d)，进一步获取(c,d)的头元素仍为(c,d)。 这份复习资料深入讲解了串的性质与操作、数组的存储布局、稀疏矩阵的表示以及广义表的常见操作，这些都是数据结构学习中的关键点，对于理解和解决问题具有重要意义。