鏁版嵁缁撴瀯璇剧▼璇惧悗涔犻闆嗙瓟妗堣В鏋?- 鐧惧害鏂囧簱

4. 算法设计题

（1）设计一个算法RepChar(s,x,y)，将顺序串s中所有字符x替换成字符y。要求空间复杂度为O(1)。

解：因要求算法空间复杂度为O(1)，所以只能对串s直接替换。从头开始遍历串s，一旦找到字符x便将其替换成y。对应算法如下：

void RepStr(SqString &s,char x,char y) { }

int i;

for (i=0;i

if (s.data[i]==x)

s.data[i]=y;

（2）设计一个算法，判断链串s中所有元素是否为递增排列的。 解：用p和q指向链串s的两个连续结点，p先指向开始结点，当q->data≥p->data时，p和q同步后移一个结点；否则返回0。当所有元素是递增排列时返回1。对应算法如下：

int increase(LinkString *s) { }

LinkString *p=s->next,*q; if (p!=NULL) { } return 1;

while (p->next!=NULL) { }

q=p->next;

p=q;

//逆序时返回0

return 0;

//q指向*p的后续结点

if (q->data>=p->data) else

（3）假设以链式结构存储一个串s，设计一个算法求串s中最长等值子串。

解：假设串用带头结点的单链表存储串s。用max存放最大平台长度，扫描串s，计算一个平台的长度n，若n大于max，则置max为n。对应的算法如下：

int maxlength(LinkString *s) {

int n,max=0;

LinkString *p=s->next,*q; while (p!=NULL) {

n=1;

q=p;p=p->next;

while (p!=NULL && p->data==q->data) { }

if (n>max) max=n;

n++; p=p->next;

数据结构简明教程

}

} return max;

上机实验题4

两个非空串s和t采用顺序存储结构存储，设计一个算法求这两个串最大公共子串，并用相关数据进行测试。

解：采用Index算法思路设计由顺序串s、t产生最大公共子串str。对应的程序如下：

#include #include \ { } void main() {

SqString s,t,str;

Assign(s,\Assign(t,\printf(\SqString str;

int midx=0,mlen=0,tlen,i=0,j,k; while (i

for (i=0;i

str.length=mlen; return str;

//返回最大公共子串

//将最大公共子串复制到str中

str.data[i]=s.data[mi