数据结构习题练习（四）-串-删除串s的子串t/实现Replace(&S,T,V)

数据结构习题练习目录

不是串串。
说起来，我现在谈起串串已经不会特别馋了呢！
推荐图片：戳我戳我

单项选择题

1. 空串与空格串是相同的，这种说法__。
   A. 正确 B. 不正确
2. 串是一中特殊的线性表，其特殊性体现在__。
   A. 可以顺序存储 B. 数据元素是一个字符
   C. 可以链接存储 D. 数据元素可以是多个字符
3. 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作__。
   A. 连接 B. 模式匹配
   C. 求子串 D. 求串长
4. 设串 s1=‟ABCDEFG‟，s2=‟PQRST‟，函数 con (x,y)返回 x 和 y 串的连接串，subs(s,i,j)返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串，len(s)返回串s 的长度，则 con (subs(s1,2,len (s2)), subs (s1,len (s2),2))的结果串是__。
   A. BCDEF B. BCDEFG
   C. BCPQRST D. BCDEFEF

填空题

1. 串的两种最基本的存储方式是__。
2. 两个串相等的充分必要条件是__。
3. 空串是__，其长度等于__。
4. 空格串是__，其长度等于__。
5. 设 s=‟I︺AM︺A︺TEACHER‟,其长度是__。（︺表示空格）

算法设计题

1. 编写算法，从串 s 中删除所有和串 t 相同的子串。
2. 编写算法，实现串的基本操作 Replace(&S,T,V)。

单项选择题分析

1. 空串与空格串是相同的，这种说法__。
   A. 正确 B. 不正确
   字符串以'\0'结尾，即便'\0'出现在字符串内容中间，也只以'\0'结尾。
   空串中，只有'\0'结束符，
   而空格串中，除了'\0'还有若干个' '。
   .
2. 串是一中特殊的线性表，其特殊性体现在__。
   A. 可以顺序存储 B. 数据元素是一个字符
   C. 可以链接存储 D. 数据元素可以是多个字符
   线性表可以顺序存储（数组）也可以链接存储（链表），因此AC错，
   链接存储中的数据元素可以是多个字符，甚至可以是数组。
   字符串每个元素只能是一个字符。
   .
3. 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作__。
   A. 连接 B. 模式匹配
   C. 求子串 D. 求串长
   字符串连接："abc"与"cde"连接后，为"abccde"，
   模式匹配：在"abc"中模式匹配"a"，输出"a"第一次出现的位置，
   求子串：我没用过这个函数，但印象中是求子串是否存在于某字符串中，
   求串长：从字符串第一个字符开始，到'\0'结束的长度，'\0'不计数。
   .
4. 设串 s1=‟ABCDEFG‟，s2=‟PQRST‟，函数 con (x,y)返回 x 和 y 串的连接串，subs(s,i,j)返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串，len(s)返回串s 的长度，则 con (subs(s1,2,len (s2)), subs (s1,len (s2),2))的结果串是__。
   A. BCDEF B. BCDEFG
   C. BCPQRST D. BCDEFEF
   len(s2)==5
   subs(s1, 2, 5)==BCDEF，subs(s1, 5, 2)==EF
   con("BCDEF", "EF")=="BCDEFEF"。
   这里的序号不是数组下标，而是第几个的意思，
   从答案都是B开头推出。

填空题分析

1. 串的两种最基本的存储方式是顺序存储与链式存储。
   我一直以为只有顺序存储的叫串，孤陋寡闻了。
   链式存储的串，每个结点数据元素只有一个字符。
   .
2. 两个串相等的充分必要条件是长度相等且各位置元素相同。
   没想到这个答案的话，记住就好。
   因为俺也一样！
   .
3. 空串是零个字符的串，其长度等于0。
   见选择题第一题分析。
   .
4. 空格串是若干个空格组成的串，其长度等于空格个数。
   见选择题第一题分析。
   .
5. 设 s=‟I︺AM︺A︺TEACHER‟,其长度是14。（︺表示空格）
   串的结束符'\0'不计数在内，因此为14.
   .

算法设计题分析

1.编写算法，从串 s 中删除所有和串 t 相同的子串。

subStrRemove函数：将串s中的t子串删除，并将新串返回，不改变s的值。

这次函数使用的方法很简单，加上去，然后将子串s与t作为参数传入，即可返回新子串，就不给完整代码了。
我已经试过了几个特殊情况，VS2017下都正常运行，若依然出错，麻烦评论告知一下。

代码用的都是基础函数，没有使用字符串函数，毕竟是实现字符串函数功能嘛，就像实现除法，不能用除号去实现一样。

