C/C++解题干货

数据类型选择

1. 整型int取值范围：$-2^{31} \sim +(2^{31}-1)$，题目要求绝对值在$10^9$以内 或 32位整数，则用int型表示

2. 长整型long long取值范围：$-2^{63} \sim +(2^{63}-1)$，题目要求绝对值在$10^{18}$以内 或 64位整数，则用long long型表示

   注：如果 long long 型赋 $> 2^{31}-1$的初值，需要在初值后加上LL，否则编译错误。如long long num = 123456789012345LL;

3. 浮点型数据一律用double存储，而不用float(精度低，6~7位)

4. 字符常量使用**ASCII码(范围0~127)**统一编码。

   • 0~9 的ASCII码值：48~57
   • AZ 的ASCII码值：6590
   • az 的ASCII码值：97122 (比大写字母的ASCII码值大32)

5. 强制类型转换

   #include <cstdio>
   
   int main() {
       double r = 12.56;
       int a = 3, b = 5;
       printf("%d\n", (int)r); //输出12
       printf("%.1f", (double)a / (double)b);//输出0.6
       return 0;
   }

---

输入输出

C语言	C++	比较
#include <cstdio> scanf函数 printf函数	#include <iostream> using std::cin; using std::cout; cin cout	cin 和 cout 无需指定输入输出格式， 但消耗的时间比 scanf 和 printf 多得多。 故推荐使用C语言的 scanf 和 printf， 只有在十分必要的时候使用 cin 和 cout

输入和输出格式

类型	输入	输出
long long	scanf("%lld", &n);	printf("%lld", n);
double	scanf("%lf", &db);	printf("%f", db);
字符串	scanf("%s", str); (无需 取地址符&)	printf("%s", str);
char	c1 = getchar(); 能读入换行符\n	putchar(c1);

实用的输出格式

1. %md

   使不足m位的int型变量以m位进行右对齐输出，高位用空格补齐；若变量本身超过m位，则保持原样。

2. %0md

   使不足m位的int型变量以m位进行右对齐输出，高位用0补齐；若变量本身超过m位，则保持原样。

3. %.mf

   让浮点数保留m位小数(四舍六入五成双)输出。如果要四舍五入，需要用到round函数。

   四舍六入五成双：

   • 5后有数时：舍5入1
   • 5后无数时：
     • 5前为奇数，舍5入1
     • 5前为偶数，舍5不进（0是偶数）

---

C++标准库头文件

C++标准库	包含内容
<iostream>	C++标准输入和输出函数 的函数原型
<cstdio>	C风格标准输入和输出函数 的函数原型
<iomanip>	格式化数据流的流操纵符 的函数原型
<cmath>	数学库函数 的函数原型
<ctime>	处理时间和日期的函数 的函数原型
<cstdlib>	数与文本的转换、内存分配、随机数及其他各种工具函数 的函数原型
<random>	产生非确定性的随机数 的功能库
<cctype>	测试 字符特定属性(如是否为数字、标点符号等)函数 的函数原型 转换 大小写字母的函数 的函数原型
<iterator>	访问 C++标准库容器中数据 的类
<algorithm>	操作 C++标准库容器中数据 的函数
<string>	C++标准库的 string类 的定义
<cstring>	C风格字符串处理函数 的函数原型

---

<cmath>

1. double fabs(double x)

   浮点型取绝对值

2. double floor(double x)和ceil(double x)

   向下取整和向上取整

3. double round(double x)
   针对小数点后一位四舍五入

   另，不使用函数进行四舍五入的方法：

   num = num + 0.5

4. double pow(double r, double p)

   求 r 的 p次方

   $10^n$还有另外的表示方法，如

   • $10^3$ 可写成 1e3
   • $2\times10^6$可写成2e6
   • $3\times10^{-6}$可写成3e-6

5. double sqrt(double x)

   求 x 的算术平方根

6. double log(double x)和double log10(double x)

   求 x 以 $e$ 为底的对数 和 以10为底的对数

   针对任意底数求对数的函数，必须用换底公式，即$\log_ab = \ln b/\ln a$

7. double exp(double x)

   指数函数$e^x$

8. 三角函数

   x为弧度

   • sin(double x)
   • cos(double x)
   • tan(double x)

---

<ctime>

