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

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

一、需求分析

在教科书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 ∅<回车>

结束程序的运行。

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

2. 测试数据

（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’

二、概要设计

1. 数据结构

串的抽象数据类型结构：
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

2. 使用函数

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)
操作结果：根据命令分析结果对串进行相应操作

三、详细设计

1. 数据储存结构

串的堆分配储存表示：

typedef struct{
    char *ch;     // 若是非空串，则按串长分配储存区，否则ch为NULL
    int length;   // 串长度
}HString;

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

typedef struct {
    HString StrHead[100];
    int CurNum;
}StrHeadList;

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

typedef struct {
    char Cmd;    // 命令符
    int s[3];    // 命令的串参数的内部名（最多3个）
    int num[3];  // 命令的数值参数（最多2个）
}ResultType;

2.基本功能实现模块

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

int StrAssign(HString *T, char *chars){
    // 生成一个其值等于串常量的chars的串T
    if(T->ch) free(T->ch);   // 释放T原有空间
    int i;
    char *c;
    for (i=0,c=chars; *c; i++,++c); //求chars长度i
    if(!i) {T->ch = NULL; T->length = 0;}
    else {
        if(!(T->ch = (char*)malloc(i*sizeof(char))))
            exit(-2);
        for(int j=0; j<i; j++)
            T->ch[j] = chars[j];
        T->length=i;
    }
    return 1;
}

int InitHString(HString *T){
    T->ch = NULL;
    T->length = 0;
    return 1;
}

int StrLength(HString S){
    // 返回串S的长度
    return S.length;
}

int StrCompare(HString S, HString T){
    // 若S>T,则返回值>0;若S=T，则返回值=0；若S<T,则返回值<0
    for(int i = 0;i<S.length && i<T.length; ++i)
        if(S.ch[i] != T.ch[i]) return(S.ch[i] - T.ch[i]);
    return(S.length - T.length);
}

int ClearString(HString *S){
    // 将S清为空串
    if(S->ch) {
        free(S->ch);
        S->ch = NULL;
    }
    S->length = 0;
}

int Concat(HString *T, HString S1, HString S2){
    // T返回由S1和S2联接而成的新串
    if(T->ch) free(T->ch);   // 释放旧空间
    if(!(T->ch = (char*)malloc((S1.length+S2.length)*sizeof(char))))
        exit(-2);
    int i;
    for(i=0; i<S1.length; i++)
        T->ch[i] = S1.ch[i];
    T->length = S1.length + S2.length;
    for(i=0; i<S2.length; i++)
        T->ch[i+S1.length] = S2.ch[i];
    return 1;
}

int SubString(HString *Sub, HString S, int pos, int len){
    // 用Sub返回串的第pos个字符起长度为len的子串
    InitHString(Sub);
    if(pos < 1 || pos > S.length || len < 0 || len > S.length-pos+1)
        return 0;
    if(Sub->ch) free(Sub->ch);   // 释放旧空间
    if(!len) {                   // 空子串
        Sub->ch = NULL; 
        Sub->length = 0;
    } else{                      // 完整子串
        Sub->ch = (char*)malloc(len * sizeof(char));
        for(int i=0; i<len; i++){
            Sub->ch[i] = S.ch[pos-1+i];
            Sub->length = len;
        }
    }
    return 1;
}

int Index(HString S, HString T, int pos){
    // 若主串S中第pos个字符之后存在与T相等的子串，
    // 则返回第一个这样的子串在S中的位置，否则返回0
    if(pos>0){
        int n = StrLength(S);
        int m = StrLength(T);
        int i = pos;
        if(m==0 && n!=0){ return 0;}
        else{
            HString sub;
            InitHString(&sub);
            while(i<=n-m+1){
                SubString(&sub,S,i,m);
                if(StrCompare(sub,T)!=0)  ++i;
                else return i;
            }
        }
    }
    return 0;
}

int Replace(HString *S1, HString S2, HString S3){
    // 用S3替换S1中所有出现的与S2相等的不重叠的子串
    HString before;
    HString after;
    HString temp;
    InitHString(&temp);
    InitHString(&before);
    InitHString(&after);
    int i = Index(*S1,S2,1);
    do{
        SubString(&before,*S1,1,i-1);
        SubString(&after,*S1,i+StrLength(S2),StrLength(*S1)-i-StrLength(S2)+1);
        Concat(&temp,before,S3);
        Concat(S1,temp,after);
        i = Index(*S1,S2,StrLength(temp)+1);
    }while(Index(after,S2,1));   // 判断未替换部分是否包含S2
    return 1;
}

3.命令分析模块

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

