sy5_1.c

数据结构实验与学习指导

/* sy5_1.c */
#define MAXSIZE 255
#include"stdio.h"
typedef struct{
   char elem[MAXSIZE];
   int length;
}SeqString;
void create_SeqStr(SeqString *s)
{
    int i=0;
    gets(s->elem);
    while(s->elem[i++]);
    s->length=i-1;
}
void print_SeqStr(SeqString *s)
{
    int i;
    for(i=0;i<s->length;i++)
      putchar(s->elem[i]);
    putchar('\n');
}
int Concat(SeqString *S,SeqString *S1,SeqString *S2)
/*连接串S1,S2，结果存放在串S中*/
{
    int i;
    int uncut;/*未截断标志,如果S2没有截断，标志为1,否则为0*/
    if(S1->length+S2->length<=MAXSIZE)
    {
        for(i=0;i<S1->length;i++)/*把串S1首先拷贝到串S*/
            S->elem[i]=S1->elem[i];        
        for(i=0;i<S2->length;i++)/*串S2被拷贝到串S的尾部，实现S1和S2的连接 */
            S->elem[S1->length+i]=S2->elem[i];
        S->length=S1->length+S2->length;
        S->elem[S->length]='\0';
        uncut=1;/*S2不需要截断*/
    }
    else /*需要对S2进行截断，只能存放S2的一部分*/
    {
        for(i=0;i<S1->length;i++)/*把串S1首先拷贝到串S中*/
            S->elem[i]=S1->elem[i];
        for(i=0;i<MAXSIZE-S1->length;i++)/*把S2一部分拷贝到S尾部*/
            S->elem[S1->length+i]=S2->elem[i];
        S->length=MAXSIZE;
        uncut=0;/*未截断标志置0*/
    }
   return uncut;
}
int SubString(SeqString *Sub,SeqString *S,int pos,int len)
  /*求子串。母串为S，子串为Sub，开始位置pos，子串长len*/
{
    int i;
    if(pos<0||pos>=S->length||len<0||len>S->length-pos-1)
          return 0;/*子串位置或者子串长度无效*/
    for(i=pos;i<pos+len;i++)
       Sub->elem[i-pos]=S->elem[i];
    Sub->length=len;
    return 1;
}
int StrCompare(SeqString *S1,SeqString *S2)/*串比较*/
{
    int i;
    for(i=0;i<S1->length&&i<S2->length;i++)
    {
        if(S1->elem[i]!=S2->elem[i])
            return S1->elem[i]-S2->elem[i];
        if(S1->length==S2->length)
            return 0;
    }
    return -32768;/*返回一个极小值，表示比较发生错误*/
}
int StrLength(SeqString *S)  /*求串长*/
{
    return S->length;
}
int Index(SeqString *S,SeqString *Sub)/*串匹配 */
{
    int i;
    int sublen=Sub->length;
    SeqString *SubT=(SeqString *)malloc(sizeof(SeqString));
    for(i=0;i<S->length;i++)
    {
        if(!SubString(SubT,S,i,sublen))
           break;
        if(!StrCompare(SubT,Sub))/*匹配成功，得到子串位置*/
           return i;
    }
    return -1;/*匹配失败*/
}
/*int Index_KMP(SeqString S,SeqString Sub)
{

}*/
void main()
{
    /*对以上算法进行应用*/
    SeqString *S1,*S2,*ps;
    int sel=7,pos,len;
    S1=(SeqString *)malloc(sizeof(SeqString));
    S2=(SeqString *)malloc(sizeof(SeqString));
    ps=(SeqString *)malloc(sizeof(SeqString));
    printf("请输入串S1:");
    create_SeqStr(S1);
    printf("请输入串S2:");
    create_SeqStr(S2);
    while(sel)
    {
        printf("可以进行的操作如下\n");
        printf("1 字符串连接\n");
        printf("2 字符串比较\n");
        printf("3 求串S1的长度\n");
        printf("4 求串S1的子串\n");
        printf("5 串匹配\n");
        /*printf("6 KMP算法\n");*/
        printf("0 退出程序\n");
        printf("输入0到5的整数选择要进行的操作:");
        scanf("%d",&sel);
        switch(sel)
        {
            case 1:Concat(ps,S1,S2);
                print_SeqStr(ps);break;
            case 2: printf("串比较的结果是:");
                printf("%d\n",StrCompare(S1,S2));
                break;
            case 3:printf("串S1的长度是:");
                printf("%d\n\n",StrLength(S1));
                break;
            case 4:printf("请输入位置（pos）和子串长（len）,例如:3,5\n");
                scanf("%d,%d",&pos,&len);
                SubString(ps,S1,pos,len);
                printf("求得的子串是:");
                print_SeqStr(ps);break;
            case 5:
                printf("串S2在母串S1中的位置是%d\n",Index(S1,S2));
                break;
            /*case 6:*/
            case 0:printf("退出程序!\n");
exit(0);
        }/*switch(sel)*/
    }/*while(sel)*/
}