数据结构-第四章.ppt

第4章4.1串案例4.1模拟“天书密码”的生成和破解案例说明天书是一条缠绕在一个圆柱体上的布条，信息纵向写在布条上。解码的过程是将布条解开传送给信息的接收者，接收者有一个同样大小的圆柱体就可以读懂密码。从理论上讲，没有这个圆柱体就不可能读懂密码，因为字母的顺序已经打乱。案例目的(1)理解串的有关概念及基本运算，了解串与线性表的关系。(2)使用串操作函数构造与串相关的算法解决简单的应用问题。4.1串技术要点以一种顺序将字符串读入一个数组，而以另一种方式输出字符串，从而使信息变得不可理解。设置明文密文字母映射表：代码1.串匹配typedefcharSeqString[27];/*定义串类型*//*以下两句设置加密及解密映射表*/SeqStringOriginal=abcdefghijklmnopqrstuvwxyz;SeqStringCipher=ngzqtcobmuhelkpdawxfyivrsj;intStrMatch(SeqStringS,charc){ /*串匹配(子串只有一个字符)*/ inti; for(i=0;istrlen(S);i++) {if(c==S[i])returni;}/*匹配成功，返回位置*/ return-1;/*映射表中没有相应字符*/}代码2.加密voidEncrypt(SeqStringOriginal,SeqStringCipher,char*T)/*加密*/{ inti,m; printf(\n); for(i=0;istrlen(T);i++) { m=StrMatch(Original,T[i]); if(m!=-1) T[i]=Cipher[m]; } printf(aencryptedstring:%s,T);}代码2.解密voidDecipher(SeqStringOriginal,SeqStringCipher,char*T)/*解密*/{ inti,m; printf(\n); for(i=0;istrlen(T);i++) { m=StrMatch(Cipher,T[i]); if(m!=-1) T[i]=Original[m]; } printf(aOriginalString:%s,T);}相关知识及注意事项1.串的概念及基本术语串定义是字符串的简称，是零个或多个字符组成的有限序列。一般记为：S=s0s1……sn-1(n≥0)其中S是串名；用双引号(“”)括起的字符序列是串的值；si(0≤I≤n-1)可以是字母、数字或其它符号；串字符的数目n称为串的长度；空串长度为零的串称为空串，它不包含任何字符。空格串由空格字符组成的串，它的长度为串中空格字符的个数。子串与主串串中任意个连续字符组成的子序列称为该串的子串。包含子串的串称为该子串的主串。子串的位置将子串在主串中首次出现时，该子串首字符对应的主串序列中的序号定义为子串在主串中的位置。串相等当且仅当两个串的长度相等，并且各个对应位置的字符也都相同，称两个串相等；例如：有下列四个串a，b，c，d：a1=,a2=,a=BEI，b=JINGc=BEIJING，d=BEIJING2.串的存储表示(1)串的顺序存储表示用一组地址连续的存储单元来依次存放串中的字符序列，串中相邻的字符顺序存放在相邻的存储单元中。①定长字符数组使用定长的字符数组存放串，一般使用特殊字符(如‘\0’)放在串值的末尾表示串的结束。类型定义如下:#defineMAXSTRLEN255typedefcharSString[MAXSTRLEN];②带串长的字符数组类型定义如下:#defineMAXSTRLEN255typedefstuct{charStr[MAXSTRLEN];intlength;}SeqString;③动态字符数组类型定义如下:typedefstuct{char*Str;intlength;}HString;3.顺序串基本运算的实现类型定义如下:typedefstuct{char*Str;intlength;}HSt