256+
2.1字符串与子串、子序列
例1:字符串“www.qq.com”所有非空子串个数为(如果两个子串相同则算一个)。
长度为1的子串有10个,减去重复的2(子串w重复)+1(子串q重复)+1(子串.重复)=4个,还剩6个,
长度为2的子串有9-1(子串ww重复)=8个,
长度为3的子串有8个,
长度为4的子串有7个,
......
长度为10的子串有1个,加起来为50。
2.2C风格字符串
例1:下列代码的输出是什么?
char x = ' '; printf("%d ", x);//0 char y = '0'; printf("%d ", y);//48 char z = 'a'; printf("%d ", z);//97 char a = 'A'; printf("%d ", a);//65
例2:下面函数的功能是?
求字符串的长度
int fun(char *x) { char *y = x; while (*y++); return y - x - 1; }
例3:What is the result of the following program?
abddcccd
#include <iostream> #include <windows.h> char * f(char *str, char ch) { char *it1 = str; char *it2 = str; while (*it2 != ' ') { while (*it2 == ch) { it2++; } *it1++ = *it2++; } return str; } int main() { char *a = new char[10]; strcpy(a, "abcdcccd"); std::cout << f(a, 'c'); delete[]a; system("pause"); return 0; }
2.3标志库提供的字符串处理函数
2.3.1strlen
自定义函数实现strlen的功能是:
int myStrlen(const char *str) { assert(str != NULL); int len = 0; while ((*str++) != ' ') { len++; } return len; }
例1:下面的程序的输出是什么?
x=tse
y=
请按任意键继续. . .
#include <iostream> #include <windows.h> int main() { int n; char y[10] = "ntse"; char *x = y; n = strlen(x); *x = x[n]; x++; printf("x=%s ", x); printf("y=%s ", y); system("pause"); return 0; }
2.3.2strcmp
自定义函数实现strcmp()函数的功能:
int myStrcmp(const char *str1, const char *str2) { assert(str1 != NULL && str2 != NULL); int ret = 0; while (!(ret = *(unsigned char *)str1 - *(unsigned char *)str2) && *str1) { str1++; str2++; } if (ret < 0) { ret = -1; } else if (ret > 0) { ret = 1; } return ret; }
例1:判断字符串a和b是否相等,应当使用?
if(strcmp(a,b))
2.3.3strcat和strcpy
自定义函数实现strcat()函数的功能:
char *myStrcat(char *strDest, const char *strSrc) { char *address = strDest; assert((strDest != NULL) && (strSrc != NULL)); while (*strDest) { strDest++; } while (*strDest++ = *strSrc++); return address; }
自定义函数实现strcpy()函数的功能:
char *myStrcpy(char *strDestination, const char *strSource) { assert(strDestination != NULL && strSource != NULL); char *strD = strDestination; while ((*strDestination++ = *strSource++) != ' '); return strD; }
例1:以下哪个说法正确?
Debug版崩溃,Release版正常
int func() { char b[2] = { 0 }; strcpy(b, "aaa"); }
2.3.4memcpy和memset
例1:下面的代码可能出现下列哪些运行结果?
程序运行正常
aucBuff数组写越界
#define MAX_BUFF_LEN 100 void MyFunc(unsigned char *pucData, unsigned short wLen) { unsigned char aucBuff[MAX_BUFF_LEN]; memcpy(aucBuff, pucData, wLen); }
2.4字符串的实际应用
2.4.1字符串包含问题
1)串的模式匹配算法
例1:在字符串中查找子串。给定一个字符串A,要求在A中查找一个子串B。
char *strFind(const char *string, const char *substring) { assert(string != NULL && substring != NULL); int m = strlen(string); int n = strlen(substring); int j = 0; if (m < n) { return NULL; } for (int i = 0; i < m - n; i++)//时间复杂度为O((m-n+1)*n) { for (j = 0; j < n; j++) { if (string[i + j] != substring[j]) { break; } } if (j == n) { return string + i; } } return NULL; }
2.4.2字符串转换为数字
例1:输入一个表示整数的字符串,把该字符串转换成整数并输出。例如输入字符串“345”,则输出整数345。
enum Status { kValid = 0, kInvalid }; int g_nStatus = kValid; int StrToInt(const char *str) { g_nStatus = kInvalid; long long num = 0; if (str != NULL) { const char *digit = str; bool minus = false; if (*digit == '+') { digit++; } else if (*digit == '-') { digit++; minus = true; } while (*digit != ' ') { if (*digit >= '0' && *digit <= '9') { num = num * 10 + (*digit - '0'); if (num > (long long)std::numeric_limits<int>::max) { num = 0; break; } digit++; } else { num = 0; break; } } if (*digit == ' ') { g_nStatus = kValid; if (minus) { num = 0 - num; } } } return num; }
例3:输入两个很大的正数(用C字符串表示),输出它们的乘积,假设不考虑非法输入。
void multiply(const char *a, const char *b) { assert(a != NULL && b != NULL); int i, j, ca, cb, *s; ca = strlen(a); cb = strlen(b); s = (int *)malloc(sizeof(int)*(ca + cb));//分配存储空间 for (i = 0; i < ca + cb; i++) { s[i] = 0;//每个元素赋初值0 } for (i = 0; i < ca; i++) { for (j = 0; j < cb; j++) { s[i + j + 1] += (a[i] - '0')*(b[j] - '0'); } } for (i = ca + cb - 1; i >= 0; i--)//这里实现进位操作 { if (s[i] >= 10) { s[i - 1] += s[i] / 10; s[i] %= 10; } } char *c = (char *)malloc((ca + cb) * sizeof(char)); i = 0; while (s[i] == 0) { i++;//跳过头部0元素 } for (j = 0; i < ca + cb; i++, j++) { c[j] = s[i] + '0'; } c[j] = ' '; for (i = 0; i < ca + cb; i++) { std::cout << c[i]; } std::cout << std::endl; }
2.4.3其他应用
例1:字符串中单词的逆转,即将单词出现的顺序进行逆转。如将“Today is Friday!”逆转为“Friday! is Today”。
void Reverse(char *pb, char *pe) { if (pb == NULL || pe == NULL) { return; } while (pb < pe) { char temp = *pb;//交换pb和pe的内容 *pb = *pe; *pe = temp; pb++; pe--; } } char *ReverseSentence(char *pData) { if (pData == NULL) { return NULL; } char *pBegin = pData; char *pEnd = pData; while (*pEnd != ' ') { pEnd++; } pEnd--;//去掉空格 Reverse(pBegin, pEnd); pBegin = pEnd = pData; while (*pBegin != ' ') { if (*pBegin == ' ') { pBegin++;; pEnd++; continue; } //反转单词 else if (*pEnd == ' ' || *pEnd == ' ') { Reverse(pBegin, --pEnd); pBegin = ++pEnd; } else { pEnd++; } } return pData; }
例2:删除模式串中出现的字符,如“welcome to asted”,模式串为“aeiou”那么得到的字符串为“wlcm t std”,要求性能最优,字符串中全部为小写字母。
void fun(char *s) { assert(s != NULL); int i = 0, j = 0; while (s[j] != ' ') { while (s[j] == 'a' || s[j] == 'e' || s[j] == 'i' || s[j] == 'o' || s[j] == 'u') { j++; } s[i++] = s[j++]; } s[i] = ' '; }
例3:删除字符串开始及末尾的空白符(若干空格),并且把数组中间的多个空格(如果有)符转化为1个。
void fun(char *s) { int i = 0, j = 0; while (s[j] == ' ')//删除头部的空白符 { j++; } int len = strlen(s) - 1; while (s[len] == ' ')//删除尾部的空白符 { len--; } s[len + 1] = ' '; while (s[j] != ' ') { while (s[j] == ' ') { j++; } /*将中间连续的空白符变为一个,判断!= 0是为了防止将头部的连续字符变为1个*/ if (s[j - 1] == ' '&& s[j - 2] == ' '&& i != 0) { s[i++] = ' '; } s[i++] = s[j++]; } s[i] = ' '; }
例4:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b,假设字符集是ASCII。
void FirstNotRepeatingChar(const char *pString) { assert(pString != NULL); const int tableSize = 256; unsigned int hashTable[tableSize]; for (unsigned int i = 0; i < tableSize; ++i) { hashTable[i] = 0; } const char *pHashKey = pString; while (*(pHashKey) != ' ') { hashTable[*(pHashKey++)]++; } pHashKey = pString; while (*pHashKey != ' ') { if (hashTable[*pHashKey] == 1) { printf("%c", *pHashKey); return; } pHashKey++; } }
判断一个字符串中所有字符是否都不相同?
bool char_set[256]; int isUniqueCharString(const char *str) { assert(str != NULL); int len = strlen(str); for (int i = 0; i < len; ++i) { int val = str[i]; if (char_set[val]) { return 0; } char_set[val] = true; } return 1; }
如果要求在上述算法的基础上进一步降低空间要求,可以使用bit-map(后续章节讲解),如果假设字符串仅包含从'a'到'z'的字符,我们可以将空间需求降低到一个int。
int isUniqueChars(char *str) { assert(str != NULL); int checker = 0; int len = strlen(str); for (int i = 0; i < len; ++i) { int val = str[i] = 'a'; if ((checker & (1 << val)) > 0) { return 0; } checker |= (1 << val); } return 1; }
本章习题
1.下面程序的运行结果是。
运行出错。因为p的对象存储于文字常量区,不能对其进行修改
char *p = "abcdefgh"; p += 3; std::cout << strlen(strcpy(p, "ABCD")) << std::endl;
2.例如需要将字符串数组strDest[]追加到字符串数组strSrc[]的后面,下面哪种方法可以保证程序不会越界?
都可以。
strncat(strSrc, strDest, min(sizeof(strSrc) - strlen(strSrc) - 1, strlen(strDest))); snprintf(strSrc, sizeof(strSrc) - 1, "%s%s", strSrc, strDest);
3.写成函数strcpy的实现。
char *myStrcpy(char *strDest, const char *strSrc) { assert((strDest != NULL) && (strSrc != NULL)); char *address = strDest; while ((*strDest++ = *strSrc++) != ' '); return address; }
4.设计一个算法移除字符串中的重复字符,并写出测试用例。
void removeDuplicates(char *str) { if (str == NULL) { return; } int len = strlen(str); if (len < 2) { return; } int tail = 1; for (int i = 1; i < len; ++i) { int j; for (j = 0; j < tail; ++j) { if (str[i] == str[j]) { break; } } if (j == tail) { str[tail] = str[i]; ++tail; } } str[tail] = 0; }
上述算法时间复杂度为O(n^2),如果可以申请一个固定大小的内存,则可以将时间复杂度降低为O(n)。
void removeDuplicates2(char *str) { if (str == NULL) { return; } int len = strlen(str); if (len < 2) { return; } bool hit[256]; for (int i = 0; i < 256; ++i) { hit[i] = false; } hit[str[0]] = true; int tail = 1; for (int i = 1; i < len; ++i) { if (!hit[str[i]]) { str[tail] = str[i]; ++tail; hit[str[i]] = true; } } str[tail] = 0; }
5.将字符串中的所有空格替换为'%20'。函数原型为:
225415112521