0

ツリー検索と置換アルゴリズムのコーディングに問題があります。入力ツリーには、任意にネストされたデータ項目が含まれます。たとえば、tree = (1 (2 3 (4 (5)) 6)) のように、1 がルートで、下の各レベルは括弧で囲まれています。したがって、1 はレベル #1 です。2、3、4、6 はレベル #2 (1 未満)、5 はレベル #3 (4 未満) です。ツリー全体は、任意のリストの car が常にデータ項目であり、その後に他のデータ項目またはサブツリーが続くように構造化されています。問題は、入力項目に一致するツリー内のデータ項目 (私の特定のケースでは #'equal) を見つけ、既存の古い項目を特定の新しいサブツリーに置き換えることです。したがって、ツリーは置換ごとに成長します。ただし、検索はツリー内でトップダウンに進み、最初に見つかったそのような olditem のみを交換してから終了する必要があります。

いくつかの観察?: 1) 二分木の場合、検索順序 (トップダウンの訪問) は通常レベル順と呼ばれ、他の可能な検索順序は前順、インオーダー、および後順ですが、私のツリーは必ずしも二分法ではありません。2) 幅優先探索アルゴリズムのようなものが機能する可能性がありますが、ノードは生成されるのではなく、ツリー トラバーサルによって選択されます。3) 標準の「置換」機能は、ツリーではなく、シーケンスに対してのみ機能します。4) 「subst」関数はツリーに対して機能しますが、一致するすべてのアイテムを置換する深さ優先の方法でトラバースするように見え、最初の置換後に停止する :count キーワード (「substitute」のように) がありません。

適切なアプローチをコーディングしたり、フレーミングしたりするのに役立つヘルプをいただければ幸いです。(また、なぜ common-lisp がリストとベクトルの両方に対してより多くの「ツリー」関数を持っていないのか不思議です。)

4

3 に答える 3

0

これは、最も浅い左端の出現を実際に置き換える実際の幅優先検索です。(残念ながら、@Leo のコードは、滑らかではありますが、それを行いません。)

楽しみのために、循環リストをキューとして使用しました。

(setf *print-circle* t)

(defun one-element-queue (item)
  (let ((link (list item)))
    (setf (cdr link) link)))

(defun enqueue (item &optional queue)
  (cond ((null queue) (one-element-queue item))
        (t (let ((new-link (cons item (cdr queue))))
             (setf (cdr queue) new-link)))))

(defun enqueue-all (items &optional queue)
  (dolist (item items queue) (setq queue (enqueue item queue))))

(defun dequeue (queue)
  (cond ((eq queue (cdr queue)) (values (car queue) nil))
        (t (let ((item (cadr queue)))
             (setf (cdr queue) (cddr queue))
             (values item queue)))))

(defun node-replace (new-item old-item node)
  (let ((position (position old-item node :test #'equal)))
    (when position (setf (nth position node) new-item))
    position))

(defun tree-replace (new-item old-item tree)
  (loop with queue = (enqueue tree) and node
        while queue
        do (multiple-value-setq (node queue) (dequeue queue))
        until (node-replace new-item old-item node)
        do (setq queue (enqueue-all (remove-if-not #'listp node) queue)))
  tree)

(setq tree '(1 ((5 ((41))) 3 (4 (5)) 5)))

(print (tree-replace 42 5 tree))
于 2016-11-09T04:01:02.037 に答える
0

宿題はあなたが自分でしなければならないので、私はこれをすべきではないかもしれませんが、何をすべきかを説明するのは、それを示すよりも時間がかかります. 幅優先検索と置換バージョンは次のとおりです。

(defun search-replace (item new-item lst)
  (when (listp lst)
    (let ((found-item (member item lst)))
      (if found-item
          (rplaca found-item new-item)
          (some #'(lambda (sublst) (search-replace item new-item sublst)) lst) ))))

この関数は破壊的です。つまり、元のリストを変更します。これは を使用しているためrplacaです。結果のリストは返されません (最後に追加できます)。equalテスト関数（または必要なもの）など、他の優れた機能を追加することもできます。サブリストであるリストでも機能しますcar（この例では、常にアトムです）。始めるのに役立つことを願っています。

于 2016-11-08T06:49:35.463 に答える