OberonCore https://forum.oberoncore.ru/ |
|
Линейный поиск по двунаправленному кольцевому списку https://forum.oberoncore.ru/viewtopic.php?f=86&t=6075 |
Страница 1 из 1 |
Автор: | kekc_leader [ Среда, 21 Июнь, 2017 22:55 ] |
Заголовок сообщения: | Линейный поиск по двунаправленному кольцевому списку |
Широко известна схема цикла «линейный поиск», которая имеет следующий вид: Код: Взять_первую_ситуацию; WHILE ~ситуации_закончились & ~искомое_найдено DO Взять_следующую_ситуацию END; IF ~ситуации_закончились THEN (* Искомое найдено *) END При работе над проектом Oberon Vision (аналог Turbo Vision — библиотеки для создания псевдографического интерфейса пользователя) оказалось, что элементы меню, окна и прочее удобно организовывать в двунаправленные кольца (то есть двунаправленные списки, в которых первый и последний элементы также взаимно связаны). Код: TYPE Control* = POINTER TO ControlDesc; ControlDesc* = RECORD parent*: Control; (* Указатель на непосредственный родительский элемент *) children*: Control; (* Указатель на первый дочерний элемент *) prev*, next*: Control; (* Указатели на братские элементы для организации двунаправленного кольца *) caption*: ARRAY 256 OF CHAR END; Одна из подзадач заключается в нахождении среди братских элементов (sibling elements), включая и сам элемент, элемента с определённым свойством. Например, необходимо найти элемент меню, у которого внутри строкового поля caption была бы определённая буква, перед которой стоит символ "&" (элемент "Save &As..." должен отреагировать на букву "A"). Это нужно для того, чтобы при нажатии на ту или иную клавишу, срабатывал соответствующий элемент меню. У меня получился такой код: Код: PROCEDURE MenuKeyDown*(c: Control; key: G.Key); VAR p: Control; (* Поиск осуществляется среди братских элементов 'c', включая его самого. *) br: Control; (* Элемент-барьер *) found: BOOLEAN; BEGIN ... p := c.prev; br := p; REPEAT p := p.next; found := MenuHotkey(p(Menu), CHR(key.sym)) UNTIL found OR (p = br); IF found THEN p.do.click(p) END; ... END MenuKeyDown; Как видите, данный код не соответствует вышеупомянутой схеме линейного поиска. Как решить данную задачу более правильно? |
Автор: | albobin [ Среда, 21 Июнь, 2017 23:55 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Не имея ввиду "более правильное", предложение такое - проверить начальный элемент на наличие свойства, а, уж в случае его отсутствия, переходить на обход братьев по схеме линейного поиска. |
Автор: | Иван Денисов [ Четверг, 22 Июнь, 2017 05:36 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Вот так должно сработать и это ближе к схеме Код: p := c; WHILE (p # NIL) & ~ MenuHotkey(p(Menu), CHR(key.sym)) DO IF p.next # с THEN p := p.next ELSE p := NIL END END; IF p # NIL THEN p.do.click(p) END; ... |
Автор: | kekc_leader [ Четверг, 22 Июнь, 2017 13:03 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Иван Денисов писал(а): Вот так должно сработать и это ближе к схеме Отлично! То, что надо. |
Автор: | Info21 [ Четверг, 22 Июнь, 2017 16:59 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Чего-то не вижу? Почему не просто WHILE (p.next # c) ... p := p.next END; IF p.next # c ... ? |
Автор: | Иван Денисов [ Четверг, 22 Июнь, 2017 17:09 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Info21 писал(а): Чего-то не вижу? Почему не просто WHILE (p.next # c) ... p := p.next END; IF p.next # c ... ? Так не получится "защучить" последний элемент при условии выполнения проверки на нем. |
Автор: | albobin [ Четверг, 22 Июнь, 2017 17:44 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Добавлю, что в случае цепочки из одного "закольцованного" элемента, тело цикла WHILE (p.next # c) вообще не выполнится. Кстати тут "двунаправленность" и даже "закольцованность" принципиально ничего кардинально усложняющего по сравнению с линейным списком (строкой, файлом и т.д) не привносит. Просто везде надо определить соответствующий рассматриваемому случаю EOF. |
Автор: | Илья Ермаков [ Четверг, 22 Июнь, 2017 20:40 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Как вариант: Код: p := first.next; WHILE (p # first) & ~условие_поиска DO p := p.next END; IF условие_поиска THEN END Относительно схемы ЛП меняется условие в IF. Цикл такой же, инвариант такой же. Другая инициализация цикла (принимаем за начальный не первый, а второй элемент, а первый - за конец. Мы вольны в кольцевом списке, всё элементы эквивалентны. Главное, что не имеем права начать с того же, которым заканчиваем.) Но в классическом ЛП end => UNDEFINED(условие_поиска), поэтому проверка по ~end. А тут E p end & условие_поиска (существует на множестве всех выполнений программы). И A p DEFINED(условие_поиска). Отсюда другой IF в конце. Ы? |
Автор: | Илья Ермаков [ Пятница, 07 Июль, 2017 18:56 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Отвечаю здесь на viewtopic.php?p=101253#p101253 Цитата: Вот здесь viewtopic.php?p=101164#p101164 приведено решение с грубой ошибкой. Поиск начинается со второго элемента, но если элемент один? Так всё нормально будет, если он там один! Цикл не выполнится ни разу - и будет сразу проверка завершающего элемента (первого). Другой вопрос, что это расчитано на непустой список. Так что придётся держать в нём "пустышку". Цитата: Само собой, я тогда тоже задумался над примером. И синтезировал (быстро, но не мгновенно!) рабочий вариант. Он короче варианта Ивана Денисова. Не томите ) Давайте вариант сюда. |
Автор: | Peter Almazov [ Суббота, 08 Июль, 2017 08:22 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
На этой площадке не веду такую деятельность. |
Автор: | Иван Денисов [ Суббота, 08 Июль, 2017 13:25 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Peter Almazov писал(а): На этой площадке не веду такую деятельность. А я придумал вариант еще короче вашего! |
Автор: | adva [ Вторник, 11 Июль, 2017 07:42 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Иван Денисов писал(а): Peter Almazov писал(а): На этой площадке не веду такую деятельность. А я придумал вариант еще короче вашего! Чё, теперь в моде у кого короче ) ? |
Автор: | kekc_leader [ Четверг, 13 Июль, 2017 14:14 ] |
Заголовок сообщения: | Re: Линейный поиск по двунаправленному кольцевому списку |
Вот как вариант т. Денисова выглядит в рабочем коде: Код: ... ELSIF (x # 0) & (c.children # NIL) THEN p := c.children; br := p; WHILE (p # NIL) & ~((p.x <= x) & (x < p.x + p.w) & (p.y <= y) & (y < p.y + p.h)) DO IF p.next = br THEN p := NIL ELSE p := p.next END END; IF (p # NIL) & (p.do.mouseDown # NIL) THEN p.do.mouseDown(p, x - p.x, y - p.y, button) END END Вполне годится. Остальные варианты прочёл только сейчас. Если использовать вариант без IF'а внутри WHILE'а, то, пожалуй, имеет смысл выделить условие проверки координат в отдельную процедуру. Ещё важно отметить, что перебирать элементы кольца в данной задаче необходимо начиная с первого, то есть с c.children. В этом случае, когда пользователь нажимает мышкой на место на экране, где находятся сразу несколько окнон, то событие будет направлено окну, находящемуся впереди. |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |