1

给定一个输入，我正在尝试构建一个应该水平生长的树，将转换应用于该输入和随之而来的孩子。

例如，给定输入“aab”和两个转换规则，例如：

ab -> bba
b -> ba

需要构建这样的树：

在此处输入图像描述

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

   #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);
}

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

谢谢

4

1 回答 1

1

@All：这个问题是这个问题的延续（即使使用我制作的图片）。

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

因此，您只需为每个创建一个列表。一开始，您将起始字符串放在当前字符串中，而下一个字符串为空。然后你看到你可以推导abba，aaba所以你把它们放到下一个。然后你清除 current并将所有内容从next放入current然后 clear next。

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

并且：正如我在上面引用的答案中所说：这可能不会终止并且无法确定它是否最终会终止（Halting-problem），但是在特定情况下有许多启发式方法来检测非终止。

编辑：好的，这是代码！

#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;
}
于 2013-02-24T11:03:37.290 回答