Algoritmo Merge

Lisp »Tips 'n Tricks »Algoritmo Merge

Mg è un'implementazione dell'algoritmo di fusione di due liste (file, array) ordinate in un'unica lista, anch'essa ordinata.

L'algoritmo di base è il seguente:

i = 1; j = 1;
a[M+1] = eleMax; b[N+1] = eleMax;
for (k = 1; k <= M+N; k++)
   c[k] = (a[i]<b[j]) ? a[i++] : b[j++];

Da: "Algoritmi in C++", R. Sedgewick Ed. Addison-Wesley

Il lisp chiede di inserire manualmente gli elementi nelle due liste (questa parte del sorgente può essere sostituita con una funzione che crea le due liste in modo automatico, ad esempio leggendo determinate entità dal disegno in Autocad).

;;;
;;;    mg.lsp - 20 Marzo 2004
;;;    (C) 2004 by Claudio Piccini.
;;;    www.cg-cad.com
;;;    
;;;    Algoritmo Merge:
;;;    una implementazione in AutoLISP.
;;;

(defun merge ( a b / c M N i j)
 (setq i 0 j 0)
 (setq M (length a))
 (setq N (length b))
 (while (and (< i M)(< j N))
  (if (< (nth i a)(nth j b))
   (progn
    (setq c (append c (list (nth i a))))  
    (setq i (1+ i))
   )
   (progn
    (setq c (append c (list (nth j b))))
    (setq j (1+ j))
   )  
  )
 )
 (while (< i M)
  (setq c (append c (list (nth i a))))  
  (setq i (1+ i))
 )
 (while (< j N)
  (setq c (append c (list (nth j b))))  
  (setq j (1+ j))
 )
 (princ "\nA=")(princ a)
 (princ "\nB=")(princ b)
 (princ "\nC=")(princ c)
 (princ)
)

(defun c:mg (/ a b rs n x)
 (setvar "cmdecho" 0)
 (initget "N n L l")
 (setq rs (getkword "\nNumeri o lettere? (n/l): "))
 (cond   
  ((or (= rs "n") (= rs "N") (= rs nil))          
   (setq rs "N")
  )
  ((or (= rs "l") (= rs "L"))
   (setq rs "L")
  )
 )
 (if (= rs "N")
  (progn
   (setq n (getint "\nLista A: quanti numeri? "))
   (repeat n
    (setq x (getint "\nNumero? "))
    (setq a (append a (list x)))
   )
   (setq n (getint "\nLista B: quanti numeri? "))
   (repeat n
    (setq x (getint "\nNumero? "))
    (setq b (append b (list x)))
   )
  )
  (progn
   (setq n (getint "\nLista A: quante lettere? "))
   (repeat n
    (setq x (getstring "\nLettera? "))
    (setq a (append a (list x)))
   )
   (setq n (getint "\nLista B: quante lettere? "))
   (repeat n
    (setq x (getstring "\nLettera? "))
    (setq b (append b (list x)))
   )
  )
 )
 (merge a b)
 (setvar "cmdecho" 1)
 (princ)
)
;;;eof

Test del lisp

Command: mg
Numeri o lettere? (n/l): n
Lista A: quanti numeri? 7
Numero? 0
Numero? 5
Numero? 25
Numero? 25
Numero? 25
Numero? 35
Numero? 89
Lista B: quanti numeri? 7
Numero? 0
Numero? 12
Numero? 45
Numero? 89
Numero? 90
Numero? 108
Numero? 114
A=(0 5 25 25 25 35 89)
B=(0 12 45 89 90 108 114)
C=(0 0 5 12 25 25 25 35 45 89 89 90 108 114)

Command: mg
Numeri o lettere? (n/l): l
Lista A: quante lettere? 4
Lettera? b
Lettera? d
Lettera? e
Lettera? h
Lista B: quante lettere? 7
Lettera? a
Lettera? c
Lettera? f
Lettera? g
Lettera? i
Lettera? q
Lettera? r
A=(b d e h)
B=(a c f g i q r)
C=(a b c d e f g h i q r)

Lisp »Tips 'n Tricks

Ultimo Aggiornamento_Last Update: 20 Marzo 2004