串、数组与广义表的数据结构详解

"广义表的基本运算-第4章+串、数组和广义表" 在计算机科学中，广义表是一种非常重要的数据结构，它能够灵活地表示复杂的数据组织形式。本章主要探讨了三种基本数据结构：串、数组和广义表，并深入讲解了广义表的基本运算。 1. 广义表的基本运算： - 求表头GetHead(L)：广义表GetHead操作用于获取非空广义表的第一个元素。这个元素可以是一个单一的原子，也可以是一个子表，即广义表中的一个嵌套结构。例如，对于广义表L = (a, (b, c), d)，GetHead(L) 将返回 'a'。 - 求表尾GetTail(L)：GetTail操作用于获取非空广义表除去第一个元素后的剩余部分，这通常是一个新的广义表。在上面的例子中，GetTail(L) 会返回 '(b, c), d'。 2. 串： - 串是字符的有限序列，可以为空。例如，"hello" 或 ""（空串）都是合法的串。串的长度是组成它的字符数量。 - 串的存储方式包括定长顺序串和堆串。定长顺序串是在内存中连续分配固定长度的空间来存储串，而堆串则利用堆数据结构进行存储，适用于动态变化的串。 - 串匹配，或模式匹配，是寻找一个字符串（模式）在另一个字符串（文本）中出现的过程，常用于网络入侵检测、病毒特征码匹配和DNA序列分析等领域。 3. 数组： - 数组是一组相同类型的数据元素的集合，这些元素在内存中以连续的方式存储。数组的每个元素可以通过索引来访问，索引通常从0开始。 - 地址计算是数组操作的关键，通过数组的起始地址和元素大小，可以计算出任意元素的地址。 - 压缩存储技术在处理特殊矩阵（如对角矩阵、三角矩阵等）时能有效节省空间。 4. 广义表： - 广义表是一种递归数据结构，它可以包含其他广义表作为元素，从而实现多层次的嵌套。 - 广义表可以用来表示复杂的数据结构，如树和图，以及在某些算法中作为临时数据结构。 - 在案例4.1中，DNA序列匹配问题就是利用串的概念来判断病毒DNA是否存在于患者DNA中。 学习目标包括掌握串的抽象数据类型定义、定长顺序串和堆串的存储结构及操作实现，理解数组存储时的地址计算，以及对特殊矩阵的压缩存储方法有基本了解。同时，广义表的特点和基本运算也是重点学习内容。