我的学校程序几乎按预期工作，我的优先级队列能够正确插入和删除值，并且内容按预期存储。然而，我的输出看起来很奇怪，因为值与预期列中不匹配，并且数据显示无序。我觉得问题可能出在我的 pq_insert 函数中，因为我没有正确分配优先级。
预期的输出应该是这样的（当然数字是随机的）
1 / 1 / 1 ( 1)
1 / 1 / 1 ( 1)
2 / 2 / 2 ( 2)
14 / 14 / 14 ( 14)
14 / 14 / 14 ( 14)
25 / 25 / 25 ( 25)
26 / 26 / 26 ( 26)
26 / 26 / 26 ( 26)
第一个/删除/优先（预期
但是我得到了这样的信息：
2/2/2 (1)
1/1/1 (4)
4/4/4 (3)
3/3/3 (2)
我尝试用几种不同的方式重写我的 pq_insert ，我觉得我需要一些可以正确渗透和重新排序的东西，但我不太确定是否能让任何东西发挥作用。这是我最新的草稿
#include <stdlib.h>
#include "pq.h"
#include "dynarray.h"
/*
* This is the structure that represents a priority queue. You must define
* this struct to contain the data needed to implement a priority queue.
*/
struct pq {
struct dynarray* array;
};
struct pq_node
{
int priority;
void* value;
};
/*
* This function should allocate and initialize an empty priority queue and
* return a pointer to it.
*/
struct pq* pq_create() {
/*
* FIXME:
*/
struct pq* new_pq = malloc(sizeof(struct pq));
//Memory
if (new_pq == NULL) {
exit(EXIT_FAILURE);
}
new_pq->array = dynarray_create();
return new_pq;
}
/*
* This function should free the memory allocated to a given priority queue.
* Note that this function SHOULD NOT free the individual elements stored in
* the priority queue. That is the responsibility of the caller.
*
* Params:
* pq - the priority queue to be destroyed. May not be NULL.
*/
void pq_free(struct pq* pq) {
/*
* FIXME:
*/
dynarray_free(pq->array);
free(pq);
return;
}
/*
* This function should return 1 if the specified priority queue is empty and
* 0 otherwise.
*
* Params:
* pq - the priority queue whose emptiness is to be checked. May not be
* NULL.
*
* Return:
* Should return 1 if pq is empty and 0 otherwise.
*/
int pq_isempty(struct pq* pq) {
/*
* FIXME:
*/
return dynarray_size(pq->array) == 0;
}
/*
* This function should insert a given element into a priority queue with a
* specified priority value. Note that in this implementation, LOWER priority
* values are assigned to elements with HIGHER priority. In other words, the
* element in the priority queue with the LOWEST priority value should be the
* FIRST one returned.
*
* Params:
* pq - the priority queue into which to insert an element. May not be
* NULL.
* value - the value to be inserted into pq.
* priority - the priority value to be assigned to the newly-inserted
* element. Note that in this implementation, LOWER priority values
* should correspond to elements with HIGHER priority. In other words,
* the element in the priority queue with the LOWEST priority value should
* be the FIRST one returned.
*/
void pq_insert(struct pq* pq, void* value, int priority) {
/*
* FIXME:
*/
int index = 0;
//Memory
struct pq_node* new_node = malloc(sizeof(struct pq_node));
if (new_node == NULL) {
exit(EXIT_FAILURE);
}
new_node->value = value;
new_node->priority = priority;
while (index < dynarray_size(pq->array) && ((struct pq_node*)dynarray_get(pq->array, index))->priority <= priority) {
index++;
}
dynarray_insert(pq->array, new_node, index);
}
/*
* This function should return the value of the first item in a priority
* queue, i.e. the item with LOWEST priority value.
*
* Params:
* pq - the priority queue from which to fetch a value. May not be NULL or
* empty.
*
* Return:
* Should return the value of the first item in pq, i.e. the item with
* LOWEST priority value.
*/
void* pq_first(struct pq* pq) {
/*
* FIXME:
*/
if (pq_isempty(pq))
{
return NULL;
}
return ((struct pq_node*)dynarray_get(pq->array, 0))->value;
}
/*
* This function should return the priority value of the first item in a
* priority queue, i.e. the item with LOWEST priority value.
*
* Params:
* pq - the priority queue from which to fetch a priority value. May not be
* NULL or empty.
*
* Return:
* Should return the priority value of the first item in pq, i.e. the item
* with LOWEST priority value.
*/
int pq_first_priority(struct pq* pq) {
/*
* FIXME:
*/
if (pq_isempty(pq))
{
return 0;
}
return ((struct pq_node*)dynarray_get(pq->array, 0))->priority;
}
/*
* This function should return the value of the first item in a priority
* queue, i.e. the item with LOWEST priority value, and then remove that item
* from the queue.
*
* Params:
* pq - the priority queue from which to remove a value. May not be NULL or
* empty.
*
* Return:
* Should return the value of the first item in pq, i.e. the item with
* LOWEST priority value.
*/
void* pq_remove_first(struct pq* pq) {
/*
* FIXME:
*/
if (pq_isempty(pq))
{
return NULL;
}
struct pq_node* first_node = dynarray_get(pq->array, 0);
dynarray_remove(pq->array, 0);
void* value = first_node->value;
free(first_node);
return value;
}
/*
* This is a small program to test your priority queue implementation.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pq.h"
/*
* This is a comparison function to be used with qsort() to sort an array of
* integers into ascending order.
*/
int ascending_int_cmp(const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int main(int argc, char** argv) {
struct pq* pq;
int* first, * removed;
int i, k, p;
const int n = 16, m = 16;
int vals[16 + 16], sorted[16 + 16];
/*
* Seed the random number generator with a constant value, so it produces the
* same sequence of pseudo-random values every time this program is run.
*/
srand(0);
/*
* Create priority queue and insert pointers to pseudo-random integer values
* into it with the same priority as the value.
*/
pq = pq_create();
printf("== Inserting some values into PQ\n");
for (int i = 0; i < n; i++) {
vals[i] = rand() % 64;
pq_insert(pq, &vals[i], vals[i]);
}
/*
* Make a copy of the random value array and sort it by ascending value. We
* make a copy here so we can maintain the original array in the same order,
* thereby ensuring that pointer values stored in the priority queue always
* point to the same integer values.
*/
memcpy(sorted, vals, n * sizeof(int));
qsort(sorted, n, sizeof(int), ascending_int_cmp);
/*
* Examine and remove half of the values currently in the PQ.
*/
k = 0;
printf("\n== Removing some from PQ: first / removed / priority (expected)\n");
while (k < n / 2) {
p = pq_first_priority(pq);
first = pq_first(pq);
removed = pq_remove_first(pq);
if (first && removed) {
printf(" - %4d / %4d / %4d (%4d)\n", *first, *removed, p, sorted[k]);
} else {
printf(" - (NULL) / (NULL) / %4d (%4d)\n", p, sorted[k]);
}
k++;
}
/*
* Add a second set of pseudo-random integer values to the end of the array,
* and add pointers to those values into the priority queue with the same
* priority as the value.
*/
printf("\n== Inserting more values into PQ\n");
for (i = n; i < n + m; i++) {
vals[i] = rand() % 64;
pq_insert(pq, &vals[i], vals[i]);
}
/*
* Copy the second array of random values to the end of the sorted array and
* re-sort all of the the sorted array except the k values that were already
* examined above (since they were already removed from the PQ, and we won't
* see them again). Again, we make a copy here so we can maintain the
* original array in the same order, thereby ensuring that pointer values
* stored in the priority queue always point to the same integer values.
*/
memcpy(sorted + n, vals + n, m * sizeof(int));
qsort(sorted + k, n - k + m, sizeof(int), ascending_int_cmp);
printf("\n== Removing remaining from PQ: first / removed / priority (expected)\n");
while (k < n + m && !pq_isempty(pq)) {
p = pq_first_priority(pq);
first = pq_first(pq);
removed = pq_remove_first(pq);
if (first && removed) {
printf(" - %4d / %4d / %4d (%4d)\n", *first, *removed, p, sorted[k]);
} else {
printf(" - (NULL) / (NULL) / %4d (%4d)\n", p, sorted[k]);
}
k++;
}
printf("\n== Is PQ empty (expect 1)? %d\n", pq_isempty(pq));
printf("== Did we see all values we expected (expect 1)? %d\n", k == m + n);
pq_free(pq);
return 0;
}
您生成
val[n+m]pqnval[n]我无法重现您的结果，
sorted