设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › 数据结构与算法 › 数据结构有关的问题--森林.(数组访问还有一些问题)
返回列表 发新帖
查看: 2362|回复: 5

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

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

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

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

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

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

森林的层序遍历，
TForst.h:
  1. #pragma once
  2. #include<iostream>
  3. #define maxn 100
  4. #define ElemenType char

  6. using namespace std;

  8. struct FSNode
  9. {
  10.         ElemenType data = NULL;
  11.         FSNode* firstchild = NULL;
  12.         FSNode* nextsibling = NULL;
  13. };


  16. class TForest
  17. {
  18. public:
  19.         TForest();
  20.         virtual ~TForest();
  21.         //输入数据
  22.         void Tree_in();
  23.         //各种遍历
  24.         void H_BL(FSNode* H);
  25.         void L_BL();
  26.         void CreatLay(FSNode* L, int layer, int num);
  27.         void T_BL(FSNode* T);
  28.         void NodeFound(FSNode* F, ElemenType n);                        //找到改造后的二叉树中的元素
  29.         void NodeFoundF(FSNode* F, ElemenType n, ElemenType m);
  30.         void Mchild(FSNode* F, ElemenType m);
  31.         void MaxH(FSNode* L, int layer);
  32.         void RenewTree(FSNode* T);
  33.         void CouNode(FSNode* T);
  34.         void CouLeaves(FSNode* T);
  35.         void Getdegree(FSNode* T, int layer, int dg);
  36.         void HHTri(FSNode* H, int h);
  37.         void GYB(FSNode* H);

  39.         //题目用函数
  40.         void choose();
  41.         void no0();
  42.         void no1();
  43.         void no2();
  44.         void no3();
  45.         void no4();
  46.         void no5();
  47.         void no6();
  48.         void no7();

  50. private:
  51.         FSNode* Tdata;
  52. };
复制代码


