数据结构 - 串实践报告(3)

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

{

/// 初始条件: 串S和T存在

/// 操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;若S

for(i=1; i<=S[0]&&i<=T[0]; ++i) if(S[i]!=T[i])

return S[i]-T[i]; return S[0]-T[0]; }

int StrLength(SString S) {

/// 返回串的元素个数 return S[0]; }

Status ClearString(SString S) {

/// 初始条件:串S存在。操作结果:将S清为空串 S[0]=0;// 令串长为零 return OK; }

Status Concat(SString &T,SString S1,SString S2) // 算法4.2改 {

// 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE int i;

if(S1[0]+S2[0]<=MAXSTRLEN) {

// 未截断

for(i=1; i<=S1[0]; i++) T[i]=S1[i];

for(i=1; i<=S2[0]; i++) T[S1[0]+i]=S2[i]; T[0]=S1[0]+S2[0]; return TRUE; } else {

// 截断S2

for(i=1; i<=S1[0]; i++) T[i]=S1[i];

for(i=1; i<=MAXSTRLEN-S1[0]; i++) T[S1[0]+i]=S2[i]; T[0]=MAXSTRLEN;

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

return FALSE; } }

Status SubString(SString &Sub,SString S,int pos,int len) {

/// 用Sub返回串S的第pos个字符起长度为len的子串。算法4.3 int i;

if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1) return ERROR; for(i=1; i<=len; i++) Sub[i]=S[pos+i-1]; Sub[0]=len; return OK; }

int Index(SString S,SString T,int pos) {

/// 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。 /// 其中,T非空,1≤pos≤StrLength(S)。算法4.5 int i,j;

if(1<=pos&&pos<=S[0]) {

i=pos; j=1;

while(i<=S[0]&&j<=T[0])

if(S[i]==T[j]) // 继续比较后继字符 {

++i; ++j; }

else // 指针后退重新开始匹配 {

i=i-j+2; j=1; } if(j>T[0])

return i-T[0]; else

return 0; } else

return 0; }

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

Status StrInsert(SString S,int pos,SString T) {

// 初始条件: 串S和T存在,1≤pos≤StrLength(S)+1

// 操作结果: 在串S的第pos个字符之前插入串T。完全插入返回TRUE,部分插入返回FALSE int i;

if(pos<1||pos>S[0]+1) return ERROR;

if(S[0]+T[0]<=MAXSTRLEN) {

///完全插入

for(i=S[0]; i>=pos; i--) S[i+T[0]]=S[i];

for(i=pos; i

///部分插入

for(i=MAXSTRLEN; i<=pos; i--) S[i]=S[i-T[0]];

for(i=pos; i

Status StrDelete(SString S,int pos,int len) {

// 初始条件: 串S存在,1≤pos≤StrLength(S)-len+1

// 操作结果: 从串S中删除第pos个字符起长度为len的子串 int i;

if(pos<1||pos>S[0]-len+1||len<0) return ERROR;

for(i=pos+len; i<=S[0]; i++) S[i-len]=S[i]; S[0]-=len; return OK; }

Status Replace(SString S,SString T,SString V)

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

{

// 初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关） // 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串 int i=1; // 从串S的第一个字符起查找串T if(StrEmpty(T)) // T是空串 return ERROR; do {

i=Index(S,T,i); // 结果i为从上一个i之后找到的子串T的位置 if(i) // 串S中存在串T {

StrDelete(S,i,StrLength(T)); // 删除该串T StrInsert(S,i,V); // 在原串T的位置插入串V

i+=StrLength(V); // 在插入的串V后面继续查找串T } }

while(i); return OK; }

void DestroyString() {

// 由于SString是定长类型,无法销毁 }

void StrPrint(SString T) {

// 输出字符串T。另加 int i;

for(i=1; i<=T[0]; i++) printf(\ printf(\// printf(\}

int main() {

SString a,b,c;

char aa[30]=\ StrAssign(a,aa); StrAssign(b,bb); StrAssign(c,cc); int bp=Index(a,b,1); int cp=Index(a,c,1);

SubString(b,a,bp,StrLength(a)-bp+1);

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

// StrPrint(b);

SubString(c,a,cp+StrLength(c),StrLength(a)-cp-StrLength(c)+1); // StrPrint(c); Concat(a,b,c); StrPrint(a); }

六、实验结果分析