鱼C论坛

 找回密码
 立即注册
查看: 2103|回复: 5

[已解决]数据结构有关的问题--森林.(数组访问还有一些问题)

[复制链接]
发表于 2019-12-9 10:47:36 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 MFwxy 于 2019-12-11 10:52 编辑

大问题已经解决了,大佬看一看附件就好啦
数组访问的[2][6]明明应该为NULL,但实际上却是[3][0]的'K'。这是为啥啊?

森林的层序遍历,
TForst.h:
#pragma once
#include<iostream>
#define maxn 100
#define ElemenType char

using namespace std;

struct FSNode
{
        ElemenType data = NULL;
        FSNode* firstchild = NULL;
        FSNode* nextsibling = NULL;
};


class TForest
{
public:
        TForest();
        virtual ~TForest();
        //输入数据
        void Tree_in();
        //各种遍历
        void H_BL(FSNode* H);
        void L_BL(); 
        void CreatLay(FSNode* L, int layer, int num);
        void T_BL(FSNode* T);
        void NodeFound(FSNode* F, ElemenType n);                        //找到改造后的二叉树中的元素
        void NodeFoundF(FSNode* F, ElemenType n, ElemenType m);
        void Mchild(FSNode* F, ElemenType m);
        void MaxH(FSNode* L, int layer);
        void RenewTree(FSNode* T);
        void CouNode(FSNode* T);
        void CouLeaves(FSNode* T);
        void Getdegree(FSNode* T, int layer, int dg);
        void HHTri(FSNode* H, int h);
        void GYB(FSNode* H);

        //题目用函数
        void choose();
        void no0();
        void no1();
        void no2();
        void no3();
        void no4();
        void no5();
        void no6();
        void no7();

private:
        FSNode* Tdata;
};

TForest.cpp:
#include "TForest.h"

ElemenType Laysort2[10][10];
int Layer = 0;
int MaxHeight = 0, degree = 0;
int num = 0;
bool flag = false;
int nNode = 0;
int nLeaves = 0;

TForest::~TForest()
{

}

TForest::TForest()//要完成"读树"以及"转化"成二叉树
{
        Tdata = new FSNode;
        Tdata->data = NULL;
}

void TForest::H_BL(FSNode* H)
{
        cout << H->data << " ";
        if (H->firstchild != NULL)
        {
                H_BL(H->firstchild);
        }
        if (H->nextsibling != NULL)
        {
                H_BL(H->nextsibling);
        }
}

void TForest::L_BL()//记得输入当前的层数,以及最大的层数;完成之后需要重置层数和最大的层数
{                
        int h = 0;
        int n = 0;
        while (h < MaxHeight)
        {
                //if(Laysort2[h][n]!='#')
                cout << Laysort2[h][n]<<" ";
                n++;
                if (Laysort2[h][n] == NULL)
                {
                        n = 0;
                        h++;
                }
                if (Laysort2[h][0] == NULL)
                {
                        break;
                }
        }
}

void TForest::CreatLay(FSNode* L, int layer, int num)//记得输入当前的层数,以及最大的层数;完成之后需要重置层数和最大的层数
{
        while (Laysort2[layer][num] != NULL)
        {
                num+=1;
        }

        Laysort2[layer][num] = L->data;

        if (L->nextsibling != NULL)
        {
                CreatLay(L->nextsibling, layer, num + 1);
        }
        if (L->firstchild != NULL)
        {
                CreatLay(L->firstchild, layer + 1, 0);
        }
}

void TForest::MaxH(FSNode* L, int layer)//读得最大的深度,然后用于创建存储每一层节点的数组
{
        if (L->nextsibling != NULL)
        {
                MaxH(L->nextsibling, layer);
        }
        if (L->firstchild != NULL)
        {
                MaxH(L->firstchild, layer + 1);
        }
        if (layer > MaxHeight)
        {
                MaxHeight = layer;
        }
}


void TForest::T_BL(FSNode* T)
{
        if (T->firstchild != NULL)
        {
                T_BL(T->firstchild);
        }
        if (T->nextsibling != NULL)
        {
                T_BL(T->nextsibling);
        }
        cout << T->data << " ";
}

void TForest::NodeFound(FSNode* F, ElemenType n)
{
        if (F->firstchild != NULL)
        {
                NodeFound(F->firstchild, n);
        }
        if (F->nextsibling != NULL)
        {
                NodeFound(F->nextsibling, n);
        }
        if (F->data == n)
        {
                flag = true;
                return;
        }

}

