一些C语言中字符串的算法问题解决实例小结
字符串问题是面试中经常出现的问题,这类问题有很多,难以不一。下面是几道字符串的题目,网上都能找到解答,自己实现了一下,供网友参考。感觉算法重要的是要有正确的思路,实现起来不是问题。自己一定要多思考,这样收获可能会更多一点。 //函数功能 : 打印最长公共子串 //函数参数 : X为源字符串1,Y为源字符串2,R为记录的过程,row为R的行坐标,col为R的列坐标 //返回值 : 空 void LCS_Print(const char *X,const char *Y,int **R,int row,int col) { if(R[row][col] == 1) { LCS_Print(X,Y,R,row-1,col-1); cout<<X[row-1]; //由Xi-1和Yj-1,再加上Xi或Yj得到 } else if(R[row][col] == 2) LCS_Print(X,col); //由Xi-1和Yj得到 else if(R[row][col] == 3) LCS_Print(X,row,col-1); //由Xi和Yj-1得到 else return; } //函数功能 : 求两个字符串的最大公共子串 //函数参数 : X为源字符串1,Y为源字符串2 //返回值 : 最大长度 int LCS(const char *X,const char *Y) { if(X == NULL || Y == NULL) return 0; int lenX = strlen(X); int lenY = strlen(Y); if(lenX == 0 || lenY == 0) return 0; int i,j; int **C = new int *[lenX+1]; int **R = new int *[lenX+1]; //初始化 for(i = 0; i <= lenX; i++) { C[i] = new int [lenY+1]; R[i] = new int [lenY+1]; for(j = 0; j <= lenY; j++) { C[i][j] = 0; R[i][j] = 0; } } //开始计算 for(i = 1; i <=lenX; i++) { for(j = 1; j <=lenY; j++) { if(X[i-1] == Y[j-1]) //字符串的下标从0开始,所以减1,即X1 = X[0] Y1 = Y[0] { C[i][j] = C[i-1][j-1] + 1; R[i][j] = 1; //由Xi-1和Yj-1,再加上Xi或Yj得到 } else { if(C[i-1][j] >= C[i][j-1]) { C[i][j] = C[i-1][j]; R[i][j] = 2; //由Xi-1和Yj得到 } else { C[i][j] = C[i][j-1]; R[i][j] = 3; //由Xi和Yj-1得到 } } } } //打印最长公共子串 LCS_Print(X,lenX,lenY); //记录最大长度 int lcs = C[lenX][lenY]; //释放空间 for(i = 0; i <= lenX; i++) { delete [] C[i]; delete [] R[i]; } delete C; delete R; R = C = NULL; return lcs; } //函数功能 : 在字符串中删除特定字符 //函数参数 : pSrc为源字符串,pDel为特定字符集 //返回值 : 空 void DeleteSpecialChars(char *pSrc,char *pDel) { if(pSrc == NULL || pDel == NULL) return; int lenSrc = strlen(pSrc); int lenDel = strlen(pDel); if(lenSrc == 0 || lenDel == 0) return; bool hash[256] = { false }; for(int i = 0; i < lenDel; i++) //建立删除字符的索引 hash[pDel[i]] = true; //开始删除 char *pCur = pSrc; while(*pSrc != ' ') { if(hash[*pSrc] == false) //不用删除 *pCur++ = *pSrc; pSrc++; } *pCur = ' '; } 问题3:左旋转字符串,其实也可以左旋数组 //函数功能 : 将字符串翻转 //函数参数 : pBegin指向第一个字符,pEnd指向最后一个字符 //返回值 : 空 void ReverseString(char *pBegin,char *pEnd) { if(pBegin == NULL || pEnd == NULL) return; while(pBegin < pEnd) { //交换字符 char tmp = *pBegin; *pBegin = *pEnd; *pEnd = tmp; //往中间靠拢 pBegin++; pEnd--; } } //函数功能 : 将字符串左旋 n 位 //函数参数 : pSrc为源字符串,n为左旋位数 //返回值 : 空 void LeftRotateString(char *pSrc,unsigned n) { if(pSrc == NULL || n == 0 || n > strlen(pSrc)) return; int len = strlen(pSrc); ReverseString(pSrc,pSrc + n - 1); ReverseString(pSrc + n,pSrc + len - 1); ReverseString(pSrc,pSrc + len - 1); } //函数功能 : 在一个字符串中找到第一个只出现一次的字符 //函数参数 : pStr为源字符串 //返回值 : 目标字符 char FirstAppearOnce(char *pStr) { if(pStr == NULL) return ' '; //未找到返回空字符 int count[256] = {0}; char *pTmp = pStr; while(*pTmp != ' ') //统计字符串中每个字符出现的次数 { count[*pTmp]++; pTmp++; } while(*pStr != ' ') //遍历字符串,找到第一个只出现一次的字符 { if(count[*pStr] == 1) break; pStr++; } return *pStr; //找到的字符 } //函数功能 : 在字符串中找出连续最长的数字串 //函数参数 : pSrc表示源串,pDest记录最长数字串的起始位置 //返回值 : 最长数字串的长度 int ContinueMax(char *pSrc,char * &pDest) { pDest = NULL; if(pSrc == NULL) return 0; int max = 0,cnt = 0; while(*pSrc != ' ') { if(*pSrc >= '0' && *pSrc <= '9') //数字 { cnt++; if(cnt > max) //更新最长的数字串 { pDest = pSrc - cnt + 1; max = cnt; } } else cnt = 0; pSrc++; } if(cnt > max) { pDest = pSrc - cnt + 1; max = cnt; } return max; } 问题6:字符串转换为整数 #include <iostream> #include <limits> //需包含这个头文件 using namespace std; int main() { cout << "The maximum value for type float is: " << numeric_limits<float>::max( ) << endl; cout << "The maximum value for type double is: " << numeric_limits<double>::max( ) << endl; cout << "The maximum value for type int is: " << numeric_limits<int>::max( ) << endl; cout << "The maximum value for type short int is: " << numeric_limits<short int>::max( ) << endl; } bool strToIntOK; //全局的变量 int StrToInt(const char *str) { strToIntOK = false; if(str == NULL) //空指针 return 0; if(str[0] == '0' && str[1] != ' ') //以'0'开始但不是"0" 这条其实可以忽略 return 0; unsigned i = 0; bool minus = false; //负数标记 if(str[i] == '-' || str[i] == '+') //判断是不是以正负号开始 { minus = (str[i] == '-')? true: false; i++; } long long result = 0; //转换的结果 while(str[i] != ' ') { char c = str[i++]; if(c >= '0' && c <='9') { result = result * 10 + (c - '0'); if(minus) //负溢出 { if(result - 1 > numeric_limits<int>::max()) return 0; } else //正溢出 { if(result > numeric_limits<int>::max()) return 0; } } else { return 0; } } strToIntOK = true; //结果返回 需强制转换一下 return minus? (int)(-result):(int)result; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |