串基本操作的演示

6 串基本操作的演示
问题描述： 如果语言没有把串作为一个预先定义好的基本类型对待，又需要用该语言写一个涉及串操作的软件系统时，用户必须自己实现串类型。试实现串类型，并写一个串的基本操作的演示系统。
基本要求： 在教科书4.2.2节用堆分配存储表示实现HString串的最小操作子集的基础上，实现串抽象数据类型的其余基本操作（不使用C语言本身提供的串函数）。参数合法性检查必须严格。 说明：（在格式中，Φ表示0个、1个或多个空格所组成的串。〈串标识〉表示一个内部名或一个串文字。前者是一个串的唯一标识，是一种内部形式的（而不是字符形式的）标识符。后者是两端由单引号括起来的仅可打印字符组成的序列。串内每两个连续的单引号表示一个单引号符。）
利用上述基本操作函数构造以下系统：它是一个命令解释程序，循环往复地处理用户键入的每一条命令，直至终止程序的命令为止。命令定义如下：
（1） 赋值。格式：AΦ〈串标识〉Φ〈回车〉
用〈串标识〉所表示的值建立新串，并显示新串的内部名和串值。如：A′Hi！′
（2） 判相等。 格式：EΦ〈串标识1〉Φ〈串标识2〉Φ〈回车〉
若两串相等，则显示“EQUAL”，否则显示“UNEQUAL”。
（3） 联接。 格式：CΦ〈串标识1〉Φ〈串标识2〉Φ〈回车〉
将两串联接产生结果串，它的内部名和串值都显示出来。
（4） 求长度 格式：LΦ〈串标识〉Φ〈回车〉 显示串的长度。
（5） 求子串 格式：SΦ〈串标识〉Φ+〈数1〉Φ+〈数2〉Φ〈回车〉
如果参数合法，则显示子串的内部名和串值。〈数〉不带正负号。
（6）子串定位。 格式：IΦ〈串标识1〉Φ〈串标识2〉Φ〈回车〉
显示第二个串在第一个串中首次出现时的位置。
（7）串替换 格式：RΦ〈串标识1〉Φ〈串标识2〉Φ〈串标识2〉Φ〈回车〉
将第一个串中出现所有出现的第二个串用第三个串替换，显示结果串的内部名和串值，原串不变。
（8）显示 格式：PΦ〈回车〉 显示所有在系统中被保持的串的内部名和串值的对照表。

现串的基本运算（一）

考核内容：

? 利用链式结构实现串的以下基本运算

? 求串长 strlen(str) 返回串 str 的长度

? 联结 strcat (str1,str2) 将 str2 连接到 str1 的末尾，形成一个新的串

? 求子串 substr （ str ， pos ， n ） 在 str 中的第 pos 个位置，取 n 个字符组成一个新的串。

? 算法分析，分析时间复杂度和空间复杂度

参考答案：

int strlen(char *s);

{ int n=0; char * p=s;

while (*p++) n++;

return(n);

}

char * strcat(char *s, char *t)

{ int k; char *p;

p=s+strlen( s );

while ( *t ) *p++ = *t++;

}

char *substr(char *s,int pos,int num)

{

char *p,*t,*head;

int i=1;

head=t; p=s+pos-1;

while(i<=num)

{ *t=*p;

i++; p++; t++;

}

return(head);

}

main()

{

int n;int m;int i;

char *sub , *str ;

char s1[]="this is

串基本操作的演示 基本的键盘操作 photoshop的基本操作 基本的系统操作！！！！！！！！！！！！！！！ Powerpoint的基本操作 CAD的基本操作 台球的基本操作 电脑的基本操作 鼠标的基本操作 流星蝴蝶剑的基本操作！