C++数据结构笔记：数组、串与广义表解析

"这份文档是关于数据结构（C++）的上课笔记，主要涵盖了数组、串与广义表的相关知识，包括2020年4月22日至27日的学习内容。文档不仅详细记录了理论知识，还包含了可调试的代码示例，非常适合用于复习和作为数据结构编程的参考资料。" 在数据结构中，数组是一种基本且重要的数据组织形式，分为一维数组和二维数组。一维数组可以视为线性的数据存储结构，而二维数组则类似于表格，常用来表示矩阵。对于二维数组，特别是存储对阵矩阵时，可以使用一维数组进行压缩存储以节省空间。例如，对于上三角矩阵，可以通过公式计算一维数组下标，如若i<j，矩阵元素A[i][j]的对应一维数组下标可以用i*(i+1)/2+j表示。反之，已知一维数组下标k，可以通过解不等式找到二维数组的行号i和列号j。 字符串(String)是另一个关键概念，它是由n个字符组成的有限序列。字符串的长度n表示字符的数量，n=0则表示空串。字符串的操作包括子串提取、串赋值和串连接。子串是指字符串中任意连续字符组成的序列，可以使用索引来定位子串在主串中的位置。主串则是包含子串的原始字符串。例如，编程实现这些操作时，可以设计函数来实现指定位置开始的子串提取，或者将两个字符串拼接成一个新的字符串。 串的模式匹配是字符串处理中的一个重要问题，这里提到了朴素的模式匹配算法，即Boyer-Moore算法（B-F算法）。该算法通过预处理模式串，创建一个坏字符规则表，从而在主串中快速跳过不可能匹配的部分，提高查找效率。在实际应用中，当需要在一个文本中查找特定模式时，这种算法非常实用。 在数据结构中，广义表（Generalized List）是一种更通用的数据结构，它可以表示具有复杂层次关系的数据。广义表可以看作是由零个或多个元素（可以是原子或子广义表）组成的序列。在广义表中，我们可以进行插入、删除、查找等操作，处理复杂的数据结构。虽然标签中提到了"广义表"，但文档内容未提供具体细节，这可能是后续章节的内容。 这份笔记详细介绍了数组、字符串和广义表的基本概念、操作方法以及实际应用，对于理解和掌握数据结构的基础知识非常有帮助。通过深入学习这些内容，可以为解决更复杂的编程问题打下坚实的基础。