数据结构第四章串.doc

第四章串：习题习 题 一、选择题 1下列关于串的叙述中，正确的是( )。 A.空串是由一个空格字符组成的串 B. 一个串的长度至少是1 C. 一个串的字符个数即该串的长度 D.两个串SI和s2若长度相同，则这两个串相等 2设有两个串S1和S2，求S2在S1中首次出现的位置的运算称为( )。 A.模式匹配 B.联接 C.求子串 D.求串长 3( )为空串。 AS= BS2= CS= a D. S=b 4sl=bc cad cabcadf，s2=”abc”，则s2在sl中的位置是( )。 A.7 B.8 C.6 D.9 二、填空题 1串具有_、_和_存储结构。 2两个串相等的充分必要条件是_。 3空串长度等于_；空格串长度等于_。 4在串的链式存储结构中，每个结点域可以存放_字符，也可以存放_字符，通常将每个结点所存储的字符个数称为结点的大小。 若S1=“ab cdefg”，S2=”def，求下列58串运算的值： 5Index (s1，“c”)_ 。 6. SubStr (s1,2,3)=_. 7. Concat(s1,s2)后，s1=_。 8 Length(s1)=_。 三、简答题 1简述空串和空格串的区别。 2串主要有哪几种存储结构？各有什么特点？ 3设s=I am a worker，t=good, u=teacher。 求：Length(s), Length(t), SubStr(s,8,6), SubStr(t,2,1), Index(s，”A), Index(s,t),Replace(s,8,6,u), Concat(SubStr(s,6,2), Concat(t,SubStr(s,7,7)。第四章 串第4章 串 一、选择题（参考答案） l.C 2A 3B 4D 二、填空题（参考答案） 1顺序，链式，堆分配。 2两个串的长度相等且对应位置的字符相同。 3零，空格字符组成的串中所包含的空格个数。 4一个，多个。 5.4. 6bc。 7ab cdefgdef。 8.8。 三、简答题 1空串和空格串的区别如下： 空串是零个字符的串，空串的长度为零;空格串是由一个或多个空格字符组成的串，空格串长度等于其包含的空格个数。 2串主要有那几种存储结构？各有什么特点？ 参见4.2 3已知：s=“(xyz)+*”，t=“(X+z)*y”。试利用联接、求子串和置换等基本运算，将s转换为t。 提示：s1= SubStr(s,3,1); s2= SubStr(s,6,1); s3= SubStr(s,7,1); s4= SubStr (Replace (s,3,1,s2),1,5); t=Concat (Concat (s4, s3),sl) 4串s=“abcabaa”的next函数值，如下表所示： 四、算法题 1试编写一个算法，在串的顺序存储结构上实现求串长度的基本运算。 int length(char s) int i; i=0; while(si!=0) i+; return i; 利用下面的函数可以对算法的功能进行测试 main() char s50; printf（n请输入字符串：（串长不超过50）; scanf(%s，s); printf(this string length is:%d,length (s); 2在串的顺序存储结构上实现串的赋值的基本算法。 void Assign( string *s，string t) /s为串指针类型的参数 /将串变量t的值赋给串变量s int i; for (i=0; it.curlen; i+) sstr i =t.stri; s.curlen=t.curlen; 3试编写一个算法，在串的顺序存储结构上实现从串s中删去从第pos个字符起长度len的子串。具体算法如下 string Delete (string s,int pos, int len) /从串s中删去从第pos个字符起长度为len的子串 int k; string ch; ch.curlen =0; if (poss.curlen-l|pos+len-ls.curlen) return ch; /参数不正确时返回空串 /将s.str 0s.str pos-l复制至ch for (k=0; kpos; k+) ch.str k =s. strk; /将s.str pos+len sstrscurlen-l复制至ch for( k=pos+len; knext, *p2=t-next, *q, *r; str_temp= (Lstring*) malloc( sizeof (Lstring); St r_temp- next=NULL; r= st r_temp. if (poss，curlen)/参数不正确时返回空串 return str_temp; for（k=0; kstr=pl-str; q- next=NULL; r-next=q; r=q; pl=pl-next; while (p2!=NULL) /将t的所有结点复制到str_t emp q= (Lstring*) malloc( sizeof (Lstring); q-str=p2-str; q-next=NULL; r-next=q; r=q; p2=p2 -next; while (p1!=NULL) /将*pl及其后的结点复制到str_t emp q= (Lstring*) malloc( sizeof (Lstring); q-str=pl-str; q-next=NULL; r-next=q; r=q; p1=p1-next; return str_temp; 5在串的链式存储结构（结点大小为1）上实现串的删除算法。 Lstring *Delete (lstring *s, int pos, int len) /从串s中删去从第pos个字符起长度为len的子串 int k; Lstring +str_temp, *p=s-next, *q, *r; str_temp= (Lstring*) malloc( sizeof (Lstring); str_temp-next=NULL; r=str_t emp; if (poslength (s) -1 | lenlength(s) return str_temp; /参数不正确时返回空串 for( k=0; kstr=p-str; q-next=NULL; r-next=q; r=q; p=p-next; for( k=0; knext; while(p!=NuLL)( /将*p及其后的结点复制到str_t emp q = (Lstring*) malloc( sizeof (Lstring); q-str=p-str; q-next=NULL; r-next=q; r=q; p=p-next; return str_temp; 6在串的堆分配存储结构上实现串的插入基本运算。 int Insert (HString &s,int pos,HString t) /在串s的第pos个字符之前插入串t int i; if (poss.curlen) return O; /插入位置不合法 if (t.curlen) /t非空，则为s重新分配空间并插入t if(!(s.str= (char*) realloc(s.str,(s.curlen+t. curlen) *sizeof( char) exit( overflow); for(i=S.curlen-l; ipos-l; -i) sstr i+t.curlen=s.stri; /为t空出插入位置 for (i=0; i0) printf(%so/s,s,t); else if (strcmp (s,t)0) printf(%s%s，s，t); else printf(%s=%s”,s,t); 8.一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为： abcdefghijklmnopqrstuvwsyz qwertyuiopasdfghjklzxcvbnm 则字符串encrypt被加密为tfeknhz。试写算法： (l)将输入的文本串进行加密后输出。 (2)将输入的加密文本串进行解密后输出。 加密算法可以用两个串中字符的一一对应关系来实现，当输入一个字符时，由算法在串l中查找其位置，然后用串2中相应位置的字符去替换原来的字符就可以了。解密算法则恰恰相反。算法如下： (1)串匹配（子串只有一个字符） int StrMatch (char S,char c) int i; for (i=O;istrlen (S); i+) if (c=S i)return i; /匹配成功，返回位置 return NULL; /映射表中没有相应字符 void Encryp (char *T) /对文本串进行加密 int