VPF::Бинарный поиск - Форум программистов

adejneka

Дата 6.1.2007, 17:59 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 105
Регистрация: 8.7.2005
Где: Москва, Россия

Репутация: 9
Всего: 11

После сортировки списка пробежаться по нему и объединить последовательные записи с одинаковым ключом:
((a . 1) (b. 2) (b . 4) (c . 3)) => ((a . (1)) (b . (2 4)) (c . (3)))
Пара замечаний по стилю.
- Нехорошо присваивать значения неописанным глобальным переменным (типа R в BISEARCH и L в DEMO). В Вашем случае лучше воспользоваться LET.
- COND нужен специально для разбора нескольких случаев:

Код

(cond ((char= (car (nth  m  list)) key)
       (return (cons (cdr (nth m list)) listq)))
      ((char< (car (nth m list)) key)
       (setq l (+ m 1)))
      (t
       (setq r (- m 1))))

В READSTRING проверку (= INDEX 1) можно заменить проверкой (= INDEX 0). Тогда функция будет работать со строками нулевой длины и можно будет убрать копию SETQ.

Agarwaen

Дата 6.1.2007, 18:32 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 4.1.2007

Репутация: нет
Всего: нет

Вот вариант с хеш-таблицей всё работает как надо. Если есть замечания, пишите.

Код

 
(defun make-char-hash (string)
  (let ((char-hash (make-hash-table)))
    (labels
      ((push-char-position (char pos)
        (setf (gethash char char-hash)
              (cons pos (gethash char char-hash)))))
      (dotimes (i (length string) char-hash)
        (push-char-position (aref string i) i)))))

(defun hash-to-list (hash)
  (let ((c-list nil))
    (maphash #'(lambda (key value)
                 (setq c-list (cons (list key value) c-list))) hash)
    c-list))

(defun READSTRING()
   (setq table (make-char-hash (read-line)))
   (setq list (hash-to-list table))
   (sort list #'char< :key #'car)
)

(defun BISEARCH(key list)
  (setq r (- (length list) 1))
  (let ((l 0) (m 0) (listq nil))
   (loop
     (cond ((> l r) (return listq)))
     (setq m (ceiling (/ (+ l r) 2)))
     (cond ((char= (car (nth  m  list)) key) (return (cons (cdr (nth m list)) listq))))
     (cond ((char< (car (nth m list)) key) (setq l (+ m 1))))
     (cond ((char> (car (nth m list)) key) (setq r (- m 1))))
   )
  )         
)

(defun demo()
    (terpri)
    (princ "============Binary search================")
    (terpri)
    (princ "Enter the string:")
        (setq L (READSTRING))
    (terpri)
        (princ "Enter the key:")
        (setq key (read-char))
        (terpri)
    (princ "===============Search====================")
    (terpri)
        (PRINC L)
        (terpri)
        (princ "Position of key in the string:")
        (princ (BISEARCH key L))
    (terpri)
    (print "===Press any key and Enter to continue===")
    (print (read))
)

(demo)

adejneka

Дата 6.1.2007, 18:45 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 105
Регистрация: 8.7.2005
Где: Москва, Россия

Репутация: 9
Всего: 11

Забыл сразу написать: поиск элемента с заданным номером в списке - операция медленная. Лучше было перед поиском (или перед сортировкой) перевести список в вектор.

linuxfan

Дата 6.1.2007, 21:34 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 11.10.2006

Репутация: 1
Всего: 1

Цитата(Agarwaen @ 6.1.2007, 17:50

)

Вот только нужно наверно саму хеш-таблицу переделать в список и его отсортировать, в нём же искать. Вопрос: как это сделать?

Ну тебе надо только получить список изо всех ключей хэш-таблицы. Для этого maphash придуман.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| LISP \| Следующая тема »