16.
Очередью называется упорядоченный набор элементов, которые могут удаляться с её начала и помещаться в её конец.
Очередь организована, в отличие от стека, согласно дисциплине обслуживания, FIFO: FIRST INPUT FIRST OUTPUT.
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows.
Существует несколько способов реализации очереди:
с помощью одномерного массива; с помощью связанного списка;
объявление структуры:
typedefstructnode_t {// Узел
intvalue;// Само значение
structnode_t* next; // Указатель на следующий элемент
}TNode;
typedefstructqueue_t {// Очередь
TNode* head; // Вершинаочереди
TNode* tail; // Хвост
}TQueue;
Функция удаления из очереди:
int Pop (TQueue* queue){
int value = 0;
TNode* node;
if (queue->head){ // Пока есть элементы в очереди
node = queue->head; // Сохраняем указатель на удаляемый элемент
value = node->value; // Сохраняем значение удаляемого элемента
queue->head = queue->head->next;// Вершиной очереди становится следующий за удаляемым элемент
free(node); // Окончательно удаляем элемент
}
returnvalue;
}
17.
Стек (или магазин) представляет собой список, упорядоченный по времени поступления элементов таким образом, что извне доступен только последний из записанных в список элементов, который называется вершиной стека. Другими словами, стек функционирует по принципу «последним пришел - первым ушел» (LIFO - LastInputFirstOutput).
Так как извне доступна только вершина стека, то основными операциями для стека являются:
выборка с одновременным удалением вершины стека;
добавление нового элемента в вершину стека.
Объявление элемента стека.
typedefstructnode{
char el;
struct node *next;
} Stack;
Глобальная переменная – указатель на вершину стека.
Stack* Head=NULL;
Добавлениевстек.
void Push(char element){
Stack *p;
p = (Stack*)malloc(sizeof(Stack));
if(p!=NULL){
p->el=element;
p->next=Head;
Head=p;
printf(“Push elem %c \n”,element);
}
else{
puts(“Error! Not free memory!”);
}
}
18.
Деком (англ. deque – аббревиатура от double-endedqueue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь.
Возможные действия с деком.
Добавить (положить) в начало дека новый элемент;
Добавить (положить) в конец дека новый элемент;
Извлечь из дека первый элемент;
Извлечь из дека последний элемент;
Узнать значение первого элемента (не удаляя его);
Узнать значение последнего элемента (не удаляя его);
Узнать количество элементов в деке;
Очистить дек (удалить из него все элементы);
Объявление
struct node {
int data;
int key;
struct node *next;
structnode *prev;
};
Глобальные переменные:
structnode *head = NULL;
struct node *last = NULL;
structnode *current = NULL;
Функция удаления элемента из начала.
struct node* deleteFirst() {
struct node *tempLink = head;
if(head->next == NULL){
last = NULL;}
else {
head->next->prev = NULL;
}
head = head->next;
returntempLink; }
19.
Обра́тнаяпо́льскаянота́ция (ОПН) — форма записи математических и логических выражений, в которой операнды расположены перед знаками операций. Также именуется как обратная польская запись,
Отличительной особенностью обратной польской нотации является то, что все аргументы (или операнды) расположены перед знаком операции.
Выражение в постфиксной форме (post-fix), которую еще называют обратной польской записью не имеет скобок, что позволяет не обращать внимания на приоритеты, связанные с ними. А за счет того, что все операнды расположены перед знаком операции, выражение можно вычислить последовательно, за один проход слева направо, что позволяет не учитывать приоритетов знаков операций.
Постфиксная форма записи7 5 2 - 4 * +
операнды в постфиксной форме не меняют своего относительного расположения, а вот порядок следования операций и функций меняется как по отношению к операндам, так и по отношению друг к другу.
Правила перевода следующие
1. Ввести в стек левую скобку '('
2. Добавить в конец строки с инфиксным выражением правую скобку ')'
3. Пока стек не пуст, считываем символы из строки содержащей инфиксное выражение слева направо и выполняем следующие действия.
a. Если текущий символ в инфиксной строке – левая скобка, помещаем ее в стек.
b. Если текущий символ в инфиксной строке – правая скобка, извлекаем знаки операций из стека и вставляем их в результирующую строку, до тех пор пока на вершине стека не появиться левая скобка. Извлечь левую скобку и отбросить ее.
c. Если текущий символ в инфиксной строке – знак операции, извлекаем знаки операций из стека (если они там есть), пока соответсвующее им операции имеют равный или более высокий приоритет по сравнению с текущей операцией, и вставляем извлеченные знаки операций в результирующую строку. Вставим текущий символ в стек.
d. Если текущий символ в инфиксной строке – цифра, копируем его в результирующую строку
Пример перевода
| Исходная инфиксная строка | Стек | Результат |
| 4+2*7 | пуст | пуст |
| 4+2*7) | ( | пуст |
| +2*7) | ( | |
| 2*7) | (+ | |
| *7) | (+ | 4 2 |
| 7) | (+ * | 4 2 |
| ) | (+ * | 4 2 7 |
| (+ | 4 2 7 * | |
| ( | 4 2 7 * + | |
| пуст | 4 2 7 * + |
Общий порядок
Автоматизация вычисления выражений в обратной польской нотации основана на использовании стека. Алгоритм вычисления для стековой машины элементарен:
1. Обработкавходногосимвола
· Если на вход подан операнд, он помещается на вершину стека.
· Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результатвыполненнойоперациикладётсянавершинустека.
2. Если входной набор символов обработан не полностью, перейти к шагу 1.
3. После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.
Реализация стековой машины, как программная, так и аппаратная, чрезвычайно проста и может быть очень эффективной. Обратная польская запись совершенно унифицирована — она принципиально одинаково записывает унарные, бинарные, тернарные и любые другие операции, а также обращения к функциям, что позволяет не усложнять конструкцию вычислительных устройств при расширении набора поддерживаемых операций. Это и послужило причиной использования обратной польской записи в некоторых научных и программируемых микрокалькуляторах.
Пример вычисления выражений
Инфиксное выражение {\displaystyle (1+2)\times 4+3}в ОПН может быть записано так: 1 2 + 4 × 3 +
Вычисление производится слева направо.
| Ввод | Операция | Стек |
| поместить в стек | ||
| поместить в стек | 1, 2 | |
| + | сложение | |
| поместить в стек | 3, 4 | |
| * | умножение | |
| поместить в стек | 12, 3 | |
| + | сложение |
Результат, 15, в конце вычислений находится на вершине стека.
Иерархические списки представляют собой несколько подсписков, ранжированных по уровням так, что эл-ты подсписка уровня 0 явл. головными эл-тами (или содержат ссылки на них) для подсписков уровня 1. Те в свою очередь явл. головными для подсписков уровня 2 и т.д.
т.e. эл-ты иерархического списка, кроме привычной информационной части содержат ссылку на головной эл-т нижнего подсписка.
При реализации такого списка основными характеристиками явл.:
1. Кол-во уровней
2. Кол-во подсписков на одном уровне
Примером применения иерархического списка может явл. база данных с информацией о студентах университета, в кот.можно выделить следующие уровни: факультеты, специальности, курсы, группы, студенты.
Поскольку в иерархическом списке присутствует большое кол-во ссылок, то изменятся и структуры, представляющие эл-ты списка.
typedefstruct item{
VAL data;
Struct item*next;
ITEM 1*sub;
}ITEM 0;
typedefstruct item{
VAL data;
struct item*next;
ITEM 2*sub;
}ITEM 1;
typedef{
VAL data;
struct item*next;
}ITEM 2;
Дляреализацииоперациивставкииудаленияэл-товвиерархическомсписке можно использовать ф-ции похожие простым спискам, но для поиска эл-та уже недостаточно указать его знач-е, т.к. необходимо сначала найти подсписок, в кот.он находится. Для этого надо знать путь к искомому эл-ту в виде последовательности значений ключей
Продолжение 21 вопроса:
эл-тов, в кот.начальное знач-е представляет собой ключ эл-та уровня 0, а все последующие явл. ключами соответствующих эл-тов нижележащих подсписков.
Назовем такую последовательность ключей спецификацией эл-тов иерархического списка.
Пример спецификации:
Intspec[4]={0,1,2,3}
0 – номер факультета, 1 – номер специальности, 2 – номер курса, 3 – номер группы
Push (int*spec, VAL new_data)
Pop (int*spec);
Кол-во значений, входящих в спецификацию эл-та, зависит от того, на каком уровне он расположен и может варьироваться от 0 для первого уровня, до N-1 для N-ого уровня.
Особенностью ф-ции удаления в иерархическом списке явл. необходимость рекурсивного удаления всех зависимых от удаляемого эл-та подсписков.