教学课件第九章群体类

第九章第九章 群体类群体类清华大学计算机与信息管理中心清华大学计算机与信息管理中心郑郑 莉莉C+语言程序设计1 前一页 休息本章主要内容本章主要内容l线性群体线性群体线性群体的概念直接访问群体-数组类顺序访问群体-链表类栈类队列类2 前一页 休息群体的概念群体的概念群体群体是指由多个数据元素组成的集是指由多个数据元素组成的集合体。群体可以分为两个大类：合体。群体可以分为两个大类：线性群线性群体体和和非线性群体非线性群体。线性群体中的元素按位置排列有序，线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元非线性群体不用位置顺序来标识元素。素。3 前一页 休息线性群体的概念线性群体的概念线性群体中的元素次序与其位置关线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照系是对应的。在线性群体中，又可按照访问元素的不同方法分为访问元素的不同方法分为直接访问直接访问、顺顺序访问序访问和和索引访问索引访问。在本章我们只介绍直接访问和顺序在本章我们只介绍直接访问和顺序访问。访问。第一个元素第二个元素第三个元素最后一个元素4 前一页 休息数组数组l静态数组是具有固定元素个数的群体，静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。其中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。l动态数组由一系列位置连续的，任意动态数组由一系列位置连续的，任意数量相同类型的元素组成。数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。直接访问线性群体5 前一页 休息动态数组类模板动态数组类模板l数组类模板：数组类模板：例例9.1（9_1.h）直接访问线性群体6#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:;7template class Array private:T*alist;int size;void Error(ErrorType error,int badIndex=0)const;public:Array(int sz=50);Array(const Array&A);Array(void);Array&operator=(const Array&rhs);T&operator(int i);operator T*(void)const;int ListSize(void)const;void Resize(int sz);/类成员函数的实现略类成员函数的实现略8 前一页 休息Array类的应用类的应用l例例9.2 求范围求范围2N中的质数，中的质数，N在程序在程序运行时由键盘输入。运行时由键盘输入。直接访问线性群体9#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是一个质数是一个质数10for(i=3;i n;i+)if(primecount=A.ListSize（）)A.Resize(primecount+10);if(i%2=0)continue;j=3;while(j i/2)Aprimecount+=i;for(i=0;i primecount;i+)cout setw(5)Ai;if(i+1)%10=0)cout endl;cout endl;11 前一页 休息链表链表l链表是一种动态数据结构，可以用来链表是一种动态数据结构，可以用来表示顺序访问的线性群体。表示顺序访问的线性群体。l链表是由系列链表是由系列结点结点组成的，结点可以组成的，结点可以在运行时动态生成。在运行时动态生成。l每一个结点包括每一个结点包括数据域数据域和指向链表中和指向链表中下一个结点的下一个结点的指针指针（即下一个结点的（即下一个结点的地址）。如果链表每个结点中只有一地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称个指向后继结点的指针，则该链表称为单链表。为单链表。顺序访问线性群体12 前一页 休息单链表单链表顺序访问线性群体 data1 data2 data3 datan NULLheadrear13 前一页 休息例例9-3 单链表的结点类模板单链表的结点类模板template class Node private:Node*next;public:T data;Node(const T&item,Node*ptrnext=NULL);void InsertAfter(Node*p);Node*DeleteAfter(void);Node*NextNode(void)const;/实现略实现略顺序访问线性群体14 前一页 休息在结点在结点p之后插入一个结点之后插入一个结点顺序访问线性群体 data1 data2 p q data15 前一页 休息 删除删除p结点之后的结点结点之后的结点顺序访问线性群体 data1 data2 data3 p q16 前一页 休息链表的基本操作链表的基本操作l生成结点生成结点l输出链表输出链表l查找结点查找结点l插入结点插入结点l删除结点删除结点l清空链表清空链表顺序访问线性群体17 前一页 休息例例9-4 实现链表操作函数实现链表操作函数#ifndef NODE_LIBRARY#define NODE_LIBRARY#include#include#include 9_3.h顺序访问线性群体18/生成节点生成节点template Node*GetNode(const T&item,Node*nextPtr=NULL)Node *newNode;newNode=new Node(item,nextPtr);if(newNode=NULL)cerr Memory allocation failure!endl;exit(1);return newNode;19enum AppendNewline noNewline,addNewline;/输出链表输出链表template void PrintList(Node*head,AppendNewline addnl=noNewline)Node*currPtr=head;while(currPtr!=NULL)if(addnl=addNewline)cout data endl;else cout data NextNode（）;20/查找节点查找节点template int Find(Node*head,T&item,Node*&prevPtr)Node*currPtr=head;prevPtr=NULL;while(currPtr!=NULL)if(currPtr-data=item)return 1;prevPtr=currPtr;currPtr=currPtr-NextNode（）;return 0;21/在表头插入节点在表头插入节点template void InsertFront(Node*&head,T item)head=GetNode(item,head);/在表尾添加节点在表尾添加节点template void InsertRear(Node*&head,const T&item)Node *newNode,*currPtr=head;if(currPtr=NULL)InsertFront(head,item);else while(currPtr-NextNode（）!=NULL)currPtr=currPtr-NextNode（）;newNode=GetNode(item);currPtr-InsertAfter(newNode);22/删除链表的第一个节点删除链表的第一个节点template void DeleteFront(Node*&head)Node*p=head;if(head!=NULL)head=head-NextNode（）;delete p;23/删除链表中第一个数据域等于删除链表中第一个数据域等于key的节点的节点template void Delete(Node*&head,T key)Node *currPtr=head,*prevPtr=NULL;if(currPtr=NULL)return;while(currPtr!=NULL&currPtr-data!=key)prevPtr=currPtr;currPtr=currPtr-NextNode（）;if(currPtr!=NULL)if(prevPtr=NULL)head=head-NextNode（）;else prevPtr-DeleteAfter（）;delete currPtr;24/在有序链表中插入一个节点在有序链表中插入一个节点template void InsertOrder(Node*&head,T item)Node*currPtr,*prevPtr,*newNode;prevPtr=NULL;currPtr=head;while(currPtr!=NULL)if(item data)break;prevPtr=currPtr;currPtr=currPtr-NextNode（）;if(prevPtr=NULL)InsertFront(head,item);else newNode=GetNode(item);prevPtr-InsertAfter(newNode);25/清空链表清空链表-删除链表中的所有节点删除链表中的所有节点template void ClearList(Node*&head)Node*currPtr,*nextPtr;currPtr=head;while(currPtr!=NULL)nextPtr=currPtr-NextNode（）;delete currPtr;currPtr=nextPtr;head=NULL;#endif /NODE_LIBRARY26 前一页 休息例例9.5 链表应用举例链表应用举例从键盘输入10个整数，用这些整数值作为结点数据，生成一个链表，按顺序输出链表中结点的数值。然后从键盘输入一个待查找整数，在链表中查找该整数，若找到则删除该整数所在的结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在程序结束之前清空链表。9-5.cpp顺序访问线性群体27#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;28 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);29 前一页 休息例例9-6 链表类模板链表类模板/9_6.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include#include#ifndef NULLconst int NULL=0;#endif /NULL#include 9_3.h顺序访问线性群体30template class LinkedList private:Node*front,*rear;Node*prevPtr,*currPtr;int size;int position;Node*GetNode(const T&item,Node*ptrNext=NULL);void FreeNode(Node*p);void CopyList(const LinkedList&L);31 public:LinkedList(void);LinkedList(const LinkedList&L);LinkedList(void);LinkedList&operator=(const LinkedList&L);int ListSize(void)const;int ListEmpty(void)const;void Reset(int pos=0);void Next(void);int EndOfList(void)const;int CurrentPosition(void)const;32 void InsertFront(const T&item);void InsertRear(const T&item);void InsertAt(const T&item);void InsertAfter(const T&item);T DeleteFront(void);void DeleteAt(void);T&Data(void);void ClearList(void);#endif /LINKEDLIST_CLASS33 前一页 休息例例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);顺序访问线性群体34 cout List:;Link.Reset（）;while(!Link.EndOfList（）)cout Link.Data（）;Link.Next（）;cout endl;cout key;Link.Reset（）;35 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;36 前一页 休息特殊的线性群体特殊的线性群体栈栈栈是只能从一端访问的线性群体，栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈可以访问的这一端称栈顶，另一端称栈底。底。ana2a1入栈出栈栈顶栈底37 前一页 休息栈的应用举例栈的应用举例函数调用函数调用特殊的线性群体栈main调fun(参数)结束fun(参数)返回参数当前现场返回地址入栈当前现场返回地址出栈参数出栈当前现场 返回地址38 前一页 休息栈的应用举例栈的应用举例表达式处理表达式处理ba/a/b+c*d(a)t1+a/b+c*dt1=a/b(b)dct1*+a/b+c*d(c)t3a/b+c*dt3=t1+t2(e)t2t1+a/b+c*dt2=c*d(d)特殊的线性群体栈39 前一页 休息栈的基本状态栈的基本状态l栈空栈空栈中没有元素l栈满栈满栈中元素个数达到上限l一般状态一般状态栈中有元素，但未达到栈满状态特殊的线性群体栈40栈顶ana1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态41 前一页 休息栈的基本操作栈的基本操作l初始化初始化l入栈入栈l出栈出栈l清空栈清空栈l访问栈顶元素访问栈顶元素l检测栈的状态（满、空）检测栈的状态（满、空）特殊的线性群体栈42 前一页 休息例例9-8 栈类模板栈类模板/9-8.h#ifndef STACK_CLASS#define STACK_CLASS#include#include const int MaxStackSize=50;特殊的线性群体栈43template class Stack private:T stacklistMaxStackSize;int top;public:Stack(void);void Push(const T&item);T Pop(void);void ClearStack(void);T Peek(void)const;int StackEmpty(void)const;int StackFull(void)const;/类的实现略类的实现略44 前一页 休息栈的应用栈的应用l例例9.9 一个简单的整数计算器一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入3 5 +。乘方运算符用表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入c。当键入q时程序结束。l9-9.h 9-9.cpp特殊的线性群体栈45/9_9.h#include#include#include#include enum Boolean False,True;#include 9_8.h 46class Calculator private:Stack S;void Enter(int num);Boolean GetTwoOperands(int&opnd1,int&opnd2);void Compute(char op);public:Calculator(void)void Run(void);void Clear(void);47void Calculator:Enter(int num)S.Push(num);Boolean Calculator:GetTwoOperands (int&opnd1,int&opnd2)if(S.StackEmpty（）)cerr Missing operand!endl;return False;opnd1=S.Pop（）;if(S.StackEmpty（）)cerr Missing operand!endl;return False;opnd2=S.Pop（）;return True;48void 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;49 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（）c,*c!=q)switch(*c)case c:S.ClearStack（）;break;case-:if(strlen(c)1)Enter(atoi(c);else Compute(*c);break;case+:51 case*:case/:case:Compute(*c);break;default:Enter(atoi(c);break;void Calculator:Clear(void)S.ClearStack（）;52/9_9.cpp#include 9-9.hvoid main(void)Calculator CALC;CALC.Run（）;53 前一页 休息特殊的线性群体特殊的线性群体队列队列队列是只能向一端添加元素，从另队列是只能向一端添加元素，从另一端删除元素的线性群体一端删除元素的线性群体a1 a2an-1 an队头队尾入队出队a054 前一页 休息队列的基本状态队列的基本状态l队空队空队列中没有元素l队满队满队列中元素个数达到上限l一般状态一般状态队列中有元素，但未达到队满状态特殊的线性群体队列55a0 a1an-1 an队头队尾入队出队数组下标 0 1 n-1 n max(一般状态)队头队尾入队出队数组下标 0 1 n-1 n max(队空状态)a0 a1 an-1 an amax队头队尾入队出队数组下标 0 1 n-1 n max(队满状态)元素移动方向元素移动方向56 前一页 休息循环队列循环队列在想象中将数组弯曲成环形，元素在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组到数组最后一个元素时，便再回到数组开头。开头。特殊的线性群体队列571234m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1队满状态 元素个数=m1234m-1m-2m-30队尾队头队空状态 元素个数=0队尾1234m-1m-2m-30a0a1a2a3队头一般状态58 前一页 休息例例9-10 队列类模板队列类模板#ifndef QUEUE_CLASS#define QUEUE_CLASS#include#include const int MaxQSize=50;特殊的线性群体队列59template class Queue private:int front,rear,count;T qlistMaxQSize;public:Queue(void);void QInsert(const T&item);T QDelete(void);void ClearQueue(void);T QFront(void)const;int QLength(void)const;int QEmpty(void)const;int QFull(void)const;/成员函数的实现略成员函数的实现略60 前一页 休息作业作业l复习第九章，预习第十章复习第九章，预习第十章l实验九实验九6162