圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台第4章串4.1复习笔记一、串及其操作1．串的逻辑结构定义串（或字符串）是由零个或多个字符组成的有限序列。一般记为S＝'a1a2…an'（n≥0）其中，S是串的名，用单引号括起来的字符序列是串的值；ai（1≤i≤n）可以是字母、数字或其他字符；n称为串的长度，零个字符的串称为空串。两个串相等：当且仅当这两个串的长度相等并且对应位置的字符全部相同。2．串的基本操作（1）ASSIGN(s,t)：赋值操作。（2）EQUAL(s,t)：判等函数。（3）LENGTH(s)：求串长函数。（4）CONCAT(s,t)：连接函数。（5）SUBSTR(s,start,len)：求子串函数。（6）INDEX(s,t)：定位函数。（7）REPLACE(s,t,v)：置换操作。（8）INSERT(s,pos,t)：插入操作。（9）DELETE(s,pos,len)：删除操作。二、串的存储结构1/186圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台1．静态存储结构串值的访问通过串名的存储映象进行，叫做串的静态存储结构。和线性表的顺序存储结构一样，采用一组地址连续的存储单元存储串中的字符序列。串的实际长度是在预定义分配的空间内随意变动的。一般有两种方式来表示串的实际长度：①将实际长度存储在数组下标为0的位置；②串的末尾用一个结束标记字符标记串的结束，比如C语言中以“\\0”标记串的结束。2．动态存储结构（1）块链存储结构和线性表的链式存储结构相类似，也可采用链表方式存储串值，但由于串中每个数据元素是一个字符，则在存储串的时候每个结点可以存放一个字符，也可以存放多个字符（避免空间的浪费），这种方式称为串的块链存储结构。例如，图4-1（a）是结点大小为4的链表，图4-1（b）是结点大小为1的链表。当结点大于1时，由于串长不一定是结点大小的整倍数，则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或其他的非串值字符。图4-1（2）堆结构串值的链表存储方式2/186圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台串的堆结构仍以一组地址连续的存储单元存放字符序列，但它们的存储空间是在程序执行过程中动态分配的。例如，C语言中用malloc()和free()管理内存空间。串的堆分配存储表示，既有顺序存储表示的特点，又弥补了定长存储的缺点。【注意】三种存储结构的比较①静态存储结构能够直接由串名访问串值，便于实现串的基本操作，但它在串的类型定义中预先规定了一个串允许的最大长度，内存空间利用率低，且在进行串的连接、置换等操作时易受存储空间限制；②块链存储结构虽串长不受限制，但受存储密度的制约，采取的“块的链表”使串的操作复杂化，且无法确定合适的结点大小。③堆结构虽然必须通过映象才能访问串值使操作稍感不便，但由于串值的存储空间在执行时才会分配，操作中更显灵活，且对串长没有任何限制。三、串基本操作的实现1．静态结构存储串时的操作由于顺序静态存储结构更容易实现串的基本操作，所以一般都采用它来存储串值。将串定义为长度在一定范围内可变的字符型数组，其长度的上界maxlen在常量中说明，如果在操作中出现串值序列的长度超过上界maxlen时，约定用截尾法进行处理，即丢弃超出maxlen部分的字符序列。（1）串的联接——CONCAT(l,s,t)函数假设l，s，t都是串变量，则联接运算是将s和t的串值分别传送到l的相应位置上，超过maxlen的部分截断。其运算结果可能有三种情况：①s.curlen＋t.curlen≤maxlen，如图4-2（a）所示，两字符串均能完整联接到l中；②s.curlen＋t.curlen＞maxlen而s.curlen＜maxlen，则将t的一部分截断，得到的l只包3/186圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台含t的一个子串，如图4-2（b）所示；③s.curlen＝maxlen，则得到的只是s一个串，如图4-2（c）所示。4/186圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台图4-2串的串联操作CONCAT(l,s,t)示意图5/186
严蔚敏《数据结构》配套辅导书(4-6章)【圣才出品】
