[图片] 用二分法搜索一个有序向量 要点 length获取列表长度 aref取向量中的元素,也可以用svref ,svref专门用来对向量进行操作,速度比aref快 递归求解 代码 ;;; 二分搜索 (defun b-search (obj vec) (let ((len (length vec))) (and (no ..

LISP 学习——特殊数据类型的操作练习

用二分法搜索一个有序向量

要点

代码

;;; 二分搜索
(defun b-search (obj vec)
  (let ((len (length vec)))
    (and (not (zerop len))
         (finder obj vec 0 (- len 1)))))

(defun finder (target vec start end)
  (if (eql end start) ; 如果起点等于终点相等
    (if (eql target (aref vec start))
      target
      nil)
    (let ((mid (+ start (round (/ (- end start) 2)))))
      (let ((e (aref vec mid))) ; 取到中间的元素
        (if (< target e)
          (finder target vec start (- mid 1))
 ; 若目标元素在左边对左半部分继续二分搜索
          (if (> target e)
            (finder target vec (+ mid 1) end)

 ; 若目标元素在右边对右半部分继续二分搜索
            target))))))

(format t "~A~%" (b-search 3 #(0 1 2 3 4 5 6 7 8 9)))
; Expected: 3

不使用原生reverse方法将列表倒序

要点

代码

;;; 将列表倒序
(defun my-rev-lst (l)
  (if (null l)
    (list)
    (append (my-rev-lst (cdr l)) (list (car l)))))

(format t "~A~%" (my-rev-lst '(a b c d)))
; Expected: (D C B A)

不使用原生copy-list复制列表

要点

代码

;;; 复制列表
(defun my-cp-lst (l)
  (reduce
    #'(lambda (new-l e)
      (if (listp new-l)
        (append new-l (list e))
        (list new-l e))
      )
    l))

(format t "~A~%" (my-cp-lst '(a b c d)))

将一个相同维度的数组顺时针转 90 度

要点

代码

; 将一个等纬度的二维数组顺时针旋转90度
(defun rotate-square-array (arr)
  (let
    ((n (car (array-dimensions arr)))
    (new-arr nil))
    (setf new-arr (make-array (list n n) :initial-element nil))
    (do ((i 0 (+ i 1)))
      ((eql i n))
      (do ((j 0 (+ j 1)))
        ((eql j n))
          (setf (aref new-arr i j) (aref arr (- (- n 1) j) i))))
    new-arr))

(let
  ((arr (make-array '(3 3) :initial-element nil)))
  (do ((i 0 (+ i 1)))
    ((eql i 3))
    (do ((j 0 (+ j 1)))
      ((eql j 3))
      (setf (aref arr i j) (+ (* i 3) (+ j 1)))))
  (format t "Before rotate: ~A~%" arr)
  (format t "After rotate: ~A~%" (rotate-square-array arr)))
; Expected: 
; Before rotate: #2A((1 2 3) (4 5 6) (7 8 9))
; After rotate: #2A((7 4 1) (8 5 2) (9 6 3))

哈希表与关联列表的相互转换

要点

;;; 哈希表转关联列表
(defun hash-table-to-lst (ht)
  (let ((l (list)))
    (maphash
      #'(lambda (k v)
        (setf l (append l (list (cons k v))))
      )
      ht
    )
    l))

(let ((ht (make-hash-table)))
  (setf (gethash 'color ht) 'red)
  (setf (gethash 'size ht) 'big)
  (format t "~A~%" (hash-table-to-lst ht)))
; Expected: ((COLOR . RED) (SIZE . BIG))

;;; 关联列表转哈希表
(defun lst-to-hash-table (l)
  (if (null l)
    (make-hash-table)
    (let (
      (e (car l))
      (ht (lst-to-hash-table (cdr l))))
      (setf (gethash (car e) ht) (cdr e))
      ht)))

(maphash
  #'(lambda (k v)
    (format t "~A = ~A~%" k v))
  (lst-to-hash-table '((+ . "add") (- . "subtract"))))
; Expected: 
; - = subtract
; + = add
回帖
请输入回帖内容...