算法基础之字符串

冷不防 2022-09-05 04:05 172阅读 0赞

### 算法基础之字符串（C++示例） ###

无论是工程设计还是算法设计均离不开字符串，字符串是由一个个单独的字符构成的串，其数据结构是线性的，常以ASCII码表示，同时只要设定得当，其展示任何一种编码UTF-8也都是可以的。

C 风格的字符串在 C++ 中继续得到支持——C++可以像C那样处理字符串，还可以使用字符串数据类型string。

字符串有很多的操作，C的头文件<string.h>(C++则是<cstring>)已经封装好了许多函数和方法可以直接使用。

**一、c++****字符串基础知识**

c++支持（提供）两种字符串

c风格的字符串

c++中的字符串

C风格的字符串起源于 C 语言，并在 C++ 中继续得到支持。字符串实际上是使用 null 字符 ‘\\0’ 终止的一维字符数组。下面的声明和初始化创建了一个 “Hello” 字符串。

由于在数组的末尾存储了空字符，所以字符数组的大小比单词 “Hello” 的字符数多一个。

char s\[6\] = \{'H', 'e', 'l', 'l', 'o', '\\0'\};

依据数组初始化规则，您可以把上面的语句写成以下语句：

char s\[\] = "Hello";

内存表示示意：

![20210817063853468.png][]

不需你显示把 null 字符放在字符串常量的末尾，C++ 编译器会在初始化数组时，自动把 ‘\\0’ 放在字符串的末尾。

