数据结构串学习教案.pptx

会计学串（或字符串），是由零个或多个字符组成(zǔchénɡ)的有穷序列。含零个字符的串称为空串，用Ф表示。
串中所含字符的个数称为该串的长度（或串长）。
通常将一个串表示成“a1a2…an”的形式。其中最外边的双引号本身不是串的内容，它们是串的标志，以便将串与标识符（如变量名等）加以区别。每个ai（1≤i≤n）代表一个字符。当且仅当两个串的长度相等并且各个对应(duìyìng)位置上的字符都相同时，这两个串才是相等的。
一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。例如，“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（真子串是指不包含自身的所有子串）。思考题：
串和线性表有什么(shénme)异同？例4.1问题(wèntí):“abcde”有多少个真子串?串的基本运算(yùnsuàn)如下:InsStr(s1,i,s2)：插入。将串s2插入到串s1的第i（1≤i≤n+1）个字符中，即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。
DelStr(s,i,j)：删除。从串s中删去从第i（1≤i≤n）个字符开始的长度为j的子串，并返回产生的新串。
RepStr(s,i,j,t)：替换(tìhuàn)。在串s中，将第i（1≤i≤n）个字符开始的j个字符构成的子串用串t替换(tìhuàn)，并返回产生的新串。
DispStr(s)：串输出。输出串s的所有元素值。4.2.1串的顺序存储及其基本操作实现(shíxiàn)串的顺序存储有两种方法：一种是每个单元只存一个(yīɡè)字符，这称为非紧缩格式（其存储密度小）；另一种是每个单元存放多个字符，这称为紧缩格式（其存储密度大）。对于非紧缩(jǐnsuō)格式的顺序串，其类型定义如下： 顺序(shùnxù)串中实现串的基本运算如下。（2）StrCopy(s,t)
将串t复制(fùzhì)给串s。（3）StrEqual(s,t)
判串相等：若两个串s与t相等返回(fǎnhuí)真（1）；否则返回(fǎnhuí)假（0）。（4）StrLength(s)
求串长：返回(fǎnhuí)串s中字符个数。（5）Concat(s,t)
串连接：返回由两个(liǎnɡɡè)串s和t连接在一起形成的新串。（6）SubStr(s,i,j)
求子串：返回(fǎnhuí)串s中从第i（1≤i≤StrLength(s)）个字符开始的、由连续j个字符组成的子串。参数不正确时返回(fǎnhuí)一个空串。（7）InsStr(s1,i,s2)
将串s2插入到串s1的第i（1≤i≤StrLength(s)+1）个字符中，即将(jíjiāng)s2的第一个字符作为s1的第i个字符，并返回产生的新串。参数不正确时返回一个空串。（8）DelStr(s,i,j)
从串s中删去第i（1≤i≤StrLength(s)）个字符开始的长度为j的子串，并返回产生的新串。参数不正确(zhèngquè)时返回一个空串。（9）RepStr(s,i,j,t)
在串s中，将第i（1≤i≤StrLength(s)）个字符开始的j个字符构成(gòuchéng)的子串用串t替换，并返回产生的新串。参数不正确时返回一个空串。（10）DispStr(s)
输出串s的所有(suǒyǒu)元素值。例设计顺序串上实现(shíxiàn)串比较运算Strcmp(s,t)的算法。intStrcmp(SqStrings,SqStringt)
{inti,comlen;
if(<t.length)comlen=;//求s和t的共同长度
elsecomlen=;
for(i=0;i<comlen;i++)//在共同长度内逐个(zhúgè)字符比较
if(s.data[i]>t.data[i])
return1;
elseif(s.data[i]<t.data[i])
return-1;
if(==) //s==t
return0;
elseif(>t.length)//s>t
return1;
elsereturn-1; //s<t
}4.2.2串的链式存储(cúnchǔ)及其基本操作实现以下两图分别表示了同一个串"ABCDEFGHIJKLMN"的节点大小(dàxiǎo)为4（存储密度大）和1（存储密度小）的链式存储结构。链串节点大小的选择与顺序串的格式选择类似。节点大小越大，则存储密度越大。但存储密度越大，一些操作（如插入、删除、替换等）有所不便，且可能引起大量字符移动，因此它适合于在串基本保持(bǎochí)静态使用方式时采用。节点大小越小（如节点大小为1时），运算处理越方便，但存储密度下降。为简便起见，这里规定链串节点大小均为1。下面讨论在链串上实现串基本(jīběn)运算的算法。（2）StrCopy(s,t