Очереди

Очередь представляет собой линейный список данных, доступ к которому осуществляется по принципу "первый вошел, первый вышел" /иногда сокращенно его называют методом доступа FIFO/. Элемент, который был первым поставлен в очередь, будет первым получен при поиске. Элемент, поставленный в очередь вторым, при поиске будет получен также вторым и т.д. Этот способ является единственным при постановке элементов в очередь и при поиске элементов в очереди. Применение очереди не позволяет делать прямой доступ к любому конкретному элементу.

В повседневной жизни очереди встречаются часто. Например, очередь в банке или очередь в кафетериях с быстрым обслуживанием являются очередью в указанном выше смысле /исключая те случае, когда человек пытается добиться обслуживания вне очереди!/. Для того, чтобы лучше понять работу очереди, рассмотрим две процедуры: постановка в очередь и выборка из очереди. При выполнении процедуры постановки в очередь элемент помещается в конец очереди. При выполнении процедуры выборки из очереди из нее удаляется первый элемент, который является результатом выполнения данной процедуры. Работа очереди проиллюстрирована на рис.1. Следует помнить, что при выборке из очереди из нее действительно удаляется один элемент. Если этот элемент нигде не будет сохранен, то в последствии к нему нельзя будет осуществить доступ.

Реализуем очередь на базе массива. Считаем, что очередь прирастает справа и убывает слева. Поскольку она может дойти до края массива, свернем массив в окружность.

#define n 100

int querry[n];

int first;

int dl;

void add(int a){

if(dl<n){

querry[(first+dl)%n]=a;

dl++;

}

}

int del(void){

int x;

if(dl>0)

x=querry[first];

first = (first+1) % n;

dl--;

return(x);

}

Наиболее широко очереди применяются в операционных системах при буферизации информации, которая считывается или записывается на дисковые файлы или консоль. Другое широкое применение эти очереди нашли в решении задач реального времени, когда, например, пользователь может продолжать делать ввод с клавиатуры во время выполнения другой задачи. Так работают многие текстовые процессоры, когда изменяется формат параграфа или выравнивается строка. Имеется короткий промежуток времени, когда набранная на клавиатуре информация не выводится на экран до окончания другого процесса. Для достижения такого эффекта в программе должна предусматриваться постоянная проверка ввода с клавиатуры в ходе выполнения другого процесса. При вводе некоторого символа его значение должно быстро ставиться в очередь и процесс должен продолжаться. После завершения процесса набранные символы выбираются из очереди и обрабатываются обычным образом.

Пример использования очереди.

Напечатать в порядке возрастания первые n натуральных чисел, в разложении которых на простые множители встречаются только числа 2, 3 и 5.

Заведем три очереди x2,x3,x5.

При печати очередного числа будем помещать туда числа, которые в 2,3 и 5 раз больше напечатанного.

void printAdd(int t){

printf(“%d”,t);

add(x2,2*t);

add(x3,3*t);

add(x5,5*t);

}

Тогда главная программа должна выглядеть так:

printfAdd(1);

for(k=1; k<n; k++){

x=min(очередной элемент x2, очередной элемент x3, очередной элемент x5);

printAdd(x);

Удалить x из очередей, где он был очередным.

}

СТЕКИ

Организация стека в определенном смысле противоположна организации очереди, поскольку здесь используется доступ по принципу "последней вошел, первый вышел" /такой метод доступа иногда называют методом LIFO/. Представим себе стопку тарелок. Нижняя тарелка из этой стопки будет использована последней, а верхняя тарелка /которая была установлена в стопку последней/ будет использована первой. Стеки широко используются в системном программном обеспечении, включая компиляторы и интерпретаторы.

Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека - получили название соответственно "затолкнуть" и "вытолкнуть". Поэтому для реализации стека необходимо создать две функции: "push" /затолкнуть/, которая помещает элемент в вершину стека, и "pop" /вытолкнуть/, которая выбирает из вершины стека значение. Необходимо также предусмотреть определенную область в памяти, где фактически будет храниться стек. Для этого можно использовать массив или динамически выделять память под вновь прибывающие элементы.

Реализуем стек на базе массива.

#define n 100

int st[n];

int top=0;

void push(int x){

st[top]=x;

top++;

}

int pop(void){

top--;

return(st[top]);

}

Хорошим примером применения стека является калькулятор, который может выполнять четыре действия. Большинство калькуляторов используют стандартную форму выражений, которая носит название инфиксной формы. В общем виде ее можно представить в виде "операнд-оператор-операнд". Например, для прибавления 100 к 200 вы должны ввести число 100, набрать символ сложения, ввести число 200 и нажать клавишу со знаком равенства. Однако, некоторые калькуляторы применяют другую форму выражений, получившую название постфиксной формы. В этом случае оба операнда вводятся перед вводом оператора. Например, для добавления 100 к 200 при использовании постфиксной формы сначала вводится число 100, затем вводится число 200 и после этого нажимается клавиша со знаком плюс. Введенные операнды помещаются в стек. При вводе оператора из стека выбираются два операнда и результат помещается в стек. При использовании постфиксной формы очень сложные выражения могут легко вычисляться на калькуляторе.

Ниже показан фрагмент программы для такого калькулятора. Для простоты считаем, что все числа лежат от 0 до 9.

char *st = “53+42-*”;

for(int i=0; st[i]; i++){

if(isdigit(st[i]))

push(st[i]-‘0’);

else{

x=pop();

y=pop();

switch(st[i]){

case ‘+’: push(x+y);break;

case ‘-’: push(y-x);break;

case ‘*’: push(x*y);break;

case ‘/’: push(x/y);break;

} }

}

Указатели.

Указатель – переменная, предназначенная для хранения адреса некоторого объекта.

Имеется две взаимно обратных операции:

