C++程序设计第6章2

1、习题：习题： 讲义讲义P217 基本概念与基础知识自测题基本概念与基础知识自测题 、习题、习题6.6本周实验：本周实验： 1） 习题习题6.6、 2）课堂补充题，调试并上传）课堂补充题，调试并上传预习：预习：6.4、第、第7章章7.17.3第第6章模板与数据结构要求：章模板与数据结构要求：（1）理解函数模板与类模版；）理解函数模板与类模版；（2）线性表：掌握模板编写程序的方法，掌握顺序表在）线性表：掌握模板编写程序的方法，掌握顺序表在 内存中的分配与使用；内存中的分配与使用；（3）掌握主要查找与排序的算法；）掌握主要查找与排序的算法；（4）模板与类参数，理解类型参数和参数化类型（模板）模板与类

2、参数，理解类型参数和参数化类型（模板） 注：本章注：本章6.5节不要求节不要求 .2 排序与查找排序与查找 人们经常需要在一个数据集合中搜寻满足特定条件的人们经常需要在一个数据集合中搜寻满足特定条件的数据元素数据元素。 为了提高查找效率，应当先对集合中的数据进行排序为了提高查找效率，应当先对集合中的数据进行排序 查找查找 : : 从一个从一个数据集合数据集合中找出中找出特定元素特定元素的过程。的过程。 数据集合中的元素一般是同类型的对象。数据集合中的元素一般是同类型的对象。 特定元素特定元素: : 某个域具有特定的值。某个域具有特定的值。 用以区分各数据元素的域称为用以区分各数据元素的域称为关

3、键域或关键字关键域或关键字。顺序查找顺序查找: :依次地考察数据集合中的每个元素依次地考察数据集合中的每个元素。顺序查找的执行时间函数的阶为顺序查找的执行时间函数的阶为 n (n (线性阶线性阶) )。 若数据集合中的元素是有序的，并存贮在一维数组中，若数据集合中的元素是有序的，并存贮在一维数组中，就可以使用效率较高的折半查找方法。就可以使用效率较高的折半查找方法。6.2.1 常用查找方法常用查找方法 顺序查找：顺序查找：从第一个元素开始，顺序查找直到找到或查到最后一个元素为止。从第一个元素开始，顺序查找直到找到或查到最后一个元素为止。 查找是按查找是按关键字关键字（key word）进行。可

4、以唯一地把资料区分出来）进行。可以唯一地把资料区分出来的数据被称为的数据被称为主关键字主关键字。如学生的资料如学生的资料(结构体变量结构体变量):struct studentint id ; /学号学号char name20; / 姓名姓名char sex; / 性别性别int age; / 年龄年龄char address60; /家庭地址家庭地址float eng, phy,math , electron; /英语英语, ,物理物理, ,数学和电子学成绩数学和电子学成绩; 学号可作为学号可作为主关键字主关键字。 如果关键字小的排在前面，我们称为升序排列，反之为降序排列。如果关键字小的排在前

5、面，我们称为升序排列，反之为降序排列。这时可以采用这时可以采用对半查找对半查找（binary search）。 8917131120719212331262925373923查找查找midlowhigh2021292623313739lowmidhigh202123lowmid high23low mid high查找成功例查找成功例有序数据有序数据方法之一：方法之一：对半查找对半查找 定义两个指针定义两个指针low和和high指向首尾两元素，取指向首尾两元素，取mid= (low+high)/2，如，如mid指向元素是所查找的，则结束。如果该元指向元素是所查找的，则结束。如果该元素关键字大了

6、，则取素关键字大了，则取low=mid +1， high不变，继续查找；如果该元素不变，继续查找；如果该元素关键字小了，则取关键字小了，则取 high=mid-1，low不变，继续查找。如果查到不变，继续查找。如果查到lowhigh仍未找到，则失败，停止。仍未找到，则失败，停止。low25781113179192023212629313710查找查找39midhigh25781113179lowmidhigh1113179low midhigh9low mid high查找失败例查找失败例 while （区间低端值不大于高端值区间低端值不大于高端值） 计算区间的中点下标值；计算区间的中点下标值

7、； if （中点处的元素值等于指定值中点处的元素值等于指定值） 返回区间中点的下标返回区间中点的下标 ； else 确定下一步考察的区间确定下一步考察的区间； 对半查找算法对半查找算法: :【例例6.4】对半查找递归算法，作为有序表模板类成员对半查找递归算法，作为有序表模板类成员函数。递归方法易读易懂，但效率低。函数。递归方法易读易懂，但效率低。（自学）（自学）【例例6.5】对半查找迭代算法。对半查找迭代算法。该例中迭代算法的可读性也不差，效率要高于递归。该例中迭代算法的可读性也不差，效率要高于递归。*本例中出现的成员函数本例中出现的成员函数Binarysearch(T & x)const ，

