电子教案-新模板第6章-新

第6章多维批量数据处理,一维数组一维数组有关的常见算法二维数组字符数组字符串处理函数引例的实现,【本章要点】,6.1引例,6.1.1问题描述大家都去超市，超市里经营的商品种类成百上千，很多时候我们会发现收银台处聚集着很多人等待结账，想象一下如果没有一个简单计算机模拟程序来实现结账，超市是什么样的，那么，如果让大家来做一个这样的模拟程序，大家会如何定义这些商品的数据呢？,6.1引例,6.1.1问题描述现在看这样一个简单模拟程序，它实现结帐和打印清单的操作，为简化问题，假设超市里共有10种商品，所有商品的价格列于表6-1中，商品的条形码用商品编号代替。,6.1引例,6.1.1问题描述表6-1商品信息,6.1引例,6.1.1问题描述假如某顾客买了三盒牛奶、两条毛巾和一块香皂。编程打印下面的购物清单：,6.1.2问题分析对于本问题，要考虑以下三步：1）把超市中销售的所有商品信息存储在计算机中；2）根据顾客购买的商品编号和数量计算总价；3）最后按照购物清单的格式把这些信息依次打印。根据问题描述可得，需要保存的商品信息有：1）10类商品的编号与单价、名称、计价单位；2）顾客购买商品的编号和购买数量。而存取、计算、打印这数量繁多的信息，就需要掌握今天所要学到的数组知识。,6.1引例,我们都知道其实生活中有很多类型相同、操作也相同的数据，就像超市中每种商品的价格。如果为每种商品都单独定义每个变量，则需要大量不同的标识符作变量名，而且这些变量在内存中也是随机存储的。如果这样定义程序将不能很好地管理这些变量。为了解决这种问题，C语言中运用了数组来存储大批同类型数据。,6.2一维数组,那么什么是数组呢？数组是由若干个相同类型的数据项组成的有序数据集合，在内存中占有一段连续的存储空间，数组名代表数组的起始地址。数组中的数据项称为数组元素，可以用数组名和不同的下标唯一确定数组中的每个元素。数组可分为一维数组和多维数组。下面我们就来了解一维数组,6.2一维数组,6.2.1一维数组的定义在C语言中，数组必须先定义后使用。定义数组的实质是为该数组分配连续的存储单元。定义一维数组的格式是：数据类型数组名常量表达式；,6.2一维数组,确定了数组中每个元素的类型。可以是基本数据类型，也可以是构造数据类型。,数组起始地址（即首元素的地址），为一个地址常量。数组名应该遵循C语言标识符命名规则。,指定数组的长度，即数组中元素的个数。,6.2.1一维数组的定义例如，下面的语句：intarray10;定义了一个名为array的数组，包含10个int型元素：array0array9，可用于存储10个int型数据。说明：1.数组元素的下标从0开始，最大下标为数组长度减一。2.数组可以看成是相同类型变量的集合，每个数组元素的作用相当于变量。3.数组定义中不能用变量表示数组长度。4.数组一经定义，其长度在程序中不可改变。,6.2一维数组,例如，下面的程序段中对数组的定义是正确的：#defineSIZE10intarray1SIZE,arraySIZE*5,array32*6;而下面的程序段定义数组的方式是错误的：intm=10;intam;这里试图用变量确定数组长度，是不正确的。,6.2.2一维数组的初始化刚定义的数组中每个数组元素的值并未确定。C语言允许在定义数组的同时给数组元素赋初值，称为初始化。一维数组初始化的格式如下：数据类型数组名常量表达式=初值表；其中，初值表列出了各数组元素的值，它们之间用逗号隔开。一维数组的初始化有以下几种情况：,6.2一维数组,6.2.2一维数组的初始化1.数组元素全部初始化例如下面的语句：inta5=0,1,2,3,4;定义的一维整型数组a中，元素a0a4的初值依次为0,1,2,3,4。,6.2一维数组,6.2.2一维数组的初始化2.数组元素全部初始化，省略数组长度如果对数组中的全部元素进行初始化，则可省略数组长度的定义，而由初值表中元素的个数自动确定。下面两个数组的定义是等价的：inta=0,1,2,3,4;inta5=0,1,2,3,4;,6.2一维数组,6.2.2一维数组的初始化3.数组元素部分初始化语言中可以只给一部分元素赋初值。例如：inta5=0,1,2;这里定义了长度为5的一维整型数组a，并且只对数组中的前三个数组元素进行了初始化，C语言会自动将数组a中的后两个数组元素赋值为0。由此，若要对数组中全部数组元素初始化为0，可以使用以下定义语句：inta5=0;,6.2一维数组,也就是说：inta5=0,1,2;inta5=0,1,2,0,0等价,6.2.3数组元素的引用C语言中除了字符数组外均不能整体引用数组。也就是说，不能一次性地读写数组中的所有元素，而只能单独引用某个元素。对数组元素的引用形式为：数组名下标方括号中的下标必须是一个整型常量、整型变量或整型表达式。,6.2一维数组,6.2.3数组元素的引用例如，若以下数组定义语句：inta5=5,6,7,8,9;则数组中的五个元素分别是a0、a1、a2、a3、a4，它们的值分别为5、6、7、8、9。数组a在内存中的存储情况如图6-1一维数组的存储结构所示。,6.2一维数组,6.2.3数组元素的引用,6.2一维数组,若在程序中访问a5则会导致下标越界，但系统并不会报错，而是访问a4后面一个整型存储空间中存放的数据，如果不慎修改了该值，则有可能造成严重后果。因此，一定要注意避免下标越界的错误。,6.2.3数组元素的引用C语言对数组元素的赋值和其他操作与对一般变量的操作类似。例如：inta5;a0=1;a1=1;a2=a1+a0;a3=a2+a1;a4=a3+a2;,6.2一维数组,这个程序段定义了一个长度为5的整型数组，分别用五条语句对数组元素进行了赋值，其中对后三个元素的赋值用到了前面的数组元素。该程序段执行后，a数组中的5个元素分别是a0=1、a1=1、a2=2、a3=3、a4=5。,6.2.3数组元素的引用C语言中由于数组元素的下标可以是整型表达式，因此上面程序段的功能可以用循环语句实现：inta5,i;a0=1;a1=1;for(i=2;ia4，如果数组中存在66，则该数一定位于a5a9中。查找范围缩小了一半。接下来再在a5a9之间比较中间的数（5+9）/2，即a7。66正好与a7相等，此时查找成功。,6.2一维数组,6.2.4数组元素的输入与输出算法设计：仿照上述过程，可得升序数组data中查找数据x的如下算法思想。设数组中查找范围的最小下标为low，最大下标为high，则中间元素的下标为mid=(low+high)/2。将datamid与x进行比较：1.若datamid与x相等，则查找成功，输出其下标mid；2.若datamidx，则查找区间缩小到数组的前半部分，即high=mid-1；,6.2一维数组,6.2.4数组元素的输入与输出3.若datamidx，则查找区间缩小到数组的后半部分，即low=mid+1。重复上述过程，直到不满足条件low=high，说明x不在数组data中，查找失败。相应的算法流程图参见图6-10。,6.2一维数组,6.2.4数组元素的输入与输出图6-10折半查找算法流程图,6.2一维数组,6.2.4数组元素的输入与输出程序设计例6-4源代码运行结果：程序运行时若输入：66，结果如图6-11所示。,6.2一维数组,想一想：顺序查找法的程序设计是怎样的？,6.2.4数组元素的输入与输出一般来说，查找问题中算法最简单的是顺序查找法，即按顺序依次查找；最快的查找是折半查找法，即总是和某范围内最中间的数据元素比较，确定被找的数据位于中间元素的左侧还是右侧，直接缩小一半的查找范围。但是折半查找法要求数组必须是有序的，而顺序查找法对此没有要求。,6.2一维数组,一维数组常用来表示数学中的向量、数据的有限序列等（如商品的价格）。若要同时存储商品的编号和数量两组信息，用两个一维数组分别存储并不是最好的选择，一般使用二维数组进行存储。C语言中可以定义二维数组甚至多维数组。二维数组常用来表示和处理矩阵、由行列组成的表格等。表示二维数组中的一个元素需要两个下标。,6.3二维数组,6.3.1二维数组的定义定义一个二维数组的格式为：数据类型数组名常量表达式1常量表达式2；其中，常量表达式1确定了二维数组中第一维的长度，常量表达式2确定了第二维的长度。例如：下面的语句：,6.3二维数组,6.3.1二维数组的定义intmatrix34;定义了一个3行4列的二维数组matrix。该二维数组在逻辑上可以看成是3行4列的表格或矩阵，如图6-12所示。其存储结构如图6-13所示，C语言编译系统为其开辟了一个具有12个int型存储空间的连续的存储区域。二维数组元素按行的顺序依次存放，即先顺序存放第一行的元素，再顺序存放第二行的元素，以此类推。,6.3二维数组,6.3.1二维数组的定义图6-12二维数组的逻辑结构图6-13二维数组的存储结构,6.3二维数组,返回,6.3.2二维数组的初始化二维数组初始化的格式如下：数据类型数组名常量表达式1常量表达式2=初值表；一般在实际应用中有以下4种情况。1.对数组元素全部初始化例如：inta34=1,2,3,4,5,6,7,8,9,10,11,12;,6.3二维数组,6.3.2二维数组的初始化该语句定义了二维数组a，并将各个元素初始化为：a00=1a01=2a02=3a03=4a10=5a11=6a12=7a13=8a20=9a21=10a22=11a23=12若按数组元素全部初始化，则数组声明语句中第一维的长度3可以省略，即该语句和下面的语句实现的功能是相同的。inta4=1,2,3,4,5,6,7,8,9,10,11,12;,6.3二维数组,6.3.2二维数组的初始化2.按行全部初始化对数组元素初始化，也可以按行进行，即在初值表中将每行数组元素的初值用一个花括号括起来。例如：inta34=1,2,3,4,5,6,7,8,9,10,11,12;同样地，数组声明语句中第一维的长度3可以省略，即可用下面的语句定义数组a：inta4=1,2,3,4,5,6,7,8,9,10,11,12;,6.3二维数组,6.3.2二维数组的初始化3.对数组元素部分初始化对数组中部分元素进行初始化，数组中其它数组元素会自动初始化为0。例如：inta34=1,2,3数组中各个元素分别为a00=1、a01=2、a02=3，而其余的数组元素全为0，即a03=0、a10=0、a11=0、a12=0、a13=0、a20=0、a21=0、a22=0、a23=0。,6.3二维数组,6.3.2二维数组的初始化4.按行部分初始化例如：inta34=1,2,5,9,10,11;在该语句中，用花括号将每行中的初值括在一起，但是每行中只对部分数组元素进行了初始化，其余的数组元素会自动初始化为0。该语句定义了二维数组a，且数组元素分别是：a00=1a01=2a02=0a03=0a10=5a11=0a12=0a13=0a20=9a21=10a22=11a23=0,6.3二维数组,6.3.2二维数组的初始化若在按行部分初始化时，对每一行都有数组元素初值，那么二维数组中第一维的长度可以省略。例如：inta4=1,2,5,9,10,11;该语句定义的二维数组a的第一维长度是3。而下面的语句定义的二维数组a的第一维长度是2：inta4=1,2,5;在这种初始化形式中，第二维的长度不能省略。,6.3二维数组,6.3.3二维数组元素的引用二维数组元素的引用形式为：数组名下标1下标2与一维数组相同，二维数组中每一维下标都有上、下界，下界为0，上界为数组该维的长度减1.,6.3二维数组,6.3.3二维数组元素的引用例6-5输出一个3行4列的矩阵及其所有元素的和。问题分析：为了方便打印该矩阵并求所有元素的和，可以采用一个二维数组存储该矩阵。设该二维数组为a，数组中元素的逻辑结构可参见图6-12，假设变量i和j分别表示该数组元素的行下标和列下标，则i的取值范围为02、j的取值范围为03。以i、j为循环变量，采用二重循环可以输入每个元素的值并求和。同样输出该二维数组也需要二重循环，而且在输出数组元素时，每输出一行中的4个元素后应输出一个换行符。,6.3二维数组,6.3.3二维数组元素的引用算法设计：根据上述分析，可将问题的实现过程分为3步。1.采用二重循环从键盘输入矩阵中各个元素的值，保存在二维数组中，并直接对各数组元素进行累加。2.采用二重循环按格式输出矩阵中各行各列元素。3.输出矩阵中所有元素的和。,6.3二维数组,6.3.3二维数组元素的引用程序设计例6-5源代码运行结果：程序运行时若输入：695135288369，结果如图6-14所示,6.3二维数组,6.3.3二维数组元素的引用例6-6杨辉三角形如下，请计算并输出前10行。11112113311464115101051,6.3二维数组,6.3.3二维数组元素的引用问题分析：杨辉三角形是(a+b)的n次幂展开后各项的系数。杨辉三角形有如下特点：1.第一行只有一个数1，以下各行比上一行多一个数。2.每行中的第一个数是1。3.每行中的最后一个数是1，即矩阵对角线元素为1。4.从第三行起，除第一个数和最后一个数外，其余各数是上一行同列的数和上一行前一列的数之和。,6.3二维数组,6.3.3二维数组元素的引用显然，杨辉三角形可以用一个二维数组来存储，设此数组为Yang1010，那么1.Yangi0为每行中的第一个数，其值应为1，即Yangi0=1。2.Yangii为每行中的对角线元素，其值应为1，即Yangii=1。3.从第三行起，除了Yangi0和Yangii，其余Yangij=Yangi-1j+Yangi-1j-1。,6.3二维数组,6.3.3二维数组元素的引用算法设计：基于以上分析，可采用二重循环打印Yang数组。程序设计例6-6源代码运行结果：程序运行后的结果如图6-15所示。,6.3二维数组,6.3.3二维数组元素的引用例6-7输入一个N*N的方阵，输出其转置矩阵。问题分析：若N3，且3*3的矩阵的内容如下：123147456则该矩阵转置后为：258789369若此矩阵用二维数组a33保存，则实现转置的过程是：1.对于第0行，将a01和a10交换，将a02和a20交换；,6.3二维数组,6.3.3二维数组元素的引用2.对于第1行，将a12和a21交换。一般地，设i、j分别为二维数组aNN的行下标和列下标，则i、j的取值范围为0N-1,实现转置的过程是：对所有下标满足ij的aij，将其与aji互换。,6.3二维数组,6.3.3二维数组元素的引用算法设计：基于以上分析，需分别采用个二重循环实现二维数组的输入、转置、输出。需要注意的是，实现矩阵转置的二重循环中，外循环变量i取值只需从0取到N-2，步长为1，而内循环变量的取值范围应为i+1N-1，步长为1。,6.3二维数组,6.3.3二维数组元素的引用程序设计例6-7源代码运行结果：程序运行时输入123456789，结果如图6-16所示。,6.3二维数组,想一想：实现转置的二重循环中i、j的取值范围是如何确定的。,6.3.3二维数组元素的引用程序设计例6-8源代码运行结果：程序运行时若输入：abcdefghi，结果如图6-18所示,6.3二维数组,字符数组用于存储字符型数据，数组中每个元素存放一个字符。可以对字符数组中的字符逐个进行输入、输出、赋值、引用等操作。另外，语言中并没有专门的保存字符串的变量，而是借助字符数组来存储字符串内的每个字符。,6.4字符数组,6.4.1字符数组的定义定义一维字符数组的格式为：char字符数组名常量表达式；例如，下面的语句：charstr120;定义了一维字符数组str1，可以存储20个字符或者长度19的字符串。,6.4字符数组,6.4.1字符数组的定义定义二维字符数组的格式为：char字符数组名常量表达式1常量表达式2；例如，下面的语句：charstr2520;定义了二维字符数组str2，可以存储20个长度的字符串或者100个字符。,6.4字符数组,6.4.2字符数组的初始化语言允许在定义字符数组的同时进行初始化。有两种初始化的方法：1.为数组各元素逐个指定初值。例如，下面的语句：charstr15=C,h,i,n,a;定义了长度为5的字符数组str1，str10str14中分别存放C、h、i、n、a。,6.4字符数组,6.4.2字符数组的初始化2.采用字符串常量对字符数组初始化，C编译程序会将字符串常量中的字符依次赋给字符数组的各个元素，并自动在尾部加上0。例如语句：charstr26=China;定义了长度为6的字符数组str2，str20str24中分别存放字符C、h、i、n、a，str25中存放0。各个元素的存储情况如图6-17所示。,6.4字符数组,6.4.2字符数组的初始化说明：1.在用字符串常量对字符数组初始化时可以省略花括号。charstr26=“China”;/*此语句是正确的*/2.字符数组初始化时可以缺省数组长度。charstr1=C,h,i,n,a;/*字符数组长度为5*/charstr2=“China”;/*此处定义的字符数组长度为6，str5中存放0*/,6.4字符数组,6.4.2字符数组的初始化说明：3.不允许用字符串常量对已定义的字符数组整体赋值。例如，下面的程序段中对str的赋值是错误的：charstr6;str=China;/*错误的赋值语句*/原因是str为表示数组首地址的常量，对常量赋值没有意义。,6.4字符数组,6.4.2字符数组的初始化4.可以对字符数组中部分元素初始化，这时未被赋初值的元素自动取0。charstr20=C,h,i,n,a;或charstr20=China;定义的数组str中str0strs4分别为C,h,i,n,a，后面其它元素的值皆为0。5.可以对二维字符数组初始化。charweekday710=Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturday;,6.4字符数组,6.4.3字符数组的输入与输出对字符数组可以逐个元素输入/输出，也可以对字符数组整体进行输入/输出。1.用scanf()函数/printf()函数对单个字符数组元素输入/输出：在scanf()函数和printf()函数中用格式控制符%c可以对单个字符数组元素进行输入输出。例6-8用格式输入输出函数对逐个输入字符数组元素。,6.4字符数组,6.4.3字符数组的输入与输出2.用scanf()函数/printf()函数对字符数组整体输入/输出在scanf()和printf()中用格式控制符%s可以对字符数组整体进行输入输出。输入的字符串用空格符、制表符或换行符表示输入结束。例6-9用格式输入输出函数对字符数组整体进行输入输出，分析下面程序的运行结果。,6.4字符数组,6.4.3字符数组的输入与输出程序设计例6-9源代码运行结果：程序运行时若输入：abcdefghi，结果如图6-19所示从结果可以看出，对于输入的字符串，scanf()函数并没有全部读入数组c中，而是遇到空格即停止键盘读取。,6.4字符数组,6.4.3字符数组的输入与输出3.用gets()函数/puts()函数对字符数组整体输入/输出字符串输入函数gets()的格式为：gets(str)；其中str可以是字符数组名或字符串指针变量名。字符串指针变量将在第8章中介绍。gets()函数的作用是从终端键盘读入字符串，该字符串中可以包括空格符或制表符，字符串以回车键表示输入结束。这是与scanf()函数不同之处。,6.4字符数组,6.4.3字符数组的输入与输出例如，对于下面的程序段：charsentence20;gets(sentence);若在运行时输入：IloveChina!则会在字符数组sentence中读入14个字符，后面的6个字符是不确定的。其具体内容如图6-20所示，其中“”表示不确定的值。,6.4字符数组,扫一扫：gets（）函数功能小视频,6.4.3字符数组的输入与输出字符串输出函数puts()的格式为：puts(str)puts()函数的作用是将字符串输出，当遇到字符串结束标志0时输出结束，并且在输出后自动换行。charsentence20=IloveChina!;puts(sentence);puts(sentence);会输出如下信息：IloveChina!IloveChina!,6.4字符数组,6.4.4字符串处理函数在C语言的标准函数库中，提供了专门的用于处理字符串的函数，使用这些函数需要包含头文件string.h。本节只介绍常用的字符串处理函数，其他的字符串处理函数可参考附录。1.字符串长度函数strlen()字符串长度函数的调用格式为：strlen(str)str可以是字符数组名、字符串指针变量名或字符串常量。strlen()函数的作用是返回字符串str的有效长度，不包括字符0。,6.4字符数组,6.4.4字符串处理函数例如，下面程序段的运行结果为13。charsentence20=IloveChina!;printf(%dn,strlen(sentence);2.字符串连接函数strcat()字符串连接函数的调用格式为：strcat(str1,str2)其中，str1可以是字符数组名或字符串指针变量名；str2可以是字符数组名、字符串指针变量名或字符串常量。,6.4字符数组,6.4.4字符串处理函数strcat()函数的作用是将字符串str2连接在字符串str1后面，生成一个新的字符串str1。该字符中只有最后一个字符串结束标志0，原str1结尾的0被覆盖。函数返回字符串str1的首地址。需要注意的是，str1不允许是字符串常量，且其长度必须足够大，以便字符串后面的剩余存储空间能够容纳str2的所有内容，否则会因越界产生错误。,6.4字符数组,6.4.4字符串处理函数例6-10分析程序运行结果。程序设计例6-10源代码运行结果：结果如图6-21所示从结果可以看出strcat()函数执行后str1内容的变化情况。,6.4字符数组,6.4.4字符串处理函数3.字符串复制函数strcpy()字符串复制函数的调用格式为：strcpy(str1,str2)其中，str1可以是字符数组名或字符串指针变量名，str2可以是字符数组名、字符串指针变量名或字符串常量。strcpy()函数的作用是将字符串str2的内容连同字符串结束标志0一起复制到str1中。函数返回值为字符串str1的首地址。,6.4字符数组,6.4.4字符串处理函数同样需要注意的是，str1不允许是字符串常量，且其长度必须足够大，以便能够容纳str2的所有内容，否则会因越界产生错误。例6-11分析下面程序运行结果。程序设计例6-11源代码该程序中与上一程序唯一不同的地方是将strcat(str1,str2)改为strcpy(str1,str2)。程序运行结果如图6-22.从结果可以看出strcat()函数执行后str1内容的变化情况。,6.4字符数组,6.4.4字符串处理函数4.字符串比较函数strcmp()字符串比较函数的调用格式为：strcmp(str1,str2)其中，str1和str2均可以是字符数组名、字符串指针变量名或字符串常量。strcmp()函数的作用是将字符串str1的内容和字符串str2的内容进行比较。,6.4字符数组,6.4.4字符串处理函数字符串比较规则：对两个字符串逐个字符比较其ASCII码值的大小，直到遇到不同的字符或字符串结束标志0为止。1.若全部字符相同，则两个字符串相等，strcmp()