C版数据结构：第4章，字符串存储与模式匹配详解

本章主要探讨了C版本数据结构中的字符串概念及其在程序设计中的应用。字符串被定义为由零个或多个字符组成的有限序列，具有明确的逻辑结构，包括非空串、空串、子串、主串以及它们的位置定义。通过字符间的比较来判断串的相等性和顺序关系。 在逻辑结构方面，非空串通常用"S=s1s2……sn"的形式表示，其中"S"是串名，双引号内的部分是串值，而si表示单个字符。串的长度指的是串中字符的数量，空串长度为0，记作"\"。 为了存储字符串，有两种常见的存储结构方案。首先，顺序存储结构分为非压缩和压缩两种方式。非压缩方式每个数组单元只存储一个字符，可能导致空间浪费；而压缩方式尝试在一个单元内存储多个字符，但可能增加算法实现的复杂性。方案1采用一个额外的变量表示实际串长度，这样数组以字符的形式存储，末尾添加一个特殊字符（如`\0`）来表示串结束，空闲单元用于扩展。方案2是在串尾附加一个特殊的终止字符，如双引号或`\0`，但这可能导致误识别，因为它也可能出现在字符串中。 此外，对于模式匹配，本章会讲解如何通过比较字符来确定两个串的关系，例如完全相等、不等或顺序上的先后。例如，通过逐个比较S1="ab12cd"、S2="ab12"和S3="ab13"中的字符，可以确定它们之间的相对顺序。 总结来说，第4章字符串关注的核心内容是字符串的定义、逻辑结构、长度计算、存储方法（包括顺序存储的不同形式）以及模式匹配算法。这些知识点是编程中处理文本数据的基础，对于理解和实现字符串处理函数、字符串搜索和替换等操作至关重要。