C语言数组PPT教程

1、第8章 数组,主讲教师：孙运雷 计算机与通信工程学院 计算机科学系回顾,基本数据类型：int, float/double, char 数据的处理：根据问题需求，先作几个简单变量的定义，然后对这些变量赋值并作相应的运算即得结果 例如：输入10个实数，求其平均值。,#include int main() int i; float num, sum=0; printf(input 10 numbers: n); for (i=1; i=10; i+) scanf(%f, ,各变量独立存储，之间没有任何关系 不需要也不可能保留变量的历史值,问题的提出,一个人n门课的成绩怎样存

2、储和处理？ 一个班n门课的成绩怎样存储和处理？ 如何从键盘输入100个数然后按相反顺序输出？ 输入10个数，将高于平均值的数输出？ .,这些数据的特点： 1.具有相同的数据类型 2.使用过程中需要保留原始数据 为了方便的使用这些数据，C语言提供了一种构造数据类型：数组。 一定要理解并用好数组！,本章主要内容,C 语言中的数组,数组是具有相同类型的数据的顺序集合 数组可以在内存中连续存储多个元素,0 1 2 3,下标标明了元素在数组中的位置 ，从0开始,数组元素,下标,Rate0 Rate1 Rate2 Rate3,数组类型,本章主要内容,定义一维数组,datatype arrayNamesiz

3、e;,类型说明符 int、char、float ,数组名,常量表达式： 数组大小,int num50; char list_of_initials20; double pressure_level6;,#define LIMIT 20 . . . int emp_codesLIMIT;,数组和变量一样，必须先定义后使用； 数组大小定义好后，将不能改变；,数组大小最好用宏来定义，以适应未来可能的变化,定义一维数组,C89：定义数组时不能使用变量定义数组的大小，即使在此之前变量已经赋值，只能使用整形常量定义数组的大小 C99：允许用变量定义数组的大小,int array(10); int n=5;

