构造型数据类型精选文档.ppt

《构造型数据类型精选文档.ppt》由会员分享，可在线阅读，更多相关《构造型数据类型精选文档.ppt（170页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、构造型数据类型本讲稿第一页，共一百七十页构造型数据类型构造型数据类型n nC中简单数据类型的特点：中简单数据类型的特点：类型值域内的每个值都是类型值域内的每个值都是单值单值一个值内不包含其他值一个值内不包含其他值n n实际生活中实际生活中N维向量维向量mn的矩阵的矩阵个人自然情况表个人自然情况表学生名表学生名表本讲稿第二页，共一百七十页n n构造型数据类型（构造型数据类型（structured-type）指一个数据类型值域之内的一个值是由若干其它指一个数据类型值域之内的一个值是由若干其它类型的值构成的类型的值构成的C中提供的中提供的3种构造数据类型种构造数据类型 数组数组数组数组 结构结构结构

2、结构 联合联合联合联合本讲稿第三页，共一百七十页n n学习使用要回答的三个问题学习使用要回答的三个问题它的基础类型是什么？它的基础类型是什么？该构造型类型是以什么类型为基点出发构该构造型类型是以什么类型为基点出发构造新类型的造新类型的。构造的方法是什么？构造的方法是什么？不同的构造方法形成了不同的构造型数据不同的构造方法形成了不同的构造型数据类型类型。一个成分的存取方式和使用方法一个成分的存取方式和使用方法不同的类型使用不同形式不同的类型使用不同形式。本讲稿第四页，共一百七十页数组类型（数组类型（array-type）n n一种数据结构一种数据结构n n变量的一个有序结合变量的一个有序结合n

3、n所有变量具有同一类型所有变量具有同一类型n n例子例子一句话一句话 由由 若干个若干个 字符字符 组成的一个组成的一个数组数组一个向量一个向量 由由 若干个若干个 实数实数 组成的一个组成的一个数组数组一个矩阵一个矩阵 由由 若干个若干个 向量向量 组成的一个组成的一个数组数组本讲稿第五页，共一百七十页n n回答前面的三个问题回答前面的三个问题回答前面的三个问题回答前面的三个问题 基础类型（成分类型）基础类型（成分类型）基础类型（成分类型）基础类型（成分类型）任意类型任意类型任意类型任意类型 构造方法构造方法构造方法构造方法 把把把把固定数目固定数目固定数目固定数目的的的的同一同一同一同一成

4、分类型的数据成分类型的数据成分类型的数据成分类型的数据顺序顺序顺序顺序排成一个排成一个排成一个排成一个表表表表。每个数据是成分类型的一个值。每个数据是成分类型的一个值。每个数据是成分类型的一个值。每个数据是成分类型的一个值。所有成分顺序排成的值表是数组类型的一个值。所有成分顺序排成的值表是数组类型的一个值。所有成分顺序排成的值表是数组类型的一个值。所有成分顺序排成的值表是数组类型的一个值。成分的存取和使用成分的存取和使用成分的存取和使用成分的存取和使用 每个成分都有唯一的一个下标每个成分都有唯一的一个下标每个成分都有唯一的一个下标每个成分都有唯一的一个下标 下标从下标从下标从下标从0 0开始顺

5、序增加开始顺序增加开始顺序增加开始顺序增加 第一个成分第一个成分第一个成分第一个成分 下标为下标为下标为下标为0 0 第二个成分第二个成分第二个成分第二个成分 下标为下标为下标为下标为1 1 下标表达式下标表达式下标表达式下标表达式本讲稿第六页，共一百七十页数组声明数组声明n n一般形式一般形式T ide;T ide;T ide,ide,.,ide;T ide,ide,.,ide;id是要声明的数组（数组变量）的是要声明的数组（数组变量）的名字名字e暂时看作常量表达式暂时看作常量表达式 它是要声明的数组的它是要声明的数组的尺尺寸寸，也就是相应数组由多少个成分组成，也就是相应数组由多少个成分组成

6、ide 称为数组声明符称为数组声明符本讲稿第七页，共一百七十页n n例子例子int m,n,v10;float vector 10000;int t110,t010,w10;float t22;bool t3 26;char t4 8 ;本讲稿第八页，共一百七十页n n干什么？干什么？具体标明（访问）数组变量的某一个成分具体标明（访问）数组变量的某一个成分n n什么样？什么样？下标表达式下标表达式 后缀表达式后缀表达式 表达式表达式 后缀表达式最终表现为一个数组变量，指出访问哪个后缀表达式最终表现为一个数组变量，指出访问哪个数组的成分；数组的成分；方括号中的表达式的类型必须是方括号中的表达式的

