第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
《數(shù)據(jù)結(jié)構(gòu)》 課程設(shè)計(jì)報(bào)告
目錄
《數(shù)據(jù)結(jié)構(gòu)》...................................................................................................................................1 課程設(shè)計(jì)報(bào)告...................................................................................................................................1 目錄..................................................................................................................................................2 課題一：表達(dá)式求值.......................................................................................................................3 一：算數(shù)表達(dá)式后綴版...........................................................................................................3
1、問題描述：.................................................................................................................3
2、設(shè)計(jì)思路：.................................................................................................................3
3、程序代碼：.................................................................................................................3
4、運(yùn)行與測試.................................................................................................................6
5、設(shè)計(jì)心得：.................................................................................................................6 二：算術(shù)表達(dá)式中綴版...........................................................................................................7
1、問題描述：.................................................................................................................7
2、設(shè)計(jì)思路：.................................................................................................................7
3、代碼：.........................................................................................................................7
4、調(diào)試及測試...............................................................................................................13
5、設(shè)計(jì)心得：...............................................................................................................13 課題四：迷宮求解.........................................................................................................................14 一：問題描述：.............................................................................................................14 二：設(shè)計(jì)思路：.............................................................................................................14 三：功能函數(shù)設(shè)計(jì).........................................................................................................14 四：代碼.........................................................................................................................14 五：測試及調(diào)試.............................................................................................................21 六：設(shè)計(jì)心得.................................................................................................................23
課題一：表達(dá)式求值
一：算數(shù)表達(dá)式后綴版
1、問題描述：一個算術(shù)表達(dá)式是由操作數(shù)、運(yùn)算符和界線符組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界線符有左右括號和表達(dá)式起始、結(jié)束符“#”，如：“1285-*+42/-#”。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。
2、設(shè)計(jì)思路：在C++環(huán)境下，用字符數(shù)組A，保存算數(shù)式，一“#”表示結(jié)束。用棧對數(shù)字和運(yùn)算符號進(jìn)行操作。當(dāng)掃描A不是‘#’時(shí)，判斷數(shù)組成員是數(shù)字還是字符，若數(shù)字，則將數(shù)字的ASCII碼入棧，若不是，則彈出兩個數(shù)字，并根據(jù)字符進(jìn)行相應(yīng)的運(yùn)算，并將結(jié)果入棧保存，以便下一次的運(yùn)算操作。
3、程序代碼：
#include
base=new int[Size];
top=base;
size=Size;};~stack(){
delete[] base;
base=NULL;
top=NULL;};};int stack::empty_stack(){ return((top==base));} int stack::push_stack(int e){ if(top-base *top=e; top++; return 1;} else return 0;} int stack::pop_stack(int &e){ if(top>base){ top--; e=*top; return 1;} else return 0;} int stack::get_stack(int &e){ if(top>base){ e=*(top-1); return 1;} else return 0;} int match(char A[]){ stack s;int i=0,x,y,z;while(A[i]!='#'){ while(A[i]>'0'&&A[i]<='9')//char型 A[],其中0~9存儲的是48~57?。? { s.push_stack(A[i]-'0');//存儲 數(shù)字0~9 char-char i++; } if(A[i]<'0'||A[i]>'9') { s.pop_stack(x); s.pop_stack(y); switch(A[i]) { case '+':s.push_stack(x+y);break;//switch,case 'ch'的用法 case '-':s.push_stack(x-y);break; case '*':s.push_stack(x*y);break; case '/':s.push_stack(x/y);break; } } i++;} s.pop_stack(z);printf(“%dn”,z);return z;} int main(){ char A[100];int m;scanf(“%s”,A);m=match(A);printf(“%dn”,m);return 0;} 4、運(yùn)行與測試 5、設(shè)計(jì)心得：考察棧的應(yīng)用，在c++環(huán)境下棧的構(gòu)建與操作，在輸入數(shù)組A時(shí)（用于存放數(shù)組），注意當(dāng)數(shù)組元素是數(shù)字時(shí)，將A[i]-’0’，（ASCII碼）作為棧相應(yīng)函數(shù)的參數(shù)。后綴表達(dá)式還是相應(yīng)比較簡單的。 二：算術(shù)表達(dá)式中綴版 1、問題描述：一個算術(shù)表達(dá)式是由操作數(shù)、運(yùn)算符和界線符組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界線符有左右括號和表達(dá)式起始、結(jié)束符“#”，如：“1285-*+42/-#”。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。 2、設(shè)計(jì)思路：在C++環(huán)境下，在后綴表達(dá)式的基礎(chǔ)上，增加將中綴轉(zhuǎn)換為后綴存儲的算法。自左向右掃描表達(dá)式，當(dāng)掃描到的是操作數(shù)時(shí)直接輸出，掃描到運(yùn)算符時(shí)不能馬上輸出，因?yàn)楹竺婵赡苓€有更高的運(yùn)算；若運(yùn)算符棧棧頂字符比這個字符低，則入棧，繼續(xù)向后處理；若高，則從運(yùn)算符棧出棧一個運(yùn)算符輸出，繼續(xù)處理當(dāng)前字符；若相等，則為括號，從棧中出棧，繼續(xù)向后處理，直到遇到字符’#‘，求值結(jié)束。例如：“1+2*（8-5）-4/2#”。 3、代碼： #include base=new int[Size]; top=base; size=Size;};~stack(){ delete[] base; base=NULL; top=NULL;};};int stack::empty_stack(){ return((top==base));} int stack::push_stack(char e){ if(top-base *top=e; top++; return 1;} else return 0;} int stack::pop_stack(char &e){ if(top>base){ top--; e=*top; return 1;} else return 0;} int stack::get_stack(char &e){ if(top>base){ e=*(top-1); return 1;} else return 0;} class temp { private: int *base;int *top;public: int size;int empty_temp();int push_temp(int e);int pop_temp(int &e);int get_temp(int &e);temp(int Size=100){ base=new int[Size]; top=base; size=Size;};~temp(){ delete[] base; base=NULL; top=NULL; };};int temp::empty_temp(){ return((top==base));} int temp::push_temp(int e){ if(top-base *top=e; top++; return 1;} else return 0;} int temp::pop_temp(int &e){ if(top>base){ top--; e=*top; return 1;} else return 0;} int temp::get_temp(int &e){ if(top>base){ e=*(top-1); return 1;} else return 0;} char fhcg(char a,char b)//#不能傳進(jìn)a { int i,j;char h;char CH[7]={'+','-','*','/','(',')','#'};char R[7][7]={{'>','>','<','<','<','>','>'}，{'>','>','<','<','<','>','>'}，{'>','>','>','>','<','>','>'}，{'>','>','>','>','<','>','>'}，{'<','<','<','<','<','=','/'}，{'>','>','>','>','/','>','>'}，{'<','<','<','<','<','/','='}};for(i=0;i<7;i++){ if(CH[i]==a) break;} for(j=0;j<7;j++){ if(CH[j]==b) break;} h=R[i][j];return(h);} int matchcg(char A[],char B[])// { stack s;char h,x,y;int i,j;i=0;j=0;s.push_stack('#');//#沒傳入 // s.get_stack(y);//cout<<“棧頂”< while(!s.empty_stack())//最后的-4/2有問題，/沒進(jìn)入B[j] { if(A[i]>'0'&&A[i]<='9') { B[j]=A[i]; j++; i++; } else//(A[i]<'0'||A[i]>'9') { s.get_stack(y); // s.pop_stack(x);// h=fhcg(y,A[i]);// switch(h) { case '>': { s.pop_stack(x); B[j++]=x;//x沒有下移，還是‘-’只有這一步把數(shù)據(jù)壓入B，j++ break;/////////// } case '<':s.push_stack(A[i]);i++;break; case '=':s.pop_stack(x);i++;break; default: return 0; } } } B[j]='#';//B[]由j控制進(jìn)程 B[++j]='