数据结构：串的基本演示操作

题目：如果语言没有把串作为一个预先定义好的基本类型对待，又需要用该语言写一个涉及串操作的软件系统时，用户必须自己实现串类型。试实现串类型，并写一个串的基本操作演示系统。

在教科书4.2.2节用堆分配储存表示实现HString串类型的最小操作子集的基础上，实现串抽象数据类型的其余基本操作（不使用C语言本身提供的串函数）。参数合法检查必须严格。

利用上述基本操作函数构造以下系统：它是一个命令解释程序，循环往复地处理用户键入的每一条命令，直到终止程序的命令为止。

（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> ∅ <串标识3> ∅ <回车>

将第一个串中所有出现的第二个串用第三个串替换。

（8）显示。格式：P ∅ <回车>

显示所有在系统中被保持的串的内部名和串值的对照表。

（9）删除。格式：D ∅ <内部名> ∅ <回车>

删除该内部名对应的串，即赋值的逆操作。

（10）退出。格式：Q ∅<回车>

结束程序的运行。

在上述命令中，如果一个自变量是串，则应首先建立它。基本操作函数的结果（即函数值）如果是一个串，则应在尚未分配的区域新辟空间存放。

（1）E ‘’ ‘’<回车>,应显示“EQUAL”

（2）E ‘abc’ ‘abcd’ <回车>,应显示“UNQUAL”

（3）C ‘’ ‘’<回车>,应显示‘’

（4）I ‘a’ ‘’<回车>，应报告：参数非法

（5）R ‘aaa’ ‘aa’ ‘b’ <回车>,应显示‘ba’

（6）R ‘aaabc’ ‘a’ ‘aab’ <回车>，应显示‘aabaabaabbc’

（7）R ‘aaaaaaaa’ ‘aaaa’ ‘ab’ <回车>，应显示‘abab’

串的抽象数据类型结构：
ADT String{
数据对象： D={ai| ai∈charcaterset,i=1,2,…,n,n>=0}
数据关系： R1={<ai-1,ai>|ai-1,ai∈D, i=1,2,…,n}
基本操作：
Assign( &T ，chars )
初始条件：chars是字符串常量。
操作结果：生成一个其值等于chars的串T。
StrCompare( S , T )
初始条件：S和T是已存在。
操作结果：比较其值，若S>T，返回值>0，若S=T，返回值=0，若S<T，返回值<0。
StrLength( S )
初始条件：S是已存在。
操作结果：返回该串的长度。
ClearString ( &S )
初始条件：S是已存在。
操作结果：将串S清为空串。
Concat( &T ，S1 , S2 )
初始条件：S1和S2是已存在。
操作结果：由S1和S2联接成新串T。
SubString( &Sub , S ，int pos , int len )
初始条件：S是已存在，1≤pos≤StrLength（S）且0≤len≤StrLength（S）-pos+1。
操作结果：用Sub返回串的第pos个字符起长度为len的子串。
Index( S , T ， pos )
初始条件：S和T已存在，T是非空串，1≤Spos≤StrLength（S）。
操作结果：若主串S中存在和串T相同的子串，则返回它在主串中第pos个字符之后第一次出现的位置；否则返回函数值为0。
Replace( &S , T , V )
初始条件：串S，T和V存在，T是非空串。
操作结果：用V替换主串S中出现的所有和T相同的不重叠的子串。
}ADT String

int StrAssign(HString *T, char *chars)
操作结果：生成值等于chars的串T
int InitHString(HString *T)
操作结果：初始化串T
int StrLength(HString S)
操作结果：返回串S的长度
int StrCompare(HString S, HString T)
操作结果：比较串S和串T，若S>T,则返回值>0;若S=T，则返回值=0；若S<T,则返回值<0
int ClearString(HString *S)
操作结果：将串S清为空串，并释放S所占空间
int Concat(HString *T, HString S1, HString S2)
操作结果：用T返回由S1和S2联接而成的新串
int SubString(HString *Sub, HString S, int pos, int len)
操作结果：返回串S的第pos个字符起长度为len的子串
int Index(HString S, HString T, int pos)
操作结果：若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0
int Replace(HString *S1, HString S2, HString S3)
操作结果：用S3替换S1中所有出现的与S2相等的不重叠的子串
int InitResultType(ResultType *R)
操作结果：初始化命令分析结果
int InitStrHeadList(StrHeadList *L)
操作结果：初始化串头表
int CmdAnalyse(ResultType *R, char str[], StrHeadList *L)
操作结果：命令分析函数，把命令分析结果通过R返回
int ShowHString(HString S)
操作结果：打印串内容
int CmdOpretor(ResultType R, StrHeadList *L)
操作结果：根据命令分析结果对串进行相应操作

串的堆分配储存表示：

演示系统的主结构是一个串头表，各串的头指针依次存于串头数组StrHead中（设串的数目不超过100），CurNum为系统中现有的串的数目，CurNum是可为下一个串头指针分配的位置，StrHead的元素下标作为对应串的内部名，定义为：

命令分析结果的储存结构如下，

赋值、求长度、求子串、子串定位、联接、子串定位、替换等操作的实现

跳过空格依次读入命令符和参数，根据字符串标识判断是否为字符串，因为只有求子串操作需要数值部分参数，因此可以据此来区分参数是否为数值或是串内部名。

根据不同操作需求，判断参数合法性

根据命令行分析函数结果判断参数是否合法

4.输入Q<回车>退出

（1）E ‘’ ‘’<回车>,应显示“EQUAL”

（2）E ‘abc’ ‘abcd’ <回车>,应显示“UNQUAL”

（3）C ‘’ ‘’<回车>,应显示‘’

（4）I ‘a’ ‘’<回车>，应报告：参数非法

（5）R ‘aaa’ ‘aa’ ‘b’ <回车>,应显示‘ba’

（6）R ‘aaabc’ ‘a’ ‘aab’ <回车>，应显示‘aabaabaabbc’