#include <iostream>
 using namespace std;
 int main (){
 char s1[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
 char s2[6] = {'H', 'e', 'l', 'l', 'o'};
 char s3[] = "hello"; //编译器会根据字符串长度的大小初始化字符数组的
 
 cout << s1 << endl;
 cout << s2 << endl;
 cout << s3 << endl;
 }

运行输出如下：  
Hello  
Hello  
hello

C风格字符串处理函数

<table style="width:434.6pt;"> 
 <tbody> 
 <tr> 
 <td style="background-color:#eeece1;border-color:#f2f2f2;width:87.3pt;"> 函数<a rel="nofollow"></a> </td> 
 <td style="background-color:#eeece1;border-color:#f2f2f2;width:347.3pt;"> 功能 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#ffffff;border-color:#d4d4d4;width:87.3pt;"> strcpy(s1, s2) </td> 
 <td style="background-color:#ffffff;width:347.3pt;"> 复制字符串 s2 到字符串 s1。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#f6f4f0;border-color:#d4d4d4;width:87.3pt;"> strcat(s1, s2)&nbsp; </td> 
 <td style="background-color:#f6f4f0;width:347.3pt;"> 连接字符串 s2 到字符串 s1 的末尾。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#ffffff;border-color:#d4d4d4;width:87.3pt;"> strlen(s1) </td> 
 <td style="background-color:#ffffff;width:347.3pt;"> 返回字符串 s1 的长度。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#f6f4f0;border-color:#d4d4d4;width:87.3pt;"> strcmp(s1, s2) </td> 
 <td style="background-color:#f6f4f0;width:347.3pt;"> 如果 s1 和 s2 是相同的，则返回 0；如果 s1&lt;s2 则返回小于 0；如果 s1&gt;s2 则返回大于 0。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#ffffff;border-color:#d4d4d4;width:87.3pt;"> strchr(s1, ch) </td> 
 <td style="background-color:#ffffff;width:347.3pt;"> 返回一个指针，指向字符串 s1 中字符 ch 的第一次出现的位置。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#f6f4f0;border-color:#d4d4d4;width:87.3pt;"> strstr(s1, s2) </td> 
 <td style="background-color:#f6f4f0;width:347.3pt;"> 返回一个指针，指向字符串 s1 中字符串 s2 的第一次出现的位置。 </td> 
 </tr> 
 </tbody> 
</table>

★ c风格字符串处理函数示例：

#include <stdio.h>
 #include <string.h>
 
 int main( )
 {
 char c[10] = "欢迎";
 printf("输出1：%s\n", c); //输出1：欢迎
 printf("输出1的长度：%d\n", strlen(c)); //输出1的长度：4
 
 char a[10];
 strcpy(a,"你好啊");
 printf("输出2：%s\n",a); //输出2：Hello world
 printf("输出2的长度：%d\n", strlen(a)); //输出2的长度：11
 
 return 0;
 }

C++ 标准库提供了 string 类类型，支持上述所有的操作，另外还增加了其他更多的功能。

string 类的构造函数

string 类有多个构造函数，用法示例如下：

string s1(); // si = ""

string s2("Hello"); // s2 = "Hello"

string s3(4, 'K'); // s3 = "KKKK"

string s4("12345", 1, 3);  //s4 = "234"，即 "12345" 的从下标 1 开始，长度为 3 的子串

为称呼方便，本教程后文将从字符串下标 n 开始、长度为 m 的字符串称为“子串(n, m)”。

string 对象的赋值

可以用 char\* 类型的变量、常量，以及 char 类型的变量、常量对 string 对象进行赋值。例如：

string s1;

s1 = "Hello"; // s1 = "Hello"

s2 = 'K'; // s2 = "K”

string 类还有 assign 成员函数，可以用来对 string 对象赋值。assign 成员函数返回对象自身的引用。例如：

string s1("12345"), s2;

s3.assign(s1);  // s3 = s1

s2.assign(s1, 1, 2);  // s2 = "23"，即 s1 的子串(1, 2)

s2.assign(4, 'K');  // s2 = "KKKK"

s2.assign("abcde", 2, 3);  // s2 = "cde"，即 "abcde" 的子串(2, 3)

C++字符串处理函数

<table style="width:399.15pt;"> 
 <tbody> 
 <tr> 
 <td style="background-color:#eeece1;border-color:#f2f2f2;width:94.4pt;"> 函数 </td> 
 <td style="background-color:#eeece1;border-color:#f2f2f2;width:304.75pt;"> 功能 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#ffffff;border-color:#d4d4d4;width:94.4pt;"> append() </td> 
 <td style="background-color:#ffffff;width:304.75pt;"> 在字符串的末尾添加字符。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#f6f4f0;border-color:#d4d4d4;width:94.4pt;"> find()&nbsp; </td> 
 <td style="background-color:#f6f4f0;width:304.75pt;"> 在字符串中查找字符串。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#ffffff;border-color:#d4d4d4;width:94.4pt;"> insert() </td> 
 <td style="background-color:#ffffff;width:304.75pt;"> 插入字符。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#f6f4f0;border-color:#d4d4d4;width:94.4pt;"> length()或size() </td> 
 <td style="background-color:#f6f4f0;width:304.75pt;"> 返回字符串的长度。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#ffffff;border-color:#d4d4d4;width:94.4pt;"> <a rel="nofollow">replace()</a> </td> 
 <td style="background-color:#ffffff;width:304.75pt;"> 替换字符串。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#f6f4f0;border-color:#d4d4d4;width:94.4pt;"> substr() </td> 
 <td style="background-color:#f6f4f0;width:304.75pt;"> 返回某个子字符串。 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#ffffff;border-color:#d4d4d4;width:94.4pt;"> erase() </td> 
 <td style="background-color:#ffffff;width:304.75pt;"> 删除字符串中的一个子字符串。 </td> 
 </tr> 
 </tbody> 
</table>

★ C++字符串处理函数示例1

#include <iostream>
 using namespace std;
 
 int main( )
 {
 string c = "Hello";
 cout <<"输出1："<< c << endl; //输出1：Hello
 cout <<"输出1的长度：" << c.size() << endl; //输出1的长度：5
 
 string a;
 a = "Hello world";
 cout <<"输出2："<< a << endl; //输出2：Hello world
 cout <<"输出2的长度："<< a.size() << endl; //输出2的长度：11
 
 return 0;
 }

★ C++字符串处理函数示例2

本示例演示replace()的使用

#include<string>
 #include<iostream>
 
 using namespace std;
 
 int main() 
 {
 	//用法一： 
 	//string replace (size_t pos, size_t len, const string& str); 
 	//源字符串中从位置 pos 开始长度为 len 的字符串 被字符串 str 代替 
 	//功能：只替换一次 
 string str_line("I love compile");
 cout << str_line.replace(str_line.find('e'), 1, "#") << endl; //输出：I lov# compile 
 
 //用法二： 
 	//string replace (const_iterator i1, const_iterator i2, const string& str); 
 	//用 str 替换 迭代器起始位置 和 结束位置 之间的字符 
 	//功能：替换一段字符串
 string str_line2("I love compile");
 cout << str_line2.replace(str_line2.begin(), str_line2.begin()+6, "**")<< endl; //输出：** compile
 
 //用法三： 
 	//tring replace (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen); 
 	//源串指定位置上的子串（pos开始len长度）被替换为 str 的指定子串（给定起始位置和长度）
 	string str_line3("I love compile"); 
 	string substr = "12345";
 cout << str_line3.replace(7, 7, substr, substr.find("2"), 3) << endl; //输出：I love 234
 
 return 0; 
 }

**二、c++****字符串算法示例**

前面提到过，字符串有很多的操作，C的头文件<string.h>(C++则是<cstring>)已经封装好了许多函数和方法可以直接使用。<algorithm>库提供的函数swap，reverse，sort等实现交换、反向、排序等功能。作为字符串算法设计学习，可以从设计的角度介绍这些字符串基本的操作以及其实现代码。

**例1、反转字符串**

编写一个函数，其作用是将输入的字符串反转过来。如

输入：hello

输出：olleh

**法一**、使用 <algorithm>库方法：reverse()

#include <iostream>
 #include <string>
 #include <algorithm>
 using namespace std;
 
 int main(void)
 {
 string str = "hello";
 reverse(str.begin(), str.end());
 cout << str << endl;
 
 return 0;
 }

**法二**、自己编写 myReverse()函数

# include <iostream>
 #include <string>
 using namespace std;
 
 string myReverse(string str);
 
 int main(void)
 {
 string strData = "hello";
 string strReverse = myReverse(strData);
 cout << strReverse << endl;
 }
 
 string myReverse(string str)
 {
 int i;
 int len = str.length();
 for (i = 0; i < len/2; i++)
 {
 char c = str[i];
 str[i] = str[len -i -1];
 str[len -i -1] = c;
 }
 return str;
 }

**例2、给定一个字符串，验证它是否是回文串，区别字母的大小写。**

这个问题，可以从字符串的两头开始比较，即第1个字符和倒数第1个字符比较，第2个字符和倒数第2个字符比较，以此类推...如果出现字符不相等的情况，说明不是回文，如果全部相等，说明是回文。代码如下：

#include <iostream>
 #include <string>
 using namespace std;
 
 int main(void)
 {
 string s; // 存放输入的字符串 
 int i, j, n;
 cout<<"输入字符串：";
 cin >> s;
 
 n=s.length();
 for(i=0,j=n-1;i<j;i++,j--)
 if(s[i]!=s[j]) break;
 if(i>=j)
 cout<<"是回文串\n";
 else
 cout<<"不是回文串\n";
 
 	return 0;
 }

【附、C代码如下

#include <stdio.h>
 #include <string.h>
 #include <string.h>
 int main(){
 char s[100]; // 存放输入的字符串 
 int i, j, n;
 printf("输入字符串：");
 gets(s);
 
 n=strlen(s);
 for(i=0,j=n-1;i<j;i++,j--)
 if(s[i]!=s[j]) break;
 if(i>=j)
 printf("是回文串\n");
 else
 printf("不是回文串\n");
 }

】

**例3、把字符串中的特定字符删除**

法一、使用来自<algorithm>的remove()函数, 此函数的template是

template <class ForwardIterator, class T>

ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val);

