数据结构 课程设计报告
题 目： 二叉树的先序遍历、中序遍历、后序遍历的递归
和 非 递 归 算 法。
学生姓名： * * * 学 号： *************** 专业班级： 计算机科学与技术专业
***班
同组姓名： ***** 指导教师： *****老师 设计时间： 年下学期第 周
指导老师意见： 评定成绩： 签名： 日期： - . -word资料-
- --
目 录
一、课题简介 ............................................3 二、系统项目设计. . . . . . . . . . . . . . .3
三、系统实现 ............................................3 1.二叉树的建立 .......................................4 2.先序遍历 .............................................4
a.递归算法 ...........................................7 b.非递归算法 ........................................7 a.递归算法 ...........................................7 b.非递归算法 ........................................7 a.递归算法 ...........................................7 b.非递归算法 ........................................7
3.中序遍历 .............................................6
4.后序遍历 .............................................6
5.主菜单程序 ..........................................4 5.子菜单程序 ..........................................4 四、系统测试 .......................................... 18 1.二叉树的建立 .......................................4 2.先序遍历 .............................................4
a.递归算法 ...........................................7 b.非递归算法 ........................................7
- . -word资料-
- --
2.中序遍历 .............................................6
a.递归算法 ...........................................7 b.非递归算法 ........................................7 a.递归算法 ...........................................7
3.后序遍历 .............................................6
b.非递归算法 .......................................7
4.主菜单程序 ..........................................4 5.子菜单程序 ..........................................4
五、小结 ................................................ 22
六、参考文献．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．23
一． 课题简介：
通过这个课题设计主要掌握三种遍历方法，包括前序遍历，中序遍历和后序遍历，以及后续遍历的非递归算法。
- . -word资料-
- --
二． 项目设计：
系 统 主 界 面 递 归 算 法 非 递 归 算 法 先 序 遍 历 中 序 遍 历 后 序 遍 历 退 出 程 序 先 序 遍 历 中 序 遍 历 后 序 遍 历 退 出 程 序
图1： 系统功能模块图
- . -word资料-
- --
准 备 系 统 登 录 选择 遍历 先 序 遍 历 中 序 遍 历 后 序 遍 历 输出遍历结果 退 出
图2：系统存盘功能流程图
- . -word资料-
- --
三 系统实现
系统核心代码：
1.二叉树的建立：
二叉树的遍历算法需要先建立二叉树，二叉树的建立需要建立栈和数组
栈和数组的建立：
typedef struct node /*结点定义*/ { char data;
struct node * lchild, * rchild; } BinTreeNode;
typedef struct{ //栈的定义 BinTreeNode * ptr; int tag; }StackNode;
二叉树的建立：
BinTreeNode * CreateBinTree (BinTreeNode * Tree )
/*,按先序序列建立二叉树，输入并建立一棵二叉树Tree*/ { char c; scanf(\"%c\ if(c=='&') Tree = NULL; else { Tree=(BinTreeNode * )malloc(sizeof(BinTreeNode)); Tree->data=c; Tree->lchild= CreateBinTree(Tree->lchild); Tree->rchild= CreateBinTree(Tree->rchild); }
return(Tree); }
- . -word资料-
- --
2.先序遍历：
a.递归算法：
先序遍历的递归算法：
/*二叉树的先序遍历*/
void PreOrder ( BinTreeNode *T ) { if ( T != NULL ) { printf(\"%c\ PreOrder ( T->lchild ); PreOrder ( T->rchild ); } }
- . -word资料-
- --
b.非递归算法：
先序遍历的非递归算法：
/*二叉树的先序遍历的非递归算法*/ void PreOrderTwo ( BinTreeNode *T ) {
BinTreeNode *p,*S[Max]; int top=-1;
p=T; /*初始化*/ do {
while ( p != NULL ) {
printf(\"%c\ top++;S[top]=p; p=p->lchild; }
if( top >-1 ) /*栈非空*/
{
p=S[top]; top--; /*取栈顶元素，出栈*/ p = p->rchild; }
}while (( p != NULL ) ||(top>-1)); }
- . -word资料-
- --
2.中序遍历：
检查该用户是否可以使用该系统，如果没有该用户则重新输入输入，若用户密码输入错误，三次错误时，退出登录系统，并且该用户被冻结。
void common_user()// 普通用户登录 {
char ch; char pass[20]; char uname[20]; int i=0; Lab:
if(i==3) exit(1); puts(\"\\n请输入用户名：\"); cin>>uname;
for(user *p= head; p!= NULL;p= p->next) {
if(!strcmp(uname,p->getmingzi())) {
if(p->getstate() >=3)
{
cout<<\"该账户已经被冻结！\\n\"; i++; goto Lab; }
else break; } } if(!p) {
- . -word资料-
- --
cout<<\"该用户不存在，请重新输入！\\n\"; i++; goto Lab; } int x = 0;
cout<<\"请输入密码：\\n\";
while((ch=getch())!= -1 && ch!= '\\r') {
pass[x++]= ch; putchar('*'); }
pass[x]='\\0';
if(!strcmp(p->getmima1(), pass))
while(1) {
system(\"cls\"); int a;
cout< - . -word资料- - -- switch(a) { case 1:cunqian(); system(\"cls\");break; case 2:quqian();system(\"cls\");break; case 3:zhuanzhang();system(\"cls\");break ; case 4: { chaxun();//cout<<\"请输入帐号：\"< { cunyonghu(); cunzhanghu(); cunguanli(); exit(1); } case 0:return; } } else { cout<<\"密码错误！\\n\"; p->setstate(p->getstate()+1); //如果密码错误，在以前基础上加状态一并存盘 cunyonghu(); i++; goto Lab; - . -word资料- - -- } } void display() //打印函数 { p= head; while(p!= NULL) { cout<<\"用户名：\"< 1) 没有此用户： - . -word资料- - -- 2）用户密码错误： 3）密码正确： 3.后序遍历： 检查该用户是否可以使用本系统，三次密码错误则退出登录系统。 void manage() // 管理员 { - . -word资料- - -- char ch; char pass[20]; char uname[20]; int i=0; Lab: if(i==3) exit(1); puts(\"\\n请输入用户名：\"); cin>>uname; for(user *p= head; p!= NULL;p= p->next) { if(!strcmp(uname,p->getmingzi())) { if(p->getstate() <0 ) { cout<<\"该账户已经被冻结！\\n\"; i++; goto Lab; } else break; } } if(!p) { cout<<\"该用户不存在，请重新输入！\\n\"; i++; goto Lab; } int x = 0; cout<<\"请输入密码：\\n\"; while((ch=getch())!= -1 && ch!= '\\r') - . -word资料- - -- { pass[x++]= ch; putchar('*'); } pass[x]='\\0'; if(!strcmp(\"133\ while(1) { system(\"cls\"); int x; cout< case 1: { system(\"cls\"); kaihu(); system(\"cls\"); - . -word资料- - -- break; } case 2: { xiaohu(); //销户 system(\"cls\"); break; } case 3: { chakan(); // 查询 system(\"cls\"); break; } case 4: { xiugai(); //修改密码才 system(\"cls\"); break; } case 5: { Delete(); //修改状态 system(\"cls\"); break; } case 6: { xiugai1(); system(\"cls\"); - . -word资料- - -- break; } case 7: { xiugaiyh(); system(\"cls\"); break; } case 8: { cunyonghu(); cunzhanghu(); cunguanli(); exit(1); } case 0: { return; } } } else { cout<<\"\\n密码错误！\\n\"; i++; goto Lab; } } - . -word资料- - -- 1) 密码错误： 2）密码正确： ④开户功能： 使用该功能可以拥有自己的账户，使用银行系统 void kaihu() { char zhanghao[20]; //用户帐号 - . -word资料- - -- char id[20]; //身份证号码 char mima[20]; //普通用户密码 int s= 0; //状态初始化为0，等于3时账户冻结 cout<<\"\\增加用户操作中\\n\"; cout<<\"请输入用户的帐号：\\n\"; cin>>zhanghao; cout<<\"请输入用户的身份证号码：\\n\"; cin>>id; cout<<\"请输入普通用户的密码：\\n\"; cin>>mima; oz= new zhanghu; oz->setzhanghao(zhanghao); oz->setid(id); oz->setmima(mima); oz->setleixing(s); oz->next = headz; headz= oz; cout<<\"注册完成！\\n\"; system(\"pause\"); } ⑤销户功能： 取消没有用了的账户。 void xiaohu () //注销一个帐户 { - . -word资料- - -- char ch; char s[20]; int n=0; cout<<\"请输入用户名：\"; cin>>s; for(pz= headz; pz!= NULL; pz=pz->next) { if(!strcmp(headz->getzhanghao(), s)) { n=1; break; } else if(!strcmp(pz->next->getzhanghao(), s)) break; } if(pz) { cout<<\"该用户已经找到，请确认删除(y/n)：\"; cin>>ch; if(ch=='y'|| ch=='Y') { if(n==1) headz= headz->next; else pz->next= pz->next->next; cout<<\"删除成功！\\n\"; system(\"pause\"); delete pz->next;// 释放节点空间 } - . -word资料- - -- } if(!pz) cout<<\"没有找到该账户！\\n\"; } ⑥挂失功能： void duzhanghu() { int v; //状态 char u[20];// 帐号 char w[20]; //身份证号码 char g[20];// 普通用户密码 int n; double x; ifstream fin(\"银行账户.txt\"); if(!fin) { cout<<\"银行账户文件打开失败！\\n\"; } else { fin>>n; for(int i=0; i< n; i++) { fin>>v>>u>>w>>g>>x; oz= new zhanghu; oz->setleixing(v); oz->setzhanghao(u); oz->setid(w); oz->setmima(g); oz->setyue(x); oz->next= headz; headz= oz; } fin.close(); cout<<\"银行账户打开成功！\\n\"; } } - . -word资料- - -- ⑥类的定义 class zhanghu //账户类 { private: char zhanghao[20]; //帐号 char id[20]; //身份证号码 char mima[20]; //普通用户密码 double yue; //余额 int leixing; //账户类型 public: zhanghu(){yue= 0;} char* getzhanghao() { return zhanghao; } void setzhanghao(char a1[]) { strcpy(zhanghao,a1); } char * getid() { return id; } void setid(char a2[]) - . -word资料- - -- { strcpy(id,a2); } char* getmima() { return mima; } void setmima(char a3[]) { strcpy(mima,a3); } double getyue() { return yue; } void setyue(double a4) { yue=a4; } int getleixing() { return leixing; } void setleixing(int a5) { leixing=a5; } class zhanghu * next; }; zhanghu * headz=NULL; - . -word资料- - -- zhanghu * pz=NULL; zhanghu * qz=NULL; zhanghu * oz=NULL; class user //用户类 { private: char mingzi[20]; //用户姓名 char mima1[20]; //普通用户密码 int state; //账户状态 public: char* getmingzi() { return mingzi; } void setmingzi(char a[]) { strcpy(mingzi,a); } char* getmima1() { return mima1; } void setmima1(char a2[]) { strcpy(mima1,a2); } int getstate() { return state; } - . -word资料- - -- void setstate(int a3) { state=a3; } user * next; }; user * head=NULL; user * p=NULL; user * q=NULL; user * o=NULL; void duyonghu() //将账用户信息读出 { int v; //状态 char u[20];// 用户名 char g[20];// 普通用户密码 int n; ifstream fin(\"银行用户.txt\"); if(!fin) { cout<<\"银行用户文件打开失败！\\n\"; } else { fin>>n; for(int i=0; i< n; i++) { fin>>v>>u>>g; o= new user; o->setstate(v); o->setmingzi(u); - . -word资料- - -- o->setmima1(g); o->next= head; head= o; } cout<<\"银行用户打开成功！\\n\"; } } void cunyonghu() //将用户信息存入 { ofstream fout(\"银行用户.txt\"); if(!fout) { cout<<\"打开文件失败\"< while(p!=NULL)//计算链表中共有多少个节点 { i++; p=p->next; } fout< p=p->next; - . -word资料- - -- }//cout<<\"文件存入成功!\"< void duzhanghu() //将账户信息读出 { int v; //状态 char u[20];// 帐号 char w[20]; //身份证号码 char g[20];// 普通用户密码 int n; double x; ifstream fin(\"银行账户.txt\"); if(!fin) { cout<<\"银行账户文件打开失败！\\n\";; } else { fin>>n; for(int i=0; i< n; i++) { fin>>v>>u>>w>>g>>x; oz= new zhanghu; oz->setleixing(v); oz->setzhanghao(u); oz->setid(w); oz->setmima(g); oz->setyue(x); oz->next= headz; headz= oz; } - . -word资料- - -- fin.close(); cout<<\"银行账户打开成功！\\n\"; } } void cunzhanghu() //将账户信息存入 { ofstream fout(\"银行账户.txt\"); if(!fout) { cout<<\"打开文件失败\"< while(pz!=NULL)//计算链表中共有多少个节点 { i++; pz=pz->next; } fout< } //cout<<\"文件存入成功!\"< - -- } fout.close(); 3 系统测试 各功能运行时界面及说明。 1 主菜单：注册用户，普通用户登录，管理员登录和退出登录。 图一：主窗口 2 普通用户：存钱，取钱，转账，查询，挂失，修改密码，保存信息，返回。 图二：普通用户登录窗口 3 管理员：开户，销户，查看，修改密码、账户、状态，保存，返回。 - . -word资料- - -- 图三：管理员登录窗口 4 管理员的查看：查看某账户所以信息，按时间查看业务信息。 图四：管理员查看窗口 4 小 结 通过为期两周的课程设计使我对银行管理系统和C++有了更深的认识和理解，也使我更加明白C++在程序设计中的重要性和地位。要想学好它要重在实践，要通过不断的上机操作才能更好的学习它，通过实践，我也发现我的好多不足之处，对各种控制结构及语句、数组的基本与高级应用、指针数组、字符数组、动态数组、函数的定义、调用方式；函数在编程中的具体应用；以及变量存储特征与标识符的作用域，通过实践，使我在这些方面有了认识和提高。课程设计它是一项任务，更是一种挑战和历练。在课程设计中，为了使用时方便，着重对不足方面的知识进行了分析与理解，在这一过程中对文件的操作有了很大的提高。通过实际的演练，可以增强对知识的理解和运用能力。 - . -word资料- - -- 我认为： 1 本系统没有做到精细的查询与模糊查询，查询时也可以设计按照月份查询等等。假如实现用户可以更好的了解自己账户的信息。 2 本系统没有做到自动生成帐号，银行的帐号应该是系统自动生成。 3 代码可以减少很多重复的。 我的编程能力还很弱，以后要好好加油。 5 参考文献 1.C++面向对象程序设计教程（第3版） 陈维兴 林小茶 编著2.C程序设计教程 谭浩强 著 清华大学出版社 3.例子代码 - . 清华大学出版社 -word资料- 因篇幅问题不能全部显示，请点此查看更多更全内容