1. time_t time(time_t *seconds)

   返回自 格林尼治标准时间的1970年1月1日0时 起 到现在的秒数。如果seconds不为空，返回值也存储在seconds中。

---

<cstdlib>

1. int rand()

   rand函数生成 [0, RAND_MAX] 之间的一个整数

   直接由rand函数生成的数的范围常常不能满足具体需要，可以通过比例缩放(scaling)方法得到所需的随机数。例如模拟投掷六面骰子，结果可以用rand() % 6 + 1表示。其中数字6称为比例缩放因子。

2. void srand(unsigned int seed)

   rand函数实际上生成的是 伪随机数。程序每次执行时产生的序列都是重复的，将其调整为每次执行时都产生不同的随机数序列的过程称为随机化，可以通过srand函数实现。srand函数接收一个unsigned int值，为 rand函数使用的随机数发生器 “播种”，从而产生不同的随机数序列。为了在随机化时不用每次都输入“种子”，可以使用如下语句：

   srand(static_cast<unsigned int>(time(NULL) ) );

---

<cctype>

1. int isalnum(int c)

   字符是否为数字或字母

2. int isalpha(int c)

   字符是否是字母

3. int isdigit(int c)

   字符是否是十进制数字

4. int islower(int c)

   是否是小写字母

5. int isupper(int c)

   是否是大写字母

6. int tolower(int c)

   把大写字母 转换为 小写字母

   不会改变非字母字符的值

7. int toupper(int c)

   把小写字母 转换为 大写字母

   不会改变非字母字符的值

---

<algorithm>

1. max(x, y)和min(x, y)

2. abs(x)：x必须是整数，因此更推荐使用<cmath>下的fabs(x)

3. swap(x, y)

4. reverse(it1, it2)

   可以将 数组指针在[it1, it2)之间的元素 或 容器的迭代器在[it1, it2)之间的元素 进行反转。

   int a[10] = {10, 11, 12, 13, 14, 15};
   reverse(a, a + 4); //将 a[0] ~ a[3]反转
   for(int i = 0; i < 6; i++)
       cout << a[i] << " ";
   //输出结果：13 12 11 10 14 15
   
   string str = "abcdefghi";
   reverse(str.begin() + 2, str.begin() + 6); //对str[2] ~ str[5]反转
   for(int i = 0; i < str.size(); i++) {
       cout << str[i];
   }
   //输出结果：abfedcghi

5. next_permutation函数

   给出一个序列在全排列中的下一个序列。

   int a[10] = {1, 2, 3};
   do{
       cout << a[0] << a[1] << a[2] << endl;
   } while(next_permutation(a, a + 3)); //a[0]~a[2]之间的序列求解下一个序列

6. fill函数

   对数组或容器中某一段区间元素赋相同的值。和<cstring>的memset不同(基本只用于赋0或-1)，可以赋数组类型对应范围中的任意值。

   int a[5] = {1, 2, 3, 4, 5}
   fill(a, a + 5, 233); //a[0] ~ a[4] 均赋值为 233
   for(int i = 0; i < 5; i++)
       cout << a[i] << " ";
   //输出结果：233 233 233 233 233

7. sort函数

   C语言的qsort函数的使用需要运用指针，且写法上没有C++的sort函数简洁。sort函数根据具体情形使用不同的排序方法，效率较高，在实现中规避了经典快速排序中可能出现的会导致实际复杂度退化到$O(n^2)$的极端情况。

   因此更推荐使用C++的sort函数进行代码编写。

   sort(首元素地址, 尾元素地址的下一个地址, 比较函数cmp(非必填))

   如果不写比较函数cmp，则默认升序排序。如果想要降序排序，需要编写比较函数cmp：

   bool cmp(int a, int b) { //返回值为true时，a被排在b之前
       return a > b; //降序
   }

   在STL标准容器中，只有vector、string、deque可以使用sort，因为像set、map这种容器是用红黑树实现的，元素本身有序，故不允许使用sort排序。

8. lower_bound和upper_bound

   lower_bound(first, last, val)用来寻找在数组或容器中的[first, last)范围内第一个值$\geq$val的元素的位置。

   upper_bound(first, last, val)用来寻找在数组或容器中的[first, last)范围内第一个值>val的元素的位置。

   如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。如果没有找到相应元素，则返回可以插入该元素的位置的指针或迭代器。