int CmdAnalyse(ResultType *R, char str[], StrHeadList *L){
    //命令行分析函数 ，命令行存放在str中，返回ResultType
    char *p; 
    char *q;
    char temp[100];
    int strcnt = 0;
    int numcnt = 0;
    int i;
    p = str;
    // 读入命令符
    char OP[11] = {'A','E','C','L','S','I','R','P','D','Q','\0'};
    for( ; *p == ' '; p++);  // 跳过空格
    if(*p == '\0') return -1;
    q = p+1;
    if(In(*p, OP) && (*q == ' '|| *q =='\0')) {R->Cmd = *p; p++;}
    else return -1;
    for( ; *p == ' '; p++);
    if(*p == '\0') return 1;
    // 读入参数
    for(int n=1; n<=3; n++){ // 最多读入3个参数
        for( ; *p == ' '; p++);
        if(*p == '\''){ //为字符串时
            p++;
            for(i=0; *p != '\''; p++,i++) temp[i] = *p;
            temp[i] = '\0';
            StrAssign(&L->StrHead[L->CurNum], temp);
            R->s[strcnt] = L->CurNum;
            L->CurNum++;
            p++; strcnt++;
        }else if(*p >= '0' && *p <= '9'){ //为内部名时
            if(R->Cmd == 'S' && R->s[0] != -1) {
                for(i=0; *p != ' '; p++,i++) temp[i] = *p;
                temp[i] = '\0';
                R->num[numcnt] = atoi(temp);
                numcnt++;
            }else { // 为数值时
                for(i=0; *p != ' '; p++,i++) temp[i] = *p;
                temp[i] = '\0';
                R->s[strcnt] = atoi(temp);
                strcnt++;
            }
        }else if(*p == '\0') break; // 仅有回车输入
    }
    return 1;
}

4.命令操作模块

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

int CmdOpretor(ResultType R, StrHeadList *L){
    // 命令行操作函数，读入ResultType，判断参数合法性并对串头表进行操作
    int i;
    switch(R.Cmd){
    case 'A':
        // 赋值操作
        if(R.s[0]==-1){
            printf("参数非法");
        }else{
            printf("%d   ",R.s[0]);
            ShowHString(L->StrHead[R.s[0]]);
        }
        break;
    case 'E':
        // 判相等
        if(R.s[0]!=-1 && R.s[1]!=-1){
            if(StrCompare(L->StrHead[R.s[0]],L->StrHead[R.s[1]])) printf("UNEQUAL");
            else printf("EQUAL");
        }else{
            printf("参数非法");
            }
        break;
    case 'C':
        // 联接两个串
        if(R.s[0]!=-1 && R.s[1]!=-1){
            Concat(&L->StrHead[L->CurNum],L->StrHead[R.s[0]],L->StrHead[R.s[1]]);
            ShowHString(L->StrHead[L->CurNum]);
            L->CurNum++;
        } else {printf("参数非法");}
        break;
    case 'I':
        // 子串的定位
        if(R.s[0]!=-1 && R.s[1]!=-1){
            int x;
            x = Index(L->StrHead[R.s[0]],L->StrHead[R.s[1]],1);
            if(x) printf("%d",x);
            else printf("参数非法");
        } else {printf("参数非法");}
        break;
    case 'R':
        // 串的替换
        if(R.s[0]!=-1 && R.s[1]!=-1 && R.s[2]!=-1){
            Replace(&L->StrHead[R.s[0]],L->StrHead[R.s[1]],L->StrHead[R.s[2]]);
            ShowHString(L->StrHead[R.s[0]]);
        } else {printf("参数非法");}
        break;
    case 'S':
        // 求子串
        if(R.num[0]!=-1 && R.num[1]!=-1 && R.s[0]!=-1){
            if(SubString(&L->StrHead[L->CurNum],L->StrHead[R.s[0]],R.num[0],R.num[1])){
                ShowHString(L->StrHead[L->CurNum]);
                L->CurNum++;
            } else {printf("参数非法");}
        } else {printf("参数非法");}
        break;
    case 'L':
        // 得到串的长度
        if(R.s[0]!=-1){
            printf("%d",StrLength(L->StrHead[R.s[0]]));
        } else {printf("参数非法");}
        break;
    case 'P':
        // 显示串头表中串名和串值
        for(i=0;i<L->CurNum;i++){
            if(L->StrHead[i].length != 0 && L->StrHead[i].ch != NULL ){
                printf("%d   ",i);
                ShowHString(L->StrHead[i]);
                printf("\n");
            }
        }
        break;
    case 'D':
        // 删除某串
        if(R.s[0]!=-1){
            ClearString(&L->StrHead[R.s[0]]);
        } else {printf("参数非法");}
        break;
    case '#':
        // 命令符错误
        printf("ERROR");
        break;
    case 'Q':
        // 退出
        break;
    }
    return 1;
}

5.主程序

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

int main(){
    char str[100];
    ResultType R;
    StrHeadList L;
    InitStrHeadList(&L);
    do{
        InitResultType(&R);
        ReadCmd(str);
        if(CmdAnalyse(&R, str, &L)){
            CmdOpretor(R, &L);
        }else{
            printf("参数错误");
        }
        printf("\n");
    }while(R.Cmd!='Q');
    return 1;
}

6.程序的层次结构

程序设计结构

五、用户手册

本程序的运行环境为DOS操作系统，执行文件为：chuan.exe
进入程序按提示操作，输入命令

起始界面.png

输入后按回车符即显示结果
串标识中可以是内部名也可以是字符串，内部名为数字（0--99），字符串用‘’括起来

4.输入Q<回车>退出

六、测试结果