Вопросы Теги

Путь в двоичном дереве

Совместимость с ISO C90 с проверкой типа. (Однако предостережение: две оценки ptr!) [/ ​​G0] 

#define container_of(ptr, type, member) \
   ((type *) ((char *) (ptr) - offsetof(type, member) + \
              (&((type *) 0)->member == (ptr)) * 0))

struct container {
  int dummy;
  int memb;
};


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

int main()
{
  struct container c;
  int *p = &c.memb;
  double *q = (double *) p;
  struct container *pc = container_of(p, struct container, memb);
  struct container *qc = container_of(q, struct container, memb);
  return 0;
}

Тест: 

$ gcc -Wall containerof.c
containerof.c: In function ‘main’:
containerof.c:20:26: warning: comparison of distinct pointer types lacks a cast
containerof.c:20:21: warning: unused variable ‘qc’
containerof.c:19:21: warning: unused variable ‘pc’

Мы получаем предупреждение distinct pointer types для 26, но не 25. Это наша диагностика о неправильном использовании указателей.

Сначала я попытался поставить проверку типа в левую сторону оператора запятой, gcc жалуется на то, что это не имеет никакого эффекта, что является неприятностью. Но, сделав его операндом, мы гарантируем, что он используется.

Трюк &((type *) 0)->member не совсем определен ISO C, но он широко используется для определения offsetof. Если ваш компилятор использует этот трюк с нулевым указателем для offsetof, он почти наверняка будет себя вести в вашем собственном макросе.

0
задан GAD3R 17 January 2019 в 17:41
поделиться

1 ответ

Я начинаю набрасывать какой-то код - 

