c数组与字符串.ppt

C语言程序设计-第6章,1,第6章 数组与字符串,C语言程序设计-第6章,2,前面所用到的数据称之为基本类型(整型、实型、字符型)。它们处理数据的能力非常有限。C语言提供了一种构造类型，它具有强有力的数据组织和数据表达能力。其中，数组是C语言组织和描述较复杂数据对象的基本工具之一，是一种应用极广的构造数据类型。,6.1 概述,C语言程序设计-第6章,3,数组：由一组有序数据（数组元素）组成。,例如，一组数据：a0，a1，a2，a99用数组表示： a0，a1， a2，a99,下标，它决定了元素在数组中的位置,数组特点： 1.一个数组由一个名字来标识； 2.数组大小必须确定，不许随机变动； 3.同一数组中的元素其类型相同，不许混合类型,C语言程序设计-第6章,4,6.2 一维数组,如果数组元素在数组中的位置只需要用一个下标就能确定，这样的数组称为一维数组。,同变量一样，数组也必须先定义，后使用。,6.2.1 一维数组的定义,数组定义格式:,类型说明符 标识符整型常量表达式;,数组元素类型,数组名,元素个数。它只能是常量或由常量构成的表达式，不能含有变量,例: int a 20; float grades 100;,C语言程序设计-第6章,5,归纳几点：,1）C在语法上没有数组变量的概念，对数组的操作只能分解为对其元素的操作，数组作为一个整体不能参加运算。,2）定义中的的值决定了该数组的元素个数，而不是该数组可用的最大下标。它可以是已定义的符号常量。,3）下标从0开始。下标可以是整型常量、字符、枚举型常量及其表达式。,4）数组名不是一个变量而是一个地址常量，它代表该数组所占存储空间的首地址，即该数组第一个元素所占空间的首址。,C语言程序设计-第6章,6,5）数组的存储结构：同一数组中的元素总是被分配在一片连续的空间，并根据数组的元素类型，为每一元素安排相同长度的存储单元。,C语言程序设计-第6章,7,6）数组元素的表示方法。有两种：,下标表示：,应是可求值的,例如：a = gradesi+j;,指针表示：也是一种常用的表示数组元素的方法,i和j已有确定的值,C语言程序设计-第6章,8,6.2.2 数组名与指针,我们考虑下面的例子： int a100； int *p； 则下面两个赋值表达式不但是合法的，而且它们的结果也是一样的： p = &a0 p = a,(3)两者所能施加的运算也不尽相同。例如： a+ /* 非法 */ p+ /* 合法 */,(1)数组名a是一个常量，它表征的实体是一种数据结构；指针p是一个变量。,(2)数组名a的值不可改变，即数组名不是左值；指针p的值可以更新，即指针是左值。,C语言程序设计-第6章,9,6.2.3 一维数组的初始化,初始化规则： 依序枚举赋值； 剩余的元素被自动初始化为0。,int a5 = 1,3,5,7,9； float x100 = 0.0 ；,有些编译器允许用逗号表示相应数组元素的初值为0，就像下面的例子那样： int a5 = ,2,8；,考虑下面这几个定义语句： char aStr1 = “Hello“; char aStr2 = H, e, l, l, o, 0 ; char aStr3 = H, e, l, l, o ; char *psz = “Hello“;,C语言程序设计-第6章,10,6.2.4 引用数组元素,C语言对数组下标没有提供安全措施，程序员要承当起确保下标不越界的全部责任和因为下标越界所产生的一切后果。,int a5 = 1,2,3,4,5; for( k = 0; k 6; k+ ) ak += ak; printf(“a%d = %dn“,k,ak); ,输出结果为： a0 = 2 a1 = 4 a2 = 6 a3 = 8 a4 = 10 a5 = 一个不确定的值,#include int main() float a = 22.2, 44.4, 66.6; float r = 11.1; printf(”r = %fn”,r); a3 = 88.8; /* a3不是数组a的元素 */ printf(”r=%fn”,r); ,这个程序的输出结果可能是： r=11.1 r=88.8,C语言程序设计-第6章,11,6.3 数组排序,简单选择排序（Simple Selection Sort）法的排序过程如下：, 49 38 65 97 76 49 13 27, 13 38 65 97 76 49 49 27, 13 27 65 97 76 49 49 38, 13 27 38 97 76 49 49 65, 13 27 38 49 76 97 49 65, 13 27 38 49 49 97 76 65, 13 27 38 49 49 65 76 97, 13 27 38 49 49 65 76 97,C语言程序设计-第6章,12,简单选择排序的算法： E1：准备 将a0，a1，an-1置于数组a中，令i = 0； E2：判断排序是否完成 如果i = n-1，则排序完成，算法结束； E3：选择第i个最小分量并交换位置 E3.1 从ai，ai+1，an-1中选择出最小分量,设为ak, E3.2 将ai与ak交换； E4：继续排序 i = i+1，转E2。,以上算法，可用如下程序段实现： for( i = 0; i n-1; +i ) k = i; for( j = i+1; j n; +j ) if( aj ak ) k=j; if( k!=i ) temp = ak； ak = ai;ai = temp； ,C语言程序设计-第6章,13,6.4 多维数组,维数大于1的数组称为多维数组。应用最广泛的是二维数组。,二维数组最根本的用途之一来自矩阵。考虑以下的34矩阵： 5 8 16 60 10 0 -9 22 0 12 0 6,矩阵中的一个元素Mi,j，在C语言中，用Mij来表示，但行列的计数自动从0开始。,C语言程序设计-第6章,14,6.4.1 多维数组的存储结构,多维数组的定义与一维数组类似。例如： int a5; /* 一维，共5个元素 int b45; /* 二维，共45个元素 int c345; /* 三维，共345个元素,下面给出int a33各元素在逻辑空间和物理存储空间的位置。,C语言程序设计-第6章,15,int a33逻辑空间：,a00,a01,a02,a10,a11,a12,a20,a21,a22,a0,a1,a2,a00,a01,a10,a02,a20,&a00,a1,a2,int a33物理存储空间（行主序原则）：,a,a0,C语言程序设计-第6章,16,我们可以将a33看成是一个一维数组，它有三个元素a0、a1和a2,它们中的每一个又是一个一维数组。即把二维数组a33分解为三个一维数组，其中，a0,a1和a2是这三个一维数组的数组名，它们都是地址常量，分别代表这三个一维数组在存储空间的首地址。 根据以上分析，可推知： a = a0 = &a00 a1 = &a10 a2 = &a20,C语言程序设计-第6章,17,6.4.2 多维数组的初始化,1按行赋值。将每一行元素作为一个赋值单位，一对花括号内的数据对应一行元素。例如; int a34=0,1,2,3,10,11,12,13,20,21,22,23;,初始化后各元素的值为： a00=0, a01=1, a02=2, a03=3; a10=10, a11=11, a12=12, a23=13; a20=20, a21=21, a22=32, a33=33.,2. 将所有数据写在一个花括号内，按数组元素排列的顺序对各元素赋值。例如: int a34=0,1,2,3,10,11,12,13,20,21,22,23; 其效果与上面的相同。,初始化方法:,C语言程序设计-第6章,18,3可以只对部分元素赋初值，无初值对应的元素自动取0值或空字符。例如: int a34=1,10,11,20; 则a00=1; a10=10, a11=11; a20=20，其余元素取0值。,4如果给数组的全部元素或部分元素赋初值，可以不指定第一维的大小，但其它维的大小必须指定，第一维的大小由系统根据初值数目及其它维的大小决定。例如: int a3=1,2,3,4,5,6; 等价 int a23=1,2,3,4,5,6;,C语言程序设计-第6章,19,5. 如果需要对某行后面的一些元素赋初值，则必须给其前面的元素赋初值0。如果不需要对某一行赋初值却需要对此行后面的元素赋初值，则该行位置以一对空花括号表示。例如: int a34=0,1,0,0,5; 则 a01=1, a22=5；其余元素为0。,以下程序的运行结果是什么？ int main() int a3=1,2,3,4,5,6,0; clrscr(); printf(“%d,%d,%dn“,a11,a21,a31); ,结果：5，0，0,C语言程序设计-第6章,20,在书写多维数组时，一定要把各下标分别用一对方括号括起来。例如，不要误写成： a3,4 问题在于上面这个表达式是完全合法的，编译器不会提供任何信息以指出你的失误。那么它表示什么呢？它就是a4！因为编译器将这对方括号里的内容当作一个逗号表达式来计算。这类失误简直就是一个恶梦。,C语言程序设计-第6章,21,6.5 数组的应用,/* 求Faibonacci数列的前N项 */,#include #define N 45 /* 设N = 45 */,int main() ,int i;,/* 定义循环控制变量 */,long aFibonacciN = 1,1; /* 初始化数列的前两项 */,for (i = 2; i N; i+),/* 生成其余N-2个Faibonacci数 */,aFibonaccii = aFibonaccii-2 + aFibonaccii-1;,for(i = 0; i N; i+) /* 输出结果，每行5个数 */ ,if(0 = i % 5) printf(“n“); printf( “%12ld“, aFibonaccii ); /* 域宽12,长整型ld */ ,C语言程序设计-第6章,22,例6.8 任意输入一个整数n(1n1000)。用筛选法求所有不大于n的全部素数。,具体做法可用如下算法描述：,E1：准备一个筛子aSieveN，预置筛中所有元素值 为TRUE;,E2：k = sqrt(n)+1; i = 2; 即认定aSievei为素数；,E3：若ik则算法终止；否则转E4；,E4：从筛中筛去是i的倍数的所有数，即令： sievei*m = FALSE; m = 2,3, ,i*mn;,E5：i=i+1; 转E3。,C语言程序设计-第6章,23,/* 用筛法求素数 */ #include #include #define FLASE 0 #define TRUE 1 #define MAX 1000,int main() int aSieveMAX; /* 准备一个筛子aSieveMAX */ int n,i,j,k;,printf(“Input an integer (1n1000):“); scanf(“%d“, /* 求不大于n的全部素数 */,for( i = 2; i = n; +i ) aSievei = TRUE; /* 假设筛中全部是素数 */,C语言程序设计-第6章,24,k = sqrt(n)+1;,for(i = 2; i = k; +i),if(aSievei) /* 如果i是素数 */ ,j = i+i;,do,aSievej = FLASE; /* 筛去所有i的倍数的数 */ j = j+i; while( j = n ); ,k=0; for( i = 2; i = n; +i ) /* 下面输出全部素数 */ if( aSievei ) printf(“%5d“,i); /* i是素数 */ k+; if( k % 10 = 0 ) printf (“n“); ,C语言程序设计-第6章,25,例6.9 将任意n个整数存放在数组a中，然后将这n个数从小到大排好序。采用冒泡排序法。,所谓冒泡排序法是因为这种排序方法能够使得较小的值像气泡一样逐渐“上浮”到数组的顶部，而较大的值逐渐“下沉”到数组的底部（通常认为都是从小到大排序）。其基本思想是：每一趟都将两两相邻的元素作比较，如果位于上面的那个值大，就交换；否则就保持原样。,C语言程序设计-第6章,26,46 55 13 94 17 5 70,46 13 55 17 94 5 70,46 13 55 17 5 94 70,46 13 55 17 5 70 94,46 13 55 94 17 5 70,13 17 5 46 55 70 94,13 5 17 46 55 70 94,5 13 17 46 55 70 94,13 46 17 5 55 70 94,46 13 55 17 5 70 94,for(i=1; iaj+1) t=aj; aj=aj+1; aj+1=t; ,第一轮过程,第一轮结果,C语言程序设计-第6章,27,6.6 字符串与字符数组,6.6.1 用字符数组表示字符串,通常情况下，字符串是用字符数组来表示的。读者可以在定义语句中把一个字符串赋给一个字符数组。例如： char word1 = H, e, l, l, o, ! ; char word2 = H, e, l, l, o, !, 0; 前者定义了一个字符数组word1，它有6个元素，每个元素是一个字符。word1不是一个字符串，因为它没有串结束符；后者定义了一个字符串word2，串的长度也是6，因为串结束符不是串的一部分。,C语言程序设计-第6章,28,当把字符数组作为字符串处理时，下列四种初始化方法都是等效的： char s18= p,r,o,g,r,a,m,0; char s2 = p,r,o,g,r,a,m,0; char s3 =”program”; char s4 = ”program”;,注意下面这个语句，它合法但潜在危险性：,char *psz = ”program”;,它相当于下面两个语句：,char *psz;,psz = ”program”;,这样做的后果是不能更新*psz，否则可能导致不可预料的结果。,C语言程序设计-第6章,29,6.6.2 字符串的输入输出,两个库函数：,gets(word); /* 输入串，见P.3