9. max_element和min_element

   max_element(first, last)用来寻找在数组或容器中的[first, last)范围内最大元素的位置。

   min_element(first, last, val)用来寻找在数组或容器中的[first, last)范围内最小元素的位置。

   如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。

---

常用容器

<vector>

向量(“变长数组”的叫法更容易理解)，长度可以根据需要进行变化，比较节省空间。试题中，有时会碰到只用普通数组会超内存的情况，使用vector会让问题的解决便捷许多；另外，vector还可以用来以邻接表的方式存储图。

1. vector的定义

   vector<typename> name

   如果typename也是一个STL(Standard Template Library)容器，在C++11之前，定义的时候，在符号>>之间要加上空格。如：vector<vector<int> > name;，可以理解为两个维都可变长的二维数组。

   而vector数组的定义，如：vector<typename> Arrayname[arraySize];，一维长度已固定，注意两者的区别。

2. vector常用函数

   1. push_back(typename x)：在 vector 末尾添加一个元素 x

   2. pop_back()：删除 vector 的末尾元素

   3. begin()：取 vector 的首元素地址

   4. end()：取 vector 的 尾后(尾元素地址的下一个)地址（美国人思维比较习惯左闭右开）

   5. size()：获取 vector 中的元素个数

   6. clear()：清空 vector 中所有元素

   7. insert(vector<typename>::iterator it, typename x)：向vector的 任意迭代器 it 处 插入一个元素 x

      如vi.insert(vi.begin() + 2, -1); //将 -1 插入vi[2]

   8. erase()

      • 删除迭代器为 it 处的元素：erase(it);
      • 删除 [firstIt, lastIt) 内所有元素：erase(firstIt, lastIt);

3. vector容器内元素的访问

   1. 通过下标访问

   2. 通过迭代器iterator访问

      vector<typename>::iterator it;，这样就得到了迭代器it，可以通过***it来访问vector里的元素**。

      例如：

      #include <iostream>
      #include <vector>
      using namespace std;
      
      int main() {
      	vector<int> vi;
          for(int i = 1; i <= 5; i++)
              vi.push_back(i); //在 vi 的 末尾 添加元素 i
          vector<int>::iterator it = vi.begin(); //vi.begin() 为取 vi 的首元素地址
          for(int i = 0; i < 5; i++)
              cout << *(it + i);
      	return 0;
      }

      可以看出vi[i]和vi.begin() + i等价。在常用的STL容器中，只有vector和string中，才允许使用vi.begin() + 1这种 迭代器加上整数 的写法。

      迭代器还实现了自增和自减的操作，于是还有一种遍历vector中元素的写法：

      //vector 的迭代器不支持 it < vi.end() 写法
      for(vector<int>::iterator it = vi.begin(); it != vi.end(); it++)
          cout << *it;

---

<set>

集合，是一个内部自动递增排序 且 不含重复元素的容器。试题中，可能出现需要去掉重复元素的情况，而且有可能因为这些元素 比较大 或者 类型不是int型 而不能直接开散列表，这种情况下就可以用set来保留元素本身而不考虑个数。虽然上述情况也可以通过再开一个数组进行下标和元素对应来解决，但set提供了更为直观的接口，并且可以实现自动排序，可以在做某些题时减少思维量。

1. set的定义

   set<typename> name;

   和vector相同，如果typename也是一个STL容器，在C++11之前，定义的时候，在符号>>之间要加上空格。如：set<vector<int> > name;，可以理解为两个维都可变长的二维数组。

2. set常用函数

   1. begin()：取 set 的首元素地址

   2. end()：取 set 的 尾后(尾元素地址的下一个)地址（美国人思维比较习惯左闭右开）

   3. size()：获取 set 中的元素个数

   4. clear()：清空 set 中所有元素

   5. insert(typename x)：将 x 插入 set 容器中，并自动递增排序和去重，时间复杂度为$O(logN)$

   6. find(typename value)：返回 set 中对应值为 value 的迭代器

      如：set<int>::iterator it = st.find(2); //在 set 中查找2，返回其迭代器

   7. erase()

      • 删除单个元素

        • 删除迭代器为 it 处的元素：erase(it);

          可以结合find函数使用，如：st.erase(st.find(100))

        • 删除值为 value 的元素：erase(value);

      • 删除 [firstIt, lastIt) 内所有元素：erase(firstIt, lastIt)

