Блог

Главная - Вопросы по программированию - Самореферентная структура в K

Самореферентная структура в K

#c #kernighan-and-ritchie

#c #керниган и Ричи

Вопрос:

K amp; R (2-й) раздел 6.5 имеет две функции.

 int main(void)
{
  struct tnode *root;
  char word[MAXWORD];

  root = NULL;
  while (getword(word, MAXWORD) != EOF)    
    if (isalpha(word[0]))                 
      root = addtree(root, word);         
  treeprint(root);
  return 0;
}

struct tnode *addtree(struct tnode *p, char *w)
{
  int cond;

  if (p == NULL)               // a new word has arrived
    {                            
      p = talloc();            // make a new node 
      p->word = strdup(w);       
      p->count = 1;
      p->left = p->right = NULL;
    }
  else if ((cond = strcmp(w, p->word)) == 0)
    p->count  ;               // repeated word
  else if (cond < 0)
    p->left = addtree(p->left, w);
  else
    p->right = addtree(p->right, w);
  return p;
}

У меня не было проблем с пониманием потока этой программы.
Но я думаю root = addtree(root, word); main , что это неэффективно. root сначала устанавливается NULL и получает адрес, когда найден соответствующий идентификатор. И как только у него есть свой адрес, дополнительное назначение бесполезно. Я прав?
Если это так, я написал свою собственную версию, чтобы избежать этого. Может ли это решить проблему?

 /* my edit */
int main(void)
{
    struct tnode *root;
    char word[MAXWORD];

    root = NULL;
    while (getword(word, MAXWORD) != EOF)   // ----------------------------------
        if (isalpha(word[0])) {             // |                                |
            root = addtree(root, word);     // |                                |
            break;                          // |          Changed part          |
    }                                       // |                                |
    while (getword(word, MAXWORD) != EOF)   // |                                |
        if (isalpha(word[0]))               // |                                |
            addtree(root, word);            // ----------------------------------
    treeprint(root);
    return 0;
}

Комментарии:

1. Это не бесполезно, потому что вызываемая функция может назначить новый указатель на узел дереву. Первый вызов является частным случаем общего случая, когда NULL может быть назначен указатель на значение узла. Предлагаемый вами код выглядит менее эффективным, чем исходный.

2. Но она рекурсивна: она вызывает саму себя. Более продвинутые реализации дерева будут поддерживать сбалансированность дерева, что может означать изменение корня.

3. Ваш код не сможет присвоить значение root , когда if (isalpha(word[0])) оно равно false .

4. В любом случае, первое while бесполезно, поскольку break предотвращает повторение цикла.

5. Вы должны сбалансировать возможную небольшую неэффективность присвоения значения переменной, которая уже имеет это значение, со сложностью и удобочитаемостью кода. С этой точки зрения предложенное вами изменение было менее эффективным, особенно потому, что оно привело к ошибке. Так что нет, я не думаю, что ваше изменение было к лучшему.