对当前节点应用修改，使树水平生长 [英] Make a tree grow horizontally applying modifications to current node

问题描述

给定一个输入，我正在尝试构建一棵树，该树应该水平生长，将转换应用于该输入和随后的子节点.

Given an input, I am trying to build a tree which should grow horizontally applying transformations to that input and the consequent children.

例如，给定输入'aab'和两个转换规则，如:

For example, given the input 'aab' and two transformation rules like:

ab -> bba
b -> ba

需要构建这样的树:

我已经编写了代码，但是按照我的方式，我的树是垂直工作的，我不想要那样.我需要它水平工作，但我看不到在哪里/如何编写递归.这是我现在所拥有的:

I have written the code, but the way I have done it, my tree works vertically, and I don't want that. I need it to work horizontally and I fail to see where/how I would write the recursion. Here is what I have right now:

   #include <string.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct t_string_node {
    struct t_string_node *next;
    char *value;
} string_node;

typedef struct t_transformation_rule {
    struct t_transformation_rule *next;
    char *needle;
    char *replacement;
} transformation_rule;


void findTransformations(char *origin, string_node **transformations, char *needle, char *replacement)
{
    char *str = origin; 

    for (char *p = str; *p != '\0'; p++) {
        if (strncmp(p, needle, strlen(needle)) == 0) {
            char *str_ = malloc(strlen(str)+1+strlen(replacement)-strlen(needle));
            strcpy(str_, str);
            char *p_ = p - str + str_;
            memmove(p_+strlen(replacement), p_+strlen(needle), strlen(p_)+1-strlen(replacement));
            memcpy(p_, replacement, strlen(replacement));
            //Create new string node.
            string_node *transformation; 
            transformation = malloc(sizeof(string_node));
            transformation->value = str_;
            transformation->next = NULL;

            while (*transformations != NULL) {
                transformations = &(*transformations)->next;
            }
            *transformations = transformation;
        }
    }
}

int hasTransformation(char *origin, char *target, transformation_rule *list_of_rules)
{
    int level;
    level = 0;
    int found;

    string_node *current;
    current = malloc(sizeof(string_node));
    current->value = origin;
    current->next = NULL;

    if(list_of_rules == NULL) {
        if (strcmp(origin, target) == 0) {
            printf("Solution in 0 steps");
            return 1;
        } else {
            printf("No solution");
            return 0;
        }
    }

    string_node *transformations;
    transformations = NULL;

    while (current != NULL) {
      findTransformations(current->value, target, &transformations, list_of_rules->needle, list_of_rules->replacement);
      findTransformations(current->value, &transformations, list_of_rules->next->needle, list_of_rules->next->replacement);
      current = current->next;
    }

    while (transformations != NULL) {
        printf("%s \n", transformations->value);
        transformations = transformations->next;
    }

    return 1;
}

void main()
{
  char *input = "aab";
  char *target = "bababab";
  char *needle = "ab";
  char *replacement = "bba";

  transformation_rule *list_of_rules;
  list_of_rules = NULL;
  list_of_rules = malloc(sizeof(transformation_rule));

  list_of_rules->needle = "ab";
  list_of_rules->replacement = "bba";
  list_of_rules->next = NULL;

  //Create another rule
  transformation_rule *new_rule;
  new_rule = malloc(sizeof(transformation_rule));
  new_rule->needle = "b";
  new_rule->replacement = "ba";
  new_rule->next = NULL;
  list_of_rules->next = new_rule;

  int has_trans;

  has_trans = hasTransformation(input, target, list_of_rules);
}

任何人都可以帮助我意识到我将如何做到这一点，使树水平而不是垂直生长?

Anybody could help me to realize how would I do this so that the tree grows horizontally instead of vertically?

谢谢

推荐答案

@All: 这个问题是 这个问题(即使使用我制作的图片).

@All: This question is a continuation on THIS question (even using the picture i made).

现在是深度优先与广度优先问题的答案:为此，您根本不应该构建树数据结构.您只需要关心当前层和下一层.

Now the answer to the depth-first vs breadth-first issue: To to this you should not build a tree-datastructure at all. All you have to care about is the current layer and the next layer.

因此，您只需为每个列表创建一个列表.一开始，您将开始字符串放在 current 中，而 next 为空.然后你会看到你可以派生 abba 和 aaba 所以你把它们放到 next 中.然后你清除current并将next的所有内容放入current，然后清除next.

So you just create one list for each. In the beginning you put your start-string in the current and your next is empty. You then see that you can derive abba and aaba so you put them into next. Then you clear current and put everything from next into current and then clear next.

您不断重复此操作，直到您注意到将目标字符串添加到下一个，然后您可以停止搜索.

You keep repeating this until you notice that you are adding your target string to next then you can stop searching.

和:正如我在上面引用的答案中所说:这可能不会终止并且无法确定它是否最终会终止(停止问题)，但是有许多启发式方法可以检测到特定案例.

And: As i said in the answer referenced above: This may not terminate and is indecidable whether it will eventually terminate (Halting-problem), BUT there are many heuristics to detect non-termination in specific cases.

编辑:好的，这是代码！

#include "stdlib.h"
#include "stdio.h"
#include "string.h"
struct list_s {
    struct list_s* next;
    char* entry;
};
char* paste(char* begin, int len1, char* mid, int len2, char* end, int len3) {
    char* a = malloc(len1+len2+len3+1);
    memcpy(a, begin, len1);
    memcpy(a+len1, mid, len2);
    memcpy(a+len1+len2, end, len3);
    a[len1+len2+len3] = '\0';
    return a;
}
void push(struct list_s** top, char* p) {
    struct list_s* l = malloc(sizeof(struct list_s));
    l->next = *top;
    l->entry = p;
    *top = l;
}
char* pop(struct list_s** top) {
    char* res = (*top)->entry;
    struct list_s* next = (*top)->next;
    free(*top);
    *top = next;
    return res;
}
int main() {
    char* input = "aab";
    // char* target = "bbabaa"; // 11th try
    char* target = "abbaa";     // 5th try
    // char* target = "bababab";// has no solution
    #define cRules 2
    char* from[cRules] = {"ab", "b"}; // ab->bba and b->ba
    char* to[cRules] = {"bba", "ba"};
    struct list_s* current = 0;
    struct list_s* nextLayer = 0;
    char* inputAlloc = malloc(strlen(input));
    strcpy(inputAlloc, input);
    push(&current, inputAlloc);
    int counter = 0;
    while(current) { // = while not empty
        char* cur = pop(&current);
        int lenCur = strlen(cur);
        printf("%s:\n", cur);
        int iRule=0; for(; iRule<cRules; ++iRule) { // for each rule
            char* pos = cur;
            for(;;) { // apply the rule wherever it fits
                pos = strstr(pos, from[iRule]);
                if(!pos) break;
                char* mod = paste(
                    cur, pos-cur, 
                    to[iRule], strlen(to[iRule]), 
                    pos+strlen(from[iRule]), 
                    cur+lenCur-(pos+strlen(from[iRule])) );
                printf("->%s\n", mod);
                if(!strcmp(mod, target)) {
                    printf("DONE\n");
                    return 0;
                }
                push(&nextLayer, mod);
                ++pos;
            }
        }
        free(cur);
        if(!current) { // next round!
            current = nextLayer;
            nextLayer = 0;
        }
        ++counter;
        // here you can add some of the fail-conditions we talked about
        if(counter==100) {
            printf("heuristic: no solution\n");
            return 0;
        }
    }
    return 0;
}

这篇关于对当前节点应用修改，使树水平生长的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！