3. set容器内元素的访问

   set只能通过 迭代器iterator 访问，因为只有vector和string中，才允许使用vi.begin() + 1这种 迭代器加上整数 的写法，因此只能按如下方式枚举：

   #include <iostream>
   #include <set>
   using namespace std;
   
   int main() {
   	set<int> st;
   	st.insert(3);
       st.insert(5);
       st.insert(2);
       st.insert(3);
       //set 的迭代器不支持 it < vi.end() 写法
   	for(set<int>::iterator it = st.begin(); it != st.end(); it++)
   		cout << *it;
   	return 0;
   }

   输出为：2 3 5，可以发现，set内的元素自动递增排序，且自动去除了重复元素。

4. 延伸

   set中元素是唯一的，如果处理元素不唯一的情况，需要使用multiset。C++11 标准中还增加了unordered_set，以散列代替set内部的红黑树(一种自平衡二叉查找树)实现，使其可以用来去重但不排序的需求，速度比set快得多。

---

<string>

1. string中内容的访问

   1. 通过下标访问

      一般来说，可以直接像字符数组那样去 访问string，如果要读入和输出整个字符串，则只能用cin和cout。那么有办法用printf输出string吗？

      用string的函数c_str()可以将string类型转换为字符数组进行输出。示例：

      string str = "abcd";
      printf("%s\n", str.c_str());

   2. 通过迭代器访问

      有些函数比如insert()与erase()要求以迭代器为参数进行访问。由于string不像其他STL容器那样需要参数，因此可以直接如下定义：

      string::iterator it;
      for(it = str.begin(); it != str.end(); i++)
          cout << *it;

      string和vector一样，允许使用vi.begin() + 1这种 迭代器加上整数 的写法

2. string常用函数

   1. operator+=

      string的加法，可以将两个string直接拼接。

   2. compare operator

      两个string类型可以直接使用 比较符 比较大小，比较规则是按字典序。

   3. begin()：取 string 的首元素地址

   4. end()：取 string 的 尾后(尾元素地址的下一个)地址（美国人思维比较习惯左闭右开）

   5. size()/length()：返回 string 的长度

   6. clear()：清空 string 中的数据

   7. insert

      • 在 pos 位置插入字符串：insert(int pos, string str)，原来位置的字符串顺延。

      • 在 迭代器it 位置插入字符串：

        insert(it, firstIt, lastIt)，firstIt和lastIt为待插字符串的首尾迭代器，用来表示串 [firstIt, lastIt) 将被插在 it 位置上

   8. string::npos：是一个常数，本身值为**-1**，但由于是unsigned_int类型，因此实际上可以认为是最大值。用于作为find函数失配时的返回值。

   9. find()

      • str.find(string str1)：当 str1 是子串时，返回在 str 中第一次出现的位置；如果不是字串，则返回string::npos
      • str.find(string str1, int pos)：从 pos 位置开始匹配 str1

   10. erase()

       • 删除单个元素：erase(it)，目标字符之后的字符字串 前移。
       • 删除一个区间内的所有元素，目标区间之后的字符字串 前移。
         • erase(firstIt, lastIt)，删除 [firstIt, lastIt) 间的所有字符
         • erase(int pos, int length)，pos 是删除的起始位置

   11. substr(int pos, int length)：返回从 pos 位置开始，长度为 length 的字串。

   12. replace()

       • str.replace(int pos, int lenth, str1)：把 str 从 pos 位置开始，长度为 length 的字串替换为 str1，替换位置之后的字符串不变。
       • str.replace(it1, it2, str1)：把 str 的迭代器 [it1, it2) 范围的字串替换为 str1，替换位置之后的字符串不变。

---

<map>

映射，map可以将 任何基本类型(包括STL容器) 映射到 任何基本类型(包括STL容器)。

来看一个情况：判定给的一些数字在某个文件中是否出现过。如果数字很大，那么就不便建立散列的数组。这时，可以通过map，将这些数字当成字符串，建立string至int的映射。

