Список
Для иллюстрации порядка организации и работы с очередью рассмотрим пример. Пусть имеется строка символов, которая следующим образом моделирует некоторую вычислительную ситуацию: символы букв означают запросы на некоторый ресурс и подлежат постановке в очередь (имеющую ограниченный размер). Если среди символов встречаются символы цифр в диапазоне 1-9, то это означает, что необходимо изъять из очереди соответствующее значению цифры количество элементов. Если очередь полна, а символов цифр все нет, то происходит потеря заявок (символов букв). В нашей программе будем считать, что очередь кольцевая и ее переполнение помимо потери новых элементов приводит к выводу соответствующего сообщения. Для кольцевой очереди возможны следующие соотношения значений указателей Р, и Р2: Pj < Р2, Pj = Р2 (пустая очередь), Р, > Р2. Память для очереди в нашей задаче выделяется динамически средствами API Win32.
Заметим, что исходя из потребностей конкретной задачи можно изменить дисциплину обслуживания очереди. Например, установить, что при переполнении очереди потере подлежат старые заявки (в голове очереди) и т. п.
jb ml cmpa1.39h ja ml xor есх.есх:удаляем из очереди элементы mov cl,al subcl,30h преобразуем символ цифры в двоичный эквивалент ш2 : pop_quechar_que.<offset temp> jc cycl;если очередь пуста 1 oop m2 jmpcycl ml: добавляем элементы в очередь mov temp,a 1 push_que char_que. <offset temp> jnc cycl;ycnex;вывод на экран сообщения об ошибке – отсутствие места в очереди jmp cycl ;выход из приложения exit::удаляем блок памяти с очередью delete_que char_que
Как и в случае со стеком, код, выполняющий работу с очередью, оформлен в виде макрокоманд. Программа выдает единственное Сообщение о переполнении очереди. Чтобы наблюдать работу программы в динамике, необходимо выполнить следующие действия.
- Загрузить исполняемый модуль программы в отладчик td32.exe.
- Отследить адрес начала блока памяти, который будет выделен системой по нашему запросу для размещения очереди. Для этого подвергните пошаговому выполнению в окне CPU содержимое макрокоманды createque.
- Выяснив адрес начала блока для размещения очереди, отобразите его в окне Dump и нажмите клавишу F7 или F8. Не отпуская этой клавиши, наблюдайте за тем, как изменяется состояние очереди.
Дека
Дека – очередь с двумя концами. Дека является последовательным списком, в котором включение и исключение элементов может осуществляться с любого из двух концов списка. Логическая и физическая структуры деки аналогичны обычной очереди, но относительно деки следует говорить не о хвосте и голове, а о правом и левом конце очереди. Реализацию операций включения и исключения в деку следует также дополнить признаками левого или правого конца. В литературе можно встретить понятие дека с ограниченным вводом. Это дека, в которой элементы могут вставляться в одном конце, а удаляться с обоих.
Связные списки
Связный список – набор элементов, каждый из которых структурно состоит из двух частей – содержательной и связующей. Содержательная часть представляет собой собственно данные или указатель на область памяти, где эти данные содержатся. Связующая часть предназначена для связи элементов в списке и определяет очередность их следования. Благодаря связующей части в каждом из элементов становятся возможными "путешествия" по списку путем последовательных переходов от одного элемента к другому.
В отличие от последовательного списка связный список относится к динамическим структурам данных. Для них характерны непредсказуемость в числе элементов, которое может быть нулевым, а может и ограничиваться объемом доступной памяти. Другая характеристика связного списка – необязательная физическая смежность элементов в памяти.
Относительно связующей части различают следующие типы связных списков.
- Односвязный список – список, начало которого определяется указателем начала, а каждый элемент списка содержит указатель на следующий элемент. Последний элемент должен содержать признак конца списка или указатель на первый элемент списка. В последнем случае мы имеем одно-связный кольцевой список. Преимущество последнего состоит в том, что просмотр всех элементов списка можно начинать с любого элемента, а не только с головы. Более того, в случае кольцевого односвязного списка указателем его начала может быть любой элемент списка. Этот вид списка всегда линейный, так как однозначно задает порядок своего просмотра.
- Двусвязный список – список, связующая часть которого состоит из двух указателей – на предыдущий и последующий элементы. Начало и конец списка определяются отдельными указателями. Последние элементы дву-связного списка в каждом из направлений просмотра содержат признаки конца. Если замкнуть эти указатели друг на друга, то мы получим кольцевой двусвязный список. В этом случае потребность в указателе конца списка отпадает. Этот вид списка может быть как линейным (иметь одинаковый порядок просмотра в обоих направлениях), так и нелинейным (второй указатель каждого элемента списка задает порядок просмотра, который не является обратным порядку, устанавливаемому первым указателем).
- Многосвязный список – список, связующая часть элементов которого в общем случае содержит произвольное количество указателей. В этом виде списка каждый элемент входит в такое количество односвязных списков, сколько он имеет в себе полей связи.