TForest.cpp:
  1. #include "TForest.h"

  3. ElemenType Laysort2[10][10];
  4. int Layer = 0;
  5. int MaxHeight = 0, degree = 0;
  6. int num = 0;
  7. bool flag = false;
  8. int nNode = 0;
  9. int nLeaves = 0;

  11. TForest::~TForest()
  12. {

  14. }

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

  22. void TForest::H_BL(FSNode* H)
  23. {
  24.         cout << H->data << " ";
  25.         if (H->firstchild != NULL)
  26.         {
  27.                 H_BL(H->firstchild);
  28.         }
  29.         if (H->nextsibling != NULL)
  30.         {
  31.                 H_BL(H->nextsibling);
  32.         }
  33. }

  35. void TForest::L_BL()//记得输入当前的层数，以及最大的层数；完成之后需要重置层数和最大的层数
  36. {               
  37.         int h = 0;
  38.         int n = 0;
  39.         while (h < MaxHeight)
  40.         {
  41.                 //if(Laysort2[h][n]!='#')
  42.                 cout << Laysort2[h][n]<<" ";
  43.                 n++;
  44.                 if (Laysort2[h][n] == NULL)
  45.                 {
  46.                         n = 0;
  47.                         h++;
  48.                 }
  49.                 if (Laysort2[h][0] == NULL)
  50.                 {
  51.                         break;
  52.                 }
  53.         }
  54. }

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

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

  65.         if (L->nextsibling != NULL)
  66.         {
  67.                 CreatLay(L->nextsibling, layer, num + 1);
  68.         }
  69.         if (L->firstchild != NULL)
  70.         {
  71.                 CreatLay(L->firstchild, layer + 1, 0);
  72.         }
  73. }

  75. void TForest::MaxH(FSNode* L, int layer)//读得最大的深度，然后用于创建存储每一层节点的数组
  76. {
  77.         if (L->nextsibling != NULL)
  78.         {
  79.                 MaxH(L->nextsibling, layer);
  80.         }
  81.         if (L->firstchild != NULL)
  82.         {
  83.                 MaxH(L->firstchild, layer + 1);
  84.         }
  85.         if (layer > MaxHeight)
  86.         {
  87.                 MaxHeight = layer;
  88.         }
  89. }


  92. void TForest::T_BL(FSNode* T)
  93. {
  94.         if (T->firstchild != NULL)
  95.         {
  96.                 T_BL(T->firstchild);
  97.         }
  98.         if (T->nextsibling != NULL)
  99.         {
  100.                 T_BL(T->nextsibling);
  101.         }
  102.         cout << T->data << " ";
  103. }

  105. void TForest::NodeFound(FSNode* F, ElemenType n)
  106. {
  107.         if (F->firstchild != NULL)
  108.         {
  109.                 NodeFound(F->firstchild, n);
  110.         }
  111.         if (F->nextsibling != NULL)
  112.         {
  113.                 NodeFound(F->nextsibling, n);
  114.         }
  115.         if (F->data == n)
  116.         {
  117.                 flag = true;
  118.                 return;
  119.         }

  121. }

  123. void TForest::NodeFoundF(FSNode* F, ElemenType n, ElemenType m)
  124. {
  125.                 if (F->firstchild != NULL)
  126.                 {
  127.                         NodeFoundF(F->firstchild, n, m);
  128.                 }
  129.                 if (F->nextsibling != NULL)
  130.                 {
  131.                         NodeFoundF(F->nextsibling, n, m);
  132.                 }
  133.                 if (F->data == n)
  134.                 {
  135.                         if (F->firstchild == NULL)
  136.                         {
  137.                                 F->firstchild = new FSNode;
  138.                                 F->firstchild->data = m;
  139.                         }
  140.                         else//反向中序遍历，找到F->firstchild的空的兄弟节点，植入新的子节点
  141.                         {
  142.                                 Mchild(F->firstchild, m);
  143.                         }                       
  144.                 }

  146.        

  148. }

  150. void TForest::Tree_in()
  151. {
  152.         FSNode* c = NULL;
  153.         int i = 0, j = 0;
  154.         char a, b;
  155.         cout << "input the father and son:(enter '#' and '#' to end)" << endl;
  156.         do
  157.         {
  158.                 cin >> a;
  159.                 cin >> b;
  160.                 if (a == '#' || '#' == b)
  161.                         break;
  162.                 //此时c没有数据，第一次手动录入
  163.                 if (Tdata->data == NULL)
  164.                 {
  165.                         Tdata->data = a;
  166.                         c = Tdata;
  167.                 }       
  168.                 //第一步查找父节点a是否存在，若存在则将b加入到左子树根节点的右节点最右方（如果有的话）
  169.                 //若不存在,则在当前根的右子树中加入一个a。最后将b加于a左子树根结点处
  170.                 NodeFound(c, a);
  171.                 if (flag)//遍历；查找到a就直接接子节点，并且跳过加载a的环节
  172.                 {
  173.                         NodeFoundF(c, a, b);
  174.                 }       
  175.                 else
  176.                 {//没找到a就加载a，并接入子节点.问题是要是c都没有。。。。
  177.                         Mchild(c, a);
  178.                         NodeFoundF(c, a, b);
  179.                 }
  180.                 flag = false;
  181.         } while (a != '#' && b != '#');
  182.         //数组创建完成之后直接变化成右兄弟左孩子的二叉树
  183. }

  185. void TForest::Mchild(FSNode* F, ElemenType m)
  186. {
  187.         if (F->nextsibling != NULL)
  188.         {
  189.                 Mchild(F->nextsibling, m);                       
  190.         }
  191.         if (F->nextsibling == NULL)
  192.         {
  193.                 F->nextsibling = new FSNode;
  194.                 F->nextsibling->data = m;
  195.                 return;
  196.         }
  197. }

  199. void TForest::RenewTree(FSNode* T)
  200. {
  201.         if (T->firstchild != NULL)
  202.         {
  203.                 RenewTree(T->firstchild);
  204.         }
  205.         if (T->nextsibling != NULL)
  206.         {
  207.                 RenewTree(T->nextsibling);
  208.         }
  209.         delete T;
  210.         T = NULL;
  211. }

  213. void TForest::CouNode(FSNode* T)
  214. {
  215.         if (T->firstchild != NULL)
  216.         {
  217.                 CouNode(T->firstchild);
  218.         }
  219.         if (T->nextsibling != NULL)
  220.         {
  221.                 CouNode(T->nextsibling);
  222.         }
  223.         if (T->data != NULL)
  224.         {
  225.                 nNode++;
  226.         }
  227. }

  229. void TForest::CouLeaves(FSNode* T)
  230. {
  231.         if (T->firstchild != NULL)
  232.         {
  233.                 CouLeaves(T->firstchild);
  234.         }
  235.         if (T->nextsibling != NULL)
  236.         {
  237.                 CouLeaves(T->nextsibling);
  238.         }
  239.         if (T->firstchild == NULL)
  240.         {
  241.                 nLeaves++;
  242.         }
  243. }

  245. void TForest::Getdegree(FSNode* T,int layer,int dg)
  246. {
  247.         if (T->firstchild != NULL)
  248.         {
  249.                 Getdegree(T->firstchild, layer + 1, 0);
  250.         }
  251.         if (T->nextsibling != NULL && layer != 0)
  252.         {
  253.                 Getdegree(T->nextsibling, layer, dg + 1);//
  254.         }
  255.         else if (T->nextsibling != NULL && layer == 0)
  256.         {
  257.                 Getdegree(T->nextsibling, layer, 0);
  258.         }
  259.         if (T->nextsibling == NULL)
  260.         {
  261.                 dg++;
  262.         }       
  263.         if (dg>degree)
  264.         {
  265.                 degree=dg;
  266.         }
  267. }

  269. void TForest::HHTri(FSNode* H,int h)
  270. {
  271.         cout <<" ( "<< H->data <<","<<h<<" ) ";
  272.         if (H->firstchild != NULL)
  273.         {
  274.                 HHTri(H->firstchild,h+1);
  275.         }
  276.         if (H->nextsibling != NULL)
  277.         {
  278.                 HHTri(H->nextsibling,h);
  279.         }
  280. }

  282. void TForest::GYB(FSNode* H)
  283. {
  284.         cout << H->data ;
  285.         if (H->firstchild != NULL)
  286.         {
  287.                 cout << "(";
  288.                 GYB(H->firstchild);
  289.                 cout << ")";
  290.         }
  291.         if (H->nextsibling != NULL)
  292.         {
  293.                 cout << ",";
  294.                 GYB(H->nextsibling);
  295.         }
  296. }

  298. /***********************************************************************************************************/


  301. void TForest::choose()
  302. {
  303.         int aa;
  304. label1:        cout << "Please choose the issue you want to solve:(enter -1 to exit)" << endl;
  305.         cin >> aa;
  306.         switch (aa)
  307.         {
  308.         case 0:
  309.                 no0();
  310.                 break;
  311.         case 1:
  312.                 no1();
  313.                 break;
  314.         case 2:
  315.                 no2();
  316.                 break;
  317.         case 3:
  318.                 no3();
  319.                 break;
  320.         case 4:
  321.                 no4();
  322.                 break;
  323.         case 5:
  324.                 no5();
  325.                 break;
  326.         case 6:
  327.                 no6();
  328.                 break;
  329.         case 7:
  330.                 no7();
  331.                 break;
  332.         case -1:
  333.                 return;
  334.         default:
  335.                 cout << "Wrong number!\n" << "Please choose again!" << endl;       
  336.                 break;
  337.         }
  338.         goto label1;
  339. }

  341. void TForest::no1()
  342. {
  343.         MaxHeight = 0;
  344.         cout << "前序遍历：" << endl;
  345.         H_BL(Tdata);
  346.         cout << "\n" << "层序遍历：" << endl;
  347.         Layer = 1;
  348.         MaxH(Tdata, Layer);
  349.         Layer = 0;
  350.         CreatLay(Tdata, Layer, 0);
  351.         L_BL();
  352.         cout << "\n" << "后序遍历：" << endl;
  353.         T_BL(Tdata);
  354.         cout << endl;
  355. }

  357. void TForest::no2()
  358. {
  359.         MaxHeight = 0;
  360.         Layer = 1;
  361.         MaxH(Tdata, Layer);
  362.         cout << "H: " << MaxHeight << " \n";
  363. }

  365. void TForest::no3()
  366. {
  367.         nNode = 0;
  368.         CouNode(Tdata);
  369.         cout << "The number of node: " << nNode << endl;
  370. }

  372. void TForest::no4()
  373. {
  374.         nLeaves = 0;
  375.         CouLeaves(Tdata);
  376.         cout << "The number of leaves: " << nLeaves << endl;
  377. }

  379. void TForest::no5()
  380. {
  381.         degree = 0;
  382.         Getdegree(Tdata, 0, 0);
  383.         cout << "Degree: " << degree << endl;
  384. }

  386. void TForest::no6()
  387. {
  388.         cout << "前序遍历以及对应高度：" << endl;
  389.         HHTri(Tdata, 1);
  390.         cout << endl;
  391. }

  393. void TForest::no7()
  394. {
  395.         cout << "广义表：" << endl;
  396.         GYB(Tdata);
  397.         cout << endl;
  398. }

  400. void TForest::no0()//有BUG,最后来实现
  401. {
  402.         RenewTree(Tdata);
  403.         Tdata->data = NULL;
  404.         Tdata->firstchild = NULL;
  405.         Tdata->nextsibling = NULL;
  406.         Tree_in();
  407. }
复制代码


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

  4. using namespace std;

  6. int main()
  7. {
  8.         TForest a;
  9.         a.Tree_in();
  10.         a.choose();
  11.         std::cout << "Hello World!\n";
  12. }
复制代码


用的是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
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

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

使用道具 举报

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


着实欠缺考虑，抱歉抱歉。
数据录入的问题已经解决了，现在正在着手遍历时有数据没有被遍历到的问题。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

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

不好意思，，，下次我先想个一两天，再试个一两天。再问问题。基本自己解决了。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

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

其中有个数组访问的问题，想请教一下大佬
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2019-12-11 13:01:30 | 显示全部楼层    本楼为最佳答案   
qq: 1440332527
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2025-5-13 14:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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