1. map的定义

   map<typename1, typename2> mp;：< >内第一个是 键(key) 的类型，第二个是 值(value) 的类型。map 会以 键 从小到大的顺序自动排序(因为 map 内部是使用红黑树实现的，set也是如此)。map 的一个键只能对应一个值。如果是 int 型映射到 int 型，就相当于普通的 int 型数组。

   如果是字符串到整型的映射，必须使用 string 而不能使用 char数组：map<string, int> mp;，因为数组不能作为键值。

2. map常用函数

   1. begin()：取 map 的首元素地址

   2. end()：取 map 的 尾后(尾元素地址的下一个)地址（美国人思维比较习惯左闭右开）

   3. find(key)：返回 键key的对应映射值 的迭代器

      map<char int>::iterator it = mp.find('b');

   4. erase()

      • 删除单个元素：
        • erase(it)：it 为待删除映射的迭代器
        • erase(key)：key 为待删除映射的键
      • 删除一个区间内的所有映射：erase(firstIt, lastIt)

   5. size()：获取映射的对数

   6. clear()：清空 map 中的所有映射

3. map容器内元素的访问

   1. 通过下标访问

      例如定义为map<char, int> mp的map来说，可以直接使用mp['c']的方式来访问对应的整数。

   2. 通过迭代器访问

      map<typename1, typename2>::iterator it;，因为 map 的每一对映射都有两个 typename，这决定了必须能通过一个 it 来同时访问键和值。事实上，map可以使用it->first来访问键，it->second来访问值。

4. 延伸

   map 的 键和值是唯一的(一对一)，而如果需要一个键对应多个值(一对多)，就只能用multimap。C++11 标准中还增加了unordered_map，以散列代替 map 内部的红黑树实现，使其可以只处理映射而不按key值排序，速度比 map 快得多。

---

<queue>

队列，先进先出。

1. queue的定义

   queue<typename> name;

2. queue常用函数

   1. push(x)：将 x 进行入 队尾
   2. front()、back()：分别获得队首和队尾元素
   3. pop()：令队首元素出队
   4. empty()：检测 queue 是否为空
   5. size()：返回队列内元素个数

3. queue容器内元素的访问

   由于队列是一种先进先出的限制性数据结构，因此只能通过front()来访问队首元素，back()访问队尾元素。

4. queue的常见用途

   当需要实现**广度优先搜索(BFS)**时，可以不用手动实现一个队列，以提高程序的准确性。需要注意的时是，使用front()和pop()函数之前，必须用empty()判断队列是否为空，否则可能因为队空而出现错误。

   延伸：STL的容器中还有两种跟队列有关：

   • 双端队列deque：首尾皆可插入和删除的队列。

   • 优先队列priority_queue：使用堆实现的默认当前队列 最大元素置于队首的容器。

priority_queue

1. priority_queue的定义

   priority_queue<typename> name;

2. priority_queue常用函数

   1. push(x)：将 x入队，时间复杂度为O(logN)
   2. top()：获得队首(即堆顶)元素
   3. pop()：令队首元素(即堆顶)元素出队，时间复杂度为O(logN)
   4. empty()：检测优先队列是否为空
   5. size()：返回优先队列内元素个数

3. priority_queue容器内元素的访问

   只能通过top()函数访问队首元素(优先级最高的元素)。

4. priority_queue内元素优先级的设置

   1. 基本数据类型的优先级设置

      下列两种优先队列的定义是等价的(以int型为例)

      priority_queue<int> q;
      priority_queue<int, vector<int>, less<int> > q;

      • vector<int>：用来承载底层数据结构—堆的容器
      • less<int>：表示数字大的优先级越大(默认优先级)；greater<int>即为数字小的优先级越大。

      因此，如果想让最小的元素放在队首，需要如下定义：

      priority_queue<int, vector<int>, greater<int> > q;

   2. 结构体的优先级设置

      比如定义水果的结构体：

      struct fruit {
      	string name;
          int price;
      }

      现在希望按水果价格高的为优先级高，就需要重载小于号<：

      • 方式一：

        struct fruit {
            string name;
            int price;
            friend bool operator < (fruit f1, fruit f2) {
                return f1.price < f2.price; //水果价格高的为优先级高
                // return f1.price > f2.price; //水果价格低的为优先级高
            }
        };

        其中，friend为友元。bool operator < (fruit f1, fruit f2)对<进行了重载。此时就可以直接定义fruit类型的优先队列，其内部就是以水果价格高的为优先级高：priority_queue<fruit> q;

      • 方式二：将重载的函数写在结构体外

        struct cmp {
            bool operator () (fruit f1, fruit f2) {
                return f1.price > f2.price;
            }
        }
        
        priority_queue<fruit, vector<fruit>, cmp> q;

      即便是基本数据类型或者其他STL容器(如 set)，也可以通过同样的方式来定义优先级。如果结构体内的数据较为庞大，建议使用引用来提高效率：

      friend bool operate < (const fruit &f1, const fruit &f2) {
          reutrn f1.price > f2.price;
      }
      //或如下
      bool operator () (const fruit &f1, const fruit &f2) {
          return f1.price > f2.price;
      }

