C语言数组教程

第8章数组,主讲教师：孙运雷计算机与通信工程学院计算机科学系sunyunle回顾,基本数据类型：int,float/double,char数据的处理：根据问题需求，先作几个简单变量的定义，然后对这些变量赋值并作相应的运算即得结果例如：输入10个实数，求其平均值。,#includeintmain()inti;floatnum,sum=0;printf(input10numbers:n);for(i=1;i=10;i+)scanf(%f,各变量独立存储，之间没有任何关系不需要也不可能保留变量的历史值,问题的提出,一个人n门课的成绩怎样存储和处理？一个班n门课的成绩怎样存储和处理？如何从键盘输入100个数然后按相反顺序输出？输入10个数，将高于平均值的数输出？.,这些数据的特点：1.具有相同的数据类型2.使用过程中需要保留原始数据为了方便的使用这些数据，C语言提供了一种构造数据类型：数组。一定要理解并用好数组！,本章主要内容,C语言中的数组,数组是具有相同类型的数据的顺序集合数组可以在内存中连续存储多个元素,0123,下标标明了元素在数组中的位置，从0开始,数组元素,下标,Rate0Rate1Rate2Rate3,数组类型,本章主要内容,定义一维数组,datatypearrayNamesize;,类型说明符int、char、float,数组名,常量表达式：数组大小,intnum50;charlist_of_initials20;doublepressure_level6;,#defineLIMIT20.intemp_codesLIMIT;,数组和变量一样，必须先定义后使用；数组大小定义好后，将不能改变；,数组大小最好用宏来定义，以适应未来可能的变化,定义一维数组,C89：定义数组时不能使用变量定义数组的大小，即使在此之前变量已经赋值，只能使用整形常量定义数组的大小C99：允许用变量定义数组的大小,intarray(10);intn=5;floatscoren;intn;scanf(%d,一维数组在内存的存放,数组下标从0开始数组元素在内存中按顺序连续存放数组名代表数组的首地址，即score的值与score0的地址值相同,高地址,低地址,intscore5;,数组元素的引用数组元素就是变量,C语言中，不允许引用数组进行运算，只能引用数组元素基本形式：,数组名下标表达式;,说明：下标表达式的值必须为整型下标从0开始，最大下标为数组长度减1是下标运算符，引用数组元素时根据数组首地址和下标计算出该元素的实际地址，然后取出该地址的内容如引用score2:计算2000+2*4=2008取出地址2008的内容,例如：inta5;a0=20;a4=2*a0;,下标越界是大忌！,inta10;scanf(%d,/*下标越界*/编译程序不检查是否越界下标越界，将访问数组以外的空间，可能带来严重后果,#includeintmain()inta=1,c=2,b5=0,i;printf(%p,%p,%pn,b,1,2,3,4,5,6,0,7,8,9,运行程序或单步执行观察变量变化情况可以看到，变量c和a的值因数组越界而被悄悄破坏了,一维数组的初始化,初始化：在定义数组时给数组元素赋初值形式：数据类型数组名称数组长度=数值列表在定义数组时，对全部数组元素赋初值：例如：inta5=0,1,2,3,4;此时也可省略数组长度例如：inta=0,1,2,3,4;/只写inta;是错误的在定义数组时，对部分数组元素赋初值：例如：inta5=0,1,2;/数组其余元素自动赋0当初值的个数多于数组元素个数时，编译出错例如：inta5=0,1,2,3,4,5;,只能逐个对数组元素进行操作（字符数组例外）一般一维数组的处理用一重循环来实现，用循环变量的值对应数组元素的下标,动态赋值方法：,inta10,i;,输入第3个数组元素：,scanf(%d,输入整个数组元素：,for(i=0;i10;i+)scanf(%d,输出方法：,输出第1个数组元素：,printf(%d,a0);,输出整个数组元素：,for(i=0;i10;i+)printf(%d,ai);,一维数组的动态赋值和输出,一维数组示例,【例1】输入10个整数，输出它们的和，并逆序打印这些数,#include#defineN10/数组程序推荐该用法intmain()inti,sum=0,dataN;for(i=0;i=0;i-)printf(%d,datai);printf(n);return0;,一维数组示例,【例2】用数组来求Fibonacci数列前20项,#include#defineN20intmain()inti,fN=1,1;for(i=2;iN;i+)fi=fi-2+fi-1;for(i=0;iN;i+)if(i%4=0)printf(n);printf(%6d,fi);printf(n);return0;,Fibonacci数列：1，1，2，3，5，8，13，21，34,总结理解：C语言中的数组,数组是一组相同类型的数据组成的有限集合数组是可以在内存中连续存储多个元素的结构数组中的数据称为数组元素，数组元素个数称为数组长度数组元素用数组名和元素下标表示，如score0,score1,0123,score4,数组名(首地址),下标标明了元素在数组中的位置，从0开始,数组元素,下标,数组大小,本章主要内容,二维数组的定义思考为何需要二维数组？,intnum42;,4X2=8,数据类型数组名常量表达式1常量表达式2;,错误的定义：inta3,4,b(3,4);intc,d(3)(4);,二维数组的存储结构思考该如何存？,inta23;,a10,a11,a12,a00,a01,a02,二维数组元素在内存中的存放顺序：先按行存放，再按列存放，即先顺序存放第0行的元素再存放第1行的元素，,a00a01a02a10a11a12,二维数组元素的引用,二维数组元素的引用形式：例如：inta34;a00=3;a01=a00+10;a34=5;/*下标越界*/,数组名行下标列下标;,二维数组的初始化,按行赋初值：例如：inta23=1,2,3,4,5,6;inta23=1,4,5;按数组元素存放顺序赋初值：例如：inta23=1,2,3,4,5,6;inta23=1,2,3;省略行数（根据初值个数和列声明自动确定行数）例如：intb3=1,2,3,4,5,6,7,8,9,10;intc3=1,2,3;,4行,二维数组的初始化,下列二维数组的定义都是错误的:inta,b3,c2;intarr2=1,2,3,4,5,6;intb23=1,2,3,4,5,6,7,8;,二维数组值的输入和输出,一般二维数组的处理用二重循环来实现，用循环变量的值控制数组元素的下标,inta34,i,j;,二维数组的输入和输出,为一个3行4列的二维数组输入/输出数据,intmain()inta34,i,j;for(i=0;i3;i+)for(j=0;j4;j+)scanf(“%d”,二维数组示例,【例3】将二维数组a转置存到二维数组b中,a01,b10,a12,b21,设行下标为i，列下标为j，则:bjiaij,【例3】将二维数组a转置存到二维数组b中,#includeintmain()inta23=1,2,3,4,5,6,b32,i,j;printf(数组a:n);for(i=0;i2;i+)for(j=0;j3;j+)printf(%5d,aij);printf(n);for(i=0;i2;i+)for(j=0;j3;j+)bji=aij;/*转置*/,printf(数组b:n);for(i=0;i=2;i+)for(j=0;j=1;j+)printf(%5d,bij);printf(n);return0;,二维数组示例,【例4】从键盘上为一个55整型数组赋值，找出其中的最小值和最大值（平均值，上三角），并显示出来分析：设最大值为max，最小值为min.1、令max=a00min=a002、对0max，则将其存入max中。3、输出min和max。,【例4】55整型数组找最小值和最大值,#includeintmain()introw,col,a55,max,min;printf(请输入5个整数：);for(row=0;rowmax)max=arowcol;printf(min=%d,min);printf(max=%dn,max);return0;,输入数据,找最小值和最大值,总结,数组是由同一种数据类型的元素系列构成数组元素按顺序在内存中连续存储，并通过使用数组下标（或索引）来访问，首元素的索引值为0数组必须先声明然后才能使用。声明一个数组只是为该数组留出连续内存空间，并不会为其赋任何值一维数组定义：数据类型数组名数组大小二维数组可以看作是一维数组的数组一维数组可用一个循环动态赋值，而二维数组可用二重嵌套循环动态赋值C把数组名解释为该数组第1个元素(a0)的首地址，并且C编译器不检查所引用的数组元素下标是否越界,本章主要内容,函数参数的传递方式,根据实参类型的不同，有两种传递方式值传递地址传递1、值传递方式类型简单变量(数组之前所学的变量类型)方式调用函数时：将实参值复制一份传给函数的形参调用结束后：原值不变（变的只是副本）特点实参与形参占用不同的内存单元,【例】输入两个数,编写函数将它们交换,#includevoidswap(intx,inty)inttemp;temp=x;x=y;y=temp;intmain()inta,b;scanf(%d%d,5,9,5,5,9,COPY,输入：59输出：5,9,形参,实参,值传递,函数参数的传递方式,2、地址传递方式类型数组、指针、结构体方式调用函数时：将实参地址复制一份传给函数的形参调用结束后：原值改变特点形参与实参占用相同的内存单元,对比,简记为：传递简单类型是值传递；传递其他类型是地址传递,简单变量和数组作函数参数的区别,数组作函数参数,1、一维数组元素作函数参数【例】求5个整数中的最小数,#include#defineN5intmain()intaN,i,m;for(i=0;iN;i+)scanf(%d,intmin(intx,inty)return(xy?x:y);,传递的是数组元素的值，所以是值传递方式,数组作函数参数,2、一维数组名作函数参数重点定义阶段：形参应定义为数组形式，形参数组的长度可以省略，但是不能省略，否则就不是数组形式如voidfun(intmyArray,intlength)调用阶段：实参为数组名如：fun(myArray);数组名表示数组在内存中的起始地址，传递的是数组名，所以是地址传递方式,例：求学生的平均成绩,#includefloataverage(intstu10,intn);intmain()intscore10,i;floatav;printf(Input10scores：n);for(i=0;i10;i+)scanf(%d,floataverage(intstu10,intn)inti;floattotal=0;for(i=0;i0?total/n:-1;/更安全,【例8.7】计算最高分,#include#defineN40intReadScore(intscore);intFindMax(intscore,intn);intmain()intscoreN,max,n;n=ReadScore(score);printf(Totalstudentsare%dn,n);max=FindMax(score,n);printf(Thehighestscoreis%dn,max);return0;,计算最大值算法,max(i=0),max(i=2),max(i=3),【例8.7】计算最高分,假设其中的一个学生成绩为最高maxScore=score0;对所有学生成绩进行比较，即for(i=1;imaxScore则修改maxScore值为scorei打印最高分maxScore,数组作函数参数,有一个班，30个学生，4门课程成绩，要求：利用函数计算每个学生的平均分并在主函数中输出平均分。思路使用二维数组作为参数,二维数组作为参数不用函数,#include#defineSN30#defineCN4intmain()inti,j;floatscoreSNCN,sum,avgSN;for(i=0;iSN;i+)sum=0;for(j=0;jCN;j+)scanf(%f,二维数组作为参数使用函数,#include#defineSN30#defineCN4intmain()inti,j;floatscoreSNCN,avgSN;for(i=0;iSN;i+)for(j=0;jCN;j+)scanf(%f,voidfun(floataCN,floataverage)floatsum;inti,j;for(i=0;iSN;i+)sum=0;for(j=0;jCN;j+)sum=sum+aij;averagei=sum/CN;,怎么写？,二维数组作函数参数方法与一维数组相同需要注意的是：形参为二维数组时，可以省略第一维长度说明，但是不能省略第二维的长度说明。,本章主要内容,排序算法,冒泡排序,BubbleSort选择排序,SelectionSort双向冒泡排序,ShakerSort插入排序,InsertionSort希尔排序,ShellSort,也称缩小增量排序归并排序,MergeSort堆排序,HeapSort快速排序,QuickSort猴子排序,BogoSort排序算法动画比较演示http:/jsdo.it/norahiko/oxIy/fullscreenhttp:/www.sorting-,交换法排序,交换法排序,【例8.8】交换法从高到低排序,交换法排序for(i=0;iscorei)交换成绩scorej和scorei,如何实现两数交换？,temp=scorej;scorej=scorei;scorei=temp;,70,50,70,交换法不用函数,#include#defineN10intmain()inti,j,t,aN;printf(顺序输入%d个整数：,N);for(i=0;iai)t=ai;ai=aj;aj=t;printf(n排序后的序列为：n);for(i=0;iN;i+)printf(%d,ai);printf(n);return0;,交换法使用函数,#include#defineN10voidprintArray(inta);voidsort(inta,intn);intmain()inta=11,22,63,97,58,80,45,32,73,36;printf(Beforesort:n);printArray(a);sort(a,N);printf(Aftersort:n);printArray(a);return0;,voidprintArray(intb)inti;for(i=0;iN;i+)printf(%5d,bi);printf(n);,voidsort(intb,intn)inti,j,t;for(i=0;ibi)t=bi;bi=bj;bj=t;,实参用数组名，相当于：把a的地址传给了形参b,形参用数组定义,选择法排序,k=1,k=2,k=0,k=1,选择法排序,k=3,k=4,k=3,k=4,选择法排序,for(i=0;iscorek)记录此轮比较中最高分的元素下标k=j;若k中记录的最大数不在位置i，则交换成绩scorek和scorei，交换学号numk和numi；,选择法排序,voidDataSort(intscore,longnum,intn)inti,j,k,temp1;longtemp2;for(i=0;iscorek)k=j;/*记录最大数下标位置*/if(k!=i)/*若最大数不在下标位置i*/temp1=scorek;scorek=scorei;scorei=temp1;temp2=numk;numk=numi;numi=temp2;,冒泡法排序,【例4】用冒泡法对数组元素进行排序，排序后元素按数值从小到大顺序排列冒泡排序：依次比较相邻的两个数，将大数上升（放右边）第一趟：首先比较第1个和第2个数，将大数放右边。然后比较第2个数和第3个数，如此继续，直至比较最后两个数，结果是将最大数放最右边。第二趟：重复以上过程，仍从第一对数开始比较，将大数放右边，一直比较到倒数第二对数，第二趟结束，得到一个次大数。如此下去，直至最终完成排序。由于排序过程如同冒气泡，所以称作冒泡排序,冒泡法排序,for(i=0;iaj+1)交换aj和aj+1;,for(i=0;iak)k=j;/*记录最大数下标位置*/if(k!=i)/*若最大数不在下标位置i*/交换aj和ak;,for(i=0;iai)交换aj和ai“;,冒泡法,交换法,选择法,快速排序,QuickSort,基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。整个排序过程需要三步：寻找一个中心元素（通常为第一个数）所有小于中心点的元素，都移到中心点的左边；所有大于中心点的元素，都移到中心点的右边。对中心点左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。,快速排序讲解,需要解决的问题当已知中心元素的前提下，怎样将其他元素划分好？（即：大于中心点在之后，小于中心点在之前）,i,0,1,2,3,4,5,i=0,i=1,j=5,j=5,j,i=1,j=3,i=1,j=4,i=2,j=3,i=2,j=2,算法终止,该算法有没有可以改进的地方?,快速排序讲解,通过动画，可以看出每次中心元素都要交换。根据划分的思想最后位置一定是中心元素,i,0,1,2,3,4,5,i=0,i=1,j=5,j=5,j,i=1,j=3,i=1,j=4,i=2,j=3,i=2,j=2,算法终止,可以申请一个变量保存中心元素，以避免交换,快速排序函数,voidQuickSort(int*arr,intleft,intright)inti,j,temp;if(lefttemp/对中心点右半部递归调用本函数,*arr为数组指针，下一章讲解,快速排序函数qsort调用,在头文件中，提供了一个快速排序函数qsort，它的函数原型如下：voidqsort(void*base,intnelem,intwidth,int(*fcmp)(constvoid*,constvoid*);四个参数分别是：1待排序数组首地址2数组中待排序元素数量3各元素的占用空间大小4指向函数的指针，用于确定排序的顺序要求学完指针后能熟练调用，有余力的同学可以先学习先用,线性表：二级C重点之一,表中除首元素和尾元素外，每个元素都有且只有一个前驱；有且只有一个后继。a0ai-1,ai,ai+1aN-1数组和链表是线性表的两种实现方式。链表选学,数组应用举例,例1假设数组a中已有5个整数，要插入一个数x到第1个数前面并保持这5个数的前后关系不变，试编程实现,分析：数组最终存放6个元素，应定义数组a6,X,4,3,2,1,5,1,数组应用举例,#include#defineN5intmain()inti,x,aN+1;printf(Input%dnumbers:,N);for(i=0;i0;i-)ai=ai-1;ai=x;/a0=xprintf(Afterinsert:);for(i=0;iN+1;i+)printf(%d,ai);printf(n);return0;,后移并插入数据,数组应用举例,【例2】随机产生20个整数保存在数组中，试用顺序查找方法查找某个整数。分析：产生随机数：使用函数srand()和rand()顺序查找：从数组的第1个元素开始逐一与要查找的数据进行比较，如果有一个元素与之相同，就是找到了，查找过程即可结束。如果所有元素都不同于要查找的数据，则没找到。,数组应用举例,#include#include#include#defineN20intmain()inti,x,aN,find=0;srand(time(NULL);/*保证每次产生不同的随机数序列*/for(i=0;iN;i+)/*产生N个小于100的随机数*/ai=rand()%100;if(i%10=0)printf(n);printf(%6d,ai);printf(n要查找的整数是?);scanf(%d,一旦找到，设置find=1，通过break语句跳出循环,数组应用举例,【例3】设整型数组a10，删去某数x，并使原来的顺序关系不变，试编程实现。问题分析：主要解决两个