void TForest::NodeFoundF(FSNode* F, ElemenType n, ElemenType m)
{
                if (F->firstchild != NULL)
                {
                        NodeFoundF(F->firstchild, n, m);
                }
                if (F->nextsibling != NULL)
                {
                        NodeFoundF(F->nextsibling, n, m);
                }
                if (F->data == n)
                {
                        if (F->firstchild == NULL)
                        {
                                F->firstchild = new FSNode;
                                F->firstchild->data = m;
                        }
                        else//反向中序遍历,找到F->firstchild的空的兄弟节点,植入新的子节点
                        {
                                Mchild(F->firstchild, m);
                        }                        
                }

        

}

void TForest::Tree_in()
{
        FSNode* c = NULL;
        int i = 0, j = 0;
        char a, b;
        cout << "input the father and son:(enter '#' and '#' to end)" << endl;
        do
        {
                cin >> a;
                cin >> b;
                if (a == '#' || '#' == b)
                        break;
                //此时c没有数据,第一次手动录入
                if (Tdata->data == NULL)
                {
                        Tdata->data = a;
                        c = Tdata;
                }        
                //第一步查找父节点a是否存在,若存在则将b加入到左子树根节点的右节点最右方(如果有的话)
                //若不存在,则在当前根的右子树中加入一个a。最后将b加于a左子树根结点处
                NodeFound(c, a);
                if (flag)//遍历;查找到a就直接接子节点,并且跳过加载a的环节 
                {
                        NodeFoundF(c, a, b);
                }        
                else
                {//没找到a就加载a,并接入子节点.问题是要是c都没有。。。。
                        Mchild(c, a);
                        NodeFoundF(c, a, b);
                }
                flag = false;
        } while (a != '#' && b != '#');
        //数组创建完成之后直接变化成右兄弟左孩子的二叉树
}

void TForest::Mchild(FSNode* F, ElemenType m)
{
        if (F->nextsibling != NULL)
        {
                Mchild(F->nextsibling, m);                        
        }
        if (F->nextsibling == NULL)
        {
                F->nextsibling = new FSNode;
                F->nextsibling->data = m;
                return;
        }
}

void TForest::RenewTree(FSNode* T)
{
        if (T->firstchild != NULL)
        {
                RenewTree(T->firstchild);
        }
        if (T->nextsibling != NULL)
        {
                RenewTree(T->nextsibling);
        }
        delete T;
        T = NULL;
}

void TForest::CouNode(FSNode* T)
{
        if (T->firstchild != NULL)
        {
                CouNode(T->firstchild);
        }
        if (T->nextsibling != NULL)
        {
                CouNode(T->nextsibling);
        }
        if (T->data != NULL)
        {
                nNode++;
        }
}

void TForest::CouLeaves(FSNode* T)
{
        if (T->firstchild != NULL)
        {
                CouLeaves(T->firstchild);
        }
        if (T->nextsibling != NULL)
        {
                CouLeaves(T->nextsibling);
        }
        if (T->firstchild == NULL)
        {
                nLeaves++;
        }
}

void TForest::Getdegree(FSNode* T,int layer,int dg)
{
        if (T->firstchild != NULL)
        {
                Getdegree(T->firstchild, layer + 1, 0);
        }
        if (T->nextsibling != NULL && layer != 0)
        {
                Getdegree(T->nextsibling, layer, dg + 1);//
        }
        else if (T->nextsibling != NULL && layer == 0)
        {
                Getdegree(T->nextsibling, layer, 0);
        }
        if (T->nextsibling == NULL)
        {
                dg++;
        }        
        if (dg>degree)
        {
                degree=dg;
        }
}

void TForest::HHTri(FSNode* H,int h)
{
        cout <<" ( "<< H->data <<","<<h<<" ) ";
        if (H->firstchild != NULL)
        {
                HHTri(H->firstchild,h+1);
        }
        if (H->nextsibling != NULL)
        {
                HHTri(H->nextsibling,h);
        }
}

void TForest::GYB(FSNode* H)
{
        cout << H->data ;
        if (H->firstchild != NULL)
        {
                cout << "(";
                GYB(H->firstchild);
                cout << ")";
        }
        if (H->nextsibling != NULL)
        {
                cout << ",";
                GYB(H->nextsibling);
        }
}

