1. 软市首页
  2. 行业观察

极光 · 哈夫曼树の生成（线段树结构 非指针）（仿邻接表）

• 行业观察

ASRC-极光科研中心  哈夫曼编码 – 非指针实现

思想参考AcWing图论中，对于【邻接表】的运用
因为【结构体优先队列】似乎无法对【node*】的排序
暂时无法突破这个技术难点，只能退而求其次
不过调整后的实际运用效果还是不错的
2022-06-22  鸿蒙纪元·乾坤 Day294

这里就是LR改成int，用idx作为指针
优势在于规避了 node *l,*r 的出现，可以实现同样效果
缺点在于需要预定义内存，不能实现动态内存和释放
从我实践的角度出发，算法竞赛中是以实现为目的

不要太追求这种细枝末节
以后的工程实践过程中再考虑这种产品优化的问题吧

详细思想的介绍：算法设计与分析2022 · 云端实验库_影月丶暮风的博客-CSDN博客

结果展示

结点读入后，优先队列内存储的信息

测试数据

数据部署模块

        这里idx是模范邻接表的书写（AcWing），规避了node *l,*r 的书写
采用后者书写将无法使用结构体优先队列（科研部前期研究产物）

极光 · STL库测试 · priority_Queue与Struct_影月丶暮风的博客-CSDN博客

        另外，wlr三数组是共享一个idx下标的；idx总是指向新节点即将存储的位置

        wlr三剑客，是实际结点的存储位置，node结构只在哈弗曼树生成初期参与

        WLR三剑客生成完成后，弃用node和优先队列（呜呜好可怜）

我们通过结构体优先队列，生成【node辅助接点】

        codes_idx是看当前生成的path，是哪个【叶子结点】的 【下标idx】

书写优化模块

 调试辅助函数

主战函数

读入模块

 建树过程-利用优先队列

 我说的【结点虚空层面】就是在优先队列里边的node，因为弹出读取之后就弃用了
实际上我们最后生成的哈夫曼树的结点是存在【WLR三剑客】顺序表中的

        后者被我称作【结点实体层面】

展示哈夫曼编码的俩函数（前者可以调动find函数，将搜索的路径存储为strintg）

 哈夫曼路径生成函数



    

  1. // ASRC-极光科研中心  哈夫曼编码 - 非指针实现
    2. 

  2. // 思想参考AcWing图论中，对于【邻接表】的运用
    3. 

  3. // 因为【结构体优先队列】似乎无法对【node*】的排序
    4. 

  4. // 暂时无法突破这个技术难点，只能退而求其次
    5. 

  5. // 不过调整后的实际运用效果还是不错的
    6. 

  6. //  2022-06-22  鸿蒙纪元·乾坤 Day294
    7. 

  7. // 这里就是LR改成int，用idx作为指针
    8. 

  8. // 优势在于规避了 node *l,*r 的出现，可以实现同样效果
    9. 

  9. // 缺点在于需要预定义内存，不能实现动态内存和释放
    10. 

  10. // 从我实践的角度出发，算法竞赛中是以实现为目的，不要太追求这种细枝末节
    11. 

  11. // 以后的工程实践过程中再考虑这种产品优化的问题吧
    12. 

  12. #include 
    13. 

  13. #include 
    14. 

  14. #include 
    15. 

  15. #include 
    16. 

  16. #include 
    17. 

  17. 
using namespace std;
    18. 

  18. #define top hfm.top()
    19. 

  19. #define pop hfm.pop()
    20. 

  20. #define size hfm.size()
    21. 

  21. #define push(x) hfm.push(x)
    22. 

  22.  
    23. 

  23. //【数据存储模块】
    24. 

  24. 
const int N = 1e5 + 7, T = 2 * N - 1;
    25. 

  25. 
struct node

    26. 

  26. {
    27. 

  27.     int w;   //权重

    28. 

  28.     int idx; //结点name下标，=0时候表示是生成结点

    29. 

  29.     int st;  //实体idx，记录【结点】在【线段表】位置

    30. 

  30.     //【线段表】：wlr三剑客

    31. 

  31. };
    32. 

  32. 
bool operator

    33. 

  33. {
    34. 

  34.     return t1.w > t2.w; //新插入T2更小，意图构造大头

    35. 

  35.     //实际上恰好相反

    36. 

  36. }
    37. 

  37. 
