Разработать функции работы с приоритетной очередью - C (СИ)
Формулировка задачи:
Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по прио-ритету, снятие - подряд из старших адресов (конец очереди). Приоритет: мin значение числового параметра, при совпадении параметров - LIFO
Решение задачи: «Разработать функции работы с приоритетной очередью»
textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct _node {
struct _node* next;
int val;
} node;
typedef struct {
node* lst;
} pqueue;
inline void pqueue_init(pqueue* pq) { pq->lst = NULL; }
inline int pqueue_top(pqueue* pq) { return pq->lst->val; }
inline int pqueue_empty(pqueue* pq) { return (pq->lst == NULL); }
int pqueue_push(pqueue* pq, int val);
void pqueue_pop(pqueue* pq);
void pqueue_clear(pqueue* pq);
int main(void){
int i;
pqueue pq;
pqueue_init(&pq);
for(i = 0; i < 10; ++i)
pqueue_push(&pq, rand() % 10);
pqueue_push(&pq, 100);
pqueue_push(&pq, -100);
while(! pqueue_empty(&pq)){
printf("%d ", pqueue_top(&pq));
pqueue_pop(&pq);
}
return 0;
}
//вставка
int pqueue_push(pqueue* pq, int val){
node* p, *i, **q = &pq->lst;
for(i = pq->lst; (i != NULL) && (i->val > val); ){
q = &i->next;
i = i->next;
}
p = (node*)malloc(sizeof(node));
if(p != NULL){
p->val = val;
p->next = i;
if(pq->lst == NULL)
pq->lst = p;
else
*q = p;
}
return (p != NULL);
}
//вытолкнуть макс
void pqueue_pop(pqueue* pq){
node* t;
if(pq->lst != NULL){
t = pq->lst;
pq->lst = pq->lst->next;
free(t);
}
}
//удаление увсех
void pqueue_clear(pqueue* pq){
node* t;
while(pq->lst != NULL){
t = pq->lst;
pq->lst = pq->lst->next;
free(t);
}
}
Объяснение кода листинга программы
- Создание структуры узла и структуры приоритетной очереди
- Инициализация пустой приоритетной очереди
- Вставка элемента в приоритетную очередь
- Извлечение максимального элемента из приоритетной очереди
- Проверка на пустоту приоритетной очереди
- Ввод 10 случайных элементов в приоритетную очередь
- Вставка элементов 100 и -100 в приоритетную очередь
- Цикл, который продолжает извлекать элементы из приоритетной очереди, пока она не станет пустой
- Вывод каждого извлеченного элемента
- Функция для вставки элемента в приоритетную очередь
- Обход списка элементов в приоритетной очереди, чтобы найти место для вставки нового элемента
- Вставка нового элемента в приоритетную очередь
- Выделение памяти под новый узел
- Установка значения в новом узле
- Установка ссылки на новый узел
- Установка ссылки на новый узел в списке
- Проверка, была ли выделена память под новый узел
- Функция для удаления максимального элемента из приоритетной очереди
- Удаление узла, содержащего максимальный элемент
- Функция для очистки приоритетной очереди путем удаления всех ее элементов
- Обход списка элементов в приоритетной очереди, чтобы удалить каждый узел
- Выделение памяти под узел для удаления
- Установка ссылки на следующий узел в узле для удаления
- Установка ссылки на узел для удаления на NULL
- Освобождение памяти, выделенной под узел для удаления
- Освобождение памяти, выделенной под все узлы в списке
- Проверка, были ли все узлы в списке удалены