其实字符串就是一种更加特殊的线性结构。他表现在:1.使用char类型的数组来存储。2.面向字符串的操作与一般的顺序表不同,比如元素的插入、删除、确定位置等,一般的顺序表定义的操作都是1次处理一个元素,而字符串的操作往往是处理若干个字符。
因为字符串操作的这些特殊性,所以C语言中专门在string.h头文件中定义了许多关于字符串的操作,其中比较重要的是:字符串输出函数 puts、字符串输入函数gets、字符串连接函数strcat、字符串拷贝函数strcpy、字符串比较函数strcmp、测字符串长度函数strlen等等。我们这里在不使用标准库的情况下,自己动手写一些与这些函数功能类似的函数。
首先考虑字符串的定义,按照我以前的风格,都不是通过定义一个很长的数组来实现,而是通过动态分配内存的方法来实现,这样的话,需要一个变量记录动态数组的长度,有了这个长度,我们就不需要像C语言那样通过在结尾加添'\0'来判断字符串是否结束了。
typedef struct String
{
char* data;
int size;
}String;
//分配字符串
bool assignStr(String *pT,char *chars)
{
//求字符串的长度
int i = 0;
while(chars[i] != '\0')
++i;
//如果是空串
if(0 == i)
{
pT->data = NULL;
pT->size = 0;
}
else
{
pT->size = i;
pT->data = (char*)malloc(sizeof(char) * pT->size);
if(NULL ==pT->data )
return false;
else
{
for(int j = 0; j < i;++j)
pT->data[j] = chars[j];
}
}
return true;
}
//销毁字符串
void clearStr(String *pS)
{
free(pS->data);
pS->data = NULL;
pS->size = 0;
}
//求字符串长度
int strLength(String *pS)
{
return pS->size;
}
//字符串拷贝
bool strCpy(String *pT,String *pS)
{
if(strLength(pT) < strLength(pS))
{
pT->data = (char*)realloc(pT->data,sizeof(char) * pS->size);
pT->size = pS->size;
}
if(NULL == pT->data)
return false;
else
{
for(int i = 0; i < strLength(pT);++i)
pT->data[i] = pS->data[i];
pT->size = pS->size;
return true;
}
}
//判断是否为空
bool is_empty(String *pS)
{
if(NULL == pS->data && 0 == pS->size)
{
printf("empty");
return true;
}
else
return false;
}
//字符串比较
int strCmp(String *pT,String *pS)
{
int i = strLength(pT);
int j = strLength(pS);
int k;
//找出长度较短的字符串
i < j ? k = i : k = j;
for(int i = 0; i< k; ++i)
{
if(pT->data[i] > pS->data[i])
return 1;
else if(pT->data[i] < pS->data[i])
return -1;
}
//如果程序能完整执行完for循环,说明两个字符串的前k个字符相等
//剩下只要比较它俩谁长就可以了
if(i < j)
return -1;
else if(i > j)
return 1;
else
return 0;
}
//将第二个字符串连接到第一个后面
void strCat(String *pT,String *pS)
{
int i = strLength(pT);
int j = strLength(pS);
pT->data = (char*)realloc(pT->data,sizeof(char) * (i+j));
for(int m = i,n = 0 ; m < (i+j); ++m,++n)
pT->data[m] = pS->data[n];
pT->size = i + j;
}
//从指定的位置返回指定长度的子串
bool getSubString(String *pS,int pos,int len,String *pSubString)
{
//判断输入的位置和长度是否合法
if(pos < 0 || len <= 0 || len+pos > strLength(pS))
return false;
for(int i = pos,j = 0; i<pos+len;++i,++j)
{
pSubString->data[j] = pS->data[i];
}
pSubString->size = len;
return true;
}
//在指定位置后插入字符串
bool insertStr(String *pT,String *pS,int pos)
{
int i = strLength(pT);
int j = strLength(pS);
if(pos < 0 || pos > j)
return false;
pS->data = (char*)realloc(pS->data,sizeof(char) * (i+j));
pS->size = i+j;
if(NULL == pS->data)
return false;
for(int m = i+j ; m > pos; --m)
pS->data[m] = pS->data[m-i];
for(int n = pos,l = 0; n < i+pos;++n,++l)
pS->data[n] = pT->data[l];
return true;
}
//删除指定位置后面的若干个字符串
bool deleteStr(String *pS,int pos,int len)
{
int j = strLength(pS);
if(pos < 0 || pos > j || len + pos > j)
return false;
for(int i = pos; i < j-len;++i)
pS->data[i] = pS->data[i+len];
pS->size -= len;
return false;
}
//检索:源字符串的某个位置以后是否有目标字符串有则返回位置,无则返回-1
int index(String *pT,String *pS,int pos)
{
int m = strLength(pS);
int n = strLength(pT);
//如果比较位置大于等于源字符串的长度,返回-1
if(pos >= m)
return -1;
int i = pos,j = 0;
//当两个字符都没有访问到最后一个元素时,继续
while(i + n < m && j < n)
{
//如果从某一个位置起二者相等,继续比较
if(pS->data[i] == pT->data[j])
{
++i;
++j;
}
//否则源字符串从第一个字符匹配的下一个位置开始继续,目标字符串从头开始继续
else
{
i = i - j+1 ;
j = 0;
}
//如果目标串已经遍历完,说明找到了
if(j == strLength(pT))
return i- strLength(pT);
}
//没有找到,返回-1
return -1;
}
//替换
void replace(String *pT,String *pS,String *pNew)
{
//使用已经定义的操作完成:查找、删除、插入
int m = strLength(pT);
int n = strLength(pNew);
int i = 0;
do{
i = index(pT,pS,i);
if(i != -1)
{
deleteStr(pS,i,m);
insertStr(pNew,pS,i);
i += n;
}
}
while(i != -1);
}
//打印字符串,调试时使用
void printStr(String *pT)
{
printf("word: ");
// 不能使用下面这句,因为pT->data之前可能曾经很长
// printf("%s",pT->data);
for(int i = 0 ; i < strLength(pT);++i)
printf("%c",pT->data[i]);
printf("\n");
}
需要注意的是,字符串的索引操作中,有一种更加有效率的办法,称为:KMP算法,这里并没有使用,而是使用的更加直观的索引算法。
下面通过一个复杂的例子来结束对字符串的讨论:求两个字符串的最长公共子串。
//查找最长的公共子串,返回这个子串的位置,子串从pNew中带出
//算法简述:
//1.将两个子串组成一个矩阵,若矩阵行、列对应的元素相同,这个元素为1,反之为0
//2.遍历对角线
//3.找出长度最大的非0对角线,这条对角线对应的元素就是最长的公共子串
//举例
/*
a b d c a b c d
d 0 0 1 0 0 0 0 1
c 0 0 0 1 0 0 1 0
a 1 0 0 0 1 0 0 0
b 0 1 0 0 0 1 0 0
c 0 0 0 1 0 0 1 0
c 0 0 0 1 0 0 1 0
a 1 0 0 0 1 0 0 0
则最长公共子串为cabc
*/
//函数声明
//对于矩阵的每一个元素,计算它的对角线为1的对角线的长度
//输入参数为:矩阵、当前点的行、列坐标,矩阵的长、宽
int getDiaLength(int **M,int m,int n,int row,int col);
int getLongestSubString(String *pS1,String *pS2,String *pR)
{
int row = strLength(pS1);
int col = strLength(pS2);
//动态分配2维数组m*n
//先分配第一维:每个是int*类型的指针,共m个
int **pM = (int**)malloc(sizeof(int*)*row);
//为每个int*类型的指针分配n个int的空间
for(int i = 0; i< row;++i)
pM[i] = (int*)malloc(sizeof(int)*col);
for(int i = 0; i < row ; ++i)
{
for(int j = 0; j < col ; ++j)
{
if(pS1->data[i] == pS2->data[j])
pM[i][j] = 1;
else
pM[i][j] = 0;
}
}
//打印矩阵结果
for(int i = 0; i < row;++i)
{
for(int j = 0; j < col; ++j)
printf("%d ",pM[i][j]);
printf("\n");
}
printf("\n");
//默认最长长度为0
int length = 0;
int k = 0;
for(int i = 0;i < row;++i)
{
for(int j = 0; j < col;++j)
{
k = getDiaLength(pM,i,j,row,col);
if(length < k)
{
length = k;
//标记这个元素
pM[i][j] = length;
}
}
}
//打印矩阵结果
for(int i = 0; i < row;++i)
{
for(int j = 0; j < col; ++j)
printf("%d ",pM[i][j]);
printf("\n");
}
char* pchar = (char*)malloc(sizeof(char)*length+1);
for(int i = 0 ; i < row; ++i)
{
for(int j = 0; j <col; ++j)
if(length == pM[i][j] )
{
for(int m = 0; m < length; ++m,++i)
{
pchar[m] = pS1->data[i];
}
//填充结尾标识符
pchar[length] = '\0';
//令循环条件不满足,这样就能跳出二重循环了
i = row;
j = col;
}
}
//打印一下字符串
printf("%s",pchar);
printf("\n");
//将这个字符串分配给pR指针
assignStr(pR,pchar);
//释放内存
free(pchar);
for(int i = 0;i < row;++i)
free(pM[i]);
free(pM);
pM = NULL;
return length;
}
int getDiaLength(int **M,int m,int n,int row,int col)
{
int len = 0;
while(m<row && n<col)
{
if(1 == M[m][n] )
{
++m;
++n;
++len;
}
else
break;
}
return len;
}
程序是我自己写的,略有点繁琐,但是基本要求还是达到了,中间的一些打印信息只是在调试的时候使用的,正常使用时可以关掉。
我不由得得吐一下槽,因为C语言中并没有C++类中的数据成员的概念,所以在getDiaLength函数中,我不得不传递了如此多的参数。如果有人有更好的办法,希望能告诉我。
再顺便说一句,在C++中,由于定义string这个类,所以很多字符串的操作可以通过这个类提供的函数更加安全的进行(使用类的程序员不必使用指针)。这种使用标准库而不是指针的风格,是现代C++程序设计所提倡的。
分享到:
相关推荐
* 使用一个字符串分割另一个字符串 * * @param delimiter 边界上的分隔字符 * @param haystack 输入的字符串 * @param out 输出的字符串指针 * @return 分割成了多少个成员 */ int explode(char *delimiter, ...
java 字符串转16进制 16进制转字符串 将两个ASCII字符合成一个字节; java 字符串转16进制 16进制转字符串 将两个ASCII字符合成一个字节; java 字符串转16进制 16进制转字符串 将两个ASCII字符合成一个字节; java ...
本文实例讲述了C#判断字符串是否存在字母及字符串中字符的替换的方法。分享给大家供大家参考。具体实现方法如下: 首先要添加对命名空间“using System.Text.RegularExpressions;”的引用 下面以一个字符串为例: ...
indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置。如果要检索的字符串值没有出现,则该方法返回 -1。 方法二:match() var str = "123" var reg = RegExp(/3/); if(str.match(reg)){ //包含; } ...
Delphi 7.0 提取字符串中指定子字符串后的字符串,这个平时在字符处理时候使用几率也挺高的,获取指定字符串后面的字符串,比如获取扩展名等也可以用此方法,本例中要用到After函数,测试时,当单击按钮时,执行以下...
编写程序:从键盘上输入一个包含10个字符的字符串,把该字符串与程序中给定的字符串("bacdbcabca") //依次比较,统计两个字符串对应字符相等的数目。然后输出从键盘上输入的字符串, //并把两个字符串中对应字符不...
给写了2个方法,一个是直接截取单个需要的字符串,比如字符串string a="ab123456",我只需要提取3,那么就是单独截取就可以了,从2开始到4结束就行。 第二个是把所有的符合条件的字符串都截取出来,提取出来,比如...
本文实例讲述了javascript实现的字符串与十六进制表示字符串相互转换方法。分享给大家供大家参考。具体如下: 之所以写这个,是因为发现SQL注入和XSS中经常利用十六进制表示的字符串,比如 SELECT CONCAT(0x68656c6...
C#字符串删除指定字符串|C#字符串删除子字符串
本文实例汇总了C++常用字符串分割方法,分享给大家供大家参考。具体分析如下: 我们在编程的时候经常会碰到字符串分割的问题,这里总结下,也方便我们以后查询使用。 一、用strtok函数进行字符串分割 原型: char *...
string常用截取字符串方法有很多,但是配合使用以下两种,基本都能满足要求: find(string strSub, npos); find_last_of(string strSub, npos); 其中strSub是需要寻找的子字符串,npos为查找起始位置。找到返回子...
通过键盘输入一串小写字母(a~z)组成的字符串,将字符串中连续出席的重复字母进行压缩,并输出压缩后的字符串。 压缩字段的格式为"字符重复的次数+字符"。例如:字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。 要求实现...
这个代码可以添加一个新的字符串到已有的字符串数组中,并确保不会重复添加相同的字符串。具体来说,它首先创建了一个包含3个字符串的字符串数组`strArray`,然后定义了一个新的字符串`newStr`。接着,使用`ismember...
|PowerBuilder 数组字符串相互转化 天津 李华锋 * * | | * *PowerBuilder 数组字符串相互转化 完全免费 * * | | * *如果你将这个程序放在你的网站上,我希望你能同时加上本站的链接 | | * | * | * *老字符串转数组...
编写控制台应用程序,接受长度大于3的字符串,完成以下功能: 1:输出字符串长度 2:输出字符串中第一个出现字母a的位置 3:在字符串的第3个字符后面插入字符串“hello”,输出新字符串. 4:将字符串“hello”替换为...
字符串数组 matlabMATLAB字符串数组 基本规则 (1)所有字符串都用单引号(英文状态下输入)括起来; (2)将字符串当作一个行向量,每个元素对应一个字符,其标识方法和数值向量相同。 (3)size指令获得串数组的大小。串...
按字典顺序比较两个字符串。该比较基于字符串中各个字符的 Unicode 值。将此 String 对象表示的字符序列与参数字符串所表示的字符序列进行比较。如果按字典顺序此 String 对象在参数字符串之前,则比较结果为一个负...
必须实现如下操作,字符串比较、求串的长度、判断串是否为空、将串置空、字符串赋值(包括两个字符串类复制,一个字符串赋值到CmyString对象)、求字符串中的一个字符或改变字符串中的一个字符(采用重载[]),...
输入一个字符串,分别统计出其中英文字母、空格、数字和其它字符的个数,本文给出解决方法 编写思路: 1、字符串的遍历,和列表类似,可以把字符串当做元素都是一个字符的一个字符列表,它可以和列表有公共的语法 2...
编写函数void fun(char *s,char *t,char *p)将未在字符串s中出现、而在字符串t中出现的字符, 形成一个新的字符串放在p中,p中字符按原字符串中字符顺序排列,但去掉重复字符。 例如: 当s为"12345", t为"8624677"时, p...