(define (find t q) ;; find q in t

(path empty) ;; the return path will be a list, we'll start it off as an empty list

(if (empty? t) ;; fundamental laws: always check for empty list first
    #f         ;; if the tree is empty, there is nothing to find, we use #f to signal this
    (if (eq? q (car t)) ;; otherwise we can check if the node matches q ...
        ;; wups we can't do eq? test yet, it's possible `(car t)` is a list of nodes
        ))

Как мне это увидеть? Я смотрю на наш список ввода - 

(define tree '(1 (2 (3) (4)) (5 (6 (7) (8)) (9))))
  1. Мы всегда сначала проверяем empty?
  2. Если список не пустой, мы знаем, что имеем :
    • хотя бы один элемент, (car tree)
    • остальные элементы, (cdr tree)
  3. Я визуализирую элементы внешнего списка ; их всего три:
    • 1
    • (2 (3) (4))
    • (5 (6 (7) (8)) (9))
    [1171]
  4. Первый элемент был [1117 ] поэтому я подумал, что могу дотянуться до eq? и проверить, соответствует ли он q сразу
  5. Я заметил, что второй элемент был другого типа . Интуитивно понятно, что мы не можем сопоставить один элемент со списком элементов, поэтому мы должны обработать случай list? , прежде чем попытаться eq?

Исправить мою бу-бу - [1161 ] 

(define (find t q)

(path empty)

(if (empty? t)
    #f
    (if (list? (car t))
        ;; when the node is a list of nodes
        (if (eq? q (car t))
            ;; when the node matches q
            ;; when the node does not match q
            )))

Свернуть цепочки от if до cond для лучшей читаемости - 

(define (find t q)

(path empty)

(cond ((empty? t)
        #f)
      ((list? (car t))
       ;; when the node is a list of nodes
       )
      ((eq? q (car t))
       ;; when the node matches q
       )
      (else
       ;; when the node does not match q
       ))

Код теперь более плоский и приятный для чтения. Некоторые из этих пробелов сложно заполнить, но меня тянет ко второму пробелу; когда q равно (car t), это означает, что мы нашли совпадение, и пришло время вернуть path - 

(define (find t q)

(path empty)

(cond ((empty? t)
        #f)
      ((list? (car t))
       ;; when the node is a list of nodes
       ;; we'll come back to this ...
       )
      ((eq? q (car t))
       (cons q path)) ;; return the path with the final node
      (else
       ;; when the nodes does not match q
       ;; and save this for later too ...
       ))

Хорошо, это было не так уж плохо. Поэтому я проверил, когда (car t) совпадает с q, теперь я должен сказать, что происходит, когда он не совпадает. Когда (car t) не совпадает, я добавлю его в path и каким-то образом проверю, соответствует ли q кому-либо из потомков узла, (cdr t) - 

(define (find t q)

(path empty)

(cond ((empty? t)
        #f)
      ((list? (car t))
       ;; when node is a list of nodes
       ;; we'll come back to this ...
       )
      ((eq? q (car t))
       (cons q path))
      (else

       ;; add the node to the path ...
       (cons (car t) path)

       ;; check the node's children for a match
       (find (cdr t) q)

       ;; this doesn't quite work ...
       ))

, который я запускаю в ситуации, когда нам нужно обновить path новым узлом, и мне нужно вызвать find, у которого нет параметра path. Чтобы исправить это, я ввел цикл, который позволяет нам многократно оценивать выражение с любыми указанными нами аргументами - 

(define (find t q)

(let loop ;; lazily and sloppily insert a named loop

((path empty) ;; initialize the parameters that will change
 (t t))

(cond ((empty? t) ;; the expression to repeat, (cond ...)
        #f)
      ((list? (car t))
       ;; when the node is a list of nodes
       )
      ((eq? q (car t))
       (cons q path))
      (else
       (loop (cons (car t) path) ;; updated path
             (cdr t))))          ;; updated tree

Предложение else научило меня сопоставлять дочерние элементы узла, представляющие собой список узлов. Это, безусловно, облегчит работу с последним пробелом в коде, что и нужно делать, когда узел представляет собой список узлов! - 

(define (find t q)

(let loop

((path empty)
 (t t))

(cond ((empty? t)
        #f)
      ((list? (car t))

       ;; we could just recur the loop with 
       (loop path
             (car t))

       ;; but what about (cdr t) in this case?
       (loop path
             (cdr t))

      ((eq? q (car t))
       (cons q path))
      (else
       (loop (cons (car t) path)
             (cdr t))))

Последняя проблема здесь - у меня есть два (2) списка для проверки; (car t) определяется как список, а (cdr t) является списком. Я должен проверить их обоих. Простое решение состоит в том, чтобы объединить два loop вызова с or. Если один loop вернет #f, другой будет проверен - 

(define (find t q)

(let loop

((path empty)
 (t t))

(cond ((empty? t)
        #f)
      ((list? (car t))
       (or (loop path   ;; or represents dysjunction!
             (car t))
           (loop path
             (cdr t))))
      ((eq? q (car t))
       (cons q path))
      (else
       (loop (cons (car t) path)
             (cdr t))))

Исправьте скобки, запустите автоматический индентор - 

(define (find t q)
  (let loop
    ((path empty)
     (t t))
    (cond ((empty? t)
           #f)
          ((list? (car t))
           (or (loop path
                     (car t))
               (loop path
                     (cdr t))))
          ((eq? q (car t))
           (cons q path))
          (else
           (loop (cons (car t) path)
                 (cdr t))))))

(define tree '(1 (2 (3) (4)) (5 (6 (7) (8)) (9))))

(find tree 4)
;; '(4 2 1)

(find tree 8)
;; (8 6 5 1)

(find tree 9)
;; (9 5 1)

Обратите внимание, что результат обратный потому что действительно path построен в обратном порядке. Условие выхода, которое возвращает путь, просто требует вызова reverse перед возвратом - 

(define (find t q)
  (let loop
    ((path empty)
     (t t))
    (cond ((empty? t)
           #f)
          ((list? (car t))
           (or (loop path
                     (car t))
               (loop path
                     (cdr t))))
          ((eq? q (car t))
           (reverse (cons q path))) ;; don't forget to reverse!
          (else
           (loop (cons (car t) path)
                 (cdr t))))))

(define tree '(1 (2 (3) (4)) (5 (6 (7) (8)) (9))))

(find tree 4)
;; '(1 2 4)

(find tree 8)
;; (1 5 6 8)

(find tree 9)
;; (1 5 9)
0
ответ дан user633183 17 January 2019 в 17:41
поделиться
Другие вопросы по тегам:

Похожие вопросы: