数据结构习题练习(四)-串-删除串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;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注