第四章串.pptVIP

第四章 串 第一节 串类型的定义 一、概念 串是一种特殊的线性表，它是由零个或多个字符组成的有限序列， 一般记作 s = ‘a1,a2, a3, ... an’ 其中 s----串名， a1,a2, a3, ... an----串值 串的应用非常广泛，许多高级语言中都把串的作为基本数据类型。在事务处理程序中，顾客的姓名、地址货物的名称、产地可作为字符串处理，文本文件中的每一行字符等也可作为字符串处理。 二、串的有关术语 1）子串 串中任意连续的字符组成的子序列称为该串的子串;例：c = “ DATA STRUCTURE”，f=“DATA” f是c的子串 2）子串的位置 子串t 在主串S中的位置是指主串s 中第一个与T相同的子串的首字母在主串中的位置; 例：s=“ababcabcac” , t=“abc” 子串T 在主串S中的位置为3 3）串相等 两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都相同； 三、串的基本操作 串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。 StrAssign (T, chars) 生成一个共值等于char的串T； StrCopy (T, S)复制串S到T； StrEmpty(S)测串S是否为空； StrCompare(S,T)两串比较； StrLength(S) 测串长度； ClearString(S)清空串； Concat(T, S1, S2)联接两串到新串T； Replace(S, T, V)用V替换S中出现的所有与T相等的子串； StrInsert (S, pos, T)在S中的第pos个字符之前插入串T； StrDelete (S, pos, len)删除S中第pos个字符起长度为len的串； DestroyString(S)销毁串； 第二节 串的表示和实现 一、定长顺序存储表示 定义：用一组地址连续的存储单元存储串值的字符序列。该存储空间为预定义大小。 #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN+1]; //下标为0的分量存放串的实际长度 5 h e l l o 0\ 0 1 2 3 4 5 6 7 … … 256 基本操作的实现： 串联结Concat (T, S1, S2) 算法分析： S1，S2联接后存入T有3种可能发生的情况： S1+S2=MAXSTRLEN S1+S2MAXSTRLEN这时要对S2串进行截断操作； S1=MAXSTRLEN则T为S1； Status Concat(SString T, SString S1, SString S2) { if (s1[0]+s2[0] = MAXSTRLEN) { T[1..S1[0]]=S1[1..S1[0]]; T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]]; T[0]=S1[0]+S2[0]; } else if (s1[0] MAXSTRLEN ) { T[1..S1[0]]=S1[1..S1[0]]; T[S1[0]+1..S1[0]+MAXSTRLEN-S1[0]] =S2[1.. MAXSTRLEN-S1[0]]; T[0]= MAXSTRLEN; } else { T[1..MAXSTRLEN]=S1[1..MAXSTRLEN]; T[0]=MAXSTRLEN; } Return OK; } 二、堆分配存储表示 以一组地址连续的存储空间存放串值，但空间大小不是预先给定，而是在程序执行过程中动态分配得来的。 动态分配函数： 分配空间malloc(), 释放空间free()； typedef struct { char *ch; int length; }HString; 顺序和堆两者的区别： 前者有预分配空间，后者无； 前者会有自动截断，后者无； 对同一个问题，后者申请空间频繁； 对0下标，前者特殊用，后者无； S1和S2联接到T用堆实现算