数据结构课程实验报告-实验7优先队列

HUNAN UNIVERSITY课程实习报告题 目： 逆波兰表达式问题 优先队列与堆 学生姓名 学生学号 指导老师 完 成 日 期 2015-5-9 逆波兰表达式问题实验背景 在工资管理软件中，不可避免的要用到公式的定义及求值等问题。对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。基本要求 使用二叉树来实现。实现提示利用二叉树后序遍历来实现表达式的转换，同时可以使用实验3的结果来求解后缀表达式的值。输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。测试用例 输入：21+23*（12-6）输出：21 23 12 6 -*+源代码:#include#include#includeusing namespace std;char str10015;/由于一个数字可能有多个数字组成 int search_1(int start,int end)/寻找优先级最小的+或- int i,count=0,pos=-1;/count用来记录括号的数量，pos用来记录优先级最小的+或-的位置 for(i=start;iend;i+)if(stri0=()count+;else if(stri0=)count-; else if(stri0=+ | stri0=-) & count=0)/无括号时 pos=i; /i记录的是优先级最小的+或-的位置 ，也就是没有括号，并且在后面的加减运算 return pos;int search_2(int start ,int end)/寻找优先级最小的*或/的位置 int i,count=0,pos=-1;/count用来记录括号的数量，pos用来记录优先级最小的+或-的位置 for(i=start;idata,strstart); else pos=search_1(start,end); /找优先级最低的加减法 if(pos=-1)pos=search_2(start,end); /如果没有的话那就找优先级最低的乘除法 if(pos=-1)root=creattree(start+1,end-1); elsestrcpy(root-data,strpos);root-lchild=creattree(start,pos);root-rchild=creattree(pos+1,end);return root;void Bintree:postorder(Node* subroot)/递归的方法后续遍历 if(subroot!=NULL) postorder(subroot-lchild);postorder(subroot-rchild);coutdatalchild);destory(subroot-rchild);delete (subroot);double Bintree:calcute(Node* subroot)/计算表达式的结果 double result; if(subroot-lchild=NULL & subroot-rchild=NULL) /递归出口，返回值result=turn(subroot-data); return result; switch(subroot-data0)case +: return calcute(subroot-lchild)+calcute(subroot-rchild);break;case -: return calcute(subroot-lchild)-calcute(subroot-rchild);break;case *: return calcute(subroot-lchild)*calcute(subroot-rchild);break;case /: return calcute(subroot-lchild)/calcute(subroot-rchild);break;int main()char a100;Bintree tree;Node* subroot;int i=0,count=0;bool flag=0;cout请输入表达式:a)int j=0;while(ai!=0)if(ai=+ | ai=- | ai=/ | ai=*)if(flag)cout表达式错误endl; /判断表达式是否正确，即是否有多个运算符连续输入 goto loop;strj+0=ai+;flag=1;else if(ai=( | ai=)strj+0=ai;if(ai+=()count+;elsecount-;if(count0)cout表达式错误endl;/判断括号是否匹配 goto loop;elseint k=0; while(ai!=+ & ai!=- & ai!=* & ai!=/ & ai!=) & ai!=( & ai!=0 ) strjk+=ai+; j+;flag=0;if(count!=0)cout表达式错误endl;goto loop;subroot=tree.creattree(0,j); tree.postorder(subroot); coutendl;cout表达式的值:endl;coutfixedsetprecision(2)tree.calcute(subroot)endl;tree.destory(subroot);loop:i=0;count=0;flag=0;return 0;运行结果：优先队列与堆一、 需求分析1 本程序可以模拟实现医院排列病人看病的顺序；2 程序要求从键盘输入来看病的病人的顺序和他们的病情的紧急程度，病情越紧急紧急程度的数值越小；3 计算机通过程序将紧急程度按照从小到大的顺序，把看病的病人重新排序，最终得到看病的顺序；4 输入的值每次有两个，病人来的顺序和紧急程度，都是整数，以-1，-1输入作为结束符；测试用例输入1 152 33 54 205 101 1输出23514二、概要设计抽象数据类型最终出列的顺序是按照priority的值从小到大的顺序排列的，所以，我们考虑用所输入的权值构建最小值堆来实现。class minheap数据对象 heap，n，有ID和priority数据关系 R：基本操作：void siftdown(const int start,const int end); /自上往下调整，使关键字小的节点在上void siftup(int start); /自下往上调整public:minheap(int n=1000);minheap();bool insert(const T &x);/插入元素T removemin();/删除最小元素T getmin();/取最小元素bool isEmpty() const; /判断堆是否为空bool isFull() const; /判断堆是否满了void clear(); /清空;算法的基本思想根据题目要求，优先队列是基于堆的思想来实现的，相应的插入、删除、以及对优先队列的维护都是通过堆的思想来实现的，在实验中我是通过对堆的数组表示后改造为队列的，其本质思想都是相通的，都是基于堆的思想来实现快速的查询工作！程序的流程程序由三个模块组成：（1） 输入模块：输入N行整数，每行两个整数分别表示病人ID和优先权。完成病人信息（ID和priority）的输入，并建立最小值堆。（2） 计算模块：利用堆进行相应的插入、删除；（3） 输出模块：输出N行整数，只输出ID,Priority小的先输出。三、详细设计物理数据类型主题思想是通过分块、分步的方法设计，从而实现对最小值堆，最后再输出；算法的具体步骤部分函数声明实现minheap:minheap(int m) /新建堆，插入元素size=m;heap=new Tsize;n=0;minheap:minheap() /删除元素delete heap;void minheap:siftup(int start) /自下往上调整int j=start,i=(j-1)/2; /i指向j的双亲节点start 是什么T temp=heapj;while(j0)/将其与父节点比较，使其移动到正确位置if(heapi=temp)/位于正确位置break;else/交换位置heapj=heapi;j=i;i=(i-1)/2;heapj=temp;void minheap:siftdown(const int start,const int end) /自上往下调整，使关键字小的节点在上,end表示个数int i=start,j=2*i+1;/j指向字节点T temp=heapi;while(j=end)if( (jheapj+1) )j+;if(temp=heapj)break;/满足条件elseheapi=heapj;i=j;j=2*j+1;heapi=temp;bool minheap:insert(const T &x) /插入元素if(n=size)return false;heapn=x;siftup(n);n+;return true;T minheap:removemin( ) /调整T x=heap0;heap0=heapn-1;n-;/总数少了1siftdown(0,n-1); /调整新的根节点return x;T minheap:getmin()return heap0;bool minheap:isEmpty() constreturn n=0;bool minheap:isFull() const /堆满return n=size;void minheap:clear() /析构类 n=0;/最小堆：根结点的键值是所有堆结点键值中最小者。算法的时空分析建立最小堆每插入一个点的时间复杂度是（），删除一个点的时间复杂度也是（）输入和输出的格式输入格式：输入（-1 -1表示输入结束）提示等待输入，每行输入两个整数，空格隔开，分别表示病人的ID和Priority输出格式：输出每行输出一个整数/只输出ID，按照优先权大小进行输出，Priority小的优先输出。四、调试分析1编译过程中出现了一些语法错误，纯属粗心大意所造成；2原本对算法思想不是很明白，经过与同学的讨论由来一定的了解。五、测试结果输入（-1 -1表示输入结束）：1 152 33 54 205 10-1 -1输出：23 5 1 4 Press any key to continue另一组数据，用于检测，发现正确六、用户使用说明（可选）1、本程序的运行环境为DOS操作系统，执行文件为gcd.exe2、运行程序时输入：病人的ID号和病情程度，输入-1 -1表示输入结束输出：输出病人队列 七、附录（可选）源代码：#include#includeusing namespace std;#includetemplateclass minheapprivate:T* heap; /元素数组，0号位置也储存元素int size; int n; /当前堆中的元素个数void siftdown(const int start,const int end); /自上往下调整，使关键字小的节点在上void siftup(int start); /自下往上调整public:minheap(int n=1000);minheap();bool insert(const T &x);/插入元素T removemin();/删除最小元素T getmin();/取最小元素bool isEmpty() const; /判断堆是否为空bool isFull() const; /判断堆是否满了void clear(); /清空;templateminheap:minheap(int m)size=m;heap=new Tsize;n=0;templateminheap:minheap()delete heap;templatevoid minheap:siftup(int start) /自下往上调整int j=start,i=(j-1)/2; /i指向j的双亲节点start 是什么T temp=heapj;while(j0)/将其与父节点比较，使其移动到正确位置if(heapi=temp)/位于正确位置break;else/交换位置heapj=heapi;j=i;i=(i-1)/2;heapj=temp;templatevoid minheap:siftdown(const int start,const int end) /自上往下调整，使关键字小的节点在上,end表示个数int i=start,j=2*i+1;/j指向字节点T temp=heapi;while(j=end)if( (jheapj+1) )j+;if(temp=heapj)break;/满足条件elseheapi=heapj;i=j;j=2*j+1;heapi=temp;templatebool minheap:insert(const T &x)if(n=size)return false;heapn=x;siftup(n);n+;return true;templateT minheap:removemin( )T x=heap0;heap0=heapn-1;n-;/总数少了1siftdo