8、称为称为 const成员函数，该函数保证只读。相应节点对象成员函数，该函数保证只读。相应节点对象重载的比较运算符也必须是重载的比较运算符也必须是const。 const函数的函数的this指针所指对象为常量，即它不能修改对指针所指对象为常量，即它不能修改对象的数据成员，而且在函数体内只能调用象的数据成员，而且在函数体内只能调用const成员函数，成员函数，不能调用其他成员函数。如果编程时不慎修改对象的数据不能调用其他成员函数。如果编程时不慎修改对象的数据成员，编译器会报错。成员，编译器会报错。 【例【例6.5】对半查找迭代算法对半查找迭代算法。template int Orderedlist:

9、BinarySearch( const T & x)const int high=last ,low=0,mid; / last 当前有序表最大下标当前有序表最大下标 while(low=high) mid=(low+high)/2; if(xslistmid) high=mid-1; /左缩查找区间左缩查找区间 else if(slistmidx) low=mid+1; / 右缩查找区间右缩查找区间 else return mid; if(slistmid!=x)mid=-1; return mid; class Elementint key;/ 其他域省略其他域省略public:bool

10、operator(Element ele)const return keyele.key; bool operator!=(Element ele)const return key!=ele.key; void putkey(int k) key=k; /要寻找的元素要寻找的元素 void show() coutkeyt; ；/重载比较运算符，元素比较，实际是元素关键域的比较重载比较运算符，元素比较，实际是元素关键域的比较int main() const int h=19; int i,k=47; Orderedlist ordlist; int ah=2,3,5,7,11,13,17,19,

11、23,29,31,37,41,43, 47,53,59,61,67; /升序升序 Element nh,elem; for(i=0;ih;i+) ni.putkey(ai); /用用ai为当前对象为当前对象ni赋值赋值 for(i=0;ih;i+) ordlist.Insert(ni,i); /在线性表尾插入，建立升序顺序表在线性表尾插入，建立升序顺序表 ordlist.print(); elem.putkey(k); i=ordlist.Binarysearch(elem); cout整数整数k在表中位置（下标）：在表中位置（下标）：iendl; k=33; elem.putkey(k);

12、i=ordlist.Binarysearch(elem); cout整数整数k在表中位置（下标）：在表中位置（下标）：iendl; return 0;6.6.2 常用的排序法常用的排序法排序功能排序功能: : 将数据元素的无序序列调整为一个有序序将数据元素的无序序列调整为一个有序序列。列。 数据元素中一般有多个数据项，排序可选择其中数据元素中一般有多个数据项，排序可选择其中一个可排序的数据项（可进行比较运算）作为依据，一个可排序的数据项（可进行比较运算）作为依据，称为称为排序关键字排序关键字。 为了能使用高效率的折半查找算法，通常希望数为了能使用高效率的折半查找算法，通常希望数据序列按关键域有

13、序排列。据序列按关键域有序排列。排序：将数据元素的任意序列重新排列成按关键域有排序：将数据元素的任意序列重新排列成按关键域有序的序列。序的序列。 和查找相比，排序相对费时。是否要对数组排序，和查找相比，排序相对费时。是否要对数组排序，取决于对数组的访问次数。取决于对数组的访问次数。 从小到大排序称从小到大排序称升序升序，反之为，反之为降序降序。 最常见的是最常见的是插入排序插入排序、选择排序选择排序和和交换排序交换排序。 1 8 10 24 35 58 60 24 8 35 1 60 10 58 8 24 35 1 60 10 58 8 24 35 1 60 10 58 1 8 24 35 6

14、0 10 581插入排序插入排序(Insert Sorting)设整数数组为设整数数组为a： 24 8 35 1 60 10 58排序目标是使数组元素按升序排列。排序目标是使数组元素按升序排列。对具有对具有n个元素的数组插入排序需要处理个元素的数组插入排序需要处理(n1)遍。遍。排序过程：排序过程： 第第i遍处理时，按冒泡方式将遍处理时，按冒泡方式将ai插入已排序部分。插入已排序部分。直接插入排序直接插入排序:【例【例6.66.6】升序直接插入排序算法】升序直接插入排序算法templatevoid Orderedlist:InsertSort()T temp;int i,j;for (i=1;

15、i0&tempslistj-1)slistj=slistj-1;j-; /查找与移动同时做查找与移动同时做slistj=temp; /插入位置已找到，立即插入插入位置已找到，立即插入class Elementstring key;/ / 其他域省略其他域省略public:bool operator(Element ele)return keyele.key;void putkey(string k)key=k;void show()coutkeyt; ;int main()const int h=10; Element nh;int i;Orderedlist ordlist;string m

