chap9-C++课件-清华大学郑莉PPT资料.ppt
- 文档编号:7751758
- 上传时间:2023-05-09
- 格式:PPT
- 页数:80
- 大小:355KB
chap9-C++课件-清华大学郑莉PPT资料.ppt
《chap9-C++课件-清华大学郑莉PPT资料.ppt》由会员分享,可在线阅读,更多相关《chap9-C++课件-清华大学郑莉PPT资料.ppt(80页珍藏版)》请在冰点文库上搜索。
/用于存放任意类型的数据inthaveValue;
/用于标记item是否已被存入内容public:
Store(void);
/默认形式(无形参)的构造函数TGetElem(void);
/提取数据函数voidPutElem(Tx);
/存入数据函数;
/默认形式构造函数的实现templateStore:
Store(void):
haveValue(0),10,template/提取数据函数的实现TStore:
GetElem(void)/如果试图提取未初始化的数据,则终止程序if(haveValue=0)cout/存入数据函数的实现voidStore:
PutElem(Tx)haveValue+;
/将haveValue置为TRUE,表示item中已存入数值item=x;
/将x值存入item,11,intmain()Studentg=1000,23;
StoreS1,S2;
StoreS3;
StoreD;
S1.PutElem(3);
S2.PutElem(-7);
coutS1.GetElem()S2.GetElem()endl;
S3.PutElem(g);
coutThestudentidisS3.GetElem().idendl;
coutRetrievingobjectD;
coutD.GetElem()endl;
/输出对象D的数据成员/由于D未经初始化,在执行函数D.GetElement()时出错,12,13,第二部分群体数据,线性群体线性群体的概念直接访问群体-数组类顺序访问群体-链表类栈类队列类,14,群体的概念,群体是指由多个数据元素组成的集合体。
群体可以分为两个大类:
线性群体和非线性群体。
线性群体中的元素按位置排列有序,可以区分为第一个元素、第二个元素等。
非线性群体不用位置顺序来标识元素。
15,线性群体的概念,线性群体中的元素次序与其位置关系是对应的。
在线性群体中,又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。
在本章我们只介绍直接访问和顺序访问。
16,数组,静态数组是具有固定元素个数的群体,其中的元素可以通过下标直接访问。
缺点:
大小在编译时就已经确定,在运行时无法修改。
动态数组由一系列位置连续的,任意数量相同类型的元素组成。
优点:
其元素个数可在程序运行时改变。
动态数组类模板:
例9-3(9_3.h),直接访问的线性群体,#ifndefARRAY_CLASS#defineARRAY_CLASSusingnamespacestd;
#include#include#ifndefNULLconstintNULL=0;
#endif/NULLenumErrorTypeinvalidArraySize,memoryAllocationError,indexOutOfRange;
char*errorMsg=Invalidarraysize,Memoryallocationerror,Invalidindex:
;
动态数组类模板程序,17,templateclassArrayprivate:
T*alist;
intsize;
voidError(ErrorTypeerror,intbadIndex=0)const;
public:
Array(intsz=50);
Array(constArray,18,19,数组类模板的构造函数,/构造函数templateArray:
Array(intsz)if(sz=0)/sz为数组大小(元素个数),若小于0,则输出错误信息Error(invalidArraySize);
size=sz;
/将元素个数赋值给变量sizealist=newTsize;
/动态分配size个T类型的元素空间if(alist=NULL)/如果分配内存不成功,输出错误信息Error(memoryAllocationError);
直接访问的线性群体,20,数组类的拷贝构造函数,templateArray:
Array(constArray,直接访问的线性群体,21,浅拷贝,intmain()ArrayA(10);
.ArrayB(A);
.,templateArray:
Array(constArray,22,深拷贝,23,数组类的重载=运算符函数,templateArray,直接访问的线性群体,24,数组类的重载下标操作符函数,templateT,直接访问的线性群体,25,为什么有的函数返回引用,如果一个函数的返回值是一个对象的值,它就被认为是一个常量,不能成为左值。
如果返回值为引用。
由于引用是对象的别名,所以通过引用当然可以改变对象的值。
直接访问的线性群体,26,重载指针转换操作符,templateArray:
operatorT*(void)const/返回当前对象中私有数组的首地址returnalist;
直接访问的线性群体,27,指针转换运算符的作用,#includeusingnamespacestd;
intmain()inta10;
voidread(int*p,intn);
read(a,10);
voidread(int*p,intn)for(inti=0;
ipi;
intmain()Arraya(10);
voidread(int*p,n);
直接访问的线性群体,28,Array类的应用,例9-4求范围2N中的质数,N在程序运行时由键盘输入。
直接访问的线性群体,#include#include#include9_3.husingnamespacestd;
intmain()ArrayA(10);
intn;
intprimecount=0,i,j;
cout=2asupperlimitforprimenumbers:
cinn;
Aprimecount+=2;
/2是一个质数for(i=3;
ii/2)Aprimecount+=i;
for(i=0;
iprimecount;
i+)coutsetw(5)Ai;
if(i+1)%10=0)coutendl;
coutendl;
29,30,链表,链表是一种动态数据结构,可以用来表示顺序访问的线性群体。
链表是由系列结点组成的,结点可以在运行时动态生成。
每一个结点包括数据域和指向链表中下一个结点的指针(即下一个结点的地址)。
如果链表每个结点中只有一个指向后继结点的指针,则该链表称为单链表。
顺序访问的线性群体,31,单链表,顺序访问的线性群体,32,单链表的结点类模板,templateclassNodeprivate:
Node*next;
Tdata;
Node(constT,顺序访问的线性群体,33,在结点之后插入一个结点,data1,p,data,templatevoidNode:
InsertAfter(Node*p)/p节点指针域指向当前节点的后继节点p-next=next;
next=p;
/当前节点的指针域指向p,顺序访问的线性群体,34,删除结点之后的结点,顺序访问的线性群体,data1,Node*Node:
DeleteAfter(void)Node*tempPtr=next;
if(next=NULL)returnNULL;
next=tempPtr-next;
returntempPtr;
tempPtr,35,链表的基本操作,生成结点插入结点查找结点删除结点遍历链表清空链表,顺序访问的线性群体,36,链表类模板(例9-6),/9_6.h#ifndefLINKEDLIST_CLASS#defineLINKEDLIST_CLASS#include#includeusingnamespacestd;
#ifndefNULLconstintNULL=0;
#endif/NULL#include9_5.h,顺序访问的线性群体,templateclassLinkedListprivate:
Node*front,*rear;
Node*prevPtr,*currPtr;
intposition;
Node*GetNode(constT,37,public:
LinkedList(void);
LinkedList(constLinkedList,38,voidInsertFront(constT#endif/LINKEDLIST_CLASS,39,40,链表类应用举例(例9-7),#includeusingnamespacestd;
#include9_6.h#include9_6.cppintmain()LinkedListLink;
inti,key,item;
iitem;
Link.InsertFront(item);
顺序访问的线性群体,coutkey;
Link.Reset();
41,while(!
Link.EndOfList()if(Link.Data()=key)Link.DeleteAt();
Link.Next();
coutList:
while(!
Link.EndOfList()coutLink.Data();
42,43,特殊的线性群体栈,栈是只能从一端访问的线性群体,可以访问的这一端称栈顶,另一端称栈底。
特殊的线性群体栈,44,栈的应用举例函数调用,特殊的线性群体栈,45,栈的应用举例表达式处理,特殊的线性群体栈,46,栈的基本状态,栈空栈中没有元素栈满栈中元素个数达到上限一般状态栈中有元素,但未达到栈满状态,特殊的线性群体栈,47,48,栈的基本操作,初始化入栈出栈清空栈访问栈顶元素检测栈的状态(满、空),特殊的线性群体栈,49,栈类模板(例9-8),特殊的线性群体栈,/9-8.h#ifndefSTACK_CLASS#defineSTACK_CLASS#include#includeusingnamespacestd;
constintMaxStackSize=50;
templateclassStackprivate:
TstacklistMaxStackSize;
inttop;
public:
Stack(void);
voidPush(constT/类的实现略,50,栈的应用,例9.9一个简单的整数计算器实现一个简单的整数计算器,能够进行加、减、乘、除和乘方运算。
使用时算式采用后缀输入法,每个操作数、操作符之间都以空白符分隔。
例如,若要计算3+5则输入35+。
乘方运算符用表示。
每次运算在前次结果基础上进行,若要将前次运算结果清除,可键入c。
当键入q时程序结束。
9-9.h9-9.cpp,特殊的线性群体栈,/9_9.h#include#include#include#includeusingnamespacestd;
enumBooleanFalse,True;
#include9_8.hclassCalculatorprivate:
StackS;
voidEnter(intnum);
BooleanGetTwoOperands(int,51,voidCalculator:
Enter(intnum)S.Push(num);
BooleanCalculator:
GetTwoOperands(int,52,voidCalculator:
Compute(charop)Booleanresult;
intoperand1,operand2;
result=GetTwoOperands(operand1,operand2);
if(result)switch(op)case+:
S.Push(operand2+operand1);
break;
case-:
S.Push(operand2-operand1);
case*:
S.Push(operand2*operand1);
case/:
if(operand1=0)cerrDivideby0!
endl;
S.ClearStack();
elseS.Push(operand2/operand1);
case:
S.Push(pow(operand2,operand1);
cout=S.Peek();
elseS.ClearStack();
53,voidCalculator:
Run(void)charc20;
while(cinc,*c!
=q)switch(*c)casec:
if(strlen(c)1)Enter(atoi(c);
elseCompute(*c);
case+:
Compute(*c);
default:
Enter(atoi(c);
54,voidCalculator:
Clear(void)S.ClearStack();
/9_9.cpp#include9-9.hintmain()CalculatorCALC;
CALC.Run();
55,56,特殊的线性群体队列,队列是只能向一端添加元素,从另一端删除元素的线性群体,57,队列的基本状态,队空队列中没有元素队满队列中元素个数达到上限一般状态队列中有元素,但未达到队满状态,特殊的线性群体队列,元素移动方向,元素移动方向,58,59,循环队列,在想象中将数组弯曲成环形,元素出队时,后继元素不移动,每当队尾达到数组最后一个元素时,便再回到数组开头。
特殊的线性群体队列,60,61,例9-10队列类模板,特殊的线性群体队列,#ifndefQUEUE_CLASS#defineQUEUE_CLASS#include#includeusingnamespacestd;
constintMaxQSize=50;
templateclassQueueprivate:
intfront,rear,count;
TqlistMaxQSize;
Queue(void);
voidQInsert(constT/成员函数的实现略,62,第三部分群体数据的组织,插入排序选择排序交换排序顺序查找折半查找,63,排序(sorting),排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素的任意序列,重新排列成一个按关键字有序的序列。
数据元素:
数据的基本单位。
在计算机中通常作为一个整体进行考虑。
一个数据元素可由若干数据项组成。
关键字:
数据元素中某个数据项的值,用它可以标识(识别)一个数据元素。
在排序过程中需要完成两种基本操作:
比较两个数的大小调整元素在序列中的位置,群体数据的组织,64,内部排序与外部排序,内部排序:
待排序的数据元素存放在计算机内存中进行的排序过程。
外部排序:
待排序的数据元素数量很大,以致内存存中一次不能容纳全部数据,在排序过程中尚需对外存进行访问的排序过程。
群体数据的组织,65,内部排序方法,插入排序选择排序交换排序,群体数据的组织,66,插入排序的基本思想,每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上,直到待排序元素插入完为止。
初始状态:
541020123,67,直接插入排序,在插入排序过程中,由于寻找插入位置的方法不同又可以分为不同的插入排序算法,这里我们只介绍最简单的直接插入排序算法。
例9-11直接插入排序函数模板(9_11.h),群体数据的组织,templatevoidInsertionSort(TA,intn)inti,j;
Ttemp;
for(i=1;
i0,直接插入排序函数模板(9_11.h),68,69,选择排序的基本思想,每次从待排序序列中选择一个关键字最小的元素,(当需要按关键字升序排列时),顺序排在已排序序列的最后,直至全部排完。
341020125,341020125,第i次选择后,将选出的那个记录与第i个记录做交换。
70,直接选择排序,在选择类排序方法中,从待排序序列中选择元素的方法不同,又分为不同的选择排序方法,其中最简单的是通过顺序比较找出待排序序列中的最小元素,称为直接选择排序。
例9-12直接选择排序函数模板(9-12.h),群体数据的组织,templatevoidSwap(T,直接选择排序函数模板(9-12.h),71,72,交换排序的基本思想,两两比较待排序序列中的元素,并交换不满足顺序要求的各对元素,直到全部满足顺序要求为止。
群体数据的组织,73,最简单的交换排序方法起泡排序,对具有n个元素的序列按升序进行起泡排序的步骤:
首先将第一个元素与第二个元素进行比较,若为逆序,则将两元素交换。
然后比较第二、第三个元素,依次类推,直到第n-1和第n个元素进行了比较和交换。
此过程称为第一趟起泡排序。
经过第一趟,最大的元素便被交换到第n个位置。
对前n-1个元素进行第二趟起泡排序,将其中最大元素交换到第n-1个位置。
如此继续,直到某一趟排序未发生任何交换时,排序完毕。
对n个元素的序列,起泡排序最多需要进行n-1趟。
群体数据的组织,74,起泡排序举例,对整数序列85243按升序排序,85243,5,2,4,3,8,2,4,3,5,8,2,3,4,5,8,2,3,4,5,8,初始状态,第一趟结果,第二趟结果,第三趟结果,第四趟结果,小的逐渐上升,每趟沉下一个最大的,群体数据的组织,75,例9-13起泡排序函数模板,templatevoidSwap(T,templatevoidBubbleSort(TA,intn)inti,j;
intlastExchangeIndex;
i=n-1;
while(i0)lastExchangeIndex=0;
for(j=0;
ji;
j+)if(Aj+1Aj)Swap(Aj,Aj+1);
lastExchangeIndex=j;
i=lastExchangeIndex;
群体数据的组织,76,顺序查找,其基本思想从序列的首元素开始,逐个元素与待查找的关键字进行比较,直到找到相等的。
若整个序列中没有与待查找关键字相等的元素,就是查找不成功。
顺序查找函数模板例9-14,群体数据的组织,templateintSeqSearch(Tlist,intn,Tkey)for(inti=0;
in;
i+)if(listi=key)returni;
return-1;
顺序查找函数模板,77,78,折半查找的基本思想,对于已按关键字排序的序列,经过一次比较,可将序列分割成两部分,然后只在有可能包含待查元素的一部分中继续查找,并根据试探结果继续分割,逐步缩小查找范围,直至找到或找不到为止。
群体数据的组织,79,折半查找举例,用折半查找法,在下列序列中查找值为21的元素:
M=INT(L+H)/2)=3,L=M+1=4,M=INT(L+H)/2)=4,80,例10-5折半查找函数模板,templateintBinSearch(Tlist,intn,Tkey)intmid,low,high;
Tmidvalue;
low=0;
high=n-1;
while(low=high)mid=(low+high)/2;
midvalue=listmid;
if(key=midvalue)returnmid;
elseif(keymidvalue)high=mid-1;
elselow=mid+1;
群体数据的组织,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- chap9 C+ 课件 清华大学
![提示](https://static.bingdoc.com/images/bang_tan.gif)