实验报告
实验目的：
1. 掌握树及二叉树的基本概念；
2. 掌握二叉树的存储结构；
3. 掌握二叉树的遍历。
实验内容：
算术表达式与二叉树之间存在着对应关系，编写一算法将前缀形式输入的算术表达式按中缀方式输出。
实验原理：
根据访问二叉树根节点的顺序，可以分为先序遍历、中序遍历、后序遍历。算术表达式与二叉树之间存在着对应的关系。在本程序建立的二叉树中，先序遍历输出的结果将是前缀表达式，中序遍历输出的结果将是中缀表达式。按照某种既定的规则建立二叉树，然后输出。
设计思想:
本程序定义了结点类、二叉树类。在结点类中定义了构造函数，二叉树类中定义了构造函数、建立二叉树函数、中序遍历函数。
在前缀表达式中，很容易将最后两个数据混为一谈。在本程序中，在输入时要求输入后的每个数据以#结尾，这样既避免了两个数据混为一谈，同时结束了该子树的建立，方便了二叉树的建立。
建立二叉树函数中，如果输入的是运算符号，则递归调用建立函数分别建立左子树和右子树；如果输入的是数字，则递归调用建立函数建立右子树；如果输入的是#，则该节点为空，结束递归调用。反复的递归调用，直至二叉树建成为止。然后按照中序遍历输出即可。
实现部分:
源代码：
#include<iostream.h>
class btree;
class bintreenode
{friend class btree;
char data;
bintreenode *lchild;
bintreenode *rchild;
public:
bintreenode(){lchild=rchild=NULL;}
bintreenode(char item)
{data=item;
lchild=rchild=NULL;
}
bintreenode(char value,bintreenode *left,bintreenode *right);
};
class btree
{public:
btree(){root=NULL;}
btree(char value,bintreenode *left,bintreenode *right);
void creat(bintreenode *&root);
void inorder(bintreenode *root);
protected:
bintreenode *root;
};
//中序遍历函数
void btree::inorder(bintreenode *root)
{if(root!=NULL)
{inorder(root->lchild);
cout<<root->data;
inorder(root->rchild);}
}
//建立二叉树函数
void btree::creat(bintreenode *&root)
{char ch;
cin>>ch;
if(ch=='#') root=NULL;
if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{
root=new bintreenode;
root->data=ch;
creat(root->lchild);
creat(root->rchild);
}
if(ch>='0'&&ch<='9')
{
root=new bintreenode;
root->data=ch;
creat(root->rchild);
}
}
int main()
{btree bt;
bintreenode *root;
cout<<"请输入前缀表达式,每个数字以#结束:"<<endl;
bt.creat(root);
cout<<"转化后的中缀表达式为:"<<endl;
bt.inorder(root);
cout<<endl;
return 0;}
测试用例1.
前缀表达式：+ 5 *6 7
输入前缀表达式：+5#*6#7#
程序运行结果:
c测试用例2.
前缀表达式：+ 123 * 56 +5 68
输入前缀表达式：+123#*56#+5#68#
程序运行结果：
实验小节：
本程序中，通过#结束子树的建立，同时避免了数据间的混淆，一举两得。
二叉树的建立和遍历的过程中，都是用了递归操作，加深了对递归的认识。
通过本程序的练习，更好的理解了二叉树的基本概念，对二叉树的建立、遍历等基本操作有了更深的认识。
第二篇：数据结构实验报告十二—最小生成树问题
问题描述：
若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。
一、 需求分析：
需定义结构体数组，根据权值逐一选择边。
二、概要设计 ：
抽象数据类型 ：
需定义结构体数组，存储每条边的起点，终点，权值。
算法的基本思想 ：
1、图的信息的读取：
定义结构体数组，存储每条边的起点，终点，权值。
2、对每条边在数组中的位置处理：
选边需从最小的开始，故按边的权值从小到大进行排序。
3、边的选取：
从最小的边的开始，若边的两端点不属于同一集合，则选
取该边。并将该边的两个顶点所在的两个集合合并成为一个。
因为有n个顶点，故只需选取n-1条边。
程序的流程
程序由三个模块组成：
输入模块：读入图的信息（顶点和边，用结构体数组进行存储）。
处理模块：Kruskal算法。
输出模块：将结果输出。
三、详细设计
算法的具体步骤：
struct G{
int fromvex;
int endvex;
int weight;
}GE[100],cur[100];
void swap(G* GE,int i,int j){ //交换函数
int temp=GE[i].fromvex;
GE[i].fromvex=GE[j].fromvex;
GE[j].fromvex=temp;
temp=GE[i].endvex;
GE[i].endvex=GE[j].endvex;
GE[j].endvex=temp;
temp=GE[i].weight;
GE[i].weight=GE[j].weight;
GE[j].weight=temp;
}
void Kruskal(int n){
int i,j,k=0,pos=-1,m1,m2;
bool** s=new bool *[n];
//定义一个二维数组，用来判断是否为同一类
for(i=0;i<n;i++)
s[i]=new bool[n];
for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
if(i==j)
s[i][j]=true; //初始化数组
else
s[i][j]=false;
}
}
while(k<n-1){
for(i=0;i<n;i++){
if(s[i][GE[k].fromvex]==1)
m1=i;
if(s[i][GE[k].endvex]==1)
m2=i;
}
if(m1!=m2){
//判断是否为同一类,如果为同一类（该类中所有的点到起点和终//点的边在s数组中赋为1），
cur[++pos].fromvex=GE[k].fromvex;
cur[pos].endvex=GE[k].endvex;
cur[pos].weight=GE[k].weight;
for(i=0;i<n;i++){
if(s[m1][i] || s[m2][i])
//把该点添加到该类，并和并两个类
s[m1][i]=1;
else
s[m1][i]=0;
s[m2][i]=0;
}
}
k++;
}
for(i=0;i<n;i++){
delete []s[i];
}
}
int main(){
int i,j;
int numVertex,numEdge;
cout<<"请输入点的个数和边的条数："<<endl;
cin>>numVertex>>numEdge;
cout<<"请输入边的起始位置和边的权值："<<endl;
for(i=0;i<numEdge;i++)
cin>>GE[i].fromvex>>GE[i].endvex>>GE[i].weight;
for(i=0;i<numEdge;i++)
for(j=i;j<numEdge;j++){
if(GE[j].weight<GE[i].weight)
//将边的权值按从小到大排列
swap(GE,i,j);
}
Kruskal(numEdge);
for(i=0;i<numVertex-1;i++)
cout<<cur[i].fromvex<<"->"<<cur[i].endvex<<":"<<cur[i].weight<<endl;
system("pause");
return 0;
}
四、调试分析 ：
将选边的过程输出来检验算法的正确性。
五、测试结果
本实验的测试结果截图如下：
六、用户使用说明（可选）
1 、本程序的运行环境为windows 操作系统，执行文件为zuixiaoshu.exe
2 、运行程序时
提示输入数据 并且输入数据然后回车就可以继续输入相应数据，最后即可得到结果。
七、实验心得（可选）
本次实验设计内容比较多，虽然实验过程中多次出现问题，但通过多次调试最终得到解决。并且通过本次试验，学会并掌握了二维数组的动态分配，另外在实验过程中，一开始写程序时，只是把一个点添加到一个类中。后来分析
才改正错误，将两个集合进行合并；另外曾试图用两个顶点是否有同一个根结点来判断两点是否为同一集合的，但未实现。
附录（实验代码）：
#include<iostream>
using namespace std;
struct G{
int fromvex;
int endvex;
int weight;
}GE[100],cur[100];
void swap(G* GE,int i,int j){ //交换函数
int temp=GE[i].fromvex;
GE[i].fromvex=GE[j].fromvex;
GE[j].fromvex=temp;
temp=GE[i].endvex;
GE[i].endvex=GE[j].endvex;
GE[j].endvex=temp;
temp=GE[i].weight;
GE[i].weight=GE[j].weight;
GE[j].weight=temp;
}
void Kruskal(int n){
int i,j,k=0,pos=-1,m1,m2;
bool** s=new bool *[n]; //定义一个二维数组，用来判断是否为同//一类
for(i=0;i<n;i++)
s[i]=new bool[n];
for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
if(i==j)
s[i][j]=true; //初始化数组
else
s[i][j]=false;
}
}
while(k<n-1){
for(i=0;i<n;i++){
if(s[i][GE[k].fromvex]==1)
m1=i;
if(s[i][GE[k].endvex]==1)
m2=i;
}
if(m1!=m2){ //判断是否为同一类,如果为//同一类（该类中所有的点到起点和终点的边在s数组中赋为1），
cur[++pos].fromvex=GE[k].fromvex;
cur[pos].endvex=GE[k].endvex;
cur[pos].weight=GE[k].weight;
for(i=0;i<n;i++){
if(s[m1][i] || s[m2][i]) //把该点添加到该类，并和并两个类
s[m1][i]=1;
else
s[m1][i]=0;
s[m2][i]=0;
}
}
k++;
}
for(i=0;i<n;i++){
delete []s[i];
}
}
int main(){
int i,j;
int numVertex,numEdge;
cout<<"请输入点的个数和边的条数："<<endl;
cin>>numVertex>>numEdge;
cout<<"请输入边的起始位置和边的权值："<<endl;
for(i=0;i<numEdge;i++)
cin>>GE[i].fromvex>>GE[i].endvex>>GE[i].weight;
for(i=0;i<numEdge;i++)
for(j=i;j<numEdge;j++){
if(GE[j].weight<GE[i].weight) //将边的权值按从小到大排列
swap(GE,i,j);
}
Kruskal(numEdge);
for(i=0;i<numVertex-1;i++)
cout<<cur[i].fromvex<<"->"<<cur[i].endvex<<":"<<cur[i].weight<<endl;
system("pause");
return 0;
}