Разработать функции работы с приоритетной очередью - 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);
    }
}

Объяснение кода листинга программы

  1. Создание структуры узла и структуры приоритетной очереди
  2. Инициализация пустой приоритетной очереди
  3. Вставка элемента в приоритетную очередь
  4. Извлечение максимального элемента из приоритетной очереди
  5. Проверка на пустоту приоритетной очереди
  6. Ввод 10 случайных элементов в приоритетную очередь
  7. Вставка элементов 100 и -100 в приоритетную очередь
  8. Цикл, который продолжает извлекать элементы из приоритетной очереди, пока она не станет пустой
  9. Вывод каждого извлеченного элемента
  10. Функция для вставки элемента в приоритетную очередь
  11. Обход списка элементов в приоритетной очереди, чтобы найти место для вставки нового элемента
  12. Вставка нового элемента в приоритетную очередь
  13. Выделение памяти под новый узел
  14. Установка значения в новом узле
  15. Установка ссылки на новый узел
  16. Установка ссылки на новый узел в списке
  17. Проверка, была ли выделена память под новый узел
  18. Функция для удаления максимального элемента из приоритетной очереди
  19. Удаление узла, содержащего максимальный элемент
  20. Функция для очистки приоритетной очереди путем удаления всех ее элементов
  21. Обход списка элементов в приоритетной очереди, чтобы удалить каждый узел
  22. Выделение памяти под узел для удаления
  23. Установка ссылки на следующий узел в узле для удаления
  24. Установка ссылки на узел для удаления на NULL
  25. Освобождение памяти, выделенной под узел для удаления
  26. Освобождение памяти, выделенной под все узлы в списке
  27. Проверка, были ли все узлы в списке удалены

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 3.8 из 5
Похожие ответы