C语言程序设计ppt第8章课件.ppt

2023/1/4,华中科技大学计算机学院,1,C语言程序设计,The C Programming Language,华中科技大学计算机学院曹计昌,2023/1/4,华中科技大学计算机学院,2,C语言程序设计,第8章 数组 一维数组的声明、初始化和使用 数组的运算、作为函数参数的使用 字符串、多维数组同时包括:字符串操作函数,数字串与数之间的转换函数,二分查找,排序等程序的设计.相关算法和程序设计方法要熟练掌握.,2023/1/4,华中科技大学计算机学院,3,8.1 数组概述,程序=算法+数据结构PASCAL程序设计语言发明者Niklaus Wirth曾经说过 简单数据类型的变量仅能描述一个单独的数据对客观对象的描述能力十分有限 如何描述一群有联系的数据集合？(全班C语言考试成绩)数组属于构造类型是相同数据类型数据的集合(不同数据类型数据如何考虑?如学生对象有学号,姓名性别,年龄,各科成绩等属性)元素 组成数组的这些数据任何类型(简单类型、构造类型),2023/1/4,华中科技大学计算机学院,4,8.1 数组概述,数组特点其所有元素数目固定其所有元素类型相同其所有元素顺序存放(在内存中也是连续存放的)数组作用集中管理将相关的同类型数据集中用一个标识符（数组名）表示元素顺序存放，但可随机定位用若干个数字序号（下标）来区别各数组元素例如定义float score30，可表述30位学生成绩 用数组具有什么好处？,2023/1/4,华中科技大学计算机学院,5,8.1 数组概述,问题计算全班30位同学某门课程的平均成绩 解决方法设置30个float型变量来记录成绩设置一个有30个float型元素的数组来记录成绩问题分析参与运算的平均成绩，其数据类型都相同(符合数组特点)30位同学属于一个班，用数组可把30个成绩表示成一个整体用数组的优点便于循环处理提高效率，便于书写、检查、修改(对海量数据效果更明显),2023/1/4,华中科技大学计算机学院,6,8.2 一维数组,维数 标识一个数组元素所需要使用的下标的个数 一维数组只有一个下标可用于表示一个线性的数据队列 使用数组的要求先声明数组对它进行初始化，然后才能使用,2023/1/4,华中科技大学计算机学院,7,8.2.1 一维数组的声明,要解决三个问题确定数组的数据类型给数组定义一个名字，以便在程序中使用指明数组的大小，即数组中元素的个数 声明形式存储类型说明符 类型修饰符 类型说明符 数组名常量表达式=初值表；存储类型说明符：extern、static 类型修饰符：const、volatile 类型说明符:int、char、数组名：是一个标识符，是一个地址常量，用以表示数组中打头元素的地址,2023/1/4,华中科技大学计算机学院,8,8.2.1 一维数组的声明,例8.1 具有基本数据类型的一维数组的声明#define SIZE 10int array5;double d5,eSIZE;char nameSIZE*5;错误例子unsigned int size;char strsize,buffer2*size;错误原因数组的大小一经说明就不能改变长度说明不是表达式，在编译之前就必须明确确定,2023/1/4,华中科技大学计算机学院,9,8.2.1 一维数组的声明,例8.2 采用类型修饰符的一维数组的声明static int y10;数组y中的每一个成员都是静态整型成员extern double s2;作了一个外部双精度型数组的引用性声明应该在另外的源文件中通过double s2;来定义s数组，这样第2个声明语句才有意义,2023/1/4,华中科技大学计算机学院,10,8.2.2 一维数组的使用,C提供的各种操作符 针对基本数据类型的变量数组是构造数据类型但其元素是基本数据类型的变量访问数组不需设计专门的数组操作符方法：数组名下标表达式例int a5,j=2；5个元素依次是a0,a1,a2,a3,a4正确用法：aj+2、a+j、aj-、a5*j-7 错误用法：aj-3、a2*j+1,2023/1/4,华中科技大学计算机学院,11,例8.3 使用一维数组计算学生的平均成绩。,#include stdio.hvoid main(void)int score30,i,sum=0;double average;printf(input the scores please:n);for(i=0;i30;i+)scanf(“%d”,/*将键盘输入的成绩赋给各个数组元素*/,for(i=0;i30;i+)sum+=scorei;/*求学生成绩的累加和*/average=sum/30.0;/*计算平均成绩*/printf(sum=%dn,sum);printf(average=%lfn,average);演示EX8_3.C,2023/1/4,华中科技大学计算机学院,12,8.2.3 一维数组的初始化,显式初始化值的个数与说明长度相同int x5=0,1,2,3,4;int y5=0,1,2,3,4,5;错误：初值个数大于数组长度有初始化值时，长度说明可缺省数组长度由初值个数确定int y=1,2,3,4,5,6,7,8;初始化值的个数可以小于说明长度，但只能缺省最后连续元素的初值int z10=0,1,2,3,4;/*前5个下标变量赋值*/int u9=,1,2;错误：缺省u0,u2不是最后连续元素,2023/1/4,华中科技大学计算机学院,13,例8.8 观察局部数组、静态数组和外部数组的缺省初值的程序,#include stdio.hdouble s2;void main(void)int a2,i;static int b2;for(i=0;i2;i+)printf(s%d=%dn,i,si);printf(a%d=%dn,i,ai);printf(b%d=%dn,i,bi);演示EX8_8.C,程序的运行结果如下：s0=0,a0=64,b0=0 s1=0,a1=3129,b1=0结论：外部数组s和静态数组b的元素的缺省初值都是0 局部数组a的初值则是随机的,2023/1/4,华中科技大学计算机学院,14,8.2.4 一维数组的存储结构,存放方法各个元素从数组名标明的起始地址开始在内存中连续存放 例如int a5;这里是16位机，1个int变量占2个字节空间,2023/1/4,华中科技大学计算机学院,15,例8.9 观察一维数组的存储情况的程序,#include stdio.h#define SIZE 3void main(void)int xSIZE=1,3,5,k;char sSIZE+1=ABC;float fSIZE=1.414,3.1415,5.25;printf(the value of x is 0 x%xn,x);for(k=0;kSIZE;k+)printf(x%d=%dt addr=0 x%xn,xk,演示EX8_9.C,程序运行结果如下：the value of x is 0 xffc8 x0=1 addr=0 xffc8 x1=3 addr=0 xffca x2=5 addr=0 xffcc,2023/1/4,华中科技大学计算机学院,16,例8.9 观察一维数组的存储情况的程序,k=0;printf(nthe value of s is 0 x%xn,x);while(sk)printf(s%d=%ct addr=0 x%xn,sk,程序运行结果如下：the value of s is 0 xffce s0=A addr=0 xffce s1=B addr=0 xffcf s2=C addr=0 xffd0,s3+X=X addr=0 xffd1the value of f is 0 xffd2f0=1.414000 addr=0 xffd2f1=3.141500 addr=0 xffd6f2=5.250000 addr=0 xffda,2023/1/4,华中科技大学计算机学院,17,8.2.5 一维数组的运算,C提供的各种操作符 赋值运算、各种算术运算、+、-针对基本数据类型的变量可针对int、float、以及double类型数组中元素合法操作 int x3=1,2,3,y3=4,5,6,z3，k=1;z0=x0+y0;z1=x0+y3;zk=+x0+-yk+;z1=x0+yx1;不允许两个数组直接相加z=x+y;编译时给出提示“cannot add two pointers”,2023/1/4,华中科技大学计算机学院,18,数组的直接相加,例8.10 设5个同学修了高等数学普通物理、程序设计语言并取得了成绩，现计算三门课总分、平均分，每门课的总分、平均分，每个同学的总分、平均分#include stdio.h#define SIZE 5void main(void)int mathSIZE=91,67,88,78,81;int physicsSIZE=87,79,81,86,67;int programmingSIZE=86,81,85,92,87;/*3个数组依次存放数学、物理、程序设计的成绩*/,2023/1/4,华中科技大学计算机学院,19,例8.10(演示EX8_10.C),int course_sum3=0,0,0;double course_even3;/*分别为各门课程总分、平均分数组*/int student_sum5=0,0,0,0,0;double student_even5;/*分别为各位同学总分、平均分数组*/int sum=0;double even;/*分别为全部课程的总分、平均分*/int i;,for(i=0;i5;i+)course_sum0+=mathi;course_sum1+=physicsi;course_sum2+=program mingi;/*计算各门课程的总分*/for(i=0;i3;i+)course_eveni=course_su mi/5.0;sum+=course_sumi;/*计算各门课平总分*/even=sum/(3.0*SIZE);/*计算全部课程的平均分*/,2023/1/4,华中科技大学计算机学院,20,例8.10,for(i=0;i5;i+)/*计算每个学生的总分、平均分*/student_sumi=mathi+physicsi+programmingi;student_eveni=student_sumi/3.0;printf(三门课程的总分:%dn,sum);printf(三门课程的平均分:%lfn,even);,程序的运行结果如下 三门课程的总分:1236 三门课程的平均分:82.400000,2023/1/4,华中科技大学计算机学院,21,例8.10,for(i=0;i3;i+)printf(course_sum%d=%dn,i,course_sumi);printf(course_even%d=%lfn,i,course_eveni);,程序的运行结果如下 course_sum0=405 course_even0=81.000000 course_sum1=400 course_even1=80.000000 course_sum2=431 course_even2=86.200000,2023/1/4,华中科技大学计算机学院,22,例8.10,for(i=0;i5;i+)printf(student_sum%d=%dn,i,student_sumi);printf(student_even%d=%lfn,i,student_eveni);,程序的运行结果如下 student_sum0=264 student_even0=88.000000 student_sum1=227 student_even1=75.666667 student_sum2=254 student_even2=84.666667,student_sum3=256student_even3=85.333333student_sum4=235student_even4=78.333333,2023/1/4,华中科技大学计算机学院,23,8.2.6 一维数组作为函数参数,参数的传递 传值 传地址 数组作为函数参数 采用的是参数传址 传送的是数组的地址 或传送数组元素的地址 还需传送数组元素的个数,2023/1/4,华中科技大学计算机学院,24,例8.11 一维数组作为函数参数的例子,#include stdio.hvoid fun(int y,int n);/*y是形式数组*/void main(void)int k,x5=1,2,3,4,5;fun(x,3);fun(void fun(int y,int n)演示EX8_11.C,子函数需给出形式数组的声明和形式数组中元素的个数 调用函数实参的值是数组x的起始地址参数传递,2023/1/4,华中科技大学计算机学院,25,例8.12 对n个整数采用冒泡法对其排序(演示EX8_12.C),分析输入n个数存放在一数组中，便于循环处理排序是将一个数据元素任意的序列按照一定的规则排列成为一个有序的序列void bubble_sort(int a,int n)对an表示的n个整数进行排序处理main()输入n个数；输出n个数检验排序效果,调用bubble_sortsort对n个数排序；,2023/1/4,华中科技大学计算机学院,26,例8.12 冒泡排序,第一遍 从下标为0的元素开始，对两两相邻的元素进行比较如果前一个元素大于后一个元素，就交换这两个元素的值循环n-1次比较在第一遍循环后不仅把最大整数移到数组最末尾（其下标为n-1）（像冒泡）还尽量把较大值往后挪，例如“31”还剩前面n-1个数需排序,2023/1/4,华中科技大学计算机学院,27,例8.12 冒泡排序,第2遍对前n-1个数，与第1遍一样循环处理还剩前n-2个数未排序第i遍对前n-i+1个数，与第1遍一样循环处理还剩前n-i个数未排序大循环结束时机(对i)i=n-1一遍循环中未发生交换，即已排好序,2023/1/4,华中科技大学计算机学院,28,例8.12 冒泡排序,void bubble_sort(int a,int n)/*形参用形式数组a*/int i,j,t,k;int flag=1;for(i=0;(iaj+1)/*对两两相邻的元素进行比较*/t=aj,aj=aj+1,aj+1=t;flag=1;,2023/1/4,华中科技大学计算机学院,29,8.3 字符数组,8.3.1 字符数组的声明和使用字符数组元素的数据类型为char或wchar_t 声明格式与前面讨论的一维数组相同char s81;字符串用一对双引号界定的一个字符序列C语言没有规定字符串类型用一个字符数组来存放字符序列，并且在末尾加一个空字符0来构造字符串,2023/1/4,华中科技大学计算机学院,30,8.3 字符数组,字符串的存储 字符串的长度字符串的长度=字符串的存储长度1 设计字符数组的最小长度应该等于该字符串的存储长度或字符数组的最小长度应该等于该字符串的长度加1 字符数组的使用 通过下标来访问字符数组中的具体字符元素,2023/1/4,华中科技大学计算机学院,31,#include stdio.hvoid main(void)char Capital27,Lowercase27;int i,delt=a-A;Capital0=A;Lowercase0=Capital0+delt;for(i=1;i26;i+)Capitali=Capitali-1+1;Lowercasei=Lowercasei-1+1;Capital26=0;Lowercase26=Capital26;printf(%sn,Capital);printf(%sn,Lowercase);(演示EX8_13.C),例8.13 产生大写和小写的26个英文字母字符串,程序运行结果如下：ABCDEFGHIJKLMN OPQRSTUVWXYZ abcdefghijklmnop qrstuvwxyz,2023/1/4,华中科技大学计算机学院,32,8.3.2 字符数组的初始化,通过初始化列表 char s18=W,u,h,a,n,0;0必须在初始化列表中显示给出 用字符串初值 char s228=Computer Science；末尾将自动加上一个0第三种方法 数组长度未明显给出char s3=Computer Engineering;字符数组的容量恰好等于字符串的存储长度,2023/1/4,华中科技大学计算机学院,33,8.4 字符串处理函数,串操作函数求字符串长度字符串的拷贝字符串的比较字符串的连接求字符串的子串删除字符串首尾空白字符从字符串中删除所有与给定字符相同的字符将字符串反转等函数,2023/1/4,华中科技大学计算机学院,34,例8.14 求字符串长度的函数,int strlen(char s)int j=0;while(sj!=0)j+;return j;(演示EX8_14.C),void main(void)char str=there is a boat on the lake;int length;length=strlen(str);printf(length of the string is%dn,length);运行结果：length of the string is 28,2023/1/4,华中科技大学计算机学院,35,例8.15 字符串拷贝的函数,void strcpy(char t,char s)int j=0;while(tj=sj+);(演示EX8_15.C),void main(void)char str130,str2=there is a boat on the lake.;strcpy(str1,str2);puts(str1);运行结果：there is a boat on the lake.,2023/1/4,华中科技大学计算机学院,36,例8.16 两个字符串比较函数,比较规则从两个字符串的第一个字符起开始按照字符ASCII码值的大小进行比较返回规定当两个字符串相等时，返回0当第一个串大于第二个串时，返回一个大于零的值当第一个串小于第二个串时，返回一个小于零的值,int strcmp(char s,char t)int j=0;while(sj=tj(演示EX8_16.C),2023/1/4,华中科技大学计算机学院,37,例8.16 两个字符串比较函数,void main(void)char s1=car,s2=bus,s3=truck,s4=car;printf(%s is%s%s.n,s1,strcmp(s1,s2)0?great then:strcmp(s1,s2)0?great then:strcmp(s1,s3)0?great then:strcmp(s1,s4)0?less then:equal to,s4);运行结果：car is great then bus.car is less then truck.car is equal to car.,2023/1/4,华中科技大学计算机学院,38,例8.17 字符串的连接函数,char*strcat(char t,char s)int j=0,k=0;while(tj+!=0);j-;while(tj+=sk+);return t;(演示EX8_17.C),void main(void)char s180=I like,s2=the C programming.;strcat(s1,s2);printf(%sn,s1);运行结果：I like the C programming.,2023/1/4,华中科技大学计算机学院,39,例8.18 求字符串子串的函数,int strstr(char cs,char ct)int j=0,k;for(;csj!=0;j+)if(csj=ct0)k=1;while(csj+k=ctk,2023/1/4,华中科技大学计算机学院,40,例8.18 求字符串子串的函数,void main(void)char s180=C is the most widely used programming language.,s2=use;int i,j=0;i=strstr(s1,s2);printf(the sub_strings beginning position is%dn,i);while(ji)putchar(s1j+);putchar(n);while(putchar(s1i+);putchar(n);(演示EX8_18.C),运行结果：the sub_strings beginning position is 21 C is the most widely used programming language.,2023/1/4,华中科技大学计算机学院,41,例8.19 删除字符串首尾空白字符的函数,int trim(char s)int i,num,j=0,k=0,L=strlen(s);while(sj=|sj=t|sj=n|sj=r)j+;/*j计算首部空白字符的个数*/i=L-1;/*i为字符串最后一个字符(0前面)的下标*/while(si-k=|si-k=t|si-k=n|si-k=r)k+;/*k计算尾部空白字符的个数*/num=L-j-k;for(i=0;inum;i+)si=si+j;snum=0;return strlen(s);(演示EX8_19_21.C),2023/1/4,华中科技大学计算机学院,42,例8.20 从字符串s中删除所有与给定字符相同的字符,从字符串s中去掉与字符变量c值相同的字符 void delete_c(char s,char c)int j=0,k=0;/*j-读指示器，k-写指示器*/while(sj!=0)if(sj!=c)sk+=sj;j+;sk=0;(演示EX8_19_21.C),2023/1/4,华中科技大学计算机学院,43,例8.21 将字符串反转的函数,将一个字符串首尾颠倒过来如：将abcde颠倒为edcbavoid reverse(char s)int j,k;/*j-前指示器 k-尾指示器*/char c;for(j=0,k=strlen(s)-1;jk;j+,k-)c=sj,sj=sk,sk=c;(演示EX8_19_21.C),2023/1/4,华中科技大学计算机学院,44,上面三个函数的应用,void main(void)char str80=atbtctdtetft;printf(before trim,the string is%sn,str);trim(str);printf(after trim,the string is%sn,str);delete_c(str,t);printf(after delete t,the string is%sn,str);reverse(str);printf(after reverse,the string is%sn,str);,运行结果：before trim,the string is atbtctdtetft after trim,the string is atbtctdtetft,after delete t,the string is abcdef after reverse,the string is fedcba,2023/1/4,华中科技大学计算机学院,45,8.4.2 数字串与数之间转换的函数,例8.22 将一个十进制数字串转换成为对应的整数的函数atoi函数功能将s字符数组中存放的一个十进制数字串转换成为对应的整数，并返回该整数算法：ASCII码字符sj转换为对应数字sj-0本位乘以10加下一位的算法54321=（5）*10+4）*10+3）*10+2*10）+1,2023/1/4,华中科技大学计算机学院,46,例8.22 atoi函数,#define BASE 10int atoi(char s)int j=0,num=0;for(;sj!=0;j+)num=num*BASE+sj-0;return num;(演示EX8_22.C),2023/1/4,华中科技大学计算机学院,47,例8.23 将一个整数转换成为基数为BASE的数字串的函数,#define BASE 10void itoa(int n,char s)int sign,j=0;if(sign=n)0)sj+=n%BASE+0;n/=BASE;if(sign0)sj+=-;sj=0;算法见p232 reverse(s);(演示EX8_19_23.C),2023/1/4,华中科技大学计算机学院,48,例8.24 将一个十六进制数字串转换成为对应的整数的函数,问题当基数BASE大于10，如：16，由于十六进制数的表示形式，如a和A，b和B以及0到f或F在ASCII码表的编码不连续性因此需要在转换中进行一定的调整 htoi函数将一个存放在字符数组s中的十六进制数字串转换成为对应的整数并且返回转换后的整数,2023/1/4,华中科技大学计算机学院,49,htoi函数(演示EX8_24.C),int htoi(char s)int j=0,num=0;if(sj=0,2023/1/4,华中科技大学计算机学院,50,8.5 多维数组,实际应用有时需要用多个下标来实现对数组元素的访问 例如张三同学，学号为01，语文和数学成绩分别为85，91，李四同学，学号位02，语文和数学成绩分别为82，95 解决方法用二维数组可以描述学号-课程成绩表中的成绩数据 多维数组的用途二维数组可以描述数学中的矩阵或行列式三维数组可以描述空间中的点集n维数组来描述n维线性空间中的n维向量,2023/1/4,华中科技大学计算机学院,51,8.5.1 多维数组的说明与使用,形式 类型说明 数组名常量表达式1 常量表达式2常量表达式n=初值表；类型说明：存储类型说明符 类型修饰符 数据类型例如，int x22;对其元素的引用 数组名下标1 下标2下标n 例如，x10=3;,2023/1/4,华中科技大学计算机学院,52,例8.25 对二维数组中元素的访问与操作,#include stdio.hvoid main(void)int x23,a=2;x02=8;scanf(%d,2023/1/4,华中科技大学计算机学院,53,计算每个同学的平均成绩并且输出数组中各元素的地址和内容#include stdio.h#define SIZE 2void main(void)int xSIZESIZE+1;int i,j;for(i=0;iSIZE;i+)for(j=0;jSIZE;j+)scanf(%d,(演示EX8_26.C),例8.26 用二维数组表示学号-课程成绩表(1),输入如下：85 91 82 95,2023/1/4,华中科技大学计算机学院,54,例8.26 用二维数组表示学号-课程成绩表(2),for(i=0;iSIZE;i+)for(j=0;jSIZE+1;j+)printf(%ptx%d%d=%dt,程序的运行结果为：FFD0 x00=85 FFD2 x01=91 FFD4 x02=88 FFD6 x10=82 FFD8 x11=95 FFDA x12=88,2023/1/4,华中科技大学计算机学院,55,8.5.2 多维数组的存储结构,二维数组x的逻辑存储结构,二维数组x的物理存储结构,2023/1/4,华中科技大学计算机学院,56,8.5.3 多维数组的初始化,按照物理存储结构的顺序int a22=85,91,82,95;按照逻辑存储结构的顺序可读性好，但初值表的形式与数组的维数有关 int x23=85,91,0，82,95，0;int d222=1,2,3,4,5,6,7,8;注意当数组的初值全部给出时，第1维大小的说明可以省略int x 3=85,91,0，82,95，0;int d 22=1,2,3,4,5,6,7,8;其它维大小不能省略,2023/1/4,华中科技大学计算机学院,57,8.5.4 二维字符数组,二维字符数组 与其它二维数组类似 用char说明的二维数组char text2580;初始化 与其它二维数组类似char s24=a,b,c,0,d,e,f,0;char s24=a,b,c,0,d,e,f,0;用字符串对二维数组进行初始化char devices312=“hard disk”,”CRT”,”keyboard”;省略第1维的方式 char devices 12=“hard disk”,”CRT”,”keyboard”;,2023/1/4,华中科技大学计算机学院,58,二维字符数组的使用,引用单个字符元素 weekendij=m;引用字符串 weekendi表示weekend数组中第i行字符串的首地址printf(“%s”,weekendi);,2023/1/4,华中科技大学计算机学院,59,例8.27 字符串数组的输入输出操作,#include stdio.hvoid main(void)int i;char devices312=hard disk,CRT,keyboard;devices00=H;/*hard disk变为Hard disk*/devices20=K;/*keyboard 变为Keyboard*/for(i=0;i3;i+)printf(%sn,(演示EX8_27.C),2023/1/4,华中科技大学计算机学院,60,*8.6 数组的应用程序设计,8.6.1 矩阵乘法运算算法定义3个2维数组 通过三重循环来实现 外层循环用于控制乘积矩阵C的行中间层循环用于控制乘积矩阵C的列内层循环用于计算乘积矩阵元素Cij,2023/1/4,华中科技大学计算机学院,61,例8.28 矩阵的乘法运算,#include stdio.h#define N 3#define K 4#define M 3void mul_matrix(int aK,int bM,int cM,int n,int k,int m)int i,j,p,sum;for(i=0;in;i+)for(j=0;jm;j+)sum=0;for(p=0;pk;p+)sum+=aip*bpj;cij=sum;(演示EX8_28.C),2023/1/4,华中科技大学计算机学院,62,例8.28 矩阵的乘法运算,void main(void)int ANK=1,2,3,4,5,6,7,8,9,0,1,2;int BKM=1,2,3,4,5,6,7,8,9,0,1,2;int CNM;int i,j;mul_matrix(A,B,C,N,K,M);for(i=0;iN;i+)for(j=0;jM;j+)printf(%8d,Cij);printf(n);,程序的运行结果为：30 40 50 78 104 130 16 28 40,2023/1/4,华中科技大学计算机学院,63,8.6.2 基于分治策略的二分查找函数,二分查找算法的思路将已排好序的n个元素数组a分成两半，取an/2与x比较如果x=an/2，则找到x，算法结束如果xan/2，则在数组a的后半部分继续查找x返回值如果找到x，返回该数所在单元的下标如果没有找到，返回-1,2023/1/4,华中科技大学计算机学院,64,例8.29 二分查找函数,#include stdio.h”(演示EX8_29.C)int BinarySearch(int a,int x,int n)int front=0,back=n-1,middle;while(frontamiddle)front=middle+1;/*查找单元变成原来的后半部*/elsereturn(middle);/*找到，返回下标*/return-1;/*没有找到，返回-1*/,2023/1/4,华中科技大学计算机学院,65,例8.29 二分查找函数,void main(void)int x=1,3,5,7,9,11,13,15,17,19,index;index=BinarySearch(x,11,10);if(index!=-1)printf(find%d!n,xindex);elseprintf(not find!n);程序的运行结果是：find 11!,2023/1/4,华中科技大学计算机学院,66,8.6.3 选择法排序,假设有下面的8个整数构成的数组算法思想首先找出数组内8个元素中最小的元素然后将它与第一个元素（下标为0）交换再在剩余的后续7个元素中找出最小的元素，再将它与第二个元素（下标为1）交换余以类推，直到在最后剩余的两个元素中找出较小者并将较大者放在最后（下标为7）为止,2023/1/4,华中科技大学计算机学院,67,例8.30 用选择法进行排序,#include stdio.hint f_small(int a,int begin,int end)/*在begin与end之间找最小数*/int i,p=begin;for(i=begin;i=end;i+)if(aiap)p=i;return p;void sel_sort(int a,int n)/*排序函数*/int cur,index,t;for(cur=0;curn-1;cur+)index=f_small(a,cur,n-1);,if(index!=cur)t=acur,acur=ain dex,aindex=t;void main(void)int x=12,2,-21,5,67,89,-12,34,i,n;n=8;sel_sort(x,n);for(i=0;i8;i+)printf(%d,xi);printf(n);(演示EX8_30.C),2023/1/4,华中科技大学计算机学院,68,8.6.4快速排序(shell法排序),shell法排序是由P.L.Shell于1959年提出的一种改进的对n个数的快速排序算法。其算法思想是：开始时，将n个数组成的数组分为两段，把后一段的每个元素分别与前一段间隔n/2处的元素进行比较，如果后者小于前者，则交换这两个元素的值。后一段的每个元素都处理完后，将比较间隔缩小一半，然后从距离第一个元素为当前间隔的哪个元素开始直到数组中的最后一个元素，重复上面的比较、交换过程。并且，一旦发生交换，被交换到前面的那个值还要继续与它前面距离为当前比较间隔的那些元素进行比较，符合交换条件的还要继续交换，这个过程要一直进行到比较中位于前面的那个元素距离数组的第一个元素小于当前比较间隔为止。余以类推。当比较间隔缩小到0时，整个排序过程结束。由于每比较一趟，就将比较间隔缩小一半，该算法又称为缩小增量排序算法。,2023/1/4,华中科技大学计算机学院,69,例8.31 用shell法对整型数组进行排序。,#include stdio.hvoid shellsort(int a,int n);void main(void)int b10=9,61,52,-12,2,26,48,32,6,15,i;shellsort(b,10);for(i=0;i0;gap=gap/2)/*初始间隔为n/2，然后每趟间隔缩小一半*/for(i=gap;i=0,2023/1/4,华中科技大学计算机学院,70,本章作业题,pp251-2528.1,8.3,8.4,8.6,8.7,8.9,8.12,8.13,8.14,8.18选做:8.20,