5. priority_queue的常见用途

   可以解决一些贪心问题，也可以对 Dijkstra 算法进行优化(因为优先队列的本质是堆)。需要注意的时是，使用top()函数之前，必须用empty()判断队列是否为空，否则可能因为队空而出现错误。

---

<stack>

栈

1. stack的定义

   stack<typename> name;

2. stack常用函数

   1. push(x)：将 x 压入栈
   2. top()：获得栈顶元素
   3. pop()：弹出栈顶元素
   4. empty()：检测 stack 是否为空
   5. size()：返回 stack 内元素的个数

3. stack容器内元素的访问

   只能通过top()函数访问栈顶元素。

4. stack的常见用途

   stack 用来模拟实现一些 递归，防止程序对栈内存的限制而导致程序运行出错。对有些题目来说，如果用普通的函数进行递归，一旦递归层数过深，则会导致程序运行崩溃。如果用栈来模拟递归算法的实现，则可以避免这一方面的问题。

---

<utility>

pair

当想要将两个元素绑在一起作为一个合成元素，又不想因此定义结构体时，使用pair可以很方便地作为一个替代品，即 pair 可以看作 内部有两个元素 的结构体。

1. pair的定义

   注意：因为 映射map 的内部实现中涉及 pair，因此添加 map头文件 时会自动添加 utility头文件，因此，记不住 utility头文件，则可以用 map头文件 来代替。

   pair 有两个参数：pair<typeName1, typeName2> name;

   • 如果想在定义 pair 时进行初始化，只需要跟上一个小括号，填写两个初始化元素即可：

     pair <string, int> p("haha", 5);

   • 如果想临时构建一个 pair：

     • pair<string, int>("haha", 5)
     • 使用自带的make_pair函数：make_pair("haha", 5)

2. pair中元素的访问

   pair 中只有两个元素，分别是first和second，只需要按 正常结构体的方式 访问即可。

3. pair常用函数

   比较操作数：

   两个 pair 类型数据可以直接使用比较符比较大小，比较规则是先以first的大小作为标准，first相等时去比较second的大小。

4. pair的常见用途

   • 代替二元结构体及其构造函数，节省编码时间

   • 作为map的键值对来进行插入：

     map<string, int> mp;
     mp.insert(make_pair("heihei", 5));
     mp.insert(pair<string, int>("haha", 10));

---

数组

1. 一维数组初始化

   如果数组没有初始化，数组中每个元素为随机数。一维数组的初始化，未被赋初始值的元素将默认初始化为0，因此，如果想要给整个数组初始化为0，只需第一个元素初始化为0即可。int a[10] = {0};(不适用C语言)

2. 二维数组初始化

   二维数组初始化需要按第一维的顺序，依次用大括号给出第二维初始化的情况，未被赋初始值的元素将默认初始化为0

   int a[4][2] = {{3}, {}, {8, 4}}; //第二行使用大括号跳过
   /**
   数组初始化为：
   3 0
   0 0
   8 4
   0 0
   */

3. 如果数组大小较大(大概$10^6$级别)，需要定义在主函数外(即全局变量)

   否则程序会异常退出（局部变量来自系统栈，允许申请空间较小；全局变量来自静态存储区，允许申请的空间较大）

4. 对数组中每一个元素赋相同的值

   需要#include <cstring>

   void* memset(数组名, 值, sizeof(数组名));

   memset 按字节赋值，即对每个字节赋同样的值，组成int型的4个字节就会被赋成相同的值。故建议只用于赋 0或 -1(0的二进制补码为全0，-1的二进制补码为全1)，不易出错。

   如果要对数组赋其他数字(如 1)，则使用 fill函数（执行速度比 memset 慢）。

