软件基础实验-树、二叉树和图

软件基础实验-树、二叉树和图实验三树、二叉树和图一、实验目的： 1．参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关　的操作； 2．参照给定的图类的程序样例，验证给出的有关图的常见算法，并实现有关的操作。二、实验内容： 1．设计实现二叉树类，要求：（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。（2）编写一主函数来验证算法实现。 2. 假设二叉树采用链式存储结构进...

实验三树、二叉树和图一、实验目的： 1．参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关　的操作； 2．参照给定的图类的程序样例，验证给出的有关图的常见算法，并实现有关的操作。二、实验内容： 1．设计实现二叉树类，要求：（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。（2）编写一主函数来验证算法实现。 2. 假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。 3. 设计图邻接表类，实现无向图的深度优先搜索法遍历、纵向优先搜索法遍历，并设计主函数输入数据进行测试。三、算法程序 1、二叉树类 #include using namespace std; template //定义二叉链表结点类型 struct Btnode { T d; Btnode* lchild; Btnode* rchild; }; //二叉链表类 template class Binary_Tree { private: Btnode *BT; public: Binary_Tree() {BT=NULL;return;} void creat_Binary_Tree(T); void pretrav_Binary_Tree(); void intrav_Binary_Tree(); void postrav_Binary_Tree(); }; //生成二叉链表 template void Binary_Tree::creat_Binary_Tree(T end) { Btnode * p; T x; cin>>x; if (x==end) return; p=new Btnode; p->d=x;p->lchild=NULL;p->rchild=NULL; BT=p; creat(p,1,end); creat(p,2,end); return; } template static creat (Btnode * p,int k,T end) { Btnode * q; T x; cin>>x; if(x!=end) { q=new Btnode; q->d=x;q->lchild=NULL;q->rchild=NULL; if (k==1) p->lchild=q; if (k==2) p->rchild=q; creat(q,1,end); creat(q,2,end); } return 0; } //前序遍历二叉链表 template void Binary_Tree::pretrav_Binary_Tree() { Btnode * p; p=BT; pretrav(p); cout< static pretrav(Btnode * p) { if (p!=NULL) {cout<d<<" "; pretrav(p->lchild); pretrav(p->rchild); } return 0; } //中序遍历二叉链表 template void Binary_Tree::intrav_Binary_Tree() { Btnode * p; p=BT; intrav(p); cout< static intrav(Btnode * p) {if (p!=NULL) { intrav(p->lchild); cout<d<<" "; intrav(p->rchild); } return 0; } //后序遍历二叉链表 template void Binary_Tree::postrav_Binary_Tree() { Btnode * p; p=BT; postrav(p); cout< static postrav(Btnode * p) {if (p!=NULL) {postrav(p->lchild); postrav(p->rchild); cout<d<<" "; } return 0; } //主函数 int main(){ Binary_Treeb; cout<<"输入各结点值(-1为结束符):"< g; g.creat_Link_GP(8,d,"f1.txt"); cout<<"图g邻接表："< #include using namespace std; template struct node { int num; T1 val; node * next; }; template struct gpnode { T2 data; node *link; }; //定义图邻接表类 template class Link_GP { private: int nn; //图中结点个数 gpnode *gp;//图邻接表中顺序存储空间首地址 public: Link_GP(){gp=NULL;return;}//图邻接表初始化 void creat_Link_GP(int,T2[]);//由键盘输入生成图邻接表 void creat_Link_GP(int,T2[],char *);//由文件数据生成图邻接表 void prt_Link_GP();//输出图邻接表 void dfs_Link_GP();//纵向优先搜索法遍历图 void bfs_Link_GP();//横向优先搜索法遍历图 void short_Link_GP(int);//求指定结点到其余各结点的最短距离 void short_path_Link_GP(int);//求指定结点到其余各结点的最短距离与路径 }; //由键盘输入生成图邻接表 template void Link_GP::creat_Link_GP(int n,T2 d[]) { node *p; nn=n; //图中结点个数 int k,m; T1 v; gp=new gpnode[nn];//申请图邻接表中顺序存储空间 for(k=0;kdata=d[k];//置顺序存储空间的结点值 (gp+k)->Link=NULL;//置顺序存储空间结点的指针域为空 cout<<"请输入图中第"<>m>>v; //输入后件信息 while(m>=0) { p=new node; //申请单链表结点 p->num=m;p->val=v; p->next=(gp+k)->link;//新结点指针指向原头结点 (gp+k)->link=p;//将新结点链接到单链表链头 cin>>m>>v; } } return; } //由文件数据生成图邻接表 template void Link_GP::creat_Link_GP(int n,T2 d[],char * filename) { node *p; int k,m; nn=n; T1 v; ifstream infile(filename,ios::in);//打开文件 gp=new gpnode[nn]; for(k=0;kdata=d[k];//置顺序存储空间的结点值 (gp+k)->link=NULL;//置顺序存储空间结点的指针域为空 infile>>m>>v; //输入后件信息 while(m>=0) { p=new node; //申请单链表结点 p->num=m;p->val=v; p->next=(gp+k)->link;//新结点指针指向原头结点 (gp+k)->link=p;//将新结点链接到单链表链头

                    本文档为【软件基础实验-树、二叉树和图】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

软件基础实验-树、二叉树和图

你可能还喜欢