Разработать функции работы с приоритетной очередью - 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
- Освобождение памяти, выделенной под узел для удаления
- Освобождение памяти, выделенной под все узлы в списке
- Проверка, были ли все узлы в списке удалены
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д