Презентация на тему Лекция 3.Линейные структуры данных

данных – математическая модель с совокупностью операторов, определённых в

рамках этой модели.
Обобщение простых типов данных.
Инкапсулирование операторов, определённых для АТД.

переменная данного типа.
Структуры данных для представления АТД – набор

переменных различных типов, объединённых определённым образом.
Базовый строительный блок структуры данных – ячейка, предназначенная для хранения значения определенного базового или составного типа данных.

и доступа к данным выполняются в первом или последнем

узле:
Стек – линейный список, в котором все операции вставки и удаления выполняются на одном из концов списка;
Очередь (односторонняя очередь) – линейный список, в котором все операции вставки выполняются на одном из концов списка, а все операции удаления – на другом;
Дек (двусторонняя очередь) – линейный список, в котором все операции вставки и удаления выполняются на обоих концах списка.

удаляется тот элемент, который был помещён в стек последним.
Добавление

в стек: объект кладётся на стек (операция проталкивания - push).
Удаление из стека: снимается верхний элемент стека (операция выталкивания - pop).

– положить (протолкнуть) n на стек stack;
pop(stack) – снять

(вытолкнуть) верхний элемент со стека stack;
Стек может быть сымитирован при помощи массива stack и указателя стека sp (stack pointer). Если стек пуст, то sp = -1.

стека (sp==-1), говорят, что возникает недостаток элементов (underflow) -

стек опустошается. Недостаток элементов, как правило не является ошибкой.
Если элемент кладётся на заполненный стек (sp==SIZE), говорят, что возникает избыток элементов (overflow) – стек переполняется . Как правило, это считается ошибкой, так как положить элемент на стек необходимо, но места в стеке для него нет.
Проверка как на опустошение, так и на переполнение должны обрабатываться при программной реализации стека.

sp++; // модификация указателя

stack[sp] = m; // сохранение
} иначе {
// переполнение
}

снять stack[sp]; // выталкивание
sp--;

// модификация указателя
} иначе {
// опустошение;
}

удаляется тот элемент, который был помещён в очередь первым.
Очередь

имеет начало – front и конец – rear.
Добавление в очередь: со стороны конца объект ставится в очередь (операция помещения в очередь - enqueue).
Удаление из очереди: со стороны начала объект выводится из очереди (операция вывода из очереди - dequeue).

– поместить n в очередь queue;
dequeue(queue) – вывести первый

элемент из очереди queue;
Очередь может быть сымитирована при помощи массива queue и указателя front на начало очереди и rear на конец очереди.

0)
enqueue(queue, 4)

очередью может возникнуть недостаток элементов (underflow) и избыток элементов

(overflow).
В случае, если реализована циклическая организация очереди (по достижении последней ячейки массива запись происходит в первую):
очередь можно считать полной, если после добавления нового элемента rear совпадает с front;
очередь можно считать пустой, если перед удалением элемента выясняется, что rear совпадает с front.

{ // закольцевать
rear = 0;

} иначе {
rear++;
}
Если (rear == front) { // избыток
// переполнение
} иначе {
queue[rear] = m;
}

rear

front

rear

front

// недостаток
// опустошение
}

иначе {
Если (front == SIZE) {
front = 0;
} иначе {
front++;
}
вывести queue(front);
}

rear

front

rear

front

модели множеств с операторами добавления в очередь и удаления

из очереди элемента с минимальным приоритетом: enqueue и dequeueMin.
enqueue понимается в обычном смысле, dequeueMin является функцией, которая возвращает элемент с наименьшим приоритетом и удаляет его из очереди.
При организации АТД priorityQueue следует учесть, что ячейка данного линейного списка содержит не только значение, но и его приоритет. Таким образом функция постановки в очередь принимает следующий вид: enqueue(priorityQueue, key, priority)

6)
enqueue(priorityQueue, 3, 2)
rear
dequeueMin(priorityQueue)
rear
dequeueMin(priorityQueue)
rear