模板与数据结构.ppt

《模板与数据结构.ppt》由会员分享，可在线阅读，更多相关《模板与数据结构.ppt（58页珍藏版）》请在课桌文档上搜索。

1、第6章 模板与数据结构,模板的引入：,6.1 模板,增强代码的通用性，使之不受数据类型的限制。,模板的实现：,将数据类型作为参数。,功能：创建一个通用功能的函数，支持多种不同形参，简化重载函数的函数体设计。,6.1.1 函数模板及其应用,函数模板定义：template返回类型 函数名(形式参数表)；,例.找出三个数中的最大数，通过函数模板来实现。,#include using namespace std;template/模板声明，其中T为类型参数T max(T a,T b,T c)/定义一个通用函数，用T作虚拟的类型名 if(ba)a=b;if(ca)a=c;return a;,int ma

2、in()int i1=185,i2=-76,i3=567,i;double d1=56.8,d2=90.2,d3=-314.7,d;long g1=6785,g2=-91245,g3=6734,g;/调用模板函数，此时T被int取代，也可缺省 i=max(i1,i2,i3);/调用模板函数，此时T被double取代 d=max(d1,d2,d3);/调用模板函数，此时T被long取代 g=max(g1,g2,g3);cout“i_max=“iendl;cout“f_max=“dendl;cout“g_max=“gendl;return 0;,函数模板注意事项,用函数模板比函数重载更方便，程序更

3、简洁。但它只适用于函数的参数个数相同而类型不同，且函数体相同的情况，若参数的个数不同，则不能用函数模板。,若有两个或多个类，其功能相同，仅数据类型不同：class Compare_int/对两个整数作比较public:Compare_int(int a,int b)x=a;y=b;int max()return(xy)?x:y;int min()return(xy)?x:y;private:int x,y;,6.1.2 类模板与线性表,若要比较两个浮点数大小呢？,类模板定义：,template class 类模板名./类体;,类模板名 对象名1，对象名n;/可带参数,template返回类型

4、类模板名:成员函数名(形参表)/成员函数体,在类模板外定义成员函数，应采用以下形式：,使用模板建立对象：,用类模板实现：,template/虚拟类型numtypeclass Compare/类模板名为Compare public:Compare(numtype a,numtype b)x=a;y=b;numtype max()return(xy)?x:y;numtype min()return(xy)?x:y;private:numtype x,y;,#include/类模板应用举例#include using namespace std;class Student/定义结构体类型Studen

5、t public:int id;/学号float gpa;/平均分 Student(int i=0,float g=0):id(i),gpa(g);template/类模板，实现对任意类型数据进行存取class Store T item;/存放任意类型数据int Valued;/标记item是否已被存入内容 public:Store();/默认形式的构造函数T GetElem();/提取数据函数void PutElem(T x);/存入数据函数;,templateStore:Store():Valued(0)templateT Store:GetElem()if(Valued=0)coutvo

6、id Store:PutElem(T x)Valued+;/将此置为ture，表示item中已存入数值 item=x;/将x值存入item,void main()Student g(1000,23);/声明Student类型结构体变量，赋以初值 Store S1,S2;/声明两个Store类对象 Store S3;/声明Store类对象S3 Store D;/声明Store类对象D S1.PutElem(3);/向对象S1中存入数据(初始化对象S1)S2.PutElem(-7);/向对象S2中存入数据(初始化对象S2)coutS1.GetElem()S2.GetElem()endl;/S1和S

7、2的数据成员 S3.PutElem(g);/向对象S3中存入数据 coutS3.GetElem().idendl;/输出对象S3的数据成员 cout“Retrieving object Dn”;coutD.GetElem()endl;/输出对象D的数据成员/由于D未初始化，在执行函数D.GetElem()过程中导致程序终止 return 0;,线性表,静态数组：由编译器编译时分配内存，数组的长度不可改变。防止的溢出：一般采用“大开小用”的方法，且应在添加新数据时判断表是否满。,直接前驱,直接后继,图6.2 向表中插入一个数据,【例6.3】顺序表类模板,template class seqlis