作用: 在容器中, 删除\[first, last)之间的所有值等于val的值。

返回值: 一个迭代器 (记作newEnd), 该迭代器指向最后一个未被删除元素的下一个元素, 即相当于容器新的end。

代码如下：

#include <iostream>
 #include <string>
 #include <algorithm> // remove()来自<algorithm>
 using namespace std;
 
 int main ()
 {
 string s="AascfAfAjAk";
 s.erase(remove(s.begin(), s.end(), 'A'), s.end());
 cout << s << '\n';
 
 return 0;
 }

法二、使用string::iterator（字符串迭代器），从开始 str.begin() 迭代到最后 str.end() ，再使用string.erase(const\_iterator p)函数来删除迭代器所指向的字符。

代码如下：

#include <iostream>
 #include <string>
 using namespace std;
 
 int main ()
 {
 string str="AascfAfAjAk";
 char ch='A';
 string::iterator it;
 for (it = str.begin(); it < str.end(); it++)
 {
 if (*it == ch)
 {
 str.erase(it);
 it--; //【注】 
 }
 }
 cout << str;
 
 return 0;
 }

【注】it-- 很重要，因为使用erase()删除it指向的字符后，后面的字符就移了过来，it指向的位置就被后一个字符填充了，而for语句最后的it++，又使it向后移了一个位置，所以就忽略掉了填充过来的这个字符。在这加上it--后就和for语句的it++抵消了，使迭代器能够访问所有的字符。

【附、C代码如下：

下面代码，在原来的数组上通过数组元素的移动完成了删除特定字符串的工作。

参见下图，通过复制操作来移动元素，恰巧跳过要删除的字符。

![20210817155940724.png][]

★代码如下：

#include <stdio.h>
 
 int main ()
 {
 char s[] = "AascfAfAjAk";
 int j, k;
 char c='A';
 for(j=k=0; s[j]!='\0'; j++)
 if(s[j]!=c)
 s[k++]=s[j];
 s[k]= '\0';
 printf("\n%s",s);
 return 0;
 }

★改的灵活点，代码如下：

#include <stdio.h>
 int main(){
 char s[], c;
 int j, k;
 printf("Enter a string: ");
 gets(s);
 printf("Enter a character: ");
 c=getchar( );
 for(j=k=0; s[j]!='\0'; j++)
 if(s[j]!=c)
 s[k++]=s[j];
 s[k]= '\0';
 printf("\n%s",s);
 return 0;
 }

】

[20210817063853468.png]: /images/20220829/5511a5a0224c4746bb06ed97ce09237c.png
[20210817155940724.png]: /images/20220829/3001c59489d046d1893e5759e1bc24b6.png