班级 02－0912
学号 02091112
软件大作业。
题目软件大作业。
学院电子工程学院。
专业电子信息工程。
学生姓名高大容。
导师姓名刘丹华。
第一题。从键盘输入字符（6个以上的字符）建立一棵二叉树（二叉树形式任意），输出该二叉树的dlr，ldr，lrd序列，统计叶子结点个数，总结点个数，及二叉树深度；
一：算法分析。
a. 建立一颗二叉树基本步骤：
1） 按照结点的序号，依次输入结点信息，若输入的结点不是虚节点，则建立一个新结点。
2） 若新结点是第一个结点，则令其为根结点，否则将新结点作为孩子结点链接到它的双亲结点上。
3） 如此反复进行，直到输入结束标志“#”为止。
b. 二叉树遍历（采用递归算法）：
dlr序列：
1） 访问根结点。
2） 先序遍历左子树。
3） 先序遍历右子树。
ldr序列：
1) 中序遍历左子树。
2) 访问根结点。
3) 中序遍历右子树。
lrd序列：
1) 后序遍历左子树。
2) 后序遍历右子树。
3) 访问根结点。
c.统计叶子结点个数（采用递归算法）：
1）调用递归访问左子树。
2）调用递归访问右子树。
3）左右子树都为空，则为叶子结点。
d.总结点个数（采用递归算法）：
1）访问根结点（非空，结点个数加1）
2）调用递归访问左子树。
3）调用递归访问右子树。
e.二叉树深度（采用递归算法）：
1）树为空，返回0
2）统计左，右子树的深度u，v
3）u>v，返回u+1，否则返回v+1
二：流程图。
a． 建立一棵二叉树流程图。
b． 三种遍历流程图。
c．统计叶子个数流程图 d。统计结点个数流程图。
e。二叉树深度流程图。
三：程序**。
#include<>
#include<>
typedef char datatype;
typedef struct node
datatype data;
struct node*lchild,*rchild;
bitree;
bitree*root;
int count1=0,count2=0;
bitree*creatree();
void preorder(bitree*p);
void inorder(bitree*p);
void postorder(bitree*p);
void yezi(bitree*p);
void jiedian(bitree*p);
int depthtree(bitree*p);
void main()
int h;
bitree*root;
root=creatree();
preorder(root);
printf("");
inorder(root);
printf("");
postorder(root);
printf("");
yezi(root);
printf("%d",count1);
jiedian(root);
printf("%d",count2);
h=depthtree(root);
printf("%d",h);
bitree*creatree()
char ch;
int front,rear;
bitree*q[1024];
bitree*s;
root=null;
front=1;rear=0;
while((ch=getchar())#
rear++;
q[rear]=s;
if(rear==1) root=s;else
return root;
void preorder(bitree*p)
if(p!=null)
void postorder(bitree*p)
if(p!=null)
postorder(p->lchild);
postorder(p->rchild);
printf("%c",p->data);
void inorder(bitree*p)
if(p!=null)
inorder(p->lchild);
printf("%c",p->data);
inorder(p->rchild);
void yezi(bitree*p)
if(p!=null)
void jiedian(bitree*p)
if(p!=null)
int depthtree(bitree *p) /深度函数。
int u,v;
if (p==null) return 0;
u=depthtree(p->lchild);
v=depthtree(p->rchild);
if (u>v)
return (u+1);
return (v+1);
四、执行结果。
第二题。设电文由a,b,c,d,e五个字符构成，出现的概率分别为0.25,0.
15,0.2,0.1,0.
3，为这些字符设计相应的哈夫曼编码（提示参考算法6.16建立一棵哈夫曼树），并验证译码是否正确。
一、算法。1）编码：提示要编码的文件文件名→读取文件→以字母出现次数为权值建立哈夫曼树→对文本进行哈夫曼编码并输出编码→提示将编码保存的文件名→保存编码文件；
2）.译码：提示输入要译码的文件名→利用建立好的哈夫曼树进行译码→将译码输出→提示保存译码文件的文件名→保存译码文件；
3）.退出：退出系统，程序运行结束。
二、流程图。
创建哈夫曼树。
编码。译码。
三、三、执行结果。
四、程序**。
#include<>
#include<>
#include<>
#include<>
#include<>
typedef struct赫夫曼树的结构体。
char ch;
int weight权值。
int parent,lchild,rchild;
htnode,*hfmtree;
typedef char **hfmcode;
void select(hfmtree &ht,int a,int *p1,int *p2) /select函数，选出ht树到a为止，权值最小且parent为0的2个节点。
int i,j,x,y;
for(j=1;j<=a;++j)
for(i=j+1;i<=a;++i)
for(j=1;j<=a;++j)
for(i=j+1;i<=a;++i)
if(x>y)
elsevoid hfmcoding(hfmtree &ht,hfmcode &hc,int n) /构建赫夫曼树ht，并求出n个字符的赫夫曼编码hc
int i,start,c,f,m,w;
int p1,p2;
char *cd,z;
if(n<=1)
m=2*n-1;
ht=(hfmtree)malloc((m+1)*sizeof(htnode));
for(i=1;i<=n;++i初始化n个叶子结点。
ht[i].ch=z;
ht[i].weight=w;
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
for(;i<=m;++i初始化其余的结点。
for(i=n+1;i<=m;++i建立赫夫曼树。
select(ht,i-1,&p1,&p2);
ht[p1].parent=i;ht[p2].parent=i;
ht[i].lchild=p1;ht[i].rchild=p2;
ht[i].weight=ht[p1].weight+ht[p2].weight;
《软件基础》大作业
项目名称 双副扑克一人升级游戏 一人与三机器人玩 班级 电气 29 学号 02041271 02041260 02041257 姓名 李余强张亚婷马媛媛 完成时间 2004 11 8 指导老师 卫颜峻。日期 2004 11 24 目录。一 需求分析。1 1开发背景3 1 2项目目标3 1 3运行环境...
软件基础大作业
软件基础课堂内容。一绪论 算法与算法分析 性质 输入性，输出性，有穷性，确定性，可行性。频度 语句重复执行的次数。时间复杂度 算法的时间耗费t n 二线性表 线性表 一个线性表是n个数据元素 结点 的有限序列。是有n个数据元素构成的有线序列。顺序表 顺序映像。插入运算。删除运算。链表 存储数据元素信...
软件工程大作业
目录。引言 1正文 1 3 软件需求分析 2 3.1系统功能需求分析 2 3.2管理信息系统的界面特点 3 3.3 管理系统具体研究 3 4 功能需求描述 5 4.1员工基本信息模块 5 4.2工资结构设置模块 6 4.3数据库设计 6 4.4数据流程图 6 总结 9参考文献 10 基于sql开发的...