char *subStrRemove(char *s, char *t) {
    int *site = subStrFindSite(s, t);           //获得子串存在位置数组
    char *newStr = (char*)malloc(sizeof(char)); //使用newStr作为新串存储变量
    int tLen;
    for (tLen = 0; t[tLen] != '\0'; tLen++);  //获得串t长度
    int i, strNum;
    for (i = 0, strNum = 1; s[i + (strNum-1)*tLen] != '\0'; i++) {
        if (strNum <= site[0] && i + (strNum - 1)*tLen == site[strNum]) {    //比较该位置是否存在子串
            strNum++;                           //存在子串，将子串个数增加
            i--;                                //continue后i会自增，因此先自减。
            continue;
        }
        newStr[i] = s[i + (strNum - 1)*tLen];   //赋值newStr
        newStr = (char*)realloc(newStr, sizeof(char)*(i + 2));  //分配下个字符空间（若无字符，则空间用于存放结束符'\0'，不会浪费）
    }
    newStr[i] = '\0';                         //字符串结束符赋值
    return newStr;
}

int *subStrFindSite(char *s, char *t) {     //返回子串位置，以数组形式放回，数组首位为子串个数。
    int *site = (int*)malloc(sizeof(int));  //site数组记录子串位置
    int i, i2;
    site[0] = 0;                            //site首位记录长度
    for (i = 0; s[i] != '\0'; i++) {
        for (i2 = 0; 1; i2++) {
            if (s[i + i2] == '\0') break; //串s到结尾，结束搜索
            if (s[i + i2] != t[i2]) break;  //串中字符不同，跳出搜索。
            if (t[i2 + 1] == '\0') {      //串t搜索至结尾
                site[0] += 1;               //子串个数+1
                site = (int*)realloc(site, sizeof(int)*(site[0] + 1));  //子串空间分配。
                site[site[0]] = i;          //保存搜索位置
                i += i2;                    //将串s搜索位置增加，减少计算量
                break;
            }
        }
    }
    return site;
}

2.编写算法，实现串的基本操作 Replace(&S,T,V)。

replace(s, t, v)：会将s串中的t串替换成v串，并返回替换个数，空串不替换。

同样使用了上面的subStrFindSite来搜索位置。
以及同样只使用基本函数。

int replace(char *s, char *t, char *v) {
    int *site = subStrFindSite(s, t);
    char *newStr = (char*)malloc(sizeof(char)); //使用newStr作为新串存储变量
    int tLen, vLen;
    for (tLen = 0; t[tLen] != '\0'; tLen++);  //获得串t长度
    for (vLen = 0; v[vLen] != '\0'; vLen++);  //获得串v长度
    int i, strNum, i2;
    for (i = 0, strNum = 1; s[i + (strNum - 1)*(tLen-vLen)] != '\0'; i++) {
        if (strNum <= site[0] && i + (strNum - 1)*(tLen - vLen) == site[strNum]) {   //比较该位置是否存在子串
            newStr = (char*)realloc(newStr, sizeof(char)*(i + 2 + vLen));   //与下面realloc功能相同，此处简化了，因为待分配的空间已知。
            for (i2 = 0; i2 < vLen; i2++, i++) {//将v加入串newStr
                newStr[i] = v[i2];  
            }
            strNum++;                           //存在子串，将子串个数增加
            i--;                                //continue后i会自增，因此先自减。
            continue;
        }
        newStr[i] = s[i + (strNum - 1)*(tLen - vLen)];          //赋值newStr
        newStr = (char*)realloc(newStr, sizeof(char)*(i + 2));  //分配下个字符空间（若无字符，则空间用于存放结束符'\0'，不会浪费）
    }
    newStr[i] = '\0';                         //字符串结束符赋值
    s = newStr;                                 //修改原串s地址为newStr
    return site[0];                             //返回替换个数
}

int *subStrFindSite(char *s, char *t) {     //返回子串位置，以数组形式放回，数组首位为子串个数。
    int *site = (int*)malloc(sizeof(int));  //site数组记录子串位置
    int i, i2;
    site[0] = 0;                            //site首位记录长度
    for (i = 0; s[i] != '\0'; i++) {
        for (i2 = 0; 1; i2++) {
            if (s[i + i2] == '\0') break; //串s到结尾，结束搜索
            if (s[i + i2] != t[i2]) break;  //串中字符不同，跳出搜索。
            if (t[i2 + 1] == '\0') {      //串t搜索至结尾
                site[0] += 1;               //子串个数+1
                site = (int*)realloc(site, sizeof(int)*(site[0] + 1));  //子串空间分配。
                site[site[0]] = i;          //保存搜索位置
                i += i2;                    //将串s搜索位置增加，减少计算量
                break;
            }
        }
    }
    return site;
}