【教学课件】第九章群体类.ppt
第九章 群体类,清华大学计算机与信息管理中心郑 莉,C+语言程序设计,2,本章主要内容,线性群体线性群体的概念直接访问群体-数组类顺序访问群体-链表类栈类队列类,3,群体的概念,群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。,4,线性群体的概念,线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。,5,数组,静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。动态数组由一系列位置连续的，任意数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。,直接访问线性群体,6,动态数组类模板,数组类模板：例9.1（9_1.h）,直接访问线性群体,#ifndef ARRAY_CLASS#define ARRAY_CLASS#include#include#ifndef NULLconst int NULL=0;#endif/NULLenum ErrorType invalidArraySize,memoryAllocationError,indexOutOfRange;char*errorMsg=Invalid array size,Memory allocation error,Invalid index:;,template class Array private:T*alist;int size;void Error(ErrorType error,int badIndex=0)const;public:Array(int sz=50);Array(const Array/类成员函数的实现略,9,Array类的应用,例9.2 求范围2N中的质数，N在程序运行时由键盘输入。,直接访问线性群体,#include#include#include 9_1.hvoid main(void)Array A(10);int n;int primecount=0,i,j;cout=2 as upper limit for prime numbers:;cin n;Aprimecount+=2;/2是一个质数,for(i=3;i i/2)Aprimecount+=i;for(i=0;i primecount;i+)cout setw(5)Ai;if(i+1)%10=0)cout endl;cout endl;,12,链表,链表是一种动态数据结构，可以用来表示顺序访问的线性群体。链表是由系列结点组成的，结点可以在运行时动态生成。每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。,顺序访问线性群体,13,单链表,顺序访问线性群体,14,例9-3 单链表的结点类模板,template class Node private:Node*next;public:T data;Node(const T/实现略,顺序访问线性群体,15,在结点p之后插入一个结点,顺序访问线性群体,data1,p,q,data,16,删除p结点之后的结点,顺序访问线性群体,data1,p,q,17,链表的基本操作,生成结点输出链表查找结点插入结点删除结点清空链表,顺序访问线性群体,18,例9-4 实现链表操作函数,#ifndef NODE_LIBRARY#define NODE_LIBRARY#include#include#include 9_3.h,顺序访问线性群体,/生成节点template Node*GetNode(const T,enum AppendNewline noNewline,addNewline;/输出链表template void PrintList(Node*head,AppendNewline addnl=noNewline)Node*currPtr=head;while(currPtr!=NULL)if(addnl=addNewline)cout data data NextNode（）;,/查找节点template int Find(Node*head,T,/在表头插入节点template void InsertFront(Node*,/删除链表的第一个节点template void DeleteFront(Node*,/删除链表中第一个数据域等于key的节点template void Delete(Node*,/在有序链表中插入一个节点template void InsertOrder(Node*,/清空链表-删除链表中的所有节点template void ClearList(Node*#endif/NODE_LIBRARY,27,例9.5 链表应用举例,从键盘输入10个整数，用这些整数值作为结点数据，生成一个链表，按顺序输出链表中结点的数值。然后从键盘输入一个待查找整数，在链表中查找该整数，若找到则删除该整数所在的结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在程序结束之前清空链表。9-5.cpp,顺序访问线性群体,#include#include 9_3.h#include 9_4.hvoid main(void)Node*head=NULL,*prevPtr,*delPtr;int i,key,item;for(i=0;i item;InsertFront(head,item);cout List:;PrintList(head,noNewline);cout endl;,cout key;prevPtr=head;while(Find(head,key,prevPtr)!=NULL)if(prevPtr=NULL)head=head-NextNode（）;else delPtr=prevPtr-DeleteAfter（）;delete delPtr;cout List:;PrintList(head,noNewline);cout endl;ClearList(head);,30,例9-6 链表类模板,/9_6.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include#include#ifndef NULLconst int NULL=0;#endif/NULL#include 9_3.h,顺序访问线性群体,template class LinkedList private:Node*front,*rear;Node*prevPtr,*currPtr;int size;int position;Node*GetNode(const T,public:LinkedList(void);LinkedList(const LinkedList,void InsertFront(const T#endif/LINKEDLIST_CLASS,34,例9-7 链表类应用举例,#include#include 9_6.h#include 9_6.cppvoid main(void)LinkedList Link;int i,key,item;for(i=0;i item;Link.InsertFront(item);,顺序访问线性群体,cout key;Link.Reset（）;,while(!Link.EndOfList（）)if(Link.Data（）=key)Link.DeleteAt（）;Link.Next（）;cout List:;Link.Reset（）;while(!Link.EndOfList（）)cout Link.Data（）;Link.Next（）;cout endl;,37,特殊的线性群体栈,栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。,38,栈的应用举例函数调用,特殊的线性群体栈,39,栈的应用举例表达式处理,特殊的线性群体栈,40,栈的基本状态,栈空栈中没有元素栈满栈中元素个数达到上限一般状态栈中有元素，但未达到栈满状态,特殊的线性群体栈,42,栈的基本操作,初始化入栈出栈清空栈访问栈顶元素检测栈的状态（满、空）,特殊的线性群体栈,43,例9-8 栈类模板,/9-8.h#ifndef STACK_CLASS#define STACK_CLASS#include#include const int MaxStackSize=50;,特殊的线性群体栈,template class Stack private:T stacklistMaxStackSize;int top;public:Stack(void);void Push(const T/类的实现略,45,栈的应用,例9.9 一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入3 5+。乘方运算符用表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入c。当键入q时程序结束。9-9.h 9-9.cpp,特殊的线性群体栈,/9_9.h#include#include#include#include enum Boolean False,True;#include 9_8.h,class Calculator private:Stack S;void Enter(int num);Boolean GetTwoOperands(int,void Calculator:Enter(int num)S.Push(num);Boolean Calculator:GetTwoOperands(int,void Calculator:Compute(char op)Boolean result;int operand1,operand2;result=GetTwoOperands(operand1,operand2);if(result=True)switch(op)case+:S.Push(operand2+operand1);break;case-:S.Push(operand2-operand1);break;case*:S.Push(operand2*operand1);break;,case/:if(operand1=0)cerr Divide by 0!endl;S.ClearStack（）;else S.Push(operand2/operand1);break;case:S.Push(pow(operand2,operand1);break;cout=S.Peek（）;else S.ClearStack（）;,void Calculator:Run(void)char c20;while(cin c,*c!=q)switch(*c)case c:S.ClearStack（）;break;case-:if(strlen(c)1)Enter(atoi(c);else Compute(*c);break;case+:,case*:case/:case:Compute(*c);break;default:Enter(atoi(c);break;void Calculator:Clear(void)S.ClearStack（）;,/9_9.cpp#include 9-9.hvoid main(void)Calculator CALC;CALC.Run（）;,54,特殊的线性群体队列,队列是只能向一端添加元素，从另一端删除元素的线性群体,55,队列的基本状态,队空队列中没有元素队满队列中元素个数达到上限一般状态队列中有元素，但未达到队满状态,特殊的线性群体队列,元素移动方向,元素移动方向,57,循环队列,在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。,特殊的线性群体队列,59,例9-10 队列类模板,#ifndef QUEUE_CLASS#define QUEUE_CLASS#include#include const int MaxQSize=50;,特殊的线性群体队列,template class Queue private:int front,rear,count;T qlistMaxQSize;public:Queue(void);void QInsert(const T/成员函数的实现略,61,作业,复习第九章，预习第十章实验九,