4、 float scoren; int n; scanf(%d, ,一维数组在内存的存放,数组下标从0开始 数组元素在内存中按顺序连续存放 数组名代表数组的首地址，即score的值与score0的地址值相同,高地址,低地址,int score5;,score,数组元素的引用数组元素就是变量,C语言中，不允许引用数组进行运算，只能引用数组元素 基本形式：,数组名下标表达式;,说明： 下标表达式的值必须为整型 下标从0开始，最大下标为数组长度减1 是下标运算符，引用数组元素时根据数组首地址和下标计算出该元素的实际地址，然后取出该地址的内容 如引用score2: 计算2000+2*4=2008 取出地

5、址2008的内容,例如： int a5; a0=20; a4=2*a0;,下标越界是大忌！,int a10; scanf(%d, /*下标越界*/ 编译程序不检查是否越界 下标越界，将访问数组以外的空间，可能带来严重后果,#include int main() int a = 1, c = 2, b5 = 0, i; printf(%p, %p, %pn, b, ,1,2,3,4,5,6,0,7,8,9,运行程序或单步执行观察变量变化情况可以看到，变量c和a的值因数组越界而被悄悄破坏了,一维数组的初始化,初始化：在定义数组时给数组元素赋初值 形式：数据类型 数组名称数组长度=数值列表 在定义数

6、组时，对全部数组元素赋初值： 例如：int a5=0,1,2,3,4; 此时也可省略数组长度 例如：int a =0,1,2,3,4; /只写int a;是错误的 在定义数组时，对部分数组元素赋初值： 例如：int a5=0,1,2; /数组其余元素自动赋0 当初值的个数多于数组元素个数时，编译出错 例如：int a5=0,1,2,3,4,5;,只能逐个对数组元素进行操作（字符数组例外） 一般一维数组的处理用一重循环来实现，用循环变量的值对应数组元素的下标,动态赋值方法：,int a10,i;,输入第3个数组元素：,scanf(%d,输入整个数组元素：,for (i=0;i10;i+) sca

7、nf(%d, ,输出方法：,输出第1个数组元素：,printf(%d, a0);,输出整个数组元素：,for (i=0;i10;i+) printf(%d, ai );,一维数组的动态赋值和输出,一维数组示例,【例1】 输入10个整数，输出它们的和，并逆序打印这些数,#include #define N 10 /数组程序推荐该用法 int main () int i,sum=0,dataN; for( i=0; i=0; i- ) printf( %d, datai ) ; printf(n); return 0; ,一维数组示例,【例2】用数组来求Fibonacci数列前20项,#inclu

8、de #define N 20 int main() int i,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); return 0; ,Fibonacci数列： 1，1，2，3，5，8，13，21，34,总结理解：C 语言中的数组,数组是一组相同类型的数据组成的有限集合 数组是可以在内存中连续存储多个元素的结构 数组中的数据称为数组元素，数组元素个数称为数组长度 数组元素用数组名和元素下标表示，如score0, score1,0 1 2

9、 3,score 4 ,数组名(首地址),下标标明了元素在数组中的位置 ，从0开始,数组元素,下标,数组大小,本章主要内容,二维数组的定义思考为何需要二维数组？,int num42;,4 X 2 = 8,数据类型 数组名常量表达式1 常量表达式2;,错误的定义： int a3,4, b(3,4); int c , d(3)(4);,二维数组的存储结构思考该如何存？,int a23;,a10,a11,a12,a00,a01,a02,二维数组元素在内存中的存放顺序： 先按行存放，再按列存放，即 先顺序存放第0行的元素 再存放第1行的元素，,a00 a01 a02 a10 a11 a12,二维数组元

10、素的引用,二维数组元素的引用形式： 例如： int a34; a00=3; a01=a00+10; a34=5; /*下标越界*/,数组名行下标 列下标;,二维数组的初始化,按行赋初值： 例如： int a23=1, 2, 3, 4, 5, 6; int a23=1, 4, 5; 按数组元素存放顺序赋初值： 例如： int a23=1, 2, 3, 4, 5, 6; int a23=1, 2, 3; 省略行数（根据初值个数和列声明自动确定行数） 例如： int b3=1, 2, 3, 4, 5, 6, 7, 8, 9,10; int c3=1, 2, 3;,4行,二维数组的初始化,下列二维数组

11、的定义都是错误的: int a, b3, c2; int arr2 = 1,2,3, 4,5,6; int b23=1, 2, 3, 4, 5, 6, 7, 8;,二维数组值的输入和输出,一般二维数组的处理用二重循环来实现，用循环变量的值控制数组元素的下标,int a34,i,j;,二维数组的输入和输出,为一个3行4列的二维数组输入/输出数据,int main() int a34, i, j; for (i=0; i3; i+) for (j=0; j4; j+) scanf(“%d”, ,二维数组示例,【例3】将二维数组a转置存到二维数组b中,a01,b10,a12,b21,设行下标为i，列

12、下标为j， 则: bji aij,【例3】将二维数组a转置存到二维数组b中,#include int main() int a23=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, bi

13、j); printf(n); return 0; ,二维数组示例,【例4】从键盘上为一个55整型数组赋值，找出其中的最小值和最大值（平均值，上三角），并显示出来 分析： 设最大值为max，最小值为min. 1、令max =a00 min =a00 2、对0max，则将其存入max中。 3、输出min和max。,【例4】55整型数组找最小值和最大值,#include int main () int row,col,a55,max,min; printf(请输入5个整数：); for(row=0; rowmax) max=arowcol; printf(min=%d ,min); printf(m

14、ax=%dn,max); return 0; ,输入数据,找最小值和最大值,总结,数组是由同一种数据类型的元素系列构成 数组元素按顺序在内存中连续存储，并通过使用数组下标（或索引）来访问，首元素的索引值为0 数组必须先声明然后才能使用。声明一个数组只是为该数组留出连续内存空间，并不会为其赋任何值 一维数组定义：数据类型 数组名数组大小 二维数组可以看作是一维数组的数组 一维数组可用一个循环动态赋值，而二维数组可用二重嵌套循环动态赋值 C把数组名解释为该数组第1个元素(a0)的首地址，并且C编译器不检查所引用的数组元素下标是否越界,本章主要内容,函数参数的传递方式,根据实参类型的不同，有两种传递

15、方式 值传递 地址传递 1、值传递方式 类型 简单变量(数组之前所学的变量类型) 方式 调用函数时：将实参值复制一份传给函数的形参 调用结束后：原值不变（变的只是副本） 特点 实参与形参占用不同的内存单元,【例】输入两个数,编写函数将它们交换,#include void swap ( int x, int y ) int temp; temp = x; x = y; y = temp; int main ( ) int a, b; scanf(%d%d, ,5,9,5,5,9,COPY,输入：5 9 输出：5,9,形参,实参,值传递,函数参数的传递方式,2、地址传递方式 类型 数组、指针、结构

16、体 方式 调用函数时：将实参地址复制一份传给函数的形参 调用结束后：原值改变 特点 形参与实参占用相同的内存单元,对比,简记为：传递简单类型是值传递；传递其他类型是地址传递,简单变量和数组作函数参数的区别,数组作函数参数,1、一维数组元素作函数参数 【例】求5个整数中的最小数,#include #define N 5 int main( ) int aN,i,m; for(i=0;iN;i+) scanf(%d, ,int min(int x,int y) return (xy?x:y); ,传递的是数组元素的值，所以是值传递方式,数组作函数参数,2、一维数组名作函数参数重点 定义阶段： 形参

17、应定义为数组形式，形参数组的长度可以省略，但是不能省略，否则就不是数组形式 如 void fun(int myArray, int length) 调用阶段： 实参为数组名 如： fun(myArray); 数组名表示数组在内存中的起始地址，传递的是数组名，所以是地址传递方式,例：求学生的平均成绩,#include float average(int stu10, int n); int main() int score10, i; float av; printf(Input 10 scores：n); for( i=0; i10; i+ ) scanf(%d, ,float average

18、(int stu10, int n) int i; float total=0; for( i=0; in; i+ ) total += stui; return total/n; ,实参用数组名,形参用数组定义 等价于int stu,return n0 ? total/n : -1; /更安全,【例8.7】计算最高分,#include #define N 40 int ReadScore(int score); int FindMax(int score, int n); int main() int scoreN, max, n; n = ReadScore(score); printf(

19、Total students are %dn, n); max = FindMax(score, n); printf(The highest score is %dn, max); return 0; ,计算最大值算法,max(i=0),max(i=2),max(i=3),【例8.7】计算最高分,假设其中的一个学生成绩为最高 maxScore = score0; 对所有学生成绩进行比较，即 for (i=1; i maxScore 则修改maxScore值为scorei 打印最高分maxScore,数组作函数参数,有一个班，30个学生，4门课程成绩，要求：利用函数计算每个学生的平均分并在主函

20、数中输出平均分。 思路 使用二维数组作为参数,二维数组作为参数不用函数,#include #define SN 30 #define CN 4 int main() int i,j; float scoreSNCN,sum,avgSN; for(i=0;iSN;i+) sum=0; for(j=0;jCN;j+) scanf(%f, ,二维数组作为参数使用函数,#include #define SN 30 #define CN 4 int main() int i,j; float scoreSNCN,avgSN; for(i=0;iSN;i+) for(j=0;jCN;j+) scanf(%

21、f, ,void fun(float aCN,float average) float sum; int i,j; for(i=0;iSN;i+) sum=0; for(j=0;jCN;j+) sum=sum+aij; averagei=sum/CN; ,怎么写？,二维数组作函数参数方法与一维数组相同 需要注意的是：形参为二维数组时，可以省略第一维长度说明，但是不能省略第二维的长度说明。,本章主要内容,排序算法,冒泡排序, BubbleSort 选择排序, Selection Sort 双向冒泡排序, ShakerSort 插入排序, InsertionSort 希尔排序, Shell Sor

22、t, 也称缩小增量排序 归并排序, Merge Sort 堆排序, HeapSort 快速排序, Quick Sort 猴子排序, BogoSort 排序算法动画比较演示 http:/jsdo.it/norahiko/oxIy/fullscreen http:/www.sorting- ,交换法排序,交换法排序,【例8.8】交换法从高到低排序,交换法排序 for (i=0; i scorei) 交换成绩scorej和scorei ,如何实现两数交换？,temp = scorej; scorej = scorei; scorei = temp;,70,50,70,交换法不用函数,#include

23、 #define N 10 int main () int i, 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); return 0; ,交换法使用函数,#include #define N 10 void printArray(int a); void sort(int a,int n); int main( ) int a=11,22,63,97,58, 80,45,32,73

24、,36; printf(Before sort:n); printArray(a); sort(a,N); printf(After sort:n); printArray(a); return 0; ,void printArray(int b) int i; for (i=0;iN;i+) printf(%5d,bi); printf(n); ,void sort(int b, int n) int i,j,t; for (i=0;ibi) t=bi; bi=bj; bj=t; ,实参用数组名，相当于： 把a的地址传给了形参b,形参用数组定义,选择法排序,k=1,k=2,k=0,k=1,选

25、择法排序,k=3,k=4,k=3,k=4,选择法排序,for (i=0; i scorek) 记录此轮比较中最高分的元素下标k=j; 若k中记录的最大数不在位置i，则 交换成绩scorek和scorei， 交换学号numk和numi； ,选择法排序,void DataSort(int score, long num, int n) int i, j, k, temp1; long temp2; for (i=0; i scorek) k = j; /*记录最大数下标位置*/ if (k != i) /*若最大数不在下标位置i*/ temp1 = scorek; scorek = scorei;

26、 scorei = temp1; temp2 = numk; numk = numi; numi = temp2; ,冒泡法排序,【例4】用冒泡法对数组元素进行排序，排序后元素按数值从小到大顺序排列 冒泡排序： 依次比较相邻的两个数，将大数上升（放右边） 第一趟：首先比较第1个和第2个数，将大数放右边。然后比较第2个数和第3个数，如此继续，直至比较最后两个数，结果是将最大数放最右边。 第二趟：重复以上过程，仍从第一对数开始比较，将大数放右边，一直比较到倒数第二对数，第二趟结束，得到一个次大数。 如此下去，直至最终完成排序。 由于排序过程如同冒气泡，所以称作冒泡排序,冒泡法排序,for (i=0

27、; i aj+1) 交换aj和aj+1;,for (i=0; i ak) k = j; /*记录最大数下标位置*/ if (k!= i) /*若最大数不在下标位置i*/ 交换aj和ak; ,for (i=0; i ai) 交换aj和ai“;,冒泡法,交换法,选择法,快速排序, Quick Sort,基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 整个排序过程需要三步： 寻找一个中心元素（通常为第一个数） 所有小于中心点的元素，都移到中心点的左边；所有大于中心点的元素，都移到中心点的右边。

28、 对中心点左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。,快速排序讲解,需要解决的问题 当已知中心元素的前提下，怎样将其他元素划分好？（即：大于中心点在之后，小于中心点在之前）,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,算

29、法终止,可以申请一个变量保存中心元素，以避免交换,快速排序函数,void QuickSort(int *arr, int left, int right) int i,j,temp; if(lefttemp /对中心点右半部递归调用本函数 ,*arr为数组指针，下一章讲解,快速排序函数qsort调用,在头文件中，提供了一个快速排序函数qsort，它的函数原型如下： void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *); 四个参数分别是： 1 待排序数组首地址 2 数组中待排序元素数量 3

30、 各元素的占用空间大小 4 指向函数的指针，用于确定排序的顺序 要求学完指针后能熟练调用，有余力的同学可以先学习先用 ,线性表：二级C重点之一,表中除首元素和尾元素外，每个元素都有且只有一个前驱；有且只有一个后继。 a0ai-1,ai,ai+1aN-1 数组和链表是线性表的两种实现方式。 链表选学,数组应用举例,例1假设数组a中已有5个整数，要插入一个数x到第1个数前面并保持这5个数的前后关系不变，试编程实现,分析： 数组最终存放6个元素，应定义数组a6,X,4,3,2,1,5,1,数组应用举例,#include #define N 5 int main() int i, x, aN+1 ;

31、printf(Input %d numbers:, N ) ; for( i=0; i0; i- ) ai = ai-1 ; ai = x ; / a0=x printf(After insert: ); for( i=0; iN+1; i+ )printf(%d, ai); printf(n); return 0; ,后移并插入数据,数组应用举例,【例2】随机产生20个整数保存在数组中，试用顺序查找方法查找某个整数。 分析： 产生随机数：使用函数srand()和rand() 顺序查找：从数组的第1个元素开始逐一与要查找的数据进行比较，如果有一个元素与之相同，就是找到了，查找过程即可结束。如果

32、所有元素都不同于要查找的数据，则没找到。,数组应用举例,#include #include #include #define N 20 int main ( ) int i, 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，并使原来的顺序关系不变，试编程实现。 问题分析： 主要解决两个关键问题： 查找某个元素是否等于x：用顺序查找法 找到后删除该元素：该元素后的数