第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
课程设计，树的应用，c语言.doc
课 程 设 计
课程设计名称： 算法分析与综合课程设计
专 业 班 级 ：
计 科 0604
学 生 姓 名 ：
杨
恒
学
号 ：
20064140405
指 导 教 师 ：
白 浩
课程设计时间：2008.06.22-2008.06.27
计算机科学与技术专业课程设计任务书
学生姓名
杨恒
专业班级 计科 0604
学号
20064140405
题 目
课题性质
指导教师
主要内容
其它
白 浩
树的应用
课题来源
同组姓名
自拟课题
无
实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，
层次序的非递归算法的实现，应包含建树的实现。
任务要求
1.实现对树的建立。
2.实现几种树的遍历算法
1.C 语言程序设计（第三版） 清华大学出版社 谭浩强 著
参考文献
2．数据结构（C 语言版） 清华大学出版社 严蔚敏 吴伟民 编著
指导教师签字：
审查意见
教研室主任签字：
2008 年 5 月 8 日
一、需求分析
1．首先选择一种结点实现树结点的存储。
2．首先建立树，在用户输入各结点信息时，应提示用户输入结点的父亲，
孩子，和兄弟的信息，即要让用户明确选择各结点之间的相互联系。
3．实现树的遍历算法。在该实验中，实现了树的先根的递归和非递归算
法，后根的递归算法以及按层次序的非递归算法。
4．用户界面的设计应满足用户的选择，可以选择不同的遍历算法显示遍
历结果。
二、概要设计
1．用孩子—兄弟表示法作为树结点的存储结构
typedef struct CSNode
{
char data;
struct CSNode *firstchild;
struct CSNode *nextbiling;
};
2．一些全局变量的声明
struct CSNode * root;
struct BTree * x;
char flag;
3．树建立的算法描述
建立根结点：
void create_root()
{
root = (struct CSNode*)malloc(sizeof(struct CSNode));
printf("请输入根结点信息:");
scanf("%c",&root->data);
}
递归建树：
voidcreate(structCSNode*temp)
//构造树
{
递归建树
if(temp!=NULL)
{//输入长子信息
printf( "是否有孩子?(y/n)\n");
flag=getchar();
if(flag == 'y' || flag == 'Y')
{
t =(struct CSNode*)malloc(sizeof(struct CSNode));
printf( "请输入长子信息:\n" );
t->data=getchar();
temp -> firstchild = t;//指向长子
}
1
else
temp -> firstchild = NULL;
//输入兄弟信息
printf("是否有兄弟?(y/n)\n" );
if(flag == 'y' || flag == 'Y')
{
m = (struct CSNode*)malloc(sizeof(struct CSNode));
printf( "请输入兄弟信息:\n");
m->data=getchar();
temp -> nextbiling = m; //指向兄弟
}
else
temp -> nextbiling = NULL;
//递归建立结点
create(temp -> firstchild);
create(temp -> nextbiling);
}
4．树的先根和后根的递归算法描述
//先序遍历的递归算法
void recur_pre_order(struct CSNode *root)
{if(root)
{printf("%c",root->data);
recur_pre_order(root->firstchild);
recur_pre_order(root->nextbiling);}
}
//后序遍历的递归算法
void recur_post_order(struct CSNode *root)
{if(root!=NULL)
{
recur_post_order(root->firstchild);
recur_post_order(root->nextbiling);
printf("%c",root->data);
}
}
5．树的先根的非递归算法预备工作之栈的设计
struct CSNode*base[100]={NULL};
struct CSNode**top=base;
struct CSNode* Pop(struct CSNode**top)
{// 如果栈空，返回 ERROR ；如果栈不空，删除栈顶元素，用 e
返回其值，并返回 OK 。
}
Push(struct CSNode**top,struct CSNode*p)
{//将元素 p插入到栈 S 中，成为新的栈顶元素}
2
6.树的先根非递归算法
void non_recur_pre_order(struct CSNode *t)
{struct CSNode *p=t;
while (p!=NULL||!StackEmpty(top))
{ while (p!=NULL)
{
printf("%c",p->data);
//遍历左子树
//通过下一次循环中的内嵌
while 实现右子树遍历
Push(top,p);
p=p->firstchild;
}//endwhile
if(!StackEmpty(top))
p=Pop(top);
p=p->nextbiling;
}//endif
}
{
}
7．树的按层次序的非递归算法
//层次遍历算法
void LevelOrder(struct CSNode *t)
{
struct
struct
CSNode *p;
CSNode *qu[MaxSize];
int front,rear;
front=rear=-1;
rear++;
qu[rear]=t;
while(front!=rear)
{
front=(front+1)%MaxSize;
p=qu[front];
printf("%c ",p->data);
if(p->firstchild!=NULL)
{
rear=(rear+1)%MaxSize;
qu[rear]=p->firstchild;
}
if(p->nextbiling!=NULL)
{
rear=(rear+1)%MaxSize;
qu[rear]=p->nextbiling;
}
}
}
3
三、 运行环境
1．硬件环境
PC
2．软件环境止上下
Windows XP
Microsoft Visual C++6.0
四、开发工具和编程语言
1．开发工具
Microsoft Visual Studio C++ 6.0
2．编程语言
C 语言
五、详细设计
1．树建立的算法实现
void create_root()
{
root = (struct CSNode*)malloc(sizeof(struct CSNode));
printf("请输入根结点信息:");
scanf("%c",&root->data);
x = (struct BTree*)malloc(sizeof(struct BTree));
x -> data = root -> data;
CSNode
*temp)
}
voidcreate(struct
//构造树
递归建树
{
struct CSNode *t=NULL;
struct CSNode *m=NULL;
if(temp!=NULL)
{//输入长子信息
printf("%c", temp -> data );
flag=getchar();
printf( "是否有孩子?(y/n)\n");
flag=getchar();
if(flag == 'y' || flag == 'Y')
{
flag=getchar();
t =(struct CSNode*)malloc(sizeof(struct CSNode));
printf( "请输入长子信息:\n" );
t->data=getchar();
temp -> firstchild = t;
}
else
4
temp -> firstchild = NULL;
//输入兄弟信息
printf("%c", temp -> data );
flag=getchar();
printf("是否有兄弟?(y/n)\n" );
flag=getchar();
if(flag == 'y' || flag == 'Y')
{
flag=getchar();
m = (struct CSNode*)malloc(sizeof(struct CSNode));
printf( "请输入兄弟信息:\n");
m->data=getchar();
temp -> nextbiling = m;
}
else
temp -> nextbiling = NULL;
//递归建立结点
create(temp -> firstchild);
create(temp -> nextbiling);
}
}
2．树的先根和后根的递归算法描述
与概要设计中的算法基本一致
3．树的先根的非递归算法预备工作之栈的实现
struct CSNode* Pop(struct CSNode**top)
{struct CSNode*t;
if (top==base)
return NULL;
else
{t=*top;
*top=NULL;
top--;
return t;
}
}
Push(struct CSNode**top,struct CSNode*p)
top++;
{
*top=p;
}
int StackEmpty(struct CSNode**top)
{if(top==base)
return 1;
else { printf ("fdhsd");return 0;}
}
5
4．树的先根非递归算法，树的按层次序的非递归算法
具体代码与算法描述一致
5．主函数的设计
main()
{
int cord;
printf("\n
do {
printf("
printf("
printf("
printf("
printf("
printf("
主菜单
建立树
先根递归遍历
先根非递归遍历
后根递归遍历
按层次非递归遍历
\n");
1
2
3
4
5
6 结束程序运行
\n");
\n");
\n");
\n");
\n");
\n");
printf("-----------------------------------------\n");
printf("请输入您的选择(1，2，3，4，5，6) ");
scanf("%d",&cord);
getchar();
switch (cord)
{case 1:
//构建树
create_root();
create(root);
printf("树构建成功");
printf("\n");
break;
case 2:
//先序遍历的递归算法
recur_pre_order(root);
printf("\n");
break;
case 3:
//先序遍历的非递归算法
non_recur_pre_order(root);
break;
case 4:
//后序遍历的递归算法
recur_post_order(root);
printf("\n");
break;
case 5:
//按层次遍历的非递归算法
LevelOrder(root);
break;
case 6:printf("
欢迎使用
\n ");
break;}
6
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