& - взятие адреса.

- снятие адреса.

&x – это адрес переменной x.

*p – это значение переменной, лежащей по адресу p.

Имя массива – это адрес его нулевого элемента. Имя функции – это адрес точки входа в функцию.

К указателю можно прибавлять целое число. Если указатель указывает на переменную типа T, то прибавление к нему числа m перемещает его на m * sizeof (T) байтов. Это позволяет строить индексные выражения для массивов (см. лекцию про массивы).

Указатели на переменные одного типа можно вычитать. При этом, если указатели p1 и p2 указывают на объекты типа Т, расположенные в памяти через n байтов, то p2 - p1 = n / sizeof (T).

Указатели объявляют точно так же, как и любую другую переменную.

Пример.

int *p;

Здесь написано, что *p является переменной типа int. Тогда p является указателем на переменную типа int.

Можно инициализировать указатели при объявлении.

int x=5;

int *p = &x;

Можно задавать указатели на объекты достаточно сложных типов, комбинировать их с массивами и функциями и т.п.

Приведем несколько примеров.

int *p; p – указатель на переменную типа int.

int *p[5]; p – массив из пяти указателей на тип int

(p[0], p[1], … p[4] - – указатели на переменную типа int.)

int (*p) [5]; p – указатель на массив из пяти целых элементов.

struct c{

float x;

float y;

} *p; p – указатель на структуру.

(доступ к отдельным полям – p->x, p->y.

См. лекцию про структуры)

float (*p)(char, int); p – указатель на функцию, зависящую от двух

аргументов типа char и int и возвращающую

значение типа float.

float *p(char, int); p – функция, зависящая от двух аргументов

типа char и int и возвращающая указатель на float.

float (*p[5])(int); p – массив из пяти указателей на функции,

зависящие от аргумента типа int и возвращающие

значение типа float.

Мы уже использовали указатели для доступа к элементам одномерных и двумерных массивов, для передачи в функцию адреса переменной, что позволяет изменять значение самой переменной (см. лекцию про функции), а также приводили пример функции, зависящей от указателя на функцию.

Указатели можно использовать для организации достаточно сложных динамических типов данных.

В качестве примеров реализуем список и бинарное дерево.

Списки.

Если у нас есть множество элементов, каждый из которых расположен в своей области памяти, то возникает проблема доступа к произвольному элементу нашего множества. Один из вариантов ее решения – сделать так, чтобы каждый элемент содержал указатель на следующий элемент. Тогда для доступа ко всем элементам множества нам необходимо знать только указатель на первый элемент. Такая конструкция называется однонаправленным линейным списком. Каждый отдельный элемент вместе с указателем на следующий называется узлом списка.

Узел списка удобно хранить в виде структуры. Пусть, например мы создаем однонаправленный список из целых чисел. Тогда соответствующая структура должна выглядеть примерно так:

struct Node {

int d;

Node * next;

};

Здесь d – это наше данное (иногда его называют ключ), next – указатель на следующий узел списка.

Указатель next последнего узла списка может указывать на NULL, тогда список называется линейным. Можно сделать кольцевой список, заставив указатель последнего узла указывать на первый.

Понадобится еще указатель на начало списка pbeg. Он тоже должен иметь тип Node *.

Можно в каждый узел добавить еще и указатель на предыдущий элемент. Тогда по списку можно будет двигаться в обоих направлениях. В этом случае желательно иметь также и указатель pend на конец списка.

Над списками можно выполнять следующие операции:

1. Начальное формирование списка.

2. Добавление элемента в конец списка.

3. Поиск элемента с заданным ключом.

4. Вставка элемента в список после элемента с заданным ключом.

5. Удаление элемента с заданным ключом.

Бинарные деревья.

Древовидные иерархические структуры данных широко применяются при классификации различных объектов (например, в биологии). Есть корень дерева, который ссылается на нескольких своих потомков (основных ветвей), те в свою очередь ссылаются на своих потомков (более мелких ветвей) и т.д. Последние потомки ни на кого не ссылаются (они называются листьями). Если у каждого предка не более двух потомков, то дерево называется бинарным.

Каждый узел бинарного дерева удобно хранить в виде следующей структуры

struct Node{

int d;

Node *left;

Node * right;

};

Здесь d – это данное, a left и right – указатели на левое и правое поддерево.

Если бинарное дерево организовано так, что для каждого узла в его левом поддереве все ключи меньше, чем у самого узла, а в правом – больше, то дерево называется деревом поиска.

Привести пример.

Каждое поддерево тоже является деревом, поэтому дерево является рекурсивной структурой данных. Работать с такими данными удобнее всего с помощью рекурсивных алгоритмов.

Пример. Напечатаем дерево.

Печатаем (дерево){

Печатаем (левое поддерево);

Печатаем (корень);

Печатаем (правое поддерево);

}

Для бинарных деревьев должны быть реализованы следующие операции:

1. Включение узла в дерево

2. Поиска по дереву

3. Обхода дерева

4. Удаления узла.

Для каждой операции можно создать рекурсивный алгоритм или его нерекурсивный аналог.

Реализация списков и деревьев с помощью массивов.

Если размер памяти под наши данные можно определить заранее и не изменять его в процессе работы, то можно реализовать списки и деревья не на базе указателей, а на базе массивов.

Для реализации двунаправленного списка целых чисел требуется 3 массива (первый массив содержит данные, второй и третий массивы – номера предшествующих и последующих элементов) и 2 целых переменных (номера начального и конечного элементов списка).

Для реализации бинарного дерева тоже требуется 3 массива (первый массив содержит данные, второй и третий массивы – номера вершин правого и левого поддерева). Если поддерево отсутствует, то в соответствующий массив можно положить отрицательное число.

ВОПРОС 29 (2)