第一篇：數(shù)據(jù)結(jié)構(gòu)實驗五報告
實驗五報告
課程名稱： 數(shù)據(jù)結(jié)構(gòu) 實驗名稱：二叉樹的創(chuàng)建與遍歷
實驗日期
2011/11/16
一、實驗目的：
通過上機實驗進一步掌握棧、隊列、二叉樹的存儲結(jié)構(gòu)及基本操作的實現(xiàn)方法。
二、實驗內(nèi)容與要求：
基于二叉鏈表存儲結(jié)構(gòu)實現(xiàn)二叉樹的基本運算，要求：
⑴能建立非空二叉樹；
⑵實現(xiàn)二叉樹的先、中、后序遞歸遍歷算法；
⑶實現(xiàn)二叉樹的非遞歸的先（或中、或后）序遍歷算法及層序遍歷算法；
⑷記錄運行結(jié)果并對遞歸算法和非遞歸算法的效率加以分析。
三、算法設(shè)計 結(jié)構(gòu)體的定義：
typedef struct BiTNote{
struct Node{
};類的定義： class CStack{
//棧 private:
};
class LinkQueue{ //隊列 public: BiTree base;BiTree top;int stacksize;//當前空間分配量 static const int STACK_INIT_SIZE=100;static const int STACKINCREMENT=10;CStack();
void Push(BiTree T);//入棧 void Pop(BiTree &T);//出棧 bool StackEmpty();//判斷是否是空棧 friend class CBiTree;Node(BiTree &d):num(d),next(NULL){} BiTree num;Node *next;char data;struct BiTNote *lchild,*rchild;}BiTNote,*BiTree;public:
};LinkQueue();bool QueueEmpty();void EnQueue(BiTree &T);void DeQueue(BiTree &T);friend class CBiTree;int length;//隊列元素的個數(shù) Node *front;
//隊列的頭指針 Node *rear;
//隊列的尾指針 private: class CBiTree{ public:
};CStack::CStack():stacksize(STACK_INIT_SIZE){ //構(gòu)造函數(shù)，初始化
} void CStack::Push(BiTree T){...} //入棧 void CStack::Pop(BiTree &T){...} //出棧 bool CStack::StackEmpty(){} int i=0;//全局變量
int CBiTree::CreatBiTree(BiTree &T){}//構(gòu)造二叉樹 //LinkQueue類函數(shù)的實現(xiàn) LinkQueue::LinkQueue(){} bool LinkQueue::QueueEmpty(){} void LinkQueue::EnQueue(BiTree &T){} void LinkQueue::DeQueue(BiTree &T){} int CBiTree::PreOrderTraverse1(BiTree T, int(*Visit)(char)){...} //前序遍歷（遞歸）int CBiTree::InOrderTraverse(BiTree T, int(*Visit)(char)){...} //中序遍歷（遞歸）int CBiTree::PostOrderTraverse(BiTree T, int(*Visit)(char)){...}//后序遍歷（遞歸）int CBiTree::PreOrderTraverse2(BiTree T, int(*Visit)(char)){ //前序遍歷（非遞歸）
BiTree p=T;while(p!=NULL||!s.StackEmpty()){ BiTree p=(BiTree)malloc(STACK_INIT_SIZE*sizeof(BiTNote));base=p;top=base;int CreatBiTree(BiTree &T);//建立二叉樹
int PreOrderTraverse1(BiTree T,int(*Visit)(char e));
//前序遍歷（遞歸）int PreOrderTraverse2(BiTree T,int(*Visit)(char e));
//前序遍歷（非遞歸）
int InOrderTraverse(BiTree T,int(*Visit)(char e));
//中序遍歷（遞歸）int PostOrderTraverse(BiTree T,int(*Visit)(char e));//后序遍歷（遞歸）int LevelOrderTraverse(BiTree T,int(*Visit)(char e));//層序遍歷（非遞歸）CStack s;LinkQueue link;private:
}
} while(p!=NULL){
} if(!s.StackEmpty()){
} s.Pop(p);p=p->rchild;Visit(p->data);s.Push(p);p=p->lchild;return 1;int CBiTree::LevelOrderTraverse(BiTree T, int(*Visit)(char))//層序遍歷（非遞歸）{
} //main.cpp #include“BiTree.h” #include“Function.h” #include
}
int main(){
CBiTree Tree;BiTree T;T=(BiTree)malloc(sizeof(BiTNote));cout<<“構(gòu)造二叉樹：”;Tree.CreatBiTree(T);cout<<“先序遍歷（遞歸）：”;Tree.PreOrderTraverse1(T,PrintData);cout< link.EnQueue(T);while(!link.QueueEmpty()){ } return 0;BiTree p;link.DeQueue(p);Visit(p->data);link.EnQueue(p->lchild);link.EnQueue(p->rchild); } cout< 四、測試結(jié)果 五、心得體會 這次實驗嘗試用C++寫，好長時間沒接觸了，所以寫的比較吃力，在寫的過程中溫習了C++的一些知識，但代碼寫的很亂，沒有用模板，C++的引用也忘了等。這次還發(fā)現(xiàn)自己對指針還是不熟練（一個指針賦值的小錯誤多花了好多時間才找到）?？傊X得自己的編程水平很有待提高。 數(shù)據(jù)結(jié)構(gòu)實驗二報告 ——簡單計算器 姓名：王稀賓 班 級：06111106 學號：1120111699 一實驗目的 按照四則運算加、減、乘、除、冪（^）和括號的優(yōu)先關(guān)系和慣例，編寫計算器程序。 二實驗內(nèi)容 要求： 從鍵盤輸入一個完整的表達式，以回車作為表達式輸入結(jié)束的標志。輸入表達式中的數(shù)值均為大于等于零的整數(shù)。中間的計算過程如果出現(xiàn)小數(shù)也只取整。 三程序設(shè)計 程序模塊： 1輸入模塊，輸入多項式； 2計算模塊，根據(jù)輸入內(nèi)容，判斷分析，計算出結(jié)果； 3輸出模塊，輸出計算結(jié)果。 定義結(jié)構(gòu)創(chuàng)建結(jié)點： typedef struct { double data[50];int top;}OPND_Stack;//運算符結(jié)構(gòu)體 typedef struct { char data[50];int top;}OPTR_Stack;主函數(shù)部分： void main(){ char a[80];int m;char b[80];printf(“============簡易計算器============n”);printf(“[四則運算.如:-1+(2+3)*9/(-2)-6].n請輸入一個表達式:n”);while(1){ gets(a); strcpy(b,a); while(1) { int p; m=strlen(a); p=Can(a,m); if(p==0)break; printf(“輸入錯誤.請從新輸入表達式:n”); gets(a); strcpy(b,a); } printf(“=*=*=*=*=*=*表達式結(jié)果=*=*=*=*=*=*n”); printf(“該表達式的結(jié)果為:n%s=%-10.3lfn”,b,EvaluateExpression(a)); printf(“=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n”); printf(“繼續(xù)使用[四則運算.如:-1+(2+3)*9/(-2)-6].<關(guān)閉退出>.n請再輸入 一個表達式:n”);} } 四程序調(diào)試分析 1在四則混合運算中，運算符號的優(yōu)先級比較難判斷。2心得體會: 我對編程是有很濃厚興趣的。在編程的過程中，我深深地體會到力不從心—有些知識沒能深入地理解和掌握以及VC++的許多功能沒能探索和了解使我編程時有好多的思想運用不上(如設(shè)計一個美觀的操作界面)。另外，我也感受到了數(shù)據(jù)結(jié)構(gòu)的重要性，有了結(jié)構(gòu)才能將好的思想付諸實踐。同時經(jīng)過查詢資料了解到棧由多種運用方法，其中包括棧的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，棧是計算表達式的經(jīng)典應用。數(shù)據(jù)結(jié)構(gòu)中的許多結(jié)構(gòu)都是很經(jīng)典思想，只有把編程語言和數(shù)據(jù)結(jié)構(gòu)都熟練掌握的情況下，才能做出一些很好的作品。在編程過程中，雖然有時候是很發(fā)悶的，尤其是程序無錯但結(jié)果不對，但是在完成一個完整的程序時所帶來的喜悅是其它事情所不能替代的。我很喜歡編程，即使我的知識和能力有限，但我相信經(jīng)過努力，一切皆有可能。 五用戶使用說明 按要求正確輸入表達式即可得到結(jié)果。 六程序運行結(jié)果 附程序清單 #include char OP[7]={'+','-','*','/','(',')','#'};//數(shù)據(jù)結(jié)構(gòu)體 typedef struct { double data[50];int top;}OPND_Stack;//運算符結(jié)構(gòu)體 typedef struct { char data[50];int top;}OPTR_Stack;//初始化運算符棧函數(shù) void InitStack_R(OPTR_Stack *a){ a->top=-1;} //初始化數(shù)據(jù)站函數(shù) void InitStack_D(OPND_Stack *a){ a->top=-1;} //運算符進棧函數(shù) void Push_R(OPTR_Stack *a,char b){ a->top++;a->data[a->top]=b;} //數(shù)據(jù)進棧函數(shù) void Push_D(OPND_Stack *a,double b){ a->top++;a->data[a->top]=b;} //取運算符棧頂符函數(shù) void GetTop_R(OPTR_Stack *a,char *b){ *b=a->data[a->top];} //取數(shù)據(jù)棧頂數(shù)函數(shù) void GetTop_D(OPND_Stack *a,double *b){ *b=a->data[a->top];} //判斷數(shù)據(jù)是否為運算符函數(shù) int In(char a,char *s){ for(int i=0;i<7;i++) if(a==s[i]) return 1;return 0;} //算符優(yōu)先級判斷函數(shù) char Precede(char a,char b){ int m,n;for(int i=0;i<7;i++){ if(a==OP[i]) m=i; if(b==OP[i]) n=i;} return First[m][n];} //刪除運算符棧頂元素，并取新棧的棧頂元素 void Pop_R(OPTR_Stack *a,char *b){ a->top--;*b=a->data[a->top];} //取數(shù)據(jù)站的棧頂元素，并從棧中刪除此元素 void Pop_D(OPND_Stack *a,double *b){ *b=a->data[a->top];a->top--;} //算符優(yōu)先算法求值核心函數(shù) double EvaluateExpression(char *s){ OPND_Stack OPND;OPTR_Stack OPTR;char ch,theta;double x,a,b;int k=0;strcat(s,“#”);InitStack_R(&OPTR);Push_R(&OPTR,'#');InitStack_D(&OPND);GetTop_R(&OPTR,&ch);while(s[k]!='#'||ch!='#'){ if(In(s[k],OP)==0) { x=Getdouble(s,&k); Push_D(&OPND,x); } else { switch(Precede(ch,s[k])) { case'<':Push_R(&OPTR,s[k]); k++; break; case'=':Pop_R(&OPTR,&ch); k++; break; case'>':GetTop_R(&OPTR,&theta);Pop_R(&OPTR,&ch); Pop_D(&OPND,&b);Pop_D(&OPND,&a); Push_D(&OPND,Operate(a,theta,b)); break; } } GetTop_R(&OPTR,&ch);} GetTop_D(&OPND,&x);return x;InitStack_R(&OPTR);Push_R(&OPTR,'#');InitStack_D(&OPND);} //判斷表達式是否輸入正確.int Can(char a[],int n){ int p=0,s=0,t=0;for(int i=0;i if(a[i]=='('||a[i]==')') p++; if((a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/')&&((a[i+1]<'0'&&a[i+1]!='(')||a[i+1]>'9')) s++; if(a[i]=='/'&&a[i+1]=='0') s++; if((a[i]=='('&&(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'))||(a[i]==')'&&a[i+1]=='(')) s++; if(a[i]==')'&&a[i+1]!='
第二篇：數(shù)據(jù)結(jié)構(gòu)實驗二報告