《c语言程序设计13第十二讲(第六章上).ppt》由会员分享，可在线阅读，更多相关《c语言程序设计13第十二讲(第六章上).ppt（57页珍藏版）》请在金锄头文库上搜索。
1、编程就是不断编程！编程就是不断编程！1高级语言程序设计高级语言程序设计主讲教师：贾彩燕主讲教师：贾彩燕计算机与信息技术学院计算机与信息技术学院计算机科学与技术系计算机科学与技术系2课程内容课程内容第一章第一章 程序设计和程序设计和C C语言语言第二章第二章 数据对象与计算数据对象与计算第三章第三章 变量、函数和控制结构变量、函数和控制结构第四章第四章 基本程序设计技术基本程序设计技术第五章第五章 C C程序结构（函数）程序结构（函数）第六章第六章 数组数组第七章第七章 指针指针第八章第八章 文件和输入输出文件和输入输出第九章第九章 结构和其它数据机制结构和其它数据机制第十章第十章 程序开发技术
2、程序开发技术第十一章第十一章 标准库标准库3第六章第六章 数组数组4语言需要提供一套语言需要提供一套数据机制数据机制，描述与数据有关的问题：，描述与数据有关的问题：n必须足够丰富，以满足需要；必须足够丰富，以满足需要；n不能过庞杂，臃肿难用；不能过庞杂，臃肿难用；n也不能太低级，使描述过于烦琐。也不能太低级，使描述过于烦琐。高级语言的高级语言的数据机制数据机制：n把数据分为类型，每个类型是一个数据集。把数据分为类型，每个类型是一个数据集。n提供一组基本数据类型；确定其书写方式；为各类型提供一组基本操作。提供一组基本数据类型；确定其书写方式；为各类型提供一组基本操作。n提供一组由简单数据类型或对
3、象构造复合数据类型或对象的机制。提供一组由简单数据类型或对象构造复合数据类型或对象的机制。组组合合的的数数据据对对象象称称为为复复合合数数据据对对象象。由由所所有有“同同类类的的”复复合合对对象象形成的类型称为形成的类型称为复合数据类型复合数据类型，组成部分称为，组成部分称为成分成分/成员成员/元素元素。5基本类型构造类型指针类型空类型void定义类型typedef数值类型字符类型char8位枚举类型enum整 型浮点型单精度型float32位双精度型double64位短整型short16位长整型long32位整型int16位数组结构体struct共用体unionC C 数据类型数据类型由基本
4、类型数据按一定规则组成的，也称为“导出类型”数组数组6问题:输入学生的学号,成绩, 计算平均成绩, 计算每个学生的成绩与平均成绩的差, 差=10 成绩等级 A 0=差10 成绩等级 B 其它 成绩等级 C 设:学号 double n1,n2,n3,n4, n30; 成绩 double s1,s2,s3,s4, s30;能否:一个变量名对应多个连续的存储单元:数组数组数组数组是程序中最常用的结构数据类型，用来描述由是程序中最常用的结构数据类型，用来描述由固固定数目定数目的的同一类型同一类型的元素组成的数据结构的元素组成的数据结构7n数组的概念、定义和使用数组的概念、定义和使用n数组程序实例数组程
5、序实例n数组作为函数参数数组作为函数参数n字符数组和字符串字符数组和字符串n两维和多维数组两维和多维数组n编程实例编程实例主要内容主要内容86.1 数组的概念、定义和使用数组的概念、定义和使用n数组（数组（array）:是多个是多个同类型同类型数据对象的组合。数据对象的组合。n一个数组汇集了多个数据项，一个数组汇集了多个数据项，数组元素数组元素。n可从数组出发处理各元素，以统一方式处理一批可从数组出发处理各元素，以统一方式处理一批/所所有元素，是有元素，是数组数组和和一组独立变量一组独立变量的主要区别。的主要区别。为此需要：为此需要：n数组描述数组描述，数组变量定义，初值化，数组变量定义，初值
6、化n数组使用数组使用，包括通过数组变量使用其元素，包括通过数组变量使用其元素n数组实现数组实现，数组的存储方式，数组的存储方式9数组变量定义数组变量定义定义数组变量（定义数组变量（定义数组定义数组）时需说明：）时需说明：n数组元素类型数组元素类型n数组（变量）名数组（变量）名n数组（变量）的元素个数（也称数组数组（变量）的元素个数（也称数组大小大小或或长度长度）v定义方式：定义方式： 数据类型数据类型 数组名数组名常量表达式常量表达式； 例，定义两个数组：例，定义两个数组：inta10;doublea1100;数组定义可以与其他变量定义写在一起，如：数组定义可以与其他变量定义写在一起，如：in
7、ta216,n,a325,m;方方括括号号内内整整型型表表达达式式说说明明元元素素个个数数，表表达达式式应应能能静静态态确确定定值值，可用可用字面量字面量或或枚举常量枚举常量10可可定定义义外外部部数数组组和和局局部部数数组组，包包括括局局部部静静态态数数组组（用用static）,作用域与存在期与简单变量相同。作用域与存在期与简单变量相同。数组的外部说明不必描述数组大小。例：数组的外部说明不必描述数组大小。例：externinta;externdoublea1;下面函数里数组定义不合法：下面函数里数组定义不合法：voidf(intm,intn)intbn;/*非法，编译时无法确定大小非法，编译
8、时无法确定大小*/.新新 C99 标准支持这种定义，满足标准支持这种定义，满足 C99 的编译器很少的编译器很少11基本操作是元素访问。元素顺序编号，首元素序号基本操作是元素访问。元素顺序编号，首元素序号0，其余顺，其余顺序编号。序编号。n元数组元素编号是元数组元素编号是0到到n-1。定义：定义：intb100;元素编号为元素编号为0、1、2、99。称为。称为下标下标或或指标指标。元元素素访访问问通通过过运运算算符符，优优先先级级最最高高，运运算算对对象象是是数数组组名名和和括号里表示下标的表达式。括号里表示下标的表达式。表达式、语句里的表达式、语句里的b3称为称为下标表达式下标表达式或或带下
9、标的变量带下标的变量。例：有上面定义后，可写：例：有上面定义后，可写：b0=1;b1=1;b2=b0+b1;b3=b1+b2;数组的使用数组的使用12数数组组的的真真正正意意义义在在于于能能以以统统一一方方式式描描述述对对一一组组数数据据的的处处理理。下标表达式下标表达式可用一般的整型表达式。如：可用一般的整型表达式。如：bi=bi-1+bi-2;访访问问哪哪个个元元素素由由i值值确确定定。同同一一语语句句可可访访问问不不同同元元素素，可可用用在在循环里访问一批元素。循环里访问一批元素。for(i=0;i100;+i)bi+=a1i*a2i;/*假设数组都有定义假设数组都有定义*/循环中涉及到
10、循环中涉及到300个基本数据对象。个基本数据对象。13#includeintmain()longfib30;intn;fib0=1;fib1=1;for(n=2;n30;+n)fibn=fibn-1+fibn-2;for(n=0;n30;+n)printf(%d,fibn);putchar(n%6=5?n:);/*6个数输出一行个数输出一行*/return0;例例：写写程程序序创创建建包包含含前前30个个Fibonacci数数的的数数组组，然然后后打打印印数数组中所有的数。组中所有的数。14对数组的多个或全部元素操作，常用对数组的多个或全部元素操作，常用for语句。语句。令令循环变量循环变量遍
11、历数组下标：遍历数组下标：for(n=0;n数组长度数组长度;+n).问题：问题：fib是是30个元素的数组，假设程序里写：个元素的数组，假设程序里写：for(n=2;n=30;+n)fibn=fibn-1+fibn-2;循环中试图访问循环中试图访问fib30，实际无此元素。实际无此元素。用用超超范范围围的的下下标标访访问问称称为为越越界界访访问问，是是数数组组使使用用中中最最常常见见的的错错误误。下标值超范围是运行中的问题下标值超范围是运行中的问题。C不检查数组元素访问的合法性，运行中出现越界不会报错。不检查数组元素访问的合法性，运行中出现越界不会报错。超超范围访问是严重错误，后果无法预料范
12、围访问是严重错误，后果无法预料。15数组的实现数组的实现数数组组占占据据一一片片连连续续存存储储区区，元元素素顺顺序序排排列列，0号号元元素素在在最最前前面面，各元素占相同空间。如有：各元素占相同空间。如有：inta8;a的存储恰好能存放的存储恰好能存放8个整型数据，情况如图：个整型数据，情况如图：a至至少少相相当当于于8个个int变变量量，a0 a7可可以以看看作作“变变量量名名”。保证元素排在一起，能以统一方式使用。保证元素排在一起，能以统一方式使用。数组名表示内存首地址，数组名表示内存首地址，是是地址常量地址常量编译时分配连续内存编译时分配连续内存内存字节数内存字节数=数组元素个数数组元
13、素个数* sizeof(元素数据类型元素数据类型)16在一些系统里越界访问可能导致动态错，系统强行终止出错的在一些系统里越界访问可能导致动态错，系统强行终止出错的程序。越界可能破坏本程序的数据程序。越界可能破坏本程序的数据/程序本身程序本身/其他软件，甚至其他软件，甚至 是整个系统。是整个系统。编程者要保证数组下标值的合法性，保证不越界。编程者要保证数组下标值的合法性，保证不越界。数组初始化数组初始化定义数组时可直接初始化。外部、局部静态或自动数组都可在定定义数组时可直接初始化。外部、局部静态或自动数组都可在定义时进行初始化。义时进行初始化。方法一：定义时直接初始化方法一：定义时直接初始化in
14、tb4=1,1,2,3;doubleax6=1.3,2.24,5.11,8.37,6.5;初值表达式必须是常量表达式。初值表达式必须是常量表达式。外部和静态数组在程序开始执行前建立并初始化，局部自动数外部和静态数组在程序开始执行前建立并初始化，局部自动数组在程序执行进入相应函数或复合语句体时建立和初始化组在程序执行进入相应函数或复合语句体时建立和初始化17这种写法只能用于数组初始化，这种写法只能用于数组初始化，不能用在语句里不能用在语句里。若若定定义义时时未未初初始始化化，外外部部和和局局部部静静态态数数组组的的元元素素自自动动初初始始化化为为0；自动数组处在不明确的状态。；自动数组处在不明确
15、的状态。方方法法二二：只只为为部部分分元元素素提提供供初初值值，其其余余元元素素将将自自动动置置0。初初始始化化表元素个数不得超过数组元素个数。例：表元素个数不得超过数组元素个数。例：intb14=1,2;b12、b13将给初值将给初值0。方方法法三三：若若给给了了所所有有元元素素的的初初值值，可可以以不不写写数数组组大大小小而而只只写写方方括括号号，元素个数由初值个数确定。例：，元素个数由初值个数确定。例：intfib=1,1,2,3,5,8,13,21,34,55;这种写法能减少维护负担，有利于程序修改。这种写法能减少维护负担，有利于程序修改。在语句中对数据在语句中对数据元素赋值的方法元素
16、赋值的方法？18说明：数组必须先定义，后使用只能逐个引用数组元素，不能一次引用整个数组数组元素表示形式： 数组名下标其中：下标可以是常量或整型表达式/顺序输入输出数组元素顺序输入输出数组元素#include void main()int i, a10; for (i = 0; i 10; i+) ai = i; for (i = 0; i = 9; i+) printf(“%4d”, ai); /将数组元素逆序输出将数组元素逆序输出#include void main()int i, a10; for (i = 0; i 10; i+) ai = i; for (i = 9; i = 0; i
17、-) printf(“%4d”, ai); 例一维数组的输入与输出。例一维数组的输入与输出。19n数组的概念、定义和使用数组的概念、定义和使用n数组程序实例数组程序实例n数组作为函数参数数组作为函数参数n字符数组和字符串字符数组和字符串n两维和多维数组两维和多维数组n编程实例编程实例主要内容主要内容206.2 数组处理程序实例数组处理程序实例从字符到下标（整数）从字符到下标（整数）写程序统计由标准输入得到的文件中数字字符的个数。写程序统计由标准输入得到的文件中数字字符的个数。 可可定定义义10个个计计数数变变量量，用用if或或switch区区分分情情况况，遇遇数数字字字字符符（isdigit）
18、时对应计数器加时对应计数器加1。不需要数组。不需要数组。将将字字符符看看作作整整数数可可得得到到另另一一解解法法。常常见见字字符符集集里里数数字字顺顺序序排排列列，ASCII字符集里字符集里0到到9的编码是的编码是48到到57。利利用用这这个个事事实实，用用10个个元元素素的的计计数数器器数数组组可可以以更更方方便便地地完完成成对对数数字出现的统计。字出现的统计。21intcs10;用用cs0记记录录0出出现现次次数数，余余类类推推。若若c是是数数字字，对对应应计计数数器器加加1可以写成：可以写成：+csc-0;/*c-0正是对应计数器的下标正是对应计数器的下标*/#include#inclu
19、deintcs10=0,0,0,0,0,0,0,0,0,0;intmain()intc,i;while(c=getchar()!=EOF)if(isdigit(c)+csc-0;for(i=0;i10;+i)printf(Digit%d:%dn,i,csi);return0;22例例1 筛法求素数筛法求素数筛筛法法是是求求素素数数的的著著名名方方法法：用用空空间间换换时时间间，1亿亿以以内内的的素素数数只只需要十几秒的时间需要十几秒的时间(如不考虑输出如不考虑输出)具体算法：取具体算法：取2开始的整数序列：开始的整数序列：1.令令n等于等于2，它是素数；，它是素数；2.划掉序列中所有划掉序列中
20、所有n的倍数；的倍数；3.令令n等于下一未划元素（它是素数），回到步骤等于下一未划元素（它是素数），回到步骤2。用数组表示整数序列，以元素下标表示对应整数。用数组表示整数序列，以元素下标表示对应整数。数组数组an，an0代表代表0，ani代表代表i。每个数只需表示划掉或未划掉，每个数只需表示划掉或未划掉，用用0/1表示。表示。开开始始时时元元素素置置1（即即假假设设所所有有元元素素都都是是素素数数），而而后后不不断断将将元元素素置置0，直到确定了给定范围里的所有素数。，直到确定了给定范围里的所有素数。 23假设假设NUM是给定范围：是给定范围：/*建数组建数组an，元素初始化元素初始化1，将将
21、an0和和an1置置0（它们不是素数）（它们不是素数）*/for(inti=2;i值不大于某个数值不大于某个数;+i)if(ani=1)/i是素数是素数for(intj=i*2;jNUM;j+=i)anj=0;/*i的倍数都不是素数的倍数都不是素数*/外层循环何时结束？可用外层循环何时结束？可用NUM作为界限。作为界限。检检验验一一个个数数是是不不是是素素数数，只只要要看看比比它它的的平方根小小的的素素数数是是不不是是能能整整除除它它 ，因因此此只只要要i超超过过NUM的的平平方方根根，就就可可以以划划掉掉到到既既定定范范围围内内的所有合数。的所有合数。 1 2 3 4 5 6 7 8 9 1
22、0 11 12 13 14 15 16 17 18 19 20 21 22 23 24 251不算不算遍历一遍，划掉遍历一遍，划掉2的倍数：得的倍数：得2 3 5 7 9 11 13 15 17 19 21 23 25遍历一遍，划掉遍历一遍，划掉3的倍数：得的倍数：得2 3 5 7 11 13 17 19 23 25遍历一遍，划掉遍历一遍，划掉5的倍数：得的倍数：得2 3 5 7 11 13 17 19 2324#includeenumNUM=200;intanNUM+1;intmain(void)inti,j;an0=an1=0;/*建立初始向量建立初始向量*/for(i=2;i=NUM;+
23、i)ani=1;for(i=2;i*i=NUM;+i)if(ani=1)for(j=i*2;j=NUM;j+=i)anj=0;for(i=2,j=0;i=NUM;+i)if(ani!=0)printf(%d,i);putchar(n);return0;25例例2：成绩分类：成绩分类写写程程序序输输入入一一批批学学生生成成绩绩（200）。先先输输出出不不及及格格成成绩绩，再再输输出出及格成绩，最后输出不及格和及格的人数。及格成绩，最后输出不及格和及格的人数。 无无法法在在输输入入过过程程中中完完成成(除除非非输输入入两两遍遍)。用用数数组组记记录录学学生生成成绩绩，输入记入数组，而后输出，可避免
24、重复输入输入记入数组，而后输出，可避免重复输入 数据装入数组后有许多可能处理方法。数据装入数组后有许多可能处理方法。最最简简单单的的是是两两次次扫扫描描数数组组，第第一一次次输输出出不不及及格格成成绩绩，第第二二次次输输出及格的成绩。出及格的成绩。统统计计工工作作可可在在某某次次扫扫描描中中完完成成（也也可可在在输输入入中中完完成成），两两部部分分人数之和就是总人数，统计一部分就够了。人数之和就是总人数，统计一部分就够了。 26enumNUM=200;constdoublePASS=60.0;doublescoresNUM;intmain()inti,n=0,fail;while(nNUM&s
25、canf(%lf,&scoresn)=1)+n;/*输入时需要判断不越界输入时需要判断不越界*/for(fail=0,i=0;in;+i)if(scoresiPASS)printf(%fn,scoresi);+fail;for(i=0;i=PASS)printf(%fn,scoresi);printf(Fail:%dnPass:%dn,fail,n-fail);return0;27例例3多项式求值多项式求值设数组设数组p中存放下列多项式的系数，中存放下列多项式的系数，其中其中pi存放存放写程序求写程序求p表示的多项式在指定点的值。表示的多项式在指定点的值。方法方法1：求出各项值累加。假设指定点
26、值存于：求出各项值累加。假设指定点值存于x：for(sum=0.0,n=0;nTERMS;+n)for(t=pn,i=1;i=n;+i)t*=x;sum+=t;循环体内可以改写为（先算循环体内可以改写为（先算x的幂）：的幂）：for(t=1.0,i=1;i=n;+i)t*=x;sum+=t*pn;可发现有大量重复计算。可发现有大量重复计算。28通过保存前次的通过保存前次的t值：值：for(sum=0.0,t=1.0,n=0;n=0;-n)sum=sum*x+pn;从计算量上比较它们：需要多少次加法，多少次乘法从计算量上比较它们：需要多少次加法，多少次乘法。29定义数组的问题定义数组的问题如如果
27、果数数组组表表示示的的是是全全局局数数据据集集合合，需需要要在在多多个个函函数数里里使使用用，那那么可考虑定义为外部数组。么可考虑定义为外部数组。大大的的数数组组应应定定义义为为外外部部，以以免免占占大大量量运运行行栈栈空空间间。一一般般系系统统不不允许在函数内定义特别大的数组。允许在函数内定义特别大的数组。 若若数数组组保保存存着着递递归归定定义义函函数数的的局局部部数数据据，就就必必须须定定义义为为自自动动数数组。因为递归调用时需要数组的多份拷贝。组。因为递归调用时需要数组的多份拷贝。其他情况可以根据需要自由选择。其他情况可以根据需要自由选择。 30n数组的概念、定义和使用数组的概念、定义
28、和使用n数组程序实例数组程序实例n数组作为函数参数数组作为函数参数n字符数组和字符串字符数组和字符串n两维和多维数组两维和多维数组n编程实例编程实例主要内容主要内容316.3 数组作为函数参数数组作为函数参数n 数组可以作为函数的参数，但是在向函数传递数组时数组可以作为函数的参数，但是在向函数传递数组时通常有两种方法：即：通常有两种方法：即：q “ “地址地址”的传递的传递q “ “值值”的传递的传递 32方法一：方法一： 用数组名作为实际参数，给函数传递数组的地址，通过这个地址就用数组名作为实际参数，给函数传递数组的地址，通过这个地址就可以访问到数组的元素了可以访问到数组的元素了双向传递双向
29、传递。#include#define N 20 void f(int b , int n , int m) int i; for (i = m; i = n; i-) bi+1 = bi;void main() int i, aN = 1,2,3,4,5,6,7,8,9,10; f(a, 2, 9); for (i = 0; i 5; i+) printf(“%4d”, ai); a12345678910 b1098764531233433方法二：方法二： 用数组元素作为实际参数，是一种传值的方式，即：调用用数组元素作为实际参数，是一种传值的方式，即：调用函数时要复制数据函数时要复制数据 单向
30、传递单向传递。 #include int fmax(int x, int y) return (x y ? x : y ) ; void main() int a10, j, max ; for (j = 0; j = 9; j+) scanf(“%d”, &aj); max = a0; for (j = 1; j = 9; j+) max = fmax(max, aj ) ; printf(“n最大值为最大值为：%8dn”, max); 34对函数参数的小结：对函数参数的小结：“值值”传递传递形参和实参都是普通变量形参和实参都是普通变量实参是数组元素，形参是普通变量实参是数组元素，形参是普通
31、变量“地址地址”传递：形参、实参都是数组名，完成传递：形参、实参都是数组名，完成双向传双向传递递。完成完成单向单向传递传递35假设有多个数组都需要求平均值假设有多个数组都需要求平均值?解决方法：解决方法：定义以数组为参数的函数定义以数组为参数的函数。n以数组为参数，不同调用可以完成对不同数组的计算。以数组为参数，不同调用可以完成对不同数组的计算。n定义以定义以double类型的数组为参数求元素平均值的函数，就可类型的数组为参数求元素平均值的函数，就可解决所有解决所有double数组的平均值问题数组的平均值问题设常量设常量LEN是被处理数组的长度。是被处理数组的长度。doubleavg0(dou
32、blea)doublex=0.0;inti;for(i=0;iLEN;+i)x+=ai;returnx/LEN;/*注意：数组形参不需要写数组大小注意：数组形参不需要写数组大小*/36若数组若数组a1长长LEN，可用：可用：x=avg0(a1);avg0有有一定一定通用性，若数组通用性，若数组a2长度也是长度也是LEN：y=avg0(a2);用符号常量指定数组大小可解决许多问题。用符号常量指定数组大小可解决许多问题。缺点缺点：若数组长度不是：若数组长度不是LEN，就不能用就不能用avg0处理。处理。可见：可见：avg0不够通用不够通用，只能正确处理长为，只能正确处理长为LEN的数组。的数组。参
33、数参数是使函数能处理一类问题的基本机制。是使函数能处理一类问题的基本机制。为为提提高高数数组组处处理理函函数数的的通通用用性性，定定义义时时应应引引进进长长度度参参数数，使使函函数数能处理任何能处理任何给定长度给定长度的数组。的数组。37改造后的函数：改造后的函数：doubleavg(intlen,doublea)doublex=0.0;inti;for(i=0;ilen;+i)x+=ai;returnx/len;对调用提出的新要求对调用提出的新要求：必须正确提供数组长度。：必须正确提供数组长度。应用实例：应用实例：intmain()doubleb1=1.2,2.43,1.74,b2=6.5,
34、9.2,8.6,4.5,0.3;printf(%f,%fn,avg(3,b1),avg(5,b2);return0;38长度参数提高了函数的通用性。长度参数提高了函数的通用性。但但使使用用时时必必须须关关注注越越界界问问题题。avg(5,b1)引引起起数数组组越越界界（b1有有3个元素个元素）。）。长长度度实实参参可可小小于于数数组组大大小小，avg(3,b2)求求b2前前3个个元元素素的的平均值。平均值。可将数组前段当作数组使用。可将数组前段当作数组使用。39例例4 4：将：将a a数组的内容按颠倒的次序重放，在操作时，只能借助一个临数组的内容按颠倒的次序重放，在操作时，只能借助一个临时存储
35、单元而不能另外开辟数组。时存储单元而不能另外开辟数组。互换偶数个元素不动奇数个元素互换40voidrev(intn,inta)intx,i,m=n/2;for(i=0;im;+i)x=ai;ai=an-i-1;an-i-1=x; 自己添加主程序自己添加主程序另一写法：另一写法：for(i=0,j=n-1;ij;+i,-j)x=ai;ai=aj;aj=x;41n数组的概念、定义和使用数组的概念、定义和使用n数组程序实例数组程序实例n数组作为函数参数数组作为函数参数n字符数组和字符串字符数组和字符串n两维和多维数组两维和多维数组n编程实例编程实例主要内容主要内容一维数值型数组的重要应用一维数值型数
36、组的重要应用42一维数组上的重要操作一维数组上的重要操作n排序排序n查找查找n插入插入n删除删除n元素交换元素交换43n将计算机学院将计算机学院08级学生按平均分高低排序级学生按平均分高低排序n将将08的奥运会各参赛国按英文字典序排序的奥运会各参赛国按英文字典序排序n搜索引擎网页排序搜索引擎网页排序(PageRank)learning to ranknn排序问题无处不在排序问题无处不在例例1 1一维数组的应用（排序）一维数组的应用（排序）44常用的排序算法常用的排序算法n冒泡排序冒泡排序n选择排序选择排序n插入排序插入排序n快速排序快速排序n45冒泡排序法冒泡排序法 输入输入n n个正整数存在
37、数组中，按由小到大的顺序排序个正整数存在数组中，按由小到大的顺序排序（最大的数下沉最大的数下沉）例例38 49 65 76 13 27 30 97 第第一一趟趟38 49 65 13 27 30 76 第第二二趟趟38 49 13 27 30 65 第第三三趟趟38 13 27 30 49 第第四四趟趟13 27 30 38 第第五五趟趟13 27 30 第第六六趟趟49 38 65 97 76 13 27 30 初初始始关关键键字字n=838497697139797273097137676762730136527653065131349493049273827383038 13 27 第第七
38、七趟趟a0a1a2a3a4a5a6a746用冒泡法对用冒泡法对1010个数进行排序（个数进行排序（N-SN-S图及程序）图及程序）变量、数组长度定义变量、数组长度定义 for(j=0;j=N-i-1;j+) scanf ( “%d” , &ai ) for(i=0;iN;i+) for(i=0;iaj+110 aj与与aj+1交换交换 for(i=1;i=N-1;i+) printf ( “%6d”, ai )/*/*冒泡法对冒泡法对1010个数由小到大排序个数由小到大排序* */ /#include #define N 10void main() int aN , i , j , t; pr
39、intf(请输入请输入10个数个数:n); for ( i = 0 ; i N ; i+) scanf(%d,&ai); printf(n); for (i = 1; i = N-1; i+) for (j = 0; j aj+1) t = aj; aj = aj+1; aj+1 = t; printf(n排序后的数据为排序后的数据为:n); for (i = 0; i 课后作业课后作业nn值值如果是如果是可变可变的的?n如果只对如果只对部分数据部分数据进行进行排序排序？n某趟循环未发生交换，后面可不再循环，某趟循环未发生交换，后面可不再循环， 如如何改进何改进冒泡排序冒泡排序?48void
40、BubbleSort(int n, int a )int flag, i, j;for (i = 1; i = n-1; i+) flag = 0; for (j = 0; j aj+1) t = ai;ai = ai+1; ai+1 = t;flag = 1;if ( !flag ) return; 改改进进的的冒冒泡泡排排序序（函函数数）：设设标标志志flag，如如果果某某趟趟未未发发生生交交换，换，flag=0，说明排序完成，返回。说明排序完成，返回。49将数组将数组a中的前中的前5个数进行排序个数进行排序#include void BubbleSort(int n, int a );i
41、nt main()int a10 , i , j , t; printf(请输入请输入10个数个数:n); for( i = 0 ; i 10 ; i+) scanf(“%d”, &ai); BubbleSort(5, a); for( i = 0 ; i 10 ; i+) printf(“%d”, ai); return 0;50冒泡排序算法的复杂度分析冒泡排序算法的复杂度分析n最坏情形下扫描数据总数最坏情形下扫描数据总数qn*(n+1)/2n最坏情形下数据交换的次数最坏情形下数据交换的次数qn*(n-1)/251选择法排序：选择法排序：把把n n个正整数按由小到大的顺序排序。个正整数按由小
42、到大的顺序排序。例例初始：初始： 49 38 65 97 76 13 27 kji=11349一趟：一趟： 13 38 65 97 76 49 27 i=22738二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 27 38 49 65 97 76 六趟：六趟： 13 27 38 49 65 76 97 kkkkjjjjjjjjjj52用选择法对用选择法对1010个数进行排序（个数进行排序（N-SN-S图及程序）图及程序）/*选择法对选择法对10个数由小到大
43、排序个数由小到大排序*/#include #define N 10void SelectSort(int n, int a);void main()int aN, i;for (i = 0; i N; i+) scanf(%d, &ai);printf(n);SelectSort(N, a);printf(the sorted numbers:n);for (i = 0; i N; i+) printf(%4d, ai);printf(n);变量、数组长度定义变量、数组长度定义k=ifor(j=i+1;jN;j+) scanf ( “%d” , &ai ) for(i=0;iN;i+) for
44、(i=0;iN;i+) ajak10k=j for(i=0;iN-1;i+) printf ( “%4d”, ai ) ai与与ak交换交换53void SelectSort(int n, int a) int i, j, k, t; for (i = 0; i n-1; i+) k = i; for (j = i+1; j n; j+) if (aj ak) k = j; t = ak; ak = ai; ai = t; 可否优化？如何优化？可否优化？如何优化？54选择排序算法的复杂度分析选择排序算法的复杂度分析n最坏情形下扫描数据总数最坏情形下扫描数据总数qn*(n+1)/2n最坏情形下数据交换的次数最坏情形下数据交换的次数qn1次次55作业作业n将一个数组中的值按逆序重新存放，如：原来将一个数组中的值按逆序重新存放，如：原来顺序为顺序为8,6,7,4,10，要求改为，要求改为10,4,7,6,8。n分别写函数用冒泡和选择两种排序方法实现分别写函数用冒泡和选择两种排序方法实现n(如如n=10)个数从大到小排序个数从大到小排序nP215q7q8q12.1,12.2(要求在主程序中调用相应的两个函数要求在主程序中调用相应的两个函数)q1556Q & A!57
