第3章数组与字符串.ppt

字符数组 习题3-8 手机键盘（keyboard） 输入一个由小写字母组成的英文单词，输出用手机的默认英文输入法的敲键序列。例如要打出pig这个单词，需要按1次p，3次i，（稍作停顿后）1次g，记为p1i3g1。 第三讲：数组与字符串 主讲：高放 哈尔滨理工大学集训队 本讲要点 数组 字符数组 小结与习题 数组 下面从一个问题出发，说明一下为何使用数组。 问题：读入一些整数，逆序输出到一行中，整数之间用空格格开。已知整数不超过100个。 【分析】 首先通过循环来读取100个整数的输入，然后把每个数都存下来，存放在数组中，最后输出。 #define是 “宏定义”，它是在编译的时候编译器执行的命令。作用是替换指定的字符串。 puts(字符串“); 相当与 printf(字符串\n); 【不支持占位符】 数组 int a[MAXN] 表示声明了一个包含 MAXN 个 int 形 变量的数组。 【注意，MAXN必须是常数】 a[0]表示数组中下标为0的变量,a[1]表示下标为1. 注意：a[100]的数组，下标范围是0~99 数组 注意学习上面这个程序中的输出技巧。 因为输出的数用空格隔开，而末尾不应该有空格，所以需要用一条判断来输出。 当然，这不是唯一的实现方式。还有很多的方式可以实现相同的功能。 另外，大数组，要开成全局变量（就是不在任何函数里面），不然容易一运行就崩溃。【具体原因在讲到递归的时候就明白了】 数组 声明方式： 类型 数组名[数组大小]; 引用方式： 数组名[下标]。 注意点： 数组大小必须为常量。 引用数组元素时，其下标可以是变量。 下标的范围为 0 ~ 数组大小-1。 数组不能像变量一样直接赋值。只能对数组中的变量赋值。 实际工程中，为了节省内存，数组的空间往往是按需要申请。这时候可以用 new 实现。但竞赛中用不到。 数组 例3-1 开灯问题。 有n盏灯，编号为1～n，第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯被打开，开着灯将被关闭），依此类推。一共有k个人，问最后有哪些灯开着？ 输入：n和k，输出开着的灯编号。k≤n≤1000。 样例输入：7 3 样例输出：1 5 6 7 【分析】 用a[1],a[2],…,a[n]表示编号为1,2,3,…,n的灯是否开着，模拟这些操作即可。 memset, string.h !a[j] % 数组 补充：memset函数原型如下： void *memset(void *buffer, char c, int count); 功能：把buffer所指内存区域的前count个字节设置成字符c，第三个参数指的是字节的个数，返回指向buffer的指针，在程序中需包含头文件：#include string.h。由memset函数的头文件可以知道，其主要是对字符数组进行设置，当然也可以对数组进行初始赋值（一般是0,-1）。 数组 有一个技巧是在输出：为了避免输出多余空格，设置了一个标志变量first，可以表示当前要输出的变量是否为第一个。第一个变量前不应有空格，但其他都有。 数组 例3-2 蛇形填数。 在n*n方阵里填入1,2,…,n*n，要求填成蛇形。例如n=4时方阵为 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 每个数字占3个位置，不足4位的在右边用空格补齐。n≤8。 数组 【分析】 与数学的矩阵相比，可以用一个所谓的二维数组来存储题目中的方阵。只需声明一个int a[MAXN][MAXN]，就可以获得一个大小为MAXN×MAXN的方阵。在声明时，两维的大小不必相同。 数组 提示3-4：用int a[MAXN][MAXM]生成一个整型的二维数组，其中MAXN和MAXM不必相等。这个数组共有MAXN×MAXM个元素，分别为 a[0][0],a[0][1],…,a[0][MAXM-1], a[1][0],a[1][1],…,a[1][MAXM-1], …, a[MAXN-1][0],a[MAXN-1][1],…, a[MAXN-1][MAXM-1]。 数组 假设从1开始依次填这写。设“笔”的坐标为(x,y)，则一开始x=0，y=n-1，即第0行第n-1列（注意行列的范围是0～n-1，没有第n列）。“笔”的移动轨迹是：下、下、下、左、左、左、上、上、上、右、右、下、下、左、上。总之，先是下，到不能填了为止，然后是左，接着是上，最后是右。“不能填”是指再走就出界（例如4→5）或者再走就要走到