16、slisth=cat,book,car,zoo,fish, cab,dog,cap,fox,can;for(i=0;ih;i+) ni.putkey(mslisti);for(i=0;ih;i+) ordlist.Insert(ni,i); /建立顺序表建立顺序表cout未排序表：未排序表：endl;ordlist.print();ordlist.InsertSort();cout已排序表：已排序表：endl;ordlist.print();return 0;【例【例6.76.7】升序对半插入排序算法】升序对半插入排序算法用对半查找思想取代顺序查找（快于插入排序）用对半查找思想取代顺序查找（快

17、于插入排序）template void Orderedlist:BinaryInsertSort() T temp; int low,high,mid,i,j; for (i=1;i=last;i+) temp=slisti; low=0; high=i-1; while (low=high) / /请注意与对半查找的不同之处请注意与对半查找的不同之处 mid=(low+high)/2;if(temp=low;j-) slistj+1=slistj; slistlow=temp; 插入排序：插入排序： 在每次循环中设法把一个元素插入到已经排序的部分在每次循环中设法把一个元素插入到已经排序的部分

18、序列里的合适位置，是得到的序列任然是有序的。序列里的合适位置，是得到的序列任然是有序的。 当被处理的最后一个元素也插入到有序序列后，整个当被处理的最后一个元素也插入到有序序列后，整个排序工作完成。排序工作完成。优点：优点： 利用一个一个元素的插入比较，将元素放入适当的位利用一个一个元素的插入比较，将元素放入适当的位置是一种简单的排序方式。置是一种简单的排序方式。缺点：缺点： 由于每插入一个元素都必须与之前已排序好的元素比由于每插入一个元素都必须与之前已排序好的元素比较，需要花费较长时间。较，需要花费较长时间。 2 . 交换排序交换排序 设数组有设数组有n n个元素，目标是使数组元素按个元素，目

19、标是使数组元素按升序升序排列。排列。在最坏情况下，冒泡排序方法也要对数组处理在最坏情况下，冒泡排序方法也要对数组处理(n-1)(n-1)遍。遍。 冒泡排序冒泡排序 交换排序的基本思想是按关键字两两排序对象，如果交换排序的基本思想是按关键字两两排序对象，如果发生逆序则交换之，直到所有的对象都排好序为止。发生逆序则交换之，直到所有的对象都排好序为止。 将相邻的两个数据加以比较，若下面一个小于上面一将相邻的两个数据加以比较，若下面一个小于上面一个，则两数交换，若下面一个大于上面一个，则两个位置个，则两数交换，若下面一个大于上面一个，则两个位置不变。继续将上面一个小的值与它上面的值进行比较，重不变。继

20、续将上面一个小的值与它上面的值进行比较，重复此操作，直到比较到最上面一个值。（完成一次排序）复此操作，直到比较到最上面一个值。（完成一次排序）第第1 1遍冒泡处理过程遍冒泡处理过程iai045451151527070334344602852860 iai045454511515152707070334342846028345286060第第1 1遍冒泡处理过程遍冒泡处理过程iai045454545115151515270707028334342870460283434528606060第第1 1遍冒泡处理过程遍冒泡处理过程iai045454545451151515151527070702828

21、334342870704602834343452860606060第第1 1遍冒泡处理过程遍冒泡处理过程iai第一遍第一遍处理后处理后045454545451511515151515452707070282828334342870707046028343434345286060606060第第1 1遍冒泡处理过程遍冒泡处理过程对数组对数组 a 进行各遍冒泡处理的结果进行各遍冒泡处理的结果第第 1 遍遍第第 2 遍遍第第 3 遍遍第第 4 遍遍iai处理后处理后处理后处理后处理后处理后处理后处理后04515151515115452828282702845343433470344545460347

22、0606052860607070第第1 1遍冒泡：遍冒泡：a0a5的最小元素上冒到的最小元素上冒到a0；第第2 2遍冒泡：遍冒泡：a1a5的最小元素上冒到的最小元素上冒到a1；第第i+1i+1遍冒泡：遍冒泡：aia5的最小元素上冒到的最小元素上冒到ai；for(i=0;ii; k-) /第第i次冒泡次冒泡 if(slistk-1slistk) 交换两者；交换两者； 改进算法改进算法过程当中排好序，则提前终止冒泡过程当中排好序，则提前终止冒泡noswap=true;noswap=false; /发生交换发生交换if(noswap) break; /终止终止i循环循环【例【例6.86.8】冒泡排序