7、类型必须是整数类型整数类型，它具体指，它具体指明访问的是数组的哪一个成分明访问的是数组的哪一个成分下标表达式下标表达式本讲稿第九页，共一百七十页n n例子例子vector255vector vector 的编号为的编号为的编号为的编号为 255(255(第第第第256256个个个个)的成分，为的成分，为的成分，为的成分，为 float float 型变量型变量型变量型变量v2+3 v v 的编号为的编号为的编号为的编号为 5(5(第第第第6 6个个个个)的成分，为的成分，为的成分，为的成分，为 int int 型变量型变量型变量型变量t3i+j*k ：若若若若 i+j*ki+j*k落在落在落在

8、落在0.250.25之内之内之内之内 则是则是则是则是 t3 t3 的编号为的编号为的编号为的编号为i+j*k(i+j*k(第第第第i+j*k+1i+j*k+1个个个个)的成分，是一个的成分，是一个的成分，是一个的成分，是一个 bool bool 型变量；型变量；型变量；型变量；否则否则否则否则 i+j*k i+j*k 落在落在落在落在 0.250.25之外，之外，之外，之外，则引起错误则引起错误则引起错误则引起错误 t40 t4 t4 的下标为的下标为的下标为的下标为 0(0(第第第第1 1个个个个)的成分，为的成分，为的成分，为的成分，为 char char 型变量型变量型变量型变量本讲稿

9、第十页，共一百七十页n n下标表达式实际是一个变量。下标表达式实际是一个变量。n n它是相应数组成分类型的一个变量。它是相应数组成分类型的一个变量。它是相应数组成分类型的一个变量。它是相应数组成分类型的一个变量。n n程序中，下标表达式的地位、作用与相应数组成分类型程序中，下标表达式的地位、作用与相应数组成分类型程序中，下标表达式的地位、作用与相应数组成分类型程序中，下标表达式的地位、作用与相应数组成分类型的一般变量的地位、作用完全相同。的一般变量的地位、作用完全相同。的一般变量的地位、作用完全相同。的一般变量的地位、作用完全相同。n n即凡是可使用数组成分类型变量的地方都可以使用下标表达即凡

10、是可使用数组成分类型变量的地方都可以使用下标表达即凡是可使用数组成分类型变量的地方都可以使用下标表达即凡是可使用数组成分类型变量的地方都可以使用下标表达式，有时也称下标表达式为式，有时也称下标表达式为式，有时也称下标表达式为式，有时也称下标表达式为“下标变量下标变量下标变量下标变量”。本讲稿第十一页，共一百七十页需要注意的问题需要注意的问题n n运算运算 C C 没有定义施于数组类型上的运算没有定义施于数组类型上的运算没有定义施于数组类型上的运算没有定义施于数组类型上的运算 数组类型的运算都是通过其成分实现数组类型的运算都是通过其成分实现数组类型的运算都是通过其成分实现数组类型的运算都是通过其

11、成分实现 例子例子例子例子求整型数组求整型数组求整型数组求整型数组t0,t1 t0,t1 的差送入整型数组的差送入整型数组的差送入整型数组的差送入整型数组 w w 中，应如下：中，应如下：中，应如下：中，应如下：for(m=0;m=9;m+)wm=t0m-t1m;而不能写成而不能写成而不能写成而不能写成 w=t0-t1;w=t0-t1;本讲稿第十二页，共一百七十页n n 数组变量不能作数组变量不能作数组变量不能作数组变量不能作I/OI/O函数的实在参数函数的实在参数函数的实在参数函数的实在参数 不能整个读入或输出一个数组不能整个读入或输出一个数组不能整个读入或输出一个数组不能整个读入或输出一个

12、数组 例子例子例子例子读入一批数据送入数组读入一批数据送入数组读入一批数据送入数组读入一批数据送入数组 w w 中，可以用如下方法实现：中，可以用如下方法实现：中，可以用如下方法实现：中，可以用如下方法实现：for(m=0;m=9;m+)for(m=0;m=9;m+)scanf(“%f“,&(wm);scanf(“%f“,&(wm);printf(“%f”,Wm);printf(“%f”,Wm);而不能写成而不能写成而不能写成而不能写成 scanf(“%f“,&w);scanf(“%f“,&w);printf(“%f”,w);printf(“%f”,w);本讲稿第十三页，共一百七十页多维数组多

13、维数组n n二维数组声明符形式：二维数组声明符形式：标识符标识符 赋值表达式赋值表达式 赋值表达式赋值表达式赋值表达式赋值表达式 n n例子例子 float a 105;float a 105;本讲稿第十四页，共一百七十页n n下标表达式形式下标表达式形式 数组变量数组变量 表达式表达式1 表达式表达式2 n n例子例子 a a 矩阵的第矩阵的第矩阵的第矩阵的第 3 行、第行、第行、第行、第 4 4 列元素表示为列元素表示为列元素表示为列元素表示为 a23a23本讲稿第十五页，共一百七十页n n多维数组声明符形式多维数组声明符形式数组标识符数组标识符数组标识符数组标识符 赋值表达式赋值表达式赋

14、值表达式赋值表达式1 1 .赋值表达式赋值表达式赋值表达式赋值表达式n n n n下标表达式形式下标表达式形式数组变量数组变量数组变量数组变量 表达式表达式表达式表达式1 1 表达式表达式表达式表达式2 .2 .表达式表达式表达式表达式k k 本讲稿第十六页，共一百七十页 int x 522653;int x 522653;声明声明声明声明 x x 是一个维数组。它的成分类型是是一个维数组。它的成分类型是是一个维数组。它的成分类型是是一个维数组。它的成分类型是intint型；型；型；型；第一维第一维第一维第一维5 5个成分；个成分；个成分；个成分；第二维第二维第二维第二维2 2个成分；个成分；

15、个成分；个成分；第三维第三维第三维第三维2626个成分；个成分；个成分；个成分；第四维第四维第四维第四维5 5个成分；个成分；个成分；个成分；第五维第五维第五维第五维3 3个成分。个成分。个成分。个成分。下标表达式下标表达式下标表达式下标表达式 x01342 x01342 是是是是 x x 的一个下标变量的一个下标变量的一个下标变量的一个下标变量,类型是类型是类型是类型是intint型。型。型。型。按语法下标表达式中的表达式可写若干，则下标表达式按语法下标表达式中的表达式可写若干，则下标表达式按语法下标表达式中的表达式可写若干，则下标表达式按语法下标表达式中的表达式可写若干，则下标表达式 x0

16、1x01 类型是一个三维数组。即这时把它看成是类型类型是一个三维数组。即这时把它看成是类型类型是一个三维数组。即这时把它看成是类型类型是一个三维数组。即这时把它看成是类型 int x 52int x 52成分类型成分类型成分类型成分类型 的一个下标表达式，成分类型是一个三维数组类型的一个下标表达式，成分类型是一个三维数组类型的一个下标表达式，成分类型是一个三维数组类型的一个下标表达式，成分类型是一个三维数组类型:int t 2653;int t 2653;本讲稿第十七页，共一百七十页程序设计实例程序设计实例n n求两向量内积求两向量内积求两向量内积求两向量内积n n求两矩阵乘积求两矩阵乘积求两

17、矩阵乘积求两矩阵乘积n n打印杨辉三角打印杨辉三角打印杨辉三角打印杨辉三角n n主元排序主元排序主元排序主元排序n n冒泡排序冒泡排序冒泡排序冒泡排序n n逐步增加递增子序列排序逐步增加递增子序列排序逐步增加递增子序列排序逐步增加递增子序列排序n n顺序检索顺序检索顺序检索顺序检索n n对半检索对半检索n n栈栈栈栈n n队列队列n nGaoss 消去法消去法消去法消去法n n星形线图形星形线图形n n最长递增子序列的长度最长递增子序列的长度本讲稿第十八页，共一百七十页例例6-1 求两向量内积求两向量内积设有向量设有向量设有向量设有向量 a an n,bn 则其内积为：则其内积为：则其内积为：

18、则其内积为：e=0for(i=0;i n;i+)e=e+ai*bi结束结束开始开始本讲稿第十九页，共一百七十页n n程序片断程序片断#define n 100#define n 100 float an,bn;float an,bn;float innerproduct(void)float innerproduct(void)float e;int i;e=0;for(i=0;in;i+)e=e+ai*bi;return e;本讲稿第二十页，共一百七十页例例6-2 求两矩阵乘积求两矩阵乘积n n设有矩阵设有矩阵设有矩阵设有矩阵 A Ampmp 、B Bpnpn ，则其乘积矩阵，则其乘积矩阵，

19、则其乘积矩阵，则其乘积矩阵 C Cmnmn 的元素的元素的元素的元素 C Cij ij 为为为为:若矩阵若矩阵若矩阵若矩阵A,B A,B 分别放在二维数组分别放在二维数组分别放在二维数组分别放在二维数组a,ba,b中；则求乘积矩阵中；则求乘积矩阵中；则求乘积矩阵中；则求乘积矩阵c c的算法的算法的算法的算法for(i=0;in;i+)计算一行计算一行 for(j=0;j m;j+)计算元素计算元素ci,je=e+aik*bkje=0cij=efor(k=0;kp;k+)本讲稿第二十一页，共一百七十页n n程序片断如下程序片断如下程序片断如下程序片断如下#define m 10#define m

20、 10#define n 20#define n 20#define p 30#define p 30 float a m p ,b p n ,c m n ;float a m p ,b p n ,c m n ;void matrixproduct(void)void matrixproduct(void)float e;float e;int i,j,k ;int i,j,k ;for(i=0;im;i+)for(i=0;im;i+)for(j=0;jn;j+)for(j=0;jn;j+)e=0;e=0;for(k=0;kp;k+)for(k=0;kp;k+)e=e+aik*bkj;e=e+

21、aik*bkj;cij=e;cij=e;本讲稿第二十二页，共一百七十页例例6-3 打印杨辉三角形前打印杨辉三角形前10行行11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1.打印第打印第i行行打印杨辉打印杨辉 三角形三角形for(i=0;i10;i+)结束结束生成第生成第i行行打印打印本讲稿第二十三页，共一百七十页生成第生成第生成第生成第i i行，用多项式定理计算组合数行，用多项式定理计算组合数n稍大一点，运算量极大稍大一点，运算量极大Cn!m nmnm=-!()!利用杨辉三角形的特性，从第利用杨辉三角形的特性，从第i-1行生成第行生成第i行。行。设把第设把第 i 行

22、数据保存在数组中，第行数据保存在数组中，第i-1行在数组中。行在数组中。并考虑到将来生成第并考虑到将来生成第i+1行时，数组中应为第行时，数组中应为第i行。行。本讲稿第二十四页，共一百七十页假设假设 把第把第0行的的输出在屏幕的第行的的输出在屏幕的第40列列各行数据中每个数占位；第各行数据中每个数占位；第 i 行应从行应从 40-i*(4)处开始显示处开始显示for(j=1;j i-1;j+)aj=bj-1+bjai=1for(j=0;ji;j+)bj=aj印印 40-i*(/2)个空格个空格印印“回车回车”printf(“%8d”,aj)for(j=0;ji;j+)打印杨辉打印杨辉 三角形三

23、角形for(i=0;i10;i+)结束结束生成第生成第i行行打印打印本讲稿第二十五页，共一百七十页#define n 10#define wideword void main()int a11,b11,i,j;for(i=0;in;i+)for(j=1;ji;j+)/生成第生成第i行行 aj=bj-1+bj;ai=1;for(j=0;j=i;j+)/形成下一次的第形成下一次的第i-1行行 bj=aj;for(j=0;j=40-i*(wideword/2);j+)/打印第打印第i行行 printf(%c,);for(j=0;j=i;j+)/printf(“%8d,aj);printf(n);本讲

24、稿第二十六页，共一百七十页0000000000a123456789下标下标0000000000b1.1.i=0i=0不执行不执行不执行不执行 循环，循环，循环，循环，a0=1a0=1b0=a0=1b0=a0=1，打印打印打印打印4040个空格个空格个空格个空格打印打印打印打印a0=1,a0=1,打印回车打印回车打印回车打印回车111.01000本讲稿第二十七页，共一百七十页1000000000a123456789下标下标1000000000b2.2.i=1i=1不执行不执行不执行不执行 循环，循环，循环，循环，a1=1a1=1b0=a0=1b0=a0=1b1=a1=1b1=a1=1打印打印打印

25、打印3636个空格个空格个空格个空格打印打印打印打印a0,a1=1a0,a1=1打印回车打印回车打印回车打印回车111 1 1 .01000本讲稿第二十八页，共一百七十页1100000000a123456789下标下标1100000000b3.3.i=2i=2j=12j=12a1=b0+b1=2a1=b0+b1=2a2=1a2=1b0=a0=1b0=a0=1b1=a1=2b1=a1=2b2=a2=1b2=a2=1打印打印打印打印3232个空格个空格个空格个空格打印打印打印打印a0,a1,a2,a0,a1,a2,打印回车打印回车打印回车打印回车221 1 1 1 2 1 .0111000本讲稿第

26、二十九页，共一百七十页1210000000a123456789下标下标1210000000b4.4.i=3i=3j=13j=13a1=b0+b1=3a1=b0+b1=3a2=b1+b2=3 a2=b1+b2=3 a3=1a3=1b0=a0=1b0=a0=1b1=a1=3b1=a1=3b2=a2=3b2=a2=3b3=a3=1b3=a3=1打印打印打印打印2828个空格个空格个空格个空格打印打印打印打印a0,a1,a2,a3a0,a1,a2,a3打印回车打印回车打印回车打印回车331 1 1 1 2 1 1 3 3 1 .011331000本讲稿第三十页，共一百七十页还可以不使用数组，只用一个数

27、组来生成和打印该杨辉三角形，这个算还可以不使用数组，只用一个数组来生成和打印该杨辉三角形，这个算法不但比上述算法节省存储空间，而且运行速度也快。法不但比上述算法节省存储空间，而且运行速度也快。void main()void main()int a11,i,j;int a11,i,j;for(i=0;in;i+)/for(i=0;i0;j-)/for(j=i-1;j0;j-)/aj=aj-1+aj;aj=aj-1+aj;/打印第打印第打印第打印第i i行行行行 本讲稿第三十一页，共一百七十页0000000000a1234567890下标下标1.1.i=0i=0a0=1a0=1j=-10,j=-1

28、0,不执行循环不执行循环不执行循环不执行循环1100本讲稿第三十二页，共一百七十页1000000000a1234567890下标下标2.2.i=1i=1a1=1a1=1j=00,j=00,不执行循环不执行循环不执行循环不执行循环1100本讲稿第三十三页，共一百七十页1100000000a1234567890下标下标3.3.i=2i=2a2=1a2=1j=10j=10a1=a1+a0=2a1=a1+a0=212100本讲稿第三十四页，共一百七十页1210000000a1234567890下标下标4.4.i=3i=3a3=1a3=1j=20j=20a2=a2+a1=3 a2=a2+a1=3 a1=

29、a1+a0=3a1=a1+a0=3133100本讲稿第三十五页，共一百七十页1331000000a1234567890下标下标5.5.i=4i=4a4=1a4=1j=30j=30a3=a3+a2=4 a3=a3+a2=4 a2=a2+a1=6 a2=a2+a1=6 a1=a1+a0=4a1=a1+a0=41446100本讲稿第三十六页，共一百七十页例例6-4 对整数数组进行主元排序对整数数组进行主元排序n n排序排序 亦称亦称“分类分类”，是计算机科学中研究，是计算机科学中研究的一类重要课题，现在已经有很多有效的算的一类重要课题，现在已经有很多有效的算法法.n n以整数组为背景介绍三种较常见算

30、法以整数组为背景介绍三种较常见算法数组的说明如下：数组的说明如下：#define n 100#define n 100 int a n ;int a n ;本讲稿第三十七页，共一百七十页n n排序思想排序思想排序思想排序思想 未排序未排序未排序未排序 在在在在a0a0、a1a1、.、an-1an-1中选一最小中选一最小中选一最小中选一最小ajaj，ajaj与与与与a0a0交换交换交换交换a0a0排好排好排好排好序序序序 在在在在a1a1、a2a2、.、an-1an-1中选一最小中选一最小中选一最小中选一最小ajaj，ajaj与与与与a1a1交换交换交换交换a0a0、a1a1排好序排好序排好序排

31、好序 在在在在a2a2、a3a3、.、an-1an-1中选一最小中选一最小中选一最小中选一最小ajaj，ajaj与与与与a2a2交换交换交换交换a0a0、a1 a1、a2a2排好序排好序排好序排好序 .a0a0、a1 a1、a2a2、an-2an-2排好序排好序排好序排好序 在在在在an-2an-2、an-1an-1中选一个最小中选一个最小中选一个最小中选一个最小ajaj，把，把，把，把ajaj与与与与an-2an-2交换交换交换交换a0a0、a1 a1、a2a2、an-2an-2、an-1an-1排好序排好序排好序排好序 排序结束排序结束排序结束排序结束本讲稿第三十八页，共一百七十页3211

32、6231162311623611本讲稿第三十九页，共一百七十页n n排序思想排序思想 未排序未排序未排序未排序 在在在在a0a0、a1a1、.、an-1an-1中选一最小中选一最小中选一最小中选一最小ajaj，ajaj与与与与a0a0交换交换交换交换a0a0排排排排好序好序好序好序 在在在在a1a1、a2a2、.、an-1an-1中选一最小中选一最小中选一最小中选一最小ajaj，ajaj与与与与a1a1交换交换交换交换a0a0、a1a1排好序排好序排好序排好序 在在在在a2a2、a3a3、.、an-1an-1中选一最小中选一最小中选一最小中选一最小ajaj，ajaj与与与与a2a2交换交换交换

33、交换a0a0、a1 a1、a2a2排好序排好序排好序排好序 .a0a0、a1 a1、a2a2、an-2an-2排好序排好序排好序排好序 在在在在an-2an-2、an-1an-1中选一个最小中选一个最小中选一个最小中选一个最小ajaj，把，把，把，把ajaj与与与与an-2an-2交换交换交换交换a0a0、a1 a1、a2a2、an-2an-2、an-1an-1排好序排好序排好序排好序 排序结束排序结束排序结束排序结束本讲稿第四十页，共一百七十页n n程序设计程序设计程序设计程序设计 第一层循环确定排第几小的元素第一层循环确定排第几小的元素第一层循环确定排第几小的元素第一层循环确定排第几小的元

34、素 循环次数循环次数循环次数循环次数 0.n-20.n-2，用用用用i i标识标识标识标识 a 0 a i-1 a 0 a i-1 已经排好序已经排好序已经排好序已经排好序 第二层循环确定第二层循环确定第二层循环确定第二层循环确定a i a n-1 a i a n-1 中最小元素中最小元素中最小元素中最小元素ajaj a j a j 是序列的第是序列的第是序列的第是序列的第i i小的元素小的元素小的元素小的元素 在在在在a i a n-1 a i a n-1 找最小，找最小，找最小，找最小，j j标识所找最小元素的下标标识所找最小元素的下标标识所找最小元素的下标标识所找最小元素的下标 以以以以

35、aiai为基准，为基准，为基准，为基准，j=ij=i，令，令，令，令k k：i+1n-1i+1n-1 若某个若某个若某个若某个a k a j ja k a j jk k 交换交换交换交换a i a i 和和和和a j a j 的值的值的值的值 a 0 a i-1 a 0 a i-1、a i a i 已经排好序已经排好序已经排好序已经排好序本讲稿第四十一页，共一百七十页主元排序主元排序结束结束交换交换 ai、aj for(i=0;in-1;i+)排第排第i个元素个元素在在aian-1之间找最小元素之间找最小元素ajj=kj=i for(k=i+1;kn;k+)akaj本讲稿第四十二页，共一百七十

36、页函数函数 sort 如下：如下：void sort(int n,int a )int i,j,k,r;for(i=0;in-1;i+)j=i;for(k=i+1;kn;k+)if(ak ai+1aiai+1则交换则交换则交换则交换aiai、ai+1 ai+1 如此反复进行，直到某一次扫描，没有数据交换为止，便完成了如此反复进行，直到某一次扫描，没有数据交换为止，便完成了如此反复进行，直到某一次扫描，没有数据交换为止，便完成了如此反复进行，直到某一次扫描，没有数据交换为止，便完成了对数组对数组对数组对数组A A的排序的排序的排序的排序 至多扫描次就可以使数组至多扫描次就可以使数组至多扫描次就可

37、以使数组至多扫描次就可以使数组A A完成排序，所以该算法能够终完成排序，所以该算法能够终完成排序，所以该算法能够终完成排序，所以该算法能够终止。止。止。止。本讲稿第四十四页，共一百七十页741654176514657第一轮第一轮:第二轮第二轮:47165471641675416571456741657第三轮第三轮:14567本讲稿第四十五页，共一百七十页用用用用bool型变量型变量型变量型变量flagflag标志一次扫描过程中是否有数据交换标志一次扫描过程中是否有数据交换标志一次扫描过程中是否有数据交换标志一次扫描过程中是否有数据交换n n判断是否需要进行下一轮扫描步骤判断是否需要进行下一轮扫

38、描步骤每次扫描开始令每次扫描开始令 flag=false，假设没有数据交换，假设没有数据交换然后，当有数据交换时令然后，当有数据交换时令 flag=true最后在一遍扫描结束后最后在一遍扫描结束后:若若若若 flag=true flag=true 则说明本次扫描有数据交换，还应进行则说明本次扫描有数据交换，还应进行则说明本次扫描有数据交换，还应进行则说明本次扫描有数据交换，还应进行下一次扫描下一次扫描下一次扫描下一次扫描 否则扫描终止否则扫描终止否则扫描终止否则扫描终止本讲稿第四十六页，共一百七十页冒泡排序冒泡排序结束结束flagfor(i=0;iai+1本讲稿第四十七页，共一百七十页void

39、 sortofup(int n,int a )int i,r;bool flag;flag=true;while(flag)flag=false;for(i=0;i ai+1)r=ai;ai=ai+1;ai+1=r;flag=true;本讲稿第四十八页，共一百七十页例例6-6 用用“逐步增加递增子序列逐步增加递增子序列”法对法对 整数组进行排序整数组进行排序n n排序思想排序思想把数组把数组A看成一个序列看成一个序列 a0、a1、.、ai-1、ai、.、an 假设下面子序列已经是递增假设下面子序列已经是递增 a0、a1、.、ai-1给上述子序列再加一个元素给上述子序列再加一个元素ai 若有办法

40、使子序列若有办法使子序列 a0、a1、.、ai-1、ai 仍是递增的便可以完成对仍是递增的便可以完成对A的排序。的排序。本讲稿第四十九页，共一百七十页32116321163211632611本讲稿第五十页，共一百七十页n n当子序列只有一个元素当子序列只有一个元素当子序列只有一个元素当子序列只有一个元素a0a0时，它自然递增时，它自然递增时，它自然递增时，它自然递增n n这样，一个个向该子序列加元素，每加一个元素后，都使新这样，一个个向该子序列加元素，每加一个元素后，都使新这样，一个个向该子序列加元素，每加一个元素后，都使新这样，一个个向该子序列加元素，每加一个元素后，都使新的子序列仍保持递增

41、；的子序列仍保持递增；的子序列仍保持递增；的子序列仍保持递增；n n直到将最后一个元素直到将最后一个元素直到将最后一个元素直到将最后一个元素an-1an-1加入子序列为止，便完成了加入子序列为止，便完成了加入子序列为止，便完成了加入子序列为止，便完成了对序列的排序对序列的排序对序列的排序对序列的排序使使 a0、.、ai 递增递增开始开始for(i=1;in;i+)结束结束本讲稿第五十一页，共一百七十页n n使使使使 a0 a0、a1 a1、.、ai-1、ai ai 递增递增递增递增 a0、a1、.、ai-1递增递增 需要在其中找到一个适当位置来放需要在其中找到一个适当位置来放ai 则应该首先找

42、到一个则应该首先找到一个则应该首先找到一个则应该首先找到一个j，使，使 aj=aiaj+1然后，把然后，把ai插到序列插到序列 a0 a0、.、aj、ai ai 、aj+1、.、ai-1ai-1开始开始for(i=1;in;i+)结束结束求位置求位置 j，使，使aj=ai aj+1把把 ai 插到插到aj 和和 aj+1 之间之间本讲稿第五十二页，共一百七十页n n为为为为ai ai 寻找适当位置使寻找适当位置使寻找适当位置使寻找适当位置使aj=aiaj+1只要从只要从只要从只要从ai-1ai-1开始向前，用开始向前，用开始向前，用开始向前，用aiai与序列上的元素逐一进行比较，与序列上的元素

43、逐一进行比较，与序列上的元素逐一进行比较，与序列上的元素逐一进行比较，直到找到满足条件的位置为止（当然直到找到满足条件的位置为止（当然直到找到满足条件的位置为止（当然直到找到满足条件的位置为止（当然j不能超过序列不能超过序列不能超过序列不能超过序列A A的第的第一个位置）一个位置）开始开始for(i=1;iai)&(j=0)j=i-1本讲稿第五十三页，共一百七十页n n把把把把aiai插到插到插到插到aj和和和和aj+1aj+1之间之间之间之间”：aj+1aj+1、aj+2aj+2、.、ai-1ai-1顺序向后串顺序向后串顺序向后串顺序向后串分别送入分别送入分别送入分别送入aj+2、aj+3

44、aj+3、.、aiai中中中中然后把然后把然后把然后把 ai ai 送入送入送入送入 aj+1 中即可中即可中即可中即可为了向后串，必须先记录为了向后串，必须先记录 aiai开始开始for(i=1;iai)&(j=0)j=i-1for(k=i-1;k=j+1;k-)ak+1=akr=aiaj+1=r本讲稿第五十四页，共一百七十页void sort(int n,int a )int i,j,k,r;for(i=1;iai)&(j=0)j=j-1;r=ai;for(k=i-1;k=j+1;k-)ak+1=ak;aj+1=r;本讲稿第五十五页，共一百七十页例例6-7 顺序检索顺序检索n n“检索检索

45、”与与“分类分类”是互相联系在一起的，是互相联系在一起的，也是计算机科学中研究的一类重要课题。也是计算机科学中研究的一类重要课题。n n我们仍以整数组为背景介绍两种较常见的我们仍以整数组为背景介绍两种较常见的算法算法n nA已经按递增排序。已经按递增排序。本讲稿第五十六页，共一百七十页n n检索思想检索思想顺次用欲检索的关键字值顺次用欲检索的关键字值key与数组中元素与数组中元素a0、a1、.、an-1逐一进行比较。逐一进行比较。找到一个找到一个j j使使key=ajkey=aj：位置为位置为位置为位置为j j，函数，函数search带着带着带着带着j j返回；返回；返回；返回；直到结束，没有

46、使直到结束，没有使直到结束，没有使直到结束，没有使key=aj的的的的j j存在：存在：存在：存在：未找到，函数未找到，函数未找到，函数未找到，函数searchsearch带回值带回值带回值带回值 1。本讲稿第五十七页，共一百七十页顺序检索顺序检索return-1;结束结束 for(j=0;jn;j+)位置为位置为jreturn j;key=ajint search(int n,int a,int key)int search(int n,int a,int key)/key/key为关键字为关键字为关键字为关键字 int j;/位置为位置为位置为位置为j j for(j=0;jn;j+)fo

47、r(j=0;jn;j+)if(key=aj)if(key=aj)return j;return j;return-1;return-1;本讲稿第五十八页，共一百七十页例例6-8 对半检索对半检索n n“对半检索对半检索对半检索对半检索”亦称亦称亦称亦称“两分法检索两分法检索两分法检索两分法检索”。在检索过程中用到。在检索过程中用到。在检索过程中用到。在检索过程中用到三个变量：三个变量：三个变量：三个变量：lower:记录检索区间下界，初值是记录检索区间下界，初值是0；upper:记录检索区间上界，初值是记录检索区间上界，初值是n-1；j:标记当前检索位置。标记当前检索位置。本讲稿第五十九页，共

48、一百七十页n n检索思想令检索思想令检索思想令检索思想令j=(lower+upper)/2j=(lower+upper)/2key=aj:找到，位置为；函数找到，位置为；函数search返回返回j keyaj:key在在aj与与aupper之间，之间，检索区间缩小一半检索区间缩小一半检索区间缩小一半检索区间缩小一半,lower=j+1重复上述过程。重复的终止条件为重复上述过程。重复的终止条件为重复上述过程。重复的终止条件为重复上述过程。重复的终止条件为 upper-lower 0 upper-lower 0，表示未找到，返回，表示未找到，返回，表示未找到，返回，表示未找到，返回 -1-1。24

49、243333454557576060616162627070757577778080909094949999lowerupperjlowerupper本讲稿第六十页，共一百七十页n n以关键字以关键字key值为值为60为例的检索过程为例的检索过程j=(lower+upper)/2keyaj:lower=j+1j=(lower+upper)/2key=aj:return j24243333454557576060616162627070757577778080909094949999lowerupperjupperjlowerj本讲稿第六十一页，共一百七十页2424333345455757606

50、0616162627070757577778080909094949999lowerupperjupperjlowerj以关键字以关键字key值为值为58为例的检索过程为例的检索过程j=(lower+upper)/2keyaj:lower=j+1j=(lower+upper)/2keyaj:lower=j+1upper-lower=0lower=0；upper=n-1；结束结束key=ajj=(lower+upper)/2return jlower=j+1upper=j-1keyajreturn -1本讲稿第六十三页，共一百七十页编出函数如下：编出函数如下：int half_search(in