/***********************************************************************************************************/


void TForest::choose()
{
        int aa;
label1:        cout << "Please choose the issue you want to solve:(enter -1 to exit)" << endl;
        cin >> aa;
        switch (aa)
        {
        case 0:
                no0();
                break;
        case 1:
                no1();
                break;
        case 2:
                no2();
                break;
        case 3:
                no3();
                break;
        case 4:
                no4();
                break;
        case 5:
                no5();
                break;
        case 6:
                no6();
                break;
        case 7:
                no7();
                break;
        case -1:
                return;
        default:
                cout << "Wrong number!\n" << "Please choose again!" << endl;        
                break;
        }
        goto label1;
}

void TForest::no1()
{
        MaxHeight = 0;
        cout << "前序遍历:" << endl;
        H_BL(Tdata);
        cout << "\n" << "层序遍历:" << endl;
        Layer = 1;
        MaxH(Tdata, Layer);
        Layer = 0;
        CreatLay(Tdata, Layer, 0);
        L_BL();
        cout << "\n" << "后序遍历:" << endl;
        T_BL(Tdata);
        cout << endl;
}

void TForest::no2()
{
        MaxHeight = 0;
        Layer = 1;
        MaxH(Tdata, Layer);
        cout << "H: " << MaxHeight << " \n";
}

void TForest::no3()
{
        nNode = 0;
        CouNode(Tdata);
        cout << "The number of node: " << nNode << endl;
}

void TForest::no4()
{
        nLeaves = 0;
        CouLeaves(Tdata);
        cout << "The number of leaves: " << nLeaves << endl;
}

void TForest::no5()
{
        degree = 0;
        Getdegree(Tdata, 0, 0);
        cout << "Degree: " << degree << endl;
}

void TForest::no6()
{
        cout << "前序遍历以及对应高度:" << endl;
        HHTri(Tdata, 1);
        cout << endl;
}

void TForest::no7()
{
        cout << "广义表:" << endl;
        GYB(Tdata);
        cout << endl;
}

void TForest::no0()//有BUG,最后来实现
{
        RenewTree(Tdata);
        Tdata->data = NULL;
        Tdata->firstchild = NULL;
        Tdata->nextsibling = NULL;
        Tree_in();
}

main.cpp:
#include <iostream>
#include"TForest.h"

using namespace std;

int main()
{
        TForest a;
        a.Tree_in();
        a.choose();
        std::cout << "Hello World!\n";
}

用的是VS2019编译
输入内容:
A B
A C
A D
B E
B F
C G
D H
D I
D J
E K
# #
1
-1

大佬看一看附件就好啦
最佳答案
2019-12-11 13:01:30
qq: 1440332527

测试用的数据

测试用的数据

新建文件夹.zip

46.48 KB, 下载次数: 0

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-12-9 12:56:04 | 显示全部楼层
我也不知道为什么数据会被无故覆盖掉,因为我看不到你的电脑屏幕,看不到你编辑器中的代码,看不到你输入了什么,看不到哪一个数据被覆盖了,我也不知道这个程序是做什么的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-12-10 16:44:46 | 显示全部楼层
本帖最后由 MFwxy 于 2019-12-10 16:49 编辑
人造人 发表于 2019-12-9 12:56
我也不知道为什么数据会被无故覆盖掉,因为我看不到你的电脑屏幕,看不到你编辑器中的代码,看不到你输入了 ...


着实欠缺考虑,抱歉抱歉。
数据录入的问题已经解决了,现在正在着手遍历时有数据没有被遍历到的问题。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-12-11 07:18:43 | 显示全部楼层
人造人 发表于 2019-12-9 12:56
我也不知道为什么数据会被无故覆盖掉,因为我看不到你的电脑屏幕,看不到你编辑器中的代码,看不到你输入了 ...

不好意思,,,下次我先想个一两天,再试个一两天。再问问题。基本自己解决了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-12-11 07:20:11 | 显示全部楼层
人造人 发表于 2019-12-9 12:56
我也不知道为什么数据会被无故覆盖掉,因为我看不到你的电脑屏幕,看不到你编辑器中的代码,看不到你输入了 ...

其中有个数组访问的问题,想请教一下大佬
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-12-11 13:01:30 | 显示全部楼层    本楼为最佳答案   
qq: 1440332527
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-23 05:42

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表