23、算法】冒泡排序算法template void Orderedlist:BubbleSort() bool noswap; int i,j; T temp; for (i=0;ii;j-) /从下往上冒泡从下往上冒泡if(slistjslistj-1) temp=slistj; slistj=slistj-1; slistj-1=temp; noswap=false; if(noswap) break; /本趟无交换，则终止算法。本趟无交换，则终止算法。 3选择排序（选择排序（Selection Sort）基本思想：基本思想：每一趟从待排序的记录中选出关键字最每一趟从待排序的记录中选出关键字最小

24、的元素，顺序放在已排好序的子序列的后面，直小的元素，顺序放在已排好序的子序列的后面，直到全部记录排序完成。到全部记录排序完成。4938659776132749 1338659776492749 1327659776493849 1327389776496549 1327384976976549 1327384949976576 1327384949659776 1327384949657697【例【例6.96.9】直接选择排序】直接选择排序作为作为Orderedlist类的成员函数。类的成员函数。 template void Orderedlist:SelectSort() int i,j,k

25、;T temp; for(i=0;ilast;i+)k=i;temp=slisti;for(j=i;j=last;j+) if(slistjtemp) /找最小元素找最小元素k=j;temp=slistj; if(k!=i) /交换交换temp=slisti;slisti=slistk;slistk=temp; 算法：算法：1 初始化初始化2 while (i a1.length) & (j a2.length) 将将a1i、a2j中的较小者送入中的较小者送入anew； 指向较小元素的指针后移一个位置指向较小元素的指针后移一个位置 3 while (a1尚有剩余元素尚有剩余元素) 将将a1剩余

26、元素添到新数组尾部剩余元素添到新数组尾部 4 while (a2尚有剩余元素尚有剩余元素) 将将a2剩余元素添到新数组尾部剩余元素添到新数组尾部 合并合并 问题：问题：将两个有序的数组合并成一个有序的数组。将两个有序的数组合并成一个有序的数组。a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=0 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=1 3 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=2 3 4 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=3 3 4

27、5 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=4 3 4 5 5 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=5 3 4 5 5 6 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=6 3 4 5 5 68 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=7 3 4 5 5 6 8 9 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=8 3 4 5 5 6 8 910a1 a24 6 8 10 11 14 3 5 5 9 i

28、j anew: k=8 3 4 5 5 6 8 910 11a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=8 3 4 5 5 6 8 910 11 14template void Orderedlist:Merge(Orderedlist & ls1,Orderedlist & ls2)int i=0,j=0,k=0;while(i=ls1.last)&(j=ls2.last)if(ls1.slistils2.slistj) slistk=ls1.slisti; i+; else slistk=ls2.slistj; j+; k+; last+;while(i

29、=ls1.last) /复制第一个表的剩余元素复制第一个表的剩余元素slistk=ls1.slisti; i+;k+; last+;while(j=ls2.last) /复制第二个表的剩余元素复制第二个表的剩余元素slistk=ls2.slistj; j+;k+; last+;6.4 模板与类参数模板与类参数 以类对象作为函数的实参，实现被积函数以类对象作为函数的实参，实现被积函数( (类对象的类对象的成员函数成员函数) )的传递：的传递： 【例【例6.12】设计梯形法求积分的函数模板。设计梯形法求积分的函数模板。以模板参数以模板参数T来引入被积函数类，由该参数调用来引入被积函数类，由该参数调

30、用欲求定积分的函数欲求定积分的函数【例【例6.11】设计梯形法求积分的类模板。设计梯形法求积分的类模板。求积分的函数为独立的非成员函数。该方法更简洁。求积分的函数为独立的非成员函数。该方法更简洁。 梯形法求积分是一种求函数定积分的近似方法。对函数梯形法求积分是一种求函数定积分的近似方法。对函数 f(x) 将积分将积分区间区间 a,b 分成分成 n 份，每一份看作一个近似梯形，函数在该区间的份，每一份看作一个近似梯形，函数在该区间的定积分就是所有近似梯形的面积和。积分步长为：定积分就是所有近似梯形的面积和。积分步长为： step=(b-a)/n面积为：面积为： s = step*(f(x0)+f(x1)/2+step*(f(x1)+f(x2)/2+. +step*(f(xn-1)+f(xn)/2 = step*(f(x0)/2+f(x1)+f(x2)+.+f(xn-1)+f(xn)/2) class F1 public: double fun(double x)return (1+x+2*x*x); ;class F2 public: double fun(double x)return (1+x+2*x*x+3*x*x*x); ;class F3 public: double fun(double x) return (1+x+2*x*x+3*x*x*x+4*x*x*x*x)