论坛 › 数据结构与算法 › 数据结构有关的问题--森林.(数组访问还有一些问题)

MFwxy 发表于 2019-12-9 10:47:36

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

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

大问题已经解决了，大佬看一看附件就好啦
数组访问的明明应该为NULL，但实际上却是的'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;
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!='#')
                cout << Laysort2<<" ";
                n++;
                if (Laysort2 == NULL)
                {
                        n = 0;
                        h++;
                }
                if (Laysort2 == NULL)
                {
                        break;
                }
        }
}

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

        Laysort2 = 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-9 12:56:04

我也不知道为什么数据会被无故覆盖掉，因为我看不到你的电脑屏幕，看不到你编辑器中的代码，看不到你输入了什么，看不到哪一个数据被覆盖了，我也不知道这个程序是做什么的

MFwxy 发表于 2019-12-10 16:44:46

本帖最后由 MFwxy 于 2019-12-10 16:49 编辑

人造人 发表于 2019-12-9 12:56
我也不知道为什么数据会被无故覆盖掉，因为我看不到你的电脑屏幕，看不到你编辑器中的代码，看不到你输入了 ...

着实欠缺考虑，抱歉抱歉。
数据录入的问题已经解决了，现在正在着手遍历时有数据没有被遍历到的问题。

MFwxy 发表于 2019-12-11 07:18:43

人造人 发表于 2019-12-9 12:56
我也不知道为什么数据会被无故覆盖掉，因为我看不到你的电脑屏幕，看不到你编辑器中的代码，看不到你输入了 ...

不好意思，，，下次我先想个一两天，再试个一两天。再问问题。基本自己解决了。

MFwxy 发表于 2019-12-11 07:20:11

人造人 发表于 2019-12-9 12:56
我也不知道为什么数据会被无故覆盖掉，因为我看不到你的电脑屏幕，看不到你编辑器中的代码，看不到你输入了 ...

其中有个数组访问的问题，想请教一下大佬

人造人 发表于 2019-12-11 13:01:30

qq: 1440332527

查看完整版本: 数据结构有关的问题--森林.(数组访问还有一些问题)