语法级-字符串

# 字符串

---

## 一、字符和ascII码

#### 1、 字符类型

c语言中，用char表示字符型数据，指一个字符（有且只有一个字符），用单引号括起来，例如'a', '#'等。

---

#### 2、字符的存储

所有数据在计算机里都存储为二进制数，为了能用二进制数表示字符，美国国家标准学会（ANSI）制订了ASCII编码（美国标准信息交换代码），用7位的二进制数来表示128个可能的字符。例如

```c++
字符空格的ASCII码为32
字符0－9 的ASCII码为48-57
字符A－Z的ASCII码为65－90
字符a－z的ASCII码为97-122
```

---

更多信息可查看：
[ASCII码表](https://baike.baidu.com/pic/ASCII/309296/0/c2fdfc039245d688c56332adacc27d1ed21b2451?fr=lemma&ct=single#aid=0&pic=c2fdfc039245d688c56332adacc27d1ed21b2451) 或 [ASCII－百度百科](https://baike.baidu.com/item/ASCII/309296?fr=aladdin&fromid=19660475&fromtitle=ascii%E7%A0%81%E8%A1%A8)

---

#### 3、字符数字转换

由于字符的存储设计为ASCII码方式，于是字符数据与整型数据是可以通用的，互相赋值、互相运算等。

```c++
int n=65;
char c=n;
cout<<c; //'A'

n = c + 1;
cout<<n; //66

c='0' + 3;
cout<<c; //'3'

n = c - '0';
cout<<n; //3
```

---

#### 4、大小写

在ASCII码里，小写字符比大写字符的ASCII码大32，所以转换成数字减32，然后转换回字符即成了大写。

```c++
char c = 'A';
c = c + 32;
cout<<c; //'a'
```

---

#### 5、练习题

##### 5.1 数字的和

输入长度为5的字符串（连续5个字符），每个字符都是数字字符，求所有单个数字字符的和。

`例如`：15673，和为1+5+6+7+3=22

`输入样例`－5个字符：

```
15673
```

`输出样例`－单个数字的和：

```
22
```

---

参考代码：

```c++
#include <iostream>
using namespace std;

int main()
{
    int sum = 0;// 累加器
    char c; // 定义字符
    for (int i = 0; i < 5;i++) // 循环5次，每次取一位
    {
        cin >> c;
        sum =sum + c - '0';
    }
    cout << sum << endl;    // 输出结果
    return 0;
}
```

---

##### 5.2 凯撒加密

古罗马皇帝凯撒在打仗时使用字母错位的方法加密军事情报，这种加密方法会把ABC变成DEF。
编写程序，用c1, c2, c3存储输入的三位字符（大写），输出加密后的三位字符，加密方法是使用ASCII码加上3，然后再输出解密后的原三位字符。

`输入样例1`：

```
A B C
```

`输出样例1`：

```
DEF
ABC
```

参考代码：

```c++
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    char c1, c2, c3;
    cin >> c1 >> c2 >> c3;
    c1 = c1 + 3;
    c1 = (c1-'A')% 26 ;
    c2 = c2 + 3;
    c3 = c3 + 3;
    cout << c1 << c2 << c3 << endl;
    //
    c1 = c1 - 3;
    c2 = c2 - 3;
    c3 = c3 - 3;
    cout << c1 << c2 << c3 << endl;
    return 0;
}
```

---

##### 5.3 一本通p1129 统计数字字符个数

[p1129](http://ybt.ssoier.cn:8088/problem_show.php?pid=1129)

参考代码：

```c++
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    char c;
    int cnt = 0;
    while(cin >> c)// 注意，在window，需要ctrl+Z 然后回车，linux是ctrl+D，然后回车，方可完成输入结束
    {
        if(c >= '0' && c <= '9')
        {
            cnt++;
        }        
    }
    cout << cnt;
    return 0;
}
```

---

## 二、字符数组

#### 1、字符串常量

我们在一开始学习c++的时候，就学会了输出"hello world!"，这种用双引号扩起来的一串内容，称之为字符串常量。

```c++
cout << "hello world!";
```

对应的，单引号扩起来的为单个字符常量。

---

#### 2、字符数组

由字符元素组成的数组，称之为字符数组。

```c
char a[5] = {'a', 'b', 'c', 'd', 'e'};
```

字符数组与整数数组一样的使用，也有一维、二维之分，同样可以使用下标访问。

---

#### 3、字符串

c语言中，字符数组加上一个'\0'元素，用来表示一个字符串，程序中通过检测'\0'所在的位置判定字符串是否结束（字符串长度）。

```c
char a[5] = {'m', 'i', 'k', 'e', '\0'};
```

下标 |0|1|2|3|4|5
-|-|-|-|-|-|-
元素|m|i|k|e|\0|b

字符串长度为4，用strlen(s)函数可以计算得到。

---

#### 4、字符数组初始化

除了用数组一样的初始化方式之外，字符数组还可以直接使用字符串常量进行初始化，例如：

```c
char a[] = "hello";
char b[] = {"tom"};
```

当使用字符串常量进行初始化时，系统会自动给数组后面加上'\0'，所以长度要多1个。

---

#### 5、输入字符串

当从终端读入字符串时，可以根据场景使用不同的方法：
char a[100];

* cin >> a： 当遇到空格、tab、换行就会停止。
* gets(a)：可以读入空格、tab，遇见换行停止，超过不会报错。
* cin.getline(a, len)：读入指定长度的字符串，长度为len-1（因为还有一个'\0'）。

---

#### 6、扩展理解

##### 6.1、转义符

'\0'是一个特殊字符，其ASCII码为0，'\'称之为转义符，有很多类似的特殊字符，例如：

---

##### 6.2. c字符串

在c++中，提供了string类用来表示字符串，为了区分字符数组和string，一般把字符数组以'\0'结束的称之为c字符串。

---

## 三、字符数组函数

1. strlen－长度
2. strcpy－拷贝
3. strcmp－比较
4. strcat - 连接
5. strlwr－大小写

---

#### 1. 长度

##### 1.1 数组长度

如果定义的时候没有声明长度，可以采用sizeof的方法：

```
char a[] = "hello";
  int len = sizeof(a) / sizeof(a[0]); //6
```

---

##### 1.2 字符串长度

对于'\0'结束的字符数组，用sizeof算出的是分配空间的长度，而字符串长度可用strlen函数计算：

```c++
char a[10] = "hello";
int len = strlen(a); //5
```

---

#### 2. 拷贝

##### 2.1 strcpy函数

strcpy(dest,  src)：将src的内容（包括结束符'\0'），拷贝到dest中， 函数返回dest。

```
char dest[10];
strcpy(dest, "hello"); //dest: hello\0
```

---

`注意`：

1. 此函数内部实现是以结束符'\0'为循环结束条件的，如果src不是'\0'结束的，会出现意外危险。
2. 如果src长度超过dest，则会出现溢出危险，即其它地址的内容被修改。

---

##### 2.2 strncpy函数

strcpy(dest,  src, len)：将src的内容的前len位，拷贝到dest中， 函数返回dest。

```
char dest[10] = "123456789";
strncpy(dest, "hello", 3); //dest: ``hel456789`
```

---

#### 3. 连接

strcat(dest, src)：将src连接到dest后面，src的第一个元素替代了dest的结束符'\0'。

```
char s1[20] = "i am";
char s2[] = "a boy";
strcat(s1,s2); //s1-->i am a boy\0
```

`注意`：如果s1的长度不够的话，也会产生溢出。

---

#### 4. 比较

strcmp(s1, s2): 比较两个字符串是否相等：

* 相等：返回0
* s1 > s2：返回正整数（第一个不等的字符的差值）
* s1 < s2：返回负整数（第一个不等的字符的差值）

```
char pwd[] = "123456";
int b = strcmp(pwd,"123456"); //b == 0
```

---

#### 5. 大小写

##### 5.1 字符大转小

tolower(c)：将一个字符转为小写，返回值为 int（ASCII码）。

```
char c = tolower('A');  //'a'
```

---

##### 5.2 字符小转大

toupper(c)：将一个字符转为大写，返回值为 int（ASCII码）。

```
char c = toupper('b'); //'B'
```

---

##### 5.3 字符串大小写

c++（c）语言标准库没有实现字符串大小写转换的函数，需要自己实现。

---

## 四、string类

1. string类
2. 变量声明和实例化
3. 常用运算符
4. 输入输出
5. 下标访问
6. 字符串数组

---

#### 1、string类

c语言使用'\0'结束的字符数组来表示字符串，为了更方便的使用字符串，c++中专门提供了一个string类，包含在命名空间std中，类库为cstring。

```c++
#include <cstring>

string s = "hello world!";
```

---

#### 2、变量声明和实例化

string类型的变量声明和基本类型（int、short、char、bool等）一样：

```
string s;
```

但是string是一个类，其变量初始化需要经过实例化，即调用构造函数来初始化。

---

以下几种典型的实例化方法：

```c++
string s("hello");  //将c字符串"hello"作为s的值
string s(str1);     //拷贝str1字符串变量的值作为s的值
string s(10, 'a');  //生成10个'a'组成的字符串作为s的值
stirng s = "hello";
```

---

#### 3、常用运算符

为了更方便的对字符串变量进行操作，string类重载了一些运算符，使用起来更加一致。

```
string s = "hello world!";  //赋值
string s2 = s + " 1234";  //连接成"hello world! 1234"
if (s2 == s1)  //是否相等
```

---

#### 4、输入输出

string类型变量的输入，可以使用几种：

* cin>>s：遇见空格、tab、回车就停止。
* getline(cin, s)：读入一行，遇见回车停止。
* getline(cin, s, ch)：读入一行，遇见ch（字符）停止。

如果想输入带空格的语句，使用getline函数。

输出字符串变量跟原来一样，如果想输出地址，使用&地址符。

---

#### 5、下标访问

string类也提供了下标运算符[]，可以使用下标来访问字符元素。

```
s = "hello";
cout << s[0] << endl;  //'h'

s[0] = 'H';
cout << s << endl; //"Hello"
```

---

#### 6、字符串数组

每个元素都是一个字符串，例如：

```
string color[3] = {"red", "blue", "yellow"};
```

---

## 五、string类字符串函数

1. 赋值：assign
2. 拼接：push_back、append
3. `查找`：find
4. 插入：insert
5. 删除：erase
6. 替换：replace
7. `子串`：substr
8. 长度：length、size

---

#### 1、拼接

##### 1.1 拼接字符

* s.push_back(ch)：时间复杂度为O(1)，`最适合循环里调用`。
* s = s + ch：时间复杂度介于O(1)和O(n)之间。

---

##### 1.2 拼接字符串

* s.append(t)：时间复杂度为O(n)。
* s = s + t: 时间复杂度为O(n)

---

#### 2、查找

* s.find(t)：在s中查找t，返回t第一个出现的位置，如果找不到返回string::npos（2^64-1）
* s.find(t, x): 从第x位开始查找
* s.find_first_of(t, x): 从x位置开始找，第一个t里的字符出现的位置。
* s.find_first_not_of(t, x)：从x位置开始找，第一个不在t里的字符出现的位置。
* s.rfind(t): 从后往前找
* s.find_last_of(t, x)：从后往前找，第一个t里的字符
* s.find_last_not_of(t, x)：从后往前找，第一个不在t里的字符

```
s = "hello world!";
int pos = s.find("world"); //6
```

---

#### 3、插入

s.insert(x, t)：在s的第x位上插入字符串t。

```
s = "01234";
s.insert(3, "abc"); //012abc34
```

`注意`：x一定要是合法的下标！

---

#### 4、删除

* s.erase(x): 从第x位开始删除到最后
* s.erase(x, len)：从第x位开始删除len位

```
s = "abcdefg";
s.erase(2, 3); // cde被删除了，剩下abf
```

`注意`：x一定要是合法的下标！

---

#### 5、替换

s.replace(x, len, t)：用t替换s中从x开始长度len的一段子串。

```
s = "abcdefg";
s.replace(2, 1, 123); //ab123def：cd被替换成了123
```

---

`注意`：

* x -> x+len-1 都要是合法的下标
* 替换可以换成删除＋插入实现

#### 6、子串

s.substr(x, len)：取出从第x位开始，长度为len 的子串。

```
s = "abcdefg";
string s2 = s.substr(3, 2); //s2 -> de
```

---

`注意`：

* x一定要是合法的下标。
* 如果x + len -1越界，则只取合法内容。

---

#### 7.长度

```c++
string s;
cin >>s;
//这个字符串的长度可以用以下两个函数来求
s.length();
s.size();
```

---

## 六、综合练习

#### 1.一本通：1130：找第一个只出现一次的字符

[1130：找第一个只出现一次的字符](http://ybt.ssoier.cn:8088/problem_show.php?pid=1130)

---

参考代码：(思路1：暴力做法)

```c++
#include <iostream>

#include <cstring>
using namespace std;

int main()
{
    string s; //定义c++字符串变量s
    cin >> s; // 输入的内容放在变量s中
    int flagG = 0; // 是否找到只出现一次的标志变量，0表示没找到，1表示找到了
    // 枚举s中的每一个字符，
    for (int i = 0; i < s.length(); ++i) // 1e5
    {
        int flag = 0;// 有没有重复标志变量，0表示没有重，1表示重复
        // 枚举的每一个字符s[i]，与其他的每一个字符比较，相同则重复
        for (int j = 0; j < s.length(); ++j) // 1e5
        {
            if(i == j) // 不能为同一个字符
                continue; // 是则不执行后面的语句，继续循环
            if(s[i] == s[j]) // 如果相同了，则表示重复
            {
                flag = 1; 
            }
        }
        if(flag == 0) // 检查s[i]这个字符没有重复
        {
            cout << s[i] << endl; // 输出这个字符
            flagG = 1; // 找到了不重复的字符，标志变量设为1
            break; // 找到就退出循环
        }
    }
    if(!flagG) //没找到只出现一次的字符，要输出no
        cout << "no";
    return 0;
     
}
```

---

参考代码2（桶数组的思路，可降低时间复杂度为O(n)）

```c++
#include <iostream>

#include <cstring>
using namespace std;

int main()
{
    string s; //定义c++字符串变量s
    cin >> s; // 输入的内容放在变量s中
    int flagG = 0; // 是否找到只出现一次的标志变量，0表示没找到，1表示找到了
    int to[200] = {0}; // 桶数组，下标表示的是字符的ASII码，内容表示这个字符有几个,注意要初始化数组内容全为0
    //
    for (int i = 0; i < s.length(); ++i)
    {
        to[s[i]]++;
    }
    for (int i = 0; i < s.length(); ++i)
    {
        //这个s[i]，在桶中的数量为1，则说明是不重复的
        if(to[s[i]] == 1)
        {
            flagG = 1;
            cout << s[i] << endl;
            break;
        }
    }
    if(!flagG)
        cout << "no";
    return 0;
}
```