8、t T slistsize;/存放顺序表的数组 int Maxsize;/最大可容纳项数 int last;/已存表项的最后位置public:seqlist()last=-1;Maxsize=size;/初始化为空表 int Length()constreturn last+1;/计算表长度 int Find(T,检验主程序,常成员函数：只能引用本类中的数据成员，不能修改,template int seqlist:Find(T/找到，返回下标,template bool seqlist:IsIn(T,template T,template bool seqlist:Insert(T,templ

9、ate bool seqlist:Remove(T/表中不存在x,template int seqlist:Next(T,int main()seqlist seqlisti;/顺序表对象seqlisti的元素为整型 int i,j,k,a10=2,3,5,7,11,13,17,19,23,29;for(j=0;j_|endl;break;j=seqlisti.Length();for(i=0;ij;i+)coutseqlisti.Get(i);cout endl;/打印出seqlisti.slist-素数表 for(j=0;j10;j+)seqlistij=0;/采用下标运算符运算 for(

10、j=0;j10;j+)coutseqlistij;coutendl;for(j=0;j10;j+)seqlistij=aj;,seqlisti10=31;/实验能否增加元素 for(j=0;j11;j+)coutseqlistij;coutendl;k=7;if(seqlisti.IsIn(k)cout素数7在顺序表中 endl;/因形参为引用，所以实参不可用整数常量7 else cout 素数7不在顺序表中endl;k=17;if(seqlisti.Remove(k)cout删除素数17endl;/删除素数17 else cout找不到素数17，无法删除;j=seqlisti.Length(

11、);for(i=0;ij;i+)coutseqlisti.Get(i);/打印剩下的素数 coutendl;,if(seqlisti.Insert(k,j-1)/把素数17装回去,成功则打印 j=seqlisti.Length();for(i=0;ij;i+)coutseqlisti.Get(i);coutendl;cout“打印17后一个素数：“seqlisti.Get(seqlisti.Next(k)endl;cout“打印17前一个素数：”seqlisti.Get(seqlisti.Prior(k)endl;cout“素数17在表中位置（下标）为：“seqlisti.Find(k)end

12、l;if(seqlisti.IsEmpty()cout表是空的endl;else cout表不空endl;if(seqlisti.IsFull()cout表是满的endl;else cout表也不满endl;if(seqlisti.IsIn(k)cout素数17在表中endl;return 0;,6.2 排序与查找,例如字典:字典中的词条是按序存放的，我们才能按字母顺序找到要查的字。,排序(sorting)：,查找(search)：,在数据集合中寻找满足条件的数据对象，找到后进一步给出对象的具体信息，在数据库技术中称为检索。,6.2.1 常用查找方法,查找按关键字（key word）进行。可以

13、唯一地把资料区分出来的数据称为主关键字。如学生的资料(结构体变量):struct studentint id;/学号：主关键字char name20;/姓名char sex;/性别int age;/年龄char address60;/家庭地址float eng,phy,math,electron;/各科成绩;,6.2.1 常用查找方法,顺序查找：从第一个元素开始，顺序查找直到找到或查到最后一个元素为止。对半查找（折半查找）：针对有序数据的查找。若关键字小的排在前面，称为升序排列，反之为降序排列。,2 3 5 8 10 15 16 18 24 28 30 low hig mid,2 3 5 8

14、10 15 16 18 24 28 30 low mid hig,2 3 5 8 10 15 16 18 24 28 30 low mid hig,2 3 5 8 10 15 16 18 24 28 30 mid low hig,2 3 5 8 10 15 16 18 24 28 30 low mid hig,【例6.4】对半查找递归算法,【例6.4】对半查找递归算法，作为有序表模板类成员函数。template int Orderedlist:Binarysearch(const T 未找到但结束了，返回mid不加判断递归方法易读易懂，但效率低。注意递归的隐式循环代码编写。,传常量,有序表和结

15、点类模板定义，基本元素为类Elemen对象：class Elementint key;/其他域省略 public:bool operatorclass Orderedlistint maxsize;int last;T slistsize;public:Orderedlist()last=-1;maxsize=size;int Binarysearch(const T,【例6.4】对半查找递归算法,template bool Orderedlist:Insert(T,【例6.4】对半查找递归算法,int main()const int h=19;int i,k=37;Orderedlist o

16、rdlist;int ah=67,61,59,53,47,43,41,37,31,29,23,19,17,13,11,7,5,3,2;/降序Element nh,elem;for(i=0;ih;i+)ni.putkey(ai);for(i=0;ih;i+)ordlist.Insert(ni,0);/始终在0号元素插入，建立升序顺序表elem.putkey(k);ordlist.print();i=ordlist.Binarysearch(elem,0,h-1);cout整数k在表中位置（下标）：iendl;return 0;,【例6.5】对半查找迭代算法,【例6.5】对半查找迭代算法。temp

17、late int Orderedlist:BinarySearch(const T,对数据成员只读不写,6.6.2 常用的排序法,插入排序交换排序(冒泡)选择排序,插入排序(Insert Sorting),直接插入排序:(升序)当插入第i(i=1)个元素时,前面的元素0,1,i-1个元素已经排好序,将第i个元素的关键字与i-1,i-2,的关键字顺序进行比较,找到第一个比它小的,则第i个元素插到该元素之后。,【例6.6】升序直接插入排序算法,作为【例6.4】Orderedlist类的成员函数template void Orderedlist:InsertSort()T temp;int i,j;

18、for(i=1;i0,交换排序(冒泡）,15,18,9,5,23,10,13,7,16,15,18,9,5,23,10,13,7,16,不需要交换,需要交换,需要交换,7,13,7,10,7,23,9,7,不需要交换,需要交换,5,18,5,15,5,原始数据排列,冒泡排序,【例6.8】冒泡排序算法,冒泡排序算法，作为Orderedlist类的成员函数。template void Orderedlist:BubbleSort()bool noswap;int i,j;T temp;for(i=0;ii;j-)/从下往上冒泡if(slistjslistj-1),temp=slistj;slist

19、j=slistj-1;slistj-1=temp;noswap=false;if(noswap)break;/本趟无交换，则终止算法。冒泡排序的优点:可利用原来的数据排列的部分有序性。,找a0a5的最小元素下标；apos与a0换位；,选择排序,找a1a5的最小元素下标；apos与a1换位；,找a2a5的最小元素下标；apos与a2换位；,找a3a5的最小元素下标；apos与a3换位；,找a4a5的最小元素下标；apos与a4换位；,【例6.9】直接选择排序,template void Orderedlist:SelectSort()int i,j,k;T temp;for(i=0;ilast;

20、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;,6.3 索引查找与指针数组,索引查找：索引，就象一种目录（地址记录），找到标题对应的页号（具体地址），立即可以找到对应的内容，称索引查找（Index Search）。指针数组：数据元素为指针的数组称指针数组。,指针数组与字符串：,字符型指针数组可以实现字符串数组的功能：字符串的长度不等。如存储每周7天的英文名称，可定义一个char*name7的一维字符指针数组。,6.4

21、 模板与类参数,函数模板常用方式：(1)函数模板作为类模板的成员函数。(2)独立的非成员函数。,冒泡排序算法(作为成员函数),字符串类定义如下：class mystring char str21;int maxsize;int last;public:mystring()；last=-1;maxsize=21;str0=0;mystring(char*s)；mystring()void show()coutstrt;/显示也必须在数据类定义 bool operator(mystring/成员函数定义略,template class Orderedlist/*无关数据成员和成员函数省略*/pub

22、lic:void BubbleSort();void print();；template void Orderedlist:BubbleSort()bool noswap;/*算法过程详见例6.8*/*其他成员函数的定义略*/,冒泡排序算法(作为成员函数),int main()const int h=10;int i;Orderedlist ordlist;mystring nh=cat,book,car,zoo,fish,cab,dog,cap,fox,can;for(i=0;ih;i+)ordlist.Insert(ni,i);cout“未排序数组：endl;ordlist.print()

23、;ordlist.BubbleSort();cout“已排序数组：endl;ordlist.print();return 0;,冒泡排序算法(作为成员函数),【例6.10】冒泡排序算法(独立的非成员函数),字符串类定义如下：class mystring char str21;int maxsize;int last;public:mystring()；last=-1;maxsize=21;str0=0;mystring(char*s)；mystring()void show()coutstrt;/显示也必须在数据类定义 bool operator(mystring/成员函数定义略,【例6.10

24、】冒泡排序算法(独立的非成员函数),template void BubbleSort(T*slist,int n)bool noswap;int i,j;T temp;/.交换排序过程略/*独立的非成员函数*/,【例6.10】冒泡排序算法(独立的非成员函数),int main()const int h=10;int i;Orderedlist ordlist;mystring listh=cat,book,car,zoo,fish,cab,dog,cap,fox,can;cout“未排序数组：endl;for(i=0;ih,i+)listi.show();BubbleSort(list,h);cout“已排序数组：endl;for(i=0;ih,i+)listi.show();return 0;,Ch6 结束！谢谢！,Ch7 内容：动态内存分配,