搜索
程序设计语言(C)王正杰第四章数组、指针与字符串[本章重点]数组的定义、初始化和使用；指针的定义、访问和运算；指针与数组和函数的联系；字符串与数组和指针的关系；结构体的应用；几种常用的算法和数据结构。[本章难点]指针的定义、赋值和运算；数组、字符串、结构体的操作以及动态存储分配。在C中，除了前面介绍的基本类型外，还有一种用基本类型数据按一定的规则组成的构造类型，构造类型的每一个分量可以是一个简单的类型变量，也可以又是一个构造类型的变量，它们可以像简单变量一样使用。C语言的构造类型有数组、结构体、共同体等。指针是C语言区别于其他程序设计语言的主要特征，指针可用于有效的表示数据之间复杂的逻辑关系，也可用于动态分配内存，还可以简单有效地处理数组。用来存放字符串的数组是字符数组，除了用访问数组的方式来操纵字符串外，我们还可以利用指针来使用字符串。本章将介绍典型的构造类型——数组和结构体，以及与数组和结构体密切相关的指针和字符串。•数组是具有一定顺序关系的若干相同类型变量的集合体，组成数组的变量称为该数组的元素。•一维数组通常用于表示由固定多个同类型的具有线性次序关系的数据所构成的复合数据，如向量、某个学生的各门课成绩、学生的姓名表等。在Ｃ语言中使用数组必须先进行定义，一维数组的定义形式为：•存储类型说明符数据类型标识符数组名[常量表达式]；•inta[5];•数组名是用户定义的数组标识符，数组名的命名规则要遵循标识符命名规则。方括号中的常量表达式表示数组元素的个数，也称为数组的长度。•对于数组定义应注意以下几点：1）数组的类型实际上是指数组元素的取值类型。对于同一个数组，其所有元素的数据类型都是相同的。2）数组名不能与其它变量名相同。3）不能在方括号中用变量来表示元素的个数，可以用符号常数或常量表达式，如arrry[10]表示数组arrry有10个元素，其下标从0开始。一维数组的初始化数组的初始化就是在定义的同时，给部分或全部元素赋值，一维数组的初始化的格式是：•数据类型标识符数组名[常量表达式]={初值表};•其中，初值表用一对花括号{}括起，每个初始值之间用逗号隔开。例如：•intarray[5]={1,2,3,4,5};•该语句定义了一个包含5个整型元素的数组array并对其进行了初始化，初始化后array[0]=1、array[1]=2、array[2]=3、array[3]=4、array[4]=5。•初值表元素的数量可以少于数组长度，也就是可以只对数组的部分元素赋初值。例如：•intarray[5]={1,2,3};•初始化后前三个元素的值为array[0]=1、array[1]=2、array[2]=3，其余没赋初值的元素的值都为0，即array[3]=0、array[4]=0。•也可以省略数组长度，例如：•intarray[]={1,2,3,4,5};•初始化后数组的长度为5。一维数组的访问像普通变量一样，数组定义之后，就可以在程序中访问数组中的元素。我们只能逐个访问其中的元素，对于数组元素的访问可以通过以下形式表示：数组名[下标]•intarray[5]={1,2,3,4,5};•a=array[3];•array[3]=6;voidmain(){intarray[5],i;//使用循环语句对数组的5个元素分别赋值for(i=0;i5;i++)array[i]=i*i;//分别输出数组元素的值for(i=0;i5;i++)cout下标为i的元素的值是：array[i]endl;}•C语言系统对数组的下标越界不做任何检查，即对有n个元素的数组，既可访问下标小于0的元素，也可访问下标大于n的元素。当然，这样的元素是不存在的，所以越界访问元素会给程序运行造成不可预测的后果，所以程序员应当自己控制下标越界的检查。用数组来处理求Fibonacci数列问题voidmain(){inti;intf[20]={1,1};//初始化第0、1个数for(i=2;i20;i++)f[i]=f[i-2]+f[i-1];//求第2～19个数for(i=0;i20;i++)//输出，每行5个数{if(i%5==0)coutendl;coutf[i];}}向函数传递一维数组当需要把一个一维数组传给一个函数时，调用者需要把该一维数组的变量名以及数组元素的个数传给被调函数，而被调函数的形参应为不带数组大小的一维数组定义以及数组元素的个数，下面我们通过一个例子来了解向函数传递一维数组的过程。intmin(inta[],intlength){inti,m=0;//m用于记录最小元的下标for(i=1;ilength;i++)if(a[i]a[m])//逐个比较数组的元素m=i;//找出最小的元素returnm;//函数min将返回最小//元素的下标：}voidmain(){intarray[10]={18,26,23,13,15,25,27,14,29,31},tag;tag=min(array,10);//调用函数min,并将数组//名作为参数传给函数cout数组中最小的元素是：array[tag]endl;}简单选择排序假设排序过程中，待排记录序列的状态为：有序序列R[1..i-1]无序序列R[i..n]第i趟简单选择排序从中选出关键字最小的记录有序序列R[1..i]无序序列R[i+1..n]对主调函数传递的数组进行排序voidsort(inta[],intlength){//定义变量tag以标记当前最小元素之下标，//定义交换变量bufferinti,j,tag,buffer;for(i=0;ilength;i++){…}}tag=i;//每次外循环，都将tag的值置为//内循环处理的第一个元素的下标//内循环的任务是找出数组中下标//从i到length的元素的最小者for(j=i;jlength;j++)if(a[tag]a[j])tag=j;//标记小元素的下标//将当前未排好序数组的最小元素a[tag]//和元素a[i]交换buffer=a[tag];a[tag]=a[i];a[i]=buffer;voidmain(){intarray[10]={6,2,10,3,7,5,9,4,8,1},i;coutendl排序前数组array:;for(i=0;i10;i++)coutarray[i];sort(array,10);//调用函数sort，并将数组array//和数组长度作为参数传递给函数coutendl排序后数组array为:;for(i=0;i10;i++)coutarray[i]“”;//输出排序//后的数组arraycoutendl;}•该程序使用的是选择排序，其思想是，第一次从所有元素中选取最小值，与a[0]交换；第二次从剩余元素中选取最小值，与a[1]交换；……；直至完成整个数组的排序。函数sort中，每轮内循环结束后tag中存放的就是剩余元素中最小者的下标；第i次外循环结束后，数组前i个元素就都是已经排好序的元素。当排序完成返回主调函数main后，主调函数的数组array就是已经完成排序的数组，这是因为main函数中的数组array和sort函数中的数组a代表同一块存储空间，从本质上讲它们是同一个数组。•用起泡法对10个数排序(由小到大)。•起泡法的思路是：将相邻两个数比较，将大的调到后头。起泡排序假设在排序过程中，记录序列R[0..n-1]的状态为：第i趟起泡排序无序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1无序序列R[1..n-i]有序序列R[n-i+1..n]比较相邻记录，将关键字最大的记录交换到n-i+1的位置上voidmain(){inta[10]={6,2,10,3,7,5,9,4,8,1};inti,j,t;for(j=1;j10;j++)//此处的j值表示末尾剩几个for(i=0;i10-j;i++)if(a[i]a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}coutthesortednumberS:endl;for(i=0;i10;i++)couta[i];}二维数组•前面介绍的数组只有一个下标，称为一维数组，而在实际问题中经常要处理多维的量，需要构造二维数组或更多维的数组。简单地说，二维数组就是具有两个下标的数组，其元素有两个下标，以标识它在数组中的位置。数组维数的概念与几何中维数的概念是相似的，如果说一维数组的元素是线性排列的，只要给出一个下标就可以确定某一特定元素。那么，二维数组就类似于几何中的X-Y坐标系，坐标系中只要指出X坐标和Y坐标就能确定一个点，而要确定二维数组中的某一个元素也只需指出元素所在的行和列。二维数组定义•存储类型说明符数据类型标识符数组名[常量表达式1][常量表达式2];•其中存储类型说明和数据类型说明与一维数组相同，常量表达式1表示第一维下标的长度，常量表达式2表示第二维下标的长度，两个常量表达式中不能包含变量。例如：•intarray[2][3];•定义了一个二维数组array，该数组有两行，每行有三个元素。•二维数组的行下标和列下标都是从0开始的，对于n行m列的二维数组，行下标的取值范围为0—n-1，列下标取值范围为0—m-1。•二维数组的所有元素占有的内存空间是连续的，因此只要知道数组在内存中的起始地址就可以很容易的算出其它元素的存储单元地址。array[0][0]array[0][1]array[0][2]array[0][3]array[0][4]array[1][0]array[1][1]array[1][2]array[1][3]array[1][4]array[2][0]array[2][1]array[2][2]array[2][3]array[2][4]array[3][0]array[3][1]array[3][2]array[3][3]array[3][4]二维数组的初始化•二维数组赋初值的方式有两种，一种是不分行给二维数组所有元素赋初值，比如intarray[2][3]={1,2,3,4,5,6};，另一种更直观的方法是分行给二维数组所有元素赋初值，如intarray[2][3]={{1,2,3},{4,5,6}};。•同一维数组一样，二维数组也可以只给部分元素赋初值，例如：•intarray[2][3]={1,2,3};•对数组前三个元素array[0][0]、array[0][1]、array[0][2]分别赋以1、2、3，其他剩余元素都为0。•此外二维数组还可以用分行的方法给部分元素赋值，例如：•intarray[2][3]={{0,2},{4}};•初始化后各元素的值是array[0][0]=0、array[0][1]=2、array[0][2]=0、array[1][0]=4、array[1][1]=0、array[1][2]=0，•对二维数组赋初值可以省略说明第一维的长度，但是无论何种情况，都不能省略说明第二维的长度。在给全部元素赋值时，例如：•intarray[2][3]={1,2,3,4,5,6};•编译系统会根据初值个数分配相应的存储单元。在分行给元素赋初值时，如：•intarray[][3]={{2},{4,5,6}};•编译系统也会根据所分的行数确定第一维的长度。二维数组的使用•对二维数组的访问同一维数组类似，也是通过下标运算符“[]”和下标值来进行的。访问的形式如下：数组名[行下标][列下标]•例如：•intarray[2][3]={1,2,3,4,5,6};•a=array[1][0];•array[1][0]=6;•这几条语句的功能是访问数组array中，第二行第一列的那个元素，将其值4赋予变量a后，赋予其新值6。求4*4二维数组各行和各列元素之voidmain(){intc[4],r[4],i,j;//定义c[4]存放列元素的和，//