字符串与数组

1. 数组重复元素

数组 a[N] 中存放了 1 至 N - 1 个数，其中某个数重复了一次。求找出重复元素，时间复杂度必须为 O（N）。

---

• 异或法
• 和差法
• 哈希表

参考：数组重复元素求值

2. 简述数组和指针的区别

指针	数组
保存数据的地址	保存数据
间接访问数据	直接访问数据
通常用于动态数据结构	通常用于存储固定数目类型相同的元素
相关操作 new，delete 等	隐式分配和删除

还要提醒一点的就是：

char a[] = "abcdefg";  //数组内容能修改(字符数组)
char *p = "abcdefg";  //内容不能修改（字符串常量）

在 C/C++ 中，初始化指针时所创建的字符串，被定义为只读 。

3. 数组的偏移

运行下面程序，求输出结果？

#include <iostream>

using namespace std;

int main()
{
    int a[5] = {1, 2, 3, 4, 5};
    int* ptr = (int*)(&a + 1);
    cout << *(a + 1) << ", " << *(ptr - 1);
    return 0;
} 

---

输出结果为：2, 5

本题考察的是 a 与 &a 的区别。

&a+1 不是 首地址+1， 系统会认为加上了一个 a[ ] 的偏移，是偏移了一个数组的大小。因为 &a 是数组指针，其类型为 int(*)[5]；而 指针+1 要根据指针类型加上一定的值，不同类型的指针+1 之后增加的大小不同。

a 是长度为 5 的 int 数组指针，所以要加 5 * sizeof(int) ，ptr 实际上是 a[5] 。但是 ptr 和 (&a + 1) 类型不一样，所以 ptr - 1 只会减去 sizeof(int*) 。

a，&a 的地址是一样的，但意义不同，&a 是对象（数组）首地址，a 是数组首地址，也就是 a[0] 的地址，a + 1 是数组下一元素的地址，即 a[1] ，故输出结果为 2 ；&a + 1 是下一个对象的地址，即 a[5] ，所以 ptr - 1
的值为 a[4] ，故输出结果为 5 。

4. 多维数组的输出

int a[2][2][3] = {{{1, 6, 3}, {5, 4, 15}}, {{3, 5, 33}, {23, 12, 7}}};
for (int i = 0; i < 12; i++)
    cout << ______ << endl;

在空格处填上合适的语句，顺序打印出 a 中的数字。

---

a[i / 6][(i / 3) % 2][i % 3]

第一维，前六次循环都取 0 ，后六次都取 1 ，于是 i / 6 可以满足要求；第二维，前三次取 0 ，再三次取 1 ，再三次取 0 ，再三次取 1 ，用量化的思想，i /3 把 12 个数字分为 4 组，每组 3 个，量化为 0、1、2、3，为了得到 0、1、0、1，这里需要取余，于是有 (i / 3) % 2 ；第三维需要（0、1、2；0、1、2；0、1、2；0、1、2），于是有 i % 3 。

5. 字符数组的输入

输入 5 个国家的英文名字，找到并输出英文名字的首字母按字母顺序排在最前面的那个国家的名字。

---

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    char a[5][30];
    char c[30];
    int i;
    for (i = 0; i < 5; i++)
        cin.getline(a[i], 30, '\n');
    strcpy(c, a[0]); 
    for (i = 5; i > 1; i--)
        if(strcmp(c, a[i]) > 0)
            strcpy(c, a[i]);
    cout << c << endl;
    return 0;
}

6. 字符串相关函数

• strcpy(a, b)：把 b 中的字符串复制到 a 中
  注意：
  （1）a 的长度必须大于等于 b；
  （2）a 必须是数组名，b 可以是数组名也可以是字符串；
  （3）复制操作执行内容包括 '\0' ；
  （4）复制操作可以复制部分数组长度（例如：strcpy(a, b[1], 5)）。
• strcmp(a, b)：比较 a，b 字符串中对应的字符
  注意：
  （1）若参数 a 和 b 字符串相同则返回 0 ； a 若大于 b 则返回大于 0 的值；a 若小于 b 则返回小于 0 的值；
  （2）区分大小写。
• strcat(a, b)：把 b 字符串连接到 a 后面
  注意：
  （1）a 数组必须要足够大，至少满足同时容纳两个字符串的长度；
  （2）连接操作时，a 数组原有的 '\0' 被删除。
• strlen：长度计算操作
• strlwr：大写变小写
• strupr：小写变大写

7. strcpy 函数和 memcpy 函数有什么区别？它们各自使用时应该注意什么问题？

• 区别：strcpy 函数操作的对象是字符串，完成从源字符串到目的字符串的复制功能；memcpy 函数顾名思义就是内存复制，实现将一个内存块的内容复制到另一个内存块的功能。
• 要注意的问题：对于字符串复制来说，两者都可以实现；但是对于非字符串类的数据复制来说，就只能用 memcpy 函数了。