程序设计初步1.ppt

第3章 堆栈和队列 主要知识点 堆栈 堆栈应用 队列 优先级队列 3.1 堆 栈 1、堆栈的基本概念 (1)定义:限定只能在固定一端进行插入和删除操作的线性表 。特点：后进先出。 (2)允许进行插入和删除操作的一端称为栈顶，另一端称为 栈底。 2、堆栈抽象数据类型 数据集合: a0,a1,an-1ai的数据类型为DataType。 操作集合：(1)Initiate(S) 初始化堆栈S (2)Push(S,x) 入栈 (3)Pop(S,d) 出栈 (4)GetTop(S) 取栈顶数据元素 (5)NotEmpty(S) 堆栈S非空否 3、顺序堆栈类 (1)顺序堆栈 顺序存储结构的堆栈。 (2)顺序栈的存储结构 它是利用一组地址连续的存储单元依次存放自栈底到栈 顶的数据元素，其结构如图所示： a0a1a2a3a4stack 栈底栈顶 MaxStackSize-1 012345 = top 其中，a0, a1, a2, a3, a4表示顺序堆栈中已存储的数据元素 ，stack表示存放数据元素的数组，MaxStackSize-1表示最大存 储单元个数，top表示当前栈顶存储下标。 类的定义： class SeqStack private: DataType dataMaxStackSize; /顺序堆栈数组 int top; /栈顶位置指示器 public: SeqStack(void) top=0; /构造函数 SeqStack(void) /析构函数 void Push(const DataType item); /入栈 DataType Pop(void); /出栈 DataType GetTop(void)const; /取栈顶数据元素 int NotEmpty(void)const; /堆栈非空否 return(top!=0); ; (3)顺序栈类的操作实现 一、void SeqStack:Push(const DataType item) /入栈 /把元素item入栈;堆栈满时出错退出 if(top=MaxStackSize) cout #include const int MaxStackSize=100; /定义问题要求的元素数目的最大值 typedef int DataType; /定义具体问题元素的数据类型 void main(voie) SeqStack myStack; /构造函数无参数时，定义的对象后不带括号 DataType test=1,3,5,7,9; int n=5; for(int i=0;i class LinStack; /前视定义，否则友元无法定义 /结点类 template /模板类型为T class StackNode friend class LinStack ; /定义类LinStack为友元 private: T data; /数据元素 StackNode *next; /指针 public: /构造函数1，用语构造头结点 StackNode(StackNode *ptrNext=NULL) next=ptrNext; /构造函数2，用于构造其他结点 StackNode(const Tnext=ptrNext; StackNode(); ; /链式堆栈类的定义 template class LinStack private: StackNode *head; /头指针 int size; /数据元素个数public: LinStack(void); /构造函数 LinStack(void) /析构函数 void Push(const T /入栈 T Pop(void); /出栈 T GetTop(void) const; /取栈顶元素 int NotEmpty(void) const; /堆栈非空否 ; (3)链式栈类的操作实现 一、template LinStack :LinStack() /构造函数 head=new StackNode ; /头指针指向头结点 size=0; /size的初值为0 二、template LinStack :LinStack(void) /析构函数 /释放所有动态申请的结点空间 StackNode *p,*q; p=head; /p指向头结点 while(p!=NULL) /循环释放结点空间 q=p; p=p-next; delete q; 三、template int LinStack :NotEmpty(void) const /堆栈非空否 if(size!=0) return 1; else return 0; 四、template void LinStack :Push(const T head-next=newNode; /新结点插入栈顶 size+; /元素个数加1 五、template T LinStack :Pop(void) /出栈 if(size=0) cout *p=head-next; /p指向栈顶元素结点 T data=p-data; head-next=head-next-next; /原栈顶元素结点脱链 delete p; /释放原栈顶结点空间 size-; /结点个数减1 return data; /返回原栈顶结点的data域值 六、template T LinStack :GetTop(void) const /取栈顶元素 return head-next-data; 说明： 1)在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁 ，可不设头结点链栈。 2)一般不会出现栈满情况；除非没有空间导致malloc分配失败。 3)链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可 完成。 4)采用链栈存储方式的优点是，可使多个栈共享空间；当栈中元素个 数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式 。 3.2 堆栈应用 1、括号匹配问题 例：假设一个算法表达式中包含圆括号、方括号和花括号三 种类型的括号，编写一个判别表达式中括号是否正确配对的函 数。 设计思路：用栈暂存左括号 void ExpIsCorrect(char exp, int n) /判断有n个字符的字符串exp左右括号是否配对正确 SeqStack myStack; /定义顺序堆栈类对象myStack int i; for(i=0;i /ch为char类型变量 T x,x1,x2; coutch /回退一位 cinx; /按数值类型重新输入 s.Push(x); /x入栈 else x2=s.Pop(); /退栈得操作数 x1=s.Pop(); /退栈得被操作数 switch(ch) case+:x1+=x2;break; case-:x1-=x2;break; case*:x1*=x2;break; case/: if(x2=0.0) cout0 /顺序队列数组 int front; /队头指示器 int rear; /队尾指示器 int count; /元素个数计数器 public: SeqQueue(void) /构造函数 front=rear=0;count=0; SeqQueue(void); /析构函数 void Append(const DataType /入队列 DataType Delete(void); /出队列 DataType GetFront(void)const; /取队头数据元素 int NotEmpty(void)const /非空否 return count!=0; ; void SeqQueue:Append(const DataType/前视定义，否则友元无法定义 template class QueueNode friend class LinQueue ; /定义类LinQueue为友元 private: QueueNode *next; /指针 T data; /数据元素 public: /构造函数 QueueNode(const % /析构函数 ; 为了方便设计，增加了一个count域用来计算当前的元素个数 链式队列类的定义如下： template class LinQueue private: QueueNode *front; /队头指针 QueueNode *rear; /队尾指针 int count; /计数器 public: LinQueue(void); /构造函数 LinQueue(void); /析构函数 void Append(const T /入队列 T Delete(void); /出队列 T GetFront(void)const; /取队头数据元素 int NotEmpty(void)const /非空否 return count!=0; ; 链式队列类的实现如下： template LinQueue :LinQueue() /构造函数 front=rear=NULL; /链式队列无头结点 count=0; /count的初值为0 template LinQueue :LinQueue(void) /析构函数 QueueNode *p,*q; p=front; /p指向第一个结点 while(p!=NULL) /循环直至全部结点空间释放 q=p; p=p-next; delete q; count=0; /置为初始化值0 front=rear=NULL; template void LinQueue :Append(const T if(rear!=NULL) rear-next=newNode; /新结点链入 rear=newNode; /队尾指针指向新队尾结点 /若队头指针原先为空则置为指向新结点 if(front=NULL) front=newNode; count+; /计数器加1 template T LinQueue :Delete(void) /出队列 /把队头结点删除并由函数返回 if(count=0) cout *p=front-next; /p指向新的队头结点 T data=front-data; /保存原队头结点的data域值 delete front; /释放原队头结点空间 front=p; /front指向新的对头结点 count-; /计数器减1 return data; /返回原队头结点的data域值 template T LinQueue :GetFront(void)const /取队头数据元素 if(count=0) coutdata; 6、队列的应用 例：编写判断一个字符序列是否是回文的函数。 编程思想： 设字符数组str中存放了要判断的字符串。把字符数组中的 字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较 出队列的字符和退栈的字符是否相等，若全部相等则该字符序 列是回文，否则就不是回文。 设计函数如下： void HuiWen(char str) LinStack myStack; LinQueue myQueue; int n=strlen(str); /求字符串长度 for(int i=0;in;i+) myQueue.Append(stri); myStack.Push(stri); while(myQueue.NotEmpty() return; cout“是回文!“endl; 3.4 优先级队列 、优先级队列 带有优先级的队列。 、顺序优先级队列 用顺序存储结构存储的优先级队列。 、优先级队列和一般队列的主要区别 优先级队列的出队列操作不是把队头元素出队列，而是把 队列中优先级最高的元素出队列。 它的数据元素定义为如下结构体： struct DataType ElemType elem; /数据元素 int priority; /优先级 ; 注：顺序优先级队列除出队列操作外的其他操作的实现方法与 前边讨论的顺序队列操作的实现方法相同。 出队列操作(把优先级最高的元素出队列并由函数返回,优先级相同 时按先进先出的原则出队列),核心语句如下： DataType min=data0; /初始选data0为优先级最高的元素 int minIndex=0; /minIndex为优先级最高元素的下标 for(int i=1;icount;i+)/寻找优先级最高的元素及对应下标 if(datai.prioritymin.priority) min=datai; minIndex=i; 例:设计一个程序模仿操作系统的进程管理进程。进程服务按优先级高 的先服务、 优先级相同的先