《数据结构课程设计10计21011001024梁志才》由会员分享，可在线阅读，更多相关《数据结构课程设计10计21011001024梁志才（13页珍藏版）》请在金锄头文库上搜索。
1、广东工业大学华立学院广东工业大学华立学院 课课 程程 设设 计（论文）计（论文） 课程名称 数据结构 题目名称 二叉树非递归算法 学生学部（系） 艺术设计与计算机 专业班级 10 计算机 1 班 学 号 21011001024 学生姓名 梁志才 指导教师 程东胜 2011 年 12 月 05 日 广东工业大学华立学院广东工业大学华立学院 课程设计（论文）任务书课程设计（论文）任务书 一、课程设计（论文）的内容 1.创建二叉树 2.二叉树的非递归算法（前、中、后） 二、课程设计（论文）的要求与数据 需求分析 概要设计 详细设计 编程实现 测试: 提供数个测试用例 符合撰写规范设计的必要说明文档
2、三、课程设计（论文）应完成的工作 题目名称二叉树非递归算法 学生学部（系）艺术设计与计算机学部 专业班级10 计算机 1 班 姓 名梁志才 学 号 21011001024 3 （1）根据要求完成课题； （2）程序书写符合规范，程序设计完善； （3）对程序进行初步的测试； （4）程序运行结果和过程的界面截图； （5）根据设计规范撰写报告并按时提交； （6）设计内容用A4纸打印并按要求装订。 四、课程设计（论文）进程安排 序号设计（论文）各阶段内容地点起止日期 1 搜集资料图书馆 12.05-12.10 2 需求分析图书馆 12.10-12.14 3 概要设计图书馆 12.14-5.17 4 详细
3、设计图书馆 12.17-12.20 5 程序实现图书馆 12.20-12.29 6 系统测试、运行机房 12.19-12.30 7 提交报告 12.30 五、应收集的资料及主要参考文献 1 朱战立编著.数据结构（使用 C 语言（第 4 版）.北京:电子工业出版社,2009.1 发出任务书日期：发出任务书日期： 20112011 年年 1212 月月 1212 日日 指导教师签名：指导教师签名： 计划完成日期：计划完成日期： 20112011 年年 1212 月月 3030 日日 教学单位责任人签章：教学单位责任人签章： 目录目录 1 1 序言序言 .1 1 2 2 需求分析需求分析.1 1 2
4、.1 需求分析.1 2.2 功能分析.1 3 3 概要设计概要设计 .1 1 4 4 详细设计详细设计 .2 2 5 5 程序实现程序实现.3 3 总结总结.6 6 参考文献参考文献.7 7 1 1 1 序言序言 本课程设计旨在熟悉与了解二叉树非递归算法的建立以其应用,培养学生独立思考、综 合应用所学有关相应知识的能力，使学生巩固课程所学的内容，掌握工程软件设计的基本方 法，强化上机动手编程能力闯过理论与实践相结合的难关。同时也培养学生的创新和创造能 力，使学生获得科学研究的基础训练，为以后的学习打下坚实的基础。 2 2 需求分析需求分析 2.12.1 需求分析需求分析 树形结构是一类重要的非
5、线性数据结构，树中节点之间具有明确的层次关系，并且结 点之间有分支，它非常类似于实际的树。树形结构在客观世界中大量存在，如行政组织机构 和人类社会的家谱关系等都可用树形结构形象地表示。在计算机应用领域，树结构也被广泛 应用，例如在编译程序中，用树形结构来表示图形结构来表示源程序的语法结构；在数据库 系统中，用树形来组织信息；在计算机图形学中，用树结构来表示图像关系等。在二叉树上 无论采用那种遍历方法，都能够访问遍数中的所有结点。由于访问结点的顺序不同，前序遍 历和后序遍历都很难达到设计的要求；但采用后序遍历二叉树是可行的，因为后序遍历是最 后访问根节点，按这个顺序将访问过的结点存储到到一个顺序
6、栈中，然后再输出即可。另外， 为了加深对遍历二叉树的理解，在这里顺便把实现二叉树的非递归遍历概念也加入到这个设 计要求中。 2.22.2 功能分析功能分析 3 概要设计 输入一个二叉树，利用栈结构建立二叉链表树，利用栈结构依次将结点入栈、出栈实 开始 创建二叉树 先序遍历中序遍历后序遍历 非递归非递归非递归 结束 2 现二叉树的非递归遍历算法。 例如：abd#e#cf#g#建立下图所示二叉树 4 详细设计 1. 二叉树数据的类型定义 struct tree char data; struct tree *lchild; strude tree *rchild; 2. 主要模板设计 创建二叉树
7、treptr build(treptr t) char c; c=getchar(); if(c=#) t=NULL; else t=(treptr)malloc(sizeof(struct tree); t-data=c; t-lchild=build(t-lchild); t-rchild=build(t-rchild); return t; 入栈 void push(stackptr s,treptr t) *(s-top+)=t; 弹出栈顶元素 treptr pop(stackptr s) treptr t; t=*(-(s-top); return t; 非递归先序实现 void p
8、reorder(treptr t) if(!t) return; else d b g fe c a 3 printf(%c ,t-data); preorder(t-lchild); preorder(t-rchild); 非递归中序实现 void inorder(treptr t) treptr s100; int top=0; while(t|top) while(t) s+top=t; t=t-lchild; if(top) putchar(stop-data); t=stop-rchild; 非递归后序实现 void postorder(treptr t) stackptr s=(s
9、tackptr)malloc(sizeof(struct stack); treptr temp=t; treptr p; treptr lastvist=NULL; init(s); p=t; while(p|s-top!=s-base) while(p) push(s,p); p=p-lchild; temp=gettop(s); if(temp-rchild=NULL|temp-rchild=lastvist) putchar(temp-data); lastvist=pop(s); else p=temp-rchild; 5 5 程序实现程序实现 #include #include s
10、truct tree char data; struct tree *lchild; struct tree *rchild; typedef struct tree * treptr; treptr build(treptr t)/先序建树 char c; c=getchar(); if(c=#) t=NULL; 4 else t=(treptr)malloc(sizeof(struct tree); t-data=c; t-lchild=build(t-lchild); t-rchild=build(t-rchild); return t; void postdorder(treptr r
11、oot) if (root!=NULL) postdorder(root-lchild); postdorder(root-rchild); printf(%c,root-data); struct stack treptr *top,*base; typedef struct stack *stackptr; void init (stackptr s)/初始化栈 s-base=(treptr*)malloc(sizeof(treptr)*100); s-top=s-base; void push(stackptr s,treptr t)/入栈 *(s-top+)=t; treptr pop(stackptr s)/弹出栈顶元素 treptr t; t=*(-(s-top); return t; treptr gettop(stackptr s)/
