數(shù)據結構課程實驗報告-實驗7優(yōu)先隊列

HUNAN UNIVERSITY課程實習報告題 目： 逆波蘭表達式問題 優(yōu)先隊列與堆 學生姓名 學生學號 指導老師 完 成 日 期 2015-5-9 逆波蘭表達式問題實驗背景 在工資管理軟件中，不可避免的要用到公式的定義及求值等問題。對于數(shù)學表達式的計算，雖然可以直接對表達式進行掃描并按照優(yōu)先級逐步計算，但也可以將中綴表達式轉換為逆波蘭表達式，這樣更容易處理?；疽?使用二叉樹來實現(xiàn)。實現(xiàn)提示利用二叉樹后序遍歷來實現(xiàn)表達式的轉換，同時可以使用實驗3的結果來求解后綴表達式的值。輸入輸出格式：輸入：在字符界面上輸入一個中綴表達式，回車表示結束。輸出：如果該中綴表達式正確，那么在字符界面上輸出其后綴表達式，其中后綴表達式中兩相鄰操作數(shù)之間利用空格隔開；如果不正確，在字符界面上輸出表達式錯誤提示。測試用例 輸入：21+23*（12-6）輸出：21 23 12 6 -*+源代碼:#include#include#includeusing namespace std;char str10015;/由于一個數(shù)字可能有多個數(shù)字組成 int search_1(int start,int end)/尋找優(yōu)先級最小的+或- int i,count=0,pos=-1;/count用來記錄括號的數(shù)量，pos用來記錄優(yōu)先級最小的+或-的位置 for(i=start;iend;i+)if(stri0=()count+;else if(stri0=)count-; else if(stri0=+ | stri0=-) & count=0)/無括號時 pos=i; /i記錄的是優(yōu)先級最小的+或-的位置 ，也就是沒有括號，并且在后面的加減運算 return pos;int search_2(int start ,int end)/尋找優(yōu)先級最小的*或/的位置 int i,count=0,pos=-1;/count用來記錄括號的數(shù)量，pos用來記錄優(yōu)先級最小的+或-的位置 for(i=start;idata,strstart); else pos=search_1(start,end); /找優(yōu)先級最低的加減法 if(pos=-1)pos=search_2(start,end); /如果沒有的話那就找優(yōu)先級最低的乘除法 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)/遞歸的方法后續(xù)遍歷 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; /判斷表達式是否正確，即是否有多個運算符連續(xù)輸入 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;運行結果：優(yōu)先隊列與堆一、 需求分析1 本程序可以模擬實現(xiàn)醫(yī)院排列病人看病的順序；2 程序要求從鍵盤輸入來看病的病人的順序和他們的病情的緊急程度，病情越緊急緊急程度的數(shù)值越??；3 計算機通過程序將緊急程度按照從小到大的順序，把看病的病人重新排序，最終得到看病的順序；4 輸入的值每次有兩個，病人來的順序和緊急程度，都是整數(shù)，以-1，-1輸入作為結束符；測試用例輸入1 152 33 54 205 101 1輸出23514二、概要設計抽象數(shù)據類型最終出列的順序是按照priority的值從小到大的順序排列的，所以，我們考慮用所輸入的權值構建最小值堆來實現(xiàn)。class minheap數(shù)據對象 heap，n，有ID和priority數(shù)據關系 R：基本操作：void siftdown(const int start,const int end); /自上往下調整，使關鍵字小的節(jié)點在上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(); /清空;算法的基本思想根據題目要求，優(yōu)先隊列是基于堆的思想來實現(xiàn)的，相應的插入、刪除、以及對優(yōu)先隊列的維護都是通過堆的思想來實現(xiàn)的，在實驗中我是通過對堆的數(shù)組表示后改造為隊列的，其本質思想都是相通的，都是基于堆的思想來實現(xiàn)快速的查詢工作！程序的流程程序由三個模塊組成：（1） 輸入模塊：輸入N行整數(shù)，每行兩個整數(shù)分別表示病人ID和優(yōu)先權。完成病人信息（ID和priority）的輸入，并建立最小值堆。（2） 計算模塊：利用堆進行相應的插入、刪除；（3） 輸出模塊：輸出N行整數(shù)，只輸出ID,Priority小的先輸出。三、詳細設計物理數(shù)據類型主題思想是通過分塊、分步的方法設計，從而實現(xiàn)對最小值堆，最后再輸出；算法的具體步驟部分函數(shù)聲明實現(xiàn)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的雙親節(jié)點start 是什么T temp=heapj;while(j0)/將其與父節(jié)點比較，使其移動到正確位置if(heapi=temp)/位于正確位置break;else/交換位置heapj=heapi;j=i;i=(i-1)/2;heapj=temp;void minheap:siftdown(const int start,const int end) /自上往下調整，使關鍵字小的節(jié)點在上,end表示個數(shù)int i=start,j=2*i+1;/j指向字節(jié)點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-;/總數(shù)少了1siftdown(0,n-1); /調整新的根節(jié)點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表示輸入結束）提示等待輸入，每行輸入兩個整數(shù)，空格隔開，分別表示病人的ID和Priority輸出格式：輸出每行輸出一個整數(shù)/只輸出ID，按照優(yōu)先權大小進行輸出，Priority小的優(yōu)先輸出。四、調試分析1編譯過程中出現(xiàn)了一些語法錯誤，純屬粗心大意所造成；2原本對算法思想不是很明白，經過與同學的討論由來一定的了解。五、測試結果輸入（-1 -1表示輸入結束）：1 152 33 54 205 10-1 -1輸出：23 5 1 4 Press any key to continue另一組數(shù)據，用于檢測，發(fā)現(xiàn)正確六、用戶使用說明（可選）1、本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為gcd.exe2、運行程序時輸入：病人的ID號和病情程度，輸入-1 -1表示輸入結束輸出：輸出病人隊列 七、附錄（可選）源代碼：#include#includeusing namespace std;#includetemplateclass minheapprivate:T* heap; /元素數(shù)組，0號位置也儲存元素int size; int n; /當前堆中的元素個數(shù)void siftdown(const int start,const int end); /自上往下調整，使關鍵字小的節(jié)點在上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的雙親節(jié)點start 是什么T temp=heapj;while(j0)/將其與父節(jié)點比較，使其移動到正確位置if(heapi=temp)/位于正確位置break;else/交換位置heapj=heapi;j=i;i=(i-1)/2;heapj=temp;templatevoid minheap:siftdown(const int start,const int end) /自上往下調整，使關鍵字小的節(jié)點在上,end表示個數(shù)int i=start,j=2*i+1;/j指向字節(jié)點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-;/總數(shù)少了1siftdo