---

字符串

字符数组

• 输入

  • #include <cstdio>
    
      - `scanf("%s", str);` 识别**空格或换行**作为输入结束，且**空格或回车符会留在缓冲区**
    
      - `char c = getchar();` 能够读入**空格和换行符**
    
      - `gets(char* str);` 识别**换行**作为输入结束，且**回车符会被舍弃，不在缓冲区**
    
        因此，**scanf一个输入后，如果要使用gets，需要先用 getchar 接收scanf后的空格或换行符**。
      
        另外，**PAT使用C++提交时**，使用`gets()`函数会出现**编译错误**，建议使用C++函数。
      
    - ```c++
      #include <iostream>
      using std::cin;
    
    - `cin >>`
    
    - `cin.getline(数组名称, 数组大小)`
    
      
    char str[100];
    /*
    指定最多读入 9 个字符，超出即报错
    （实际数组最多能存放99个字符，空字符\0 占用一个字符位）
    */
    cin.getline(str, 10);
    

• 输出

  • #include <cstdio>
    
      - `printf(str);` 
      - `putchar(char c);`
      - `puts(char* str);` 输出数组内容后，**紧跟一个换行**
    
    - ```c++
      #include <iostream>
      using std::cout;
    
    - `cout <<`
    

• 字符数组的存放方式

  字符数组的末尾都有一个 空字符\0(即NULL)，表示存放的字符串的结尾。空字符\0 在gets和scanf输入字符串时，会自动添加在输入的字符串后面，并占用一个字符位。puts和printf就是通过识别\0作为字符串的结尾进行输出。

  • 空字符\0占用一个字符位，因此字符数组的长度一定要比实际存储字符串的长度 至少多1。
  • 如果使用getchar()输入字符串，一定要在每个字符串后加入\0，否则printf和puts输出字符串会因无法识别字符串末尾而输出一大堆乱码。

---

C++ 的标准库类 string

#include <string>
using std::string;

若引用了<iostream>头文件，创建string对象时，无须引用<string>，因为<iostream>有对std::string的间接引用。但时要对string对象运用相关的函数操作，仍须引用<string>。

• 输入一整行

  getline(cin, str)

• 比较字符串大小

  • str1.compare(str2)

    按字典顺序(顺序越靠后，越大)，返回两个字符串大小的比较

---

<cstring>

1. strlen(str)

   得到字符数组中第一个\0前 的字符个数

2. strcmp(str1, str2)

   按字典顺序(顺序越靠后，越大)，返回两个字符串大小的比较结果：

   • str1 < str2，返回一个负整数(不同编译器处理不同，不一定是 -1)
   • str1 == str2，返回一个0
   • str1 > str2，返回一个正整数(不同编译器处理不同，不一定是 +1)

3. strcpy(str1, str2)

   把 str2 复制给 str1，包括结束符\0

4. strcat(str1, str2)

   把 str2 拼接到 str1 后面

---

字符串与数字的相互转换

C语言

方法一：

#include <cstdlib>

字符串 转为 数字

• atoi(str)：将字符串转为 int型
• atol(str)：将字符串转为 long long型
• atof(str)：将字符串转为 double型

---

方法二： sscanf 与 sprintf

如果想从屏幕输入 int型变量n 并将 n 输出到屏幕：

scanf("%d", &n);
printf("%d", n);
//其实可以表示成如下
scanf(screen, "%d", &n);
printf(screen, "%d", n);

sscanf与sprintf的格式如出一辙，只是把screen换成了字符数组

sscanf(str, "%d", &n); //将字符数组str中的内容以"%d"格式写到n中
sprintf(str, "%d", n); //把n以"%d"的格式写到str数组中

例：

#include <cstdio>

int main() {
    int n;
    double db;
    char str[100] = "2048:3.14,hello", str2[100];
    /*
    从字符串读取格式化输入
    使得 n = 2048, db = 3.14, str2 = hello
    */
    sscanf(str, "%d:%lf,%s", &n, &db, str2);
    n = 12;
    db = 3.1415;
    str2[100] = "good";
    /*
    发送格式化输出到字符串
    使得 str = "12:3.14,good"
    */
    sprintf(str, "%d:%.2f,%s", n, db, str2);
    return 0;
}

---

C++：

