数据结构c语言版（严蔚敏）

《数据结构C语言版》第四章详细探讨了“串”的概念和实现，串是计算机科学中一种重要的数据结构，它由n（大于等于0）个字符组成的有限序列。本章内容包括字符串的基本术语、存储方式以及模式匹配算法。 字符串的定义包括串名字和串值，例如"Shenzhen University"就是一个例子，其中"Shenzhen University"是串值，而S是串名字。串的长度是指字符的数量，空串是没有字符的串，长度为0。空格串则是由一个或多个空格组成。子串是主串中任意个连续字符组成的子序列，例如在字符串"A=’Shenzhen University’"中，"University"就是子串，而"A"是主串。串的位置指的是字符在序列中的序号，串相等的条件是长度相同且对应位置的字符相等。 串与线性表有相似之处，都是线性结构，每个字符都有唯一的前驱和后继。然而，它们也有区别：串的数据对象限于字符集，且串的基本操作通常涉及整个串，比如查找子串和插入子串。 在串的存储表示方面，有三种主要方式：定长顺序存储、堆分配存储和链存储。定长顺序存储使用连续的内存空间，C语言中的字符串常以此形式存在，以'\0'作为结束标志。堆分配存储则是在程序运行时动态分配内存，允许更灵活的串长度处理。链存储则通过链表结构存储串值，每个节点可以存放一个或多个字符。 串的匹配算法是数据结构中的关键问题，这里介绍了基本的求子串位置的Index()函数，采用穷举法逐个字符比较。在最好情况下，时间复杂度为O(n+m)，但在最坏情况下，时间复杂度为O(n*m)。为了优化匹配效率，KMP算法被提出，它利用部分匹配的结果避免不必要的回溯，提高了匹配速度。 第四章深入讲解了串这一数据结构，涵盖了其基本概念、术语、存储方式和匹配算法，旨在帮助不同层次的学习者理解和应用字符串处理技术。通过学习这部分内容，可以提升对数据结构的理解，并为后续的编程实践奠定坚实基础。