数据结构chap004.ppt

嘉兴学院数学与信息工程学院 综合举例： 答案： s=’THIS SAMPLE IS’ t=’A GOOD’ (u=’ONE’) v=’THIS SAMPLE IS A GOOD ONE’ strlength(s)=14 Index(v, g)=3 Index(u,g)=0 　void replace(String S, String T, String V)　{ // 以串V替代串S中出现的所有和串T相同的子串　　 n=StrLength(S); m=StrLength(T); pos = 1;　　StrAssign(news, NullStr);　// 初始化 news 串为空串　　i=1;　　while ( pos = n-m+1 i )　　{　　　i=Index(S, T, pos);　// 从pos指示位置起查找串T　　　if (i!=0) {　　　　SubString(sub, S, pos, i-pos); // 不置换子串　　　　Concat(news, news, sub); // 联接S串中不被置换部分　　　　Concat(news, news, V);　　　// 联接V串　　　　pos = i+m; 　　　　// pos 移至继续查询的起始位置　　　} // if　　} // while　　SubString(sub, S, pos, n-pos+1); 　// 剩余串　　Concat( S, news, sub );　 // 联接剩余子串并将新的串赋给S　} 例如: 可利用串比较、求串长和截子串等操作实现子串的定位操作Index(S,T,pos)。 StrCompare(SubString(S, i, StrLength(T)),T ) ? 0 S 串 T 串 T 串 i pos n-m+1 算法的基本思想为： int Index (String S, String T, int pos) { // T为非空串。若主串S中第pos个字符之后存在与 T相等的子串，则返回第一个 这样的子串在S中的位置，否则返回0 } // Index while ( i = n-m+1) { SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) ++i ; else return i ; } // while n = StrLength(S); m = StrLength(T); i = pos; return 0; // S中不存在与T相等的子串 if (pos 0) { } // if P72/算法4.1 又如串的置换Replace(s,t,v)： S 串 T 串 V 串 V 串 pos pos sub1 i news 串 sub2 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别: 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。 一、串的定长顺序存储表示 二、串的堆分配存储表示 三、串的块链存储表示 4.3 串的表示和实现 #define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char Sstring [MAXSTRLEN + 1]; // 0号单元存放串的长度 一、串的定长顺序存储表示 Sstring s; n a1 a2 … an … S[0] s[1] s[2] s[3] … s[n] s[maxstrlen] 此单元用来存放串长值 则S的存储结构图如下： char S[maxstrlen+1]; 按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。 串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称