int n;      //【初始结点个数】

    38. 

  38. 
int idx = 1;//【新结点存储位置】仿造邻接表

    39. 

  39. 
int HFM;    //【哈夫曼树根节点idx】

    40. 

  40. 
bool path[N];              //【搜索路径】

    41. 

  41. string codes[N];           //【结点对应的哈夫曼编码】

    42. 

  42. 
int codes_idx;             //【哈夫曼编码追踪标记】：当前捕获的path对应哪个结点

    43. 

  43. 
int l[T], r[T], w[T];      //【左节点idx】【右节点idx】【结点权值】

    44. 

  44. priority_queue hfm;  //【生成树辅助优先队列】，存储结点对应的idx下标和权值，权值小的往前排

    45. 

  45. 
char name[N][27] = {"ASRC-极光科研中心"}; //【结点名称】，

    46. 

  46.  
    47. 

  47. //【测试函数模块】
    48. 

  48. void show_queue()
    49. 

  49. {
    50. 

  50.     puts("nnASRC 队列内容展示n");
    51. 

  51.     int tmp = 0;
    52. 

  52.     while (size)
    53. 

  53.     {
    54. 

  54.         printf("%d：权值：%d", ++tmp, top.w);
    55. 

  55.         printf("t名称：%sn", name[top.idx]), pop;
    56. 

  56.     }
    57. 

  57.     puts("nn");
    58. 

  58. }
    59. 

  59. void show_node()
    60. 

  60. {
    61. 

  61.     puts("nn生成的实体层面 【权值展示】");
    62. 

  62.     for (int i = 1; i 

    63. 

  63.         printf("%d ", w[i]);
    64. 

  64.     puts("nn生成的实体层面 【L展示】");
    65. 

  65.     for (int i = 1; i 

    66. 

  66.         printf("%d ", l[i]);
    67. 

  67.     puts("nn生成的实体层面 【R展示】");
    68. 

  68.     for (int i = 1; i 

    69. 

  69.         printf("%d ", r[i]);
    70. 

  70.     puts("nn");
    71. 

  71. }
    72. 

  72.  
    73. 

  73. //【功能函数模块】
    74. 

  74. void get_in()
    75. 

  75. {
    76. 

  76.     scanf("%d", &n);
    77. 

  77.     for (idx = 1; idx 

    78. 

  78.     { //跳出的时候，idx指向n+1

    79. 

  79.         scanf("%d%s", &w[idx], &name[idx]);
    80. 

  80.         node tmp = {w[idx], idx, idx};
    81. 

  81.         //第一个idx，结点名称位置，也代表是不是合成结点

    82. 

  82.         //第二个idx，作为一个结点，在实体层面的下标（w中的下标）

    83. 

  83.         push(tmp);
    84. 

  84.     }
    85. 

  85. }
    86. 

  86. void c_Tree()
    87. 

  87. {
    88. 

  88.     while (size != 1)
    89. 

  89.     {
    90. 

  90.         node t1, t2, t3;
    91. 

  91.         t1 = top, pop;
    92. 

  92.         t2 = top, pop;
    93. 

  93.         { //新建结点(实体层面)

    94. 

  94.             t3.w = w[idx] = t1.w + t2.w;
    95. 

  95.             t3.idx = 0;  //表示是【合成结点】

    96. 

  96.             t3.st = idx; //实体层面坐标

    97. 

  97.             l[idx] = t1.st;
    98. 

  98.             r[idx] = t2.st;
    99. 

  99.         }
    100. 

  100.         push(t3); //新建结点（虚空层面）

    101. 

  101.         idx++;
    102. 

  102.     }
    103. 

  103.     HFM = top.st;
    104. 

  104. }
    105. 

  105. void find(int way, int step) // destination
    106. 

  106. {
    107. 

  107.     if (way //追踪坐标落到了1~n，说明是叶子结点了
    108. 

  108.     {
    109. 

  109.         if (strcmp(name[codes_idx], name[way]) == 0)
    110. 

  110.         {
    111. 

  111.             printf("找到了啊啊啊woc！ %s Path=", name[codes_idx]);
    112. 

  112. 

                                                        
    声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！
                            
    113.
上一篇 2022年8月21日
下一篇 2022年8月21日

相关推荐

首页
软件超市
企服市场
会员中心