数据结构课件第4章串学习教案.pptx

会计学2零个字符的串称为空串(nullstring)，它的长度(chángdù)为零。用“”来表示空串。例4-4假设(jiǎshè)a、b、c、d为如下4个字符串：
a=beijing，b=bei，c=jing，d=beijing
则：6串的逻辑结构和线性表极为相似，区别仅在于(zàiyú)串的数据对象约束为字符集(characterset)。在串的13种基本操作操作中，以下5种操作构成串类型的最小操作子集(zǐjí)，即：这些操作不可能利用其他操作来实现：如果在程序设计语言中，串只是作为输入或者输出的常量出现，则只需要存储此串的串值，即字符序列即可。但是在多数非数值处理的程序中，串也以变量(biànliàng)的形式出现。串有3种机内表示方法。串的定长顺序存储表示类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照予定义的大小，为每个定长的串变量分配一个固定长度的存储区，则可以(kěyǐ)用定长数组描述。1.定长顺序存储表示(biǎoshì)(1)串联(chuànlián)接StrCat(SString*s,SStringt)s->len+t.len≤MAXLEN
得到的串是正确(zhèngquè)的结果。s串长s->lenIntstrCat(SString*s,SStringt){
/*用s返回由s和t联接而成的新串。*/
/*如果没有(méiyǒu)截断，则返回flag=1，否则返回flag=0。*/elseif(s->len<MAXLEN){ /*截断(jiéduàn)t的一部份*/
for(i=s->len;i<MAXLEN;i++)
s->ch[i]=t.ch[i-s->len];
s->len=MAXLEN;
flag=0;
}(2)求子串SubString(SString*Sub,SStringS,pos,len)SubString(SString*Sub,SStringS,intpos,intlen){
/*用Sub返回(fǎnhuí)串S的下标pos起长度为len的子串。*/StrIndex(SStringS,intpos,SStringt){
/*求从主串s的下标pos起,串t第一次出现(chūxiàn)的位置,成功返回位置序号,不成功返回-1*/3.定长顺序存储结构串操作(cāozuò)的特点堆分配(fēnpèi)存储表示的特点是，仍然以一组地址连续的存储单元存储串值的字符序列，但是它们的存储空间是在程序执行过程中动态分配(fēnpèi)而得的。1.堆分配(fēnpèi)存储表示(1)堆串赋值函数(hánshù)(2)求串长(3)串比较(bǐjiào)(4)清空串(5)串插入(chārù)(在S中下标为pos前插入(chārù)串t)StrInsert(HString*s,intpos,HString*t){
/*在串s的下标pos之前(zhīqián)插入串t。*/3.堆分配存储结构串操作(cāozuò)的特点和线性表的链式存储结构相类似，也可以采用(cǎiyòng)链表方式存储串值。由于串结构的特殊性结构中的每个数据元素是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。结点大小为1（即每个结点存放(cúnfàng)一个字符）的链表：1.块链存储(cúnchǔ)表示a12.块链存储(cúnchǔ)的存储(cúnchǔ)密度