串、数组和广义表

串与数组的定义

串

定义：串是一种字符序列，元素可以是字母、数字或其他字符。

特点：

• 串中的字符按照一定顺序排列。
• 串是线性结构，长度固定或可变。

主要操作：字符查找、子串匹配、插入、删除等。

数组

定义：数组是一组相同类型的数据元素按一定顺序存储的集合。

特点：

• 每个元素都有一个固定的索引位置。
• 索引从零开始。
• 数组在内存中是连续存储的。

空串与空格串的区别

空串

• 定义：长度为 0 的串，没有任何字符。
• 表示：""（双引号中无内容）。
• 特点：空串是合法的，是字符串的一个特殊形式。

空格串

• 定义：仅包含空格字符的串。
• 表示：" "（双引号中有一个或多个空格）。
• 特点：空格串的长度不为 0，字符串内容为一个或多个空格字符。

总结：空串是完全没有字符，长度为 0；空格串包含空格字符，长度不为 0。

广义表的表头、表尾、长度和深度

广义表的定义

广义表是一种递归定义的线性结构，其元素可以是：

• 原子：不可再分的数据元素。
• 子表：广义表中的一个元素，可以是另一个广义表。

术语解释

• 表头（Head）：广义表中第一个元素，可能是原子或子表。
• 表尾（Tail）：除去表头后剩余的部分，可能是空表或另一广义表。
• 长度（Length）：广义表中元素的个数（原子和子表均算一个元素）。
• 深度（Depth）：广义表中最大嵌套层次。

示例分析

广义表 $C=((a,b,c),(d,e))$

• 表头：$(a,b,c)$
• 表尾：$((d,e))$
• 长度：2（即 $(a,b,c)$ 和 $((d,e))$ 是两个元素）。
• 深度：2（最深嵌套层次为子表）。