数据结构-基于Python语言（微课版） 课件T8-串(串)

串第四章：串

主讲：周翔回顾请分别简述栈和队列的操作特点。请思考循环队列是如何解决顺序队列的“溢出”问题的。预习检查请概括一下字符串的概念串的顺序存储原理本章目标3串的链式存储重点了解掌握2串的概念串的模式匹配算法串的顺序存储及实现1什么是串什么是串？什么是串字符串（string）又简称串，它是由0个或多个字符组成的有限序列，由一对双引号““””括起来。什么是串串的相关操作strAssign()：给串赋值；strLength()：求串的长度；strCopy()：复制串；strEqual()：判断两个串是否相等；strConnect()：连接两个串；strCompete()：比较两个串的大小；Insert()：插入操作；Delete()：删除操作；串的存储结构——顺序存储串的顺序存储在串的顺序存储结构中，用一组地址连续的空间，即数组来存储串中的字符，串中的每一个字符占据一个空间。像高级语言中的串一样，这里同样使用字符’\0’来标识串的结尾。串的存储结构——顺序存储串的顺序存储用顺序结构来实现串，需要先定义一个结构体来保存串的一些信息。str是指向串的指针，它在分配空间时，利用malloc()/free()来操作堆上的内存空间。typedefstructstring{ char*str;//指向串的指针 intlength;//串的长度}String;串的存储结构——顺序存储串的顺序存储赋值：在为串赋值时，需要先求出待赋值的串的长度，然后利用malloc()函数在堆上开辟相应大小的存储空间，再将要赋值的串复制到新开辟的空间中。求串的长度：求串的长度非常简单，只需要获取struct中的length变量即可。复制：将一个串t复制到串s中，需要将s串的空间释放，再重新为其分配与串t大小相等的空间，然后将t串的内容复制到s串中。串的存储结构——顺序存储串的顺序存储判断两个串是否相等：比较两个串是否相等，首先要判断其长度是否相等，在长度相等的前提下，再比对串的每一个字符是否相同。连接两个字符串：连接两个串，如将串s与串t连接起来，先用malloc()函数分配一段内存空间，其大小为s串与t串的长度之和；然后依次将串s与串t复制到新分配的空间，将s串指向这一段新分配的空间。比较两个串的大小：比较两个串的大小，并不是比较其长度，而是比较串中字符的大小。串的存储结构——顺序存储串的顺序存储插入：如果向串s中插入串t，则要先求出t串的长度，然后调用malloc()函数分配一块内存，大小为s串与t串的长度之和。如果t串要插入到s串的pos位置，则将s串pos位置前的字符复制到新开辟的内存中，然后将t串顺延复制过来，最后再将s串中pos位置后的字符复制进来。删除：删除串的某一个子串，例如删除s串中的某一个子串，则分配一块内存，大小为s串长度减去子串长度。要被删除的子串把s串分为前后两部分，先将前半部分复制到新开辟的内存空间中，然后再将后半部分复制进来，这样在新空间里的串就是s串删除后的串。串的存储结构——链式存储串的链式存储又叫作链串，它也是用链表来实现的，串中的每一个字符都用一个结点来存储。串的存储结构——链式存储串的链式存