数字 转为 字符串

#include <string>
using namespace std;

string str = to_string(num);
len = str.length();

---

数组作为函数参数

• 参数中数组的第一维不需要填写长度(如果是二维数组，第二维需要填写长度)
• 在函数中对数组元素的修改 等同于 对原数组元素的修改(与普通局部变量不同)

例：

#include <cstdio>

void change(int a[], int b[][5]) {//参数数组 第一维不需要填写长度，第二维需要填写长度
    a[0] = 1;
    a[1] = 3;
    a[2] = 5;
    b[0][0] = 1;
}

int main() {
    int a[3] = {0}; //不适用C语言
    int b[5][5] = {0}; //不适用C语言
    change(a, b);
    for (int i = 0; i < 3; i++) {
        printf("%d\n", a[i]);
    }
    /*
    输出结果为：
    1
    3
    5
    */
    return 0;
}

• 数组不允许作为返回类型出现，想要返回数组，只能通过参数返回

---

指针

• C语言习惯于把*放在变量名之前：int *p;(声明多个指针时，易统一)

• C++习惯把*放在数据类型之后：int* p;

• 地址赋给p而不是*p

  int a;
  int* p;
  p = &a; //等价于 int* p = &a;

• 指针的加减法

  • 两个指针相减，得到两个地址的距离
  • p + 1指 p所指的int型变量 的下一个int型变量地址
  • 指针支持自增和自减操作

---

指针变量作为函数参数

例子：交换两个数

只有在获取地址的情况下对元素进行操作，才能真正修改变量

#include <cstdio>

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main() {
    int a = 1, b = 2;
    int *p1 = &a, *p2 = &b;
    swap(p1, p2);
    return 0;
}

错误写法：

void swap1(int* a, int* b) {
    int* tmp;
    *tmp = *a;
    *a = *b;
    *b = *tmp;   
}
/*
tmp未初始化，存放的地址很大概率指向系统工作区间，不能修改，故后续报错
初始化tmp即可
*/
void swap2(int* a, int* b) {
    int x;
    int* tmp = &x;
    *a = *b;
    *b = *tmp;
}

---

引用

引用的含义

引用是C++的语法，在编程时极为实用。如果要修改传入函数的参数，且不使用指针，可以通过C++的引用。引用不产生副本，只是给原变量起个别名。

引用的方法：在函数的参数变量名前加个&即可。要将**引用&与取地址运算符&**区分开来，引用并不是取地址的意思。

#include <cstdio>

void change(int &x) {
    x = 1;
}

int main() {
    int x = 10;
    change(x);
    printf("%d\n", x); //输出1
    return 0;
}

指针的引用

例子：交换两个数

//错误写法
void swap(int* a, int* b) {
    int* tmp = a;
    a = b; //交换的地址 是 值传递，不会修改原指针的地址
    b = tmp;
}

通过引用实现交换

#include <cstdio>

void  swap(int* &a, int* &b) { //通过引用实现交换
    int* tmp = a;
    a = b;
    b = tmp;
}

int main() {
    int a = 1, b = 2;
    int *p1 = &a, *p2 = &b;
    swap(p1, p2); //不能写成 swap(&a, &b);
    return 0;
}

引用是产生变量的别名，常量不可使用引用。故上述

swap(p1, p2); //不能写成 swap(&a, &b);

---

结构体（struct）的使用

访问结构体内的元素

假设p是一个指向结构的指针，可以用**p->结构成员的形式（等价于(*p).结构成员）**，引用相应的结构成员。

---

申请动态内存空间

如需要定义链表的结点时。

C语言有malloc和free函数用于内存的申请和释放，C++有new和delete运算符用于内存的申请和释放。推荐使用C++进行内存的申请和释放(用法更简洁)。

• 申请内存空间 — new运算符：

  使用new + 类型名即可分配一块该类型的内存空间，返回申请的同变量类型的指针：typename* p = new typename;

  示例：

  int* p = new int;
  node* p = new node;

  通常情况下，内存空间的申请不会失败。失败一般发生在使用new申请了较大的动态数组，如：int* p = new int[1000000];。申请失败会发生异常。

• 释放内存 — delete运算符：

  以需要释放的内存空间的指针变量为参数：delete(p);，执行之后，指针变量p没有消失，只是指向了空地址NULL。