1

我想按用户输入的优先级对列表项进行排序，它做得很好。但是，当有多个具有相同优先级的项目时，它不会像预期的那样按到达顺序对它们进行排序。

对不起，如果我说得不够清楚，以便您理解。变量的名称是葡萄牙语，所以如果您不明白，请询问。

这是代码：

typedef struct pedido pedido, *ppedido;

struct pedido{
    char id[5];
    int prioridade;
    int mesa, n_pratos;
    struct prato *prato[TAM];
    ppedido prox;
};

struct prato{
    char id[5];
};

ppedido novo_pedido(ppedido lista)
{
    ppedido novo, aux, anterior = NULL;
    int i;

    novo = (struct pedido*)malloc(sizeof(pedido));

    if(novo == NULL){
        printf("Erro na alocacao de memoria...\n");
        return;
    }

    printf("Number of menus: ");
    scanf("%d", &novo->n_pratos);

    printf("Table number: ");
    scanf("%d", &novo->mesa);

    printf("Priority of request? ");
        scanf("%d", &novo->prioridade);

        printf("Introduza o ID do pedido: ");
        scanf("%s", &novo->id);

    for(i=0;i<novo->n_pratos;i++){
        printf("ID of menu %d: ", i+1);  //something like "M1, M4..." doesn't matter
        scanf("%s", &novo->prato[i]);
        fflush(stdin);
    }

    novo->prox=NULL;

    if(lista == NULL || novo->prioridade > lista->prioridade) { 
        novo->prox = lista; 
        lista = novo; 
    }
    else
    { 
        aux = lista;

        while(aux != NULL && novo->prioridade < aux->prioridade)   //this is where it should be sort requests by their priority and order of arrival
            aux = aux->prox; 
        novo->prox = aux->prox; 
        aux->prox = novo;
    }
    return lista;
}
4

3 回答 3

0

我在您发布的代码中没有看到任何排序，但大多数排序算法都不稳定。这意味着它们通常不会保留被认为“相等”的元素的顺序。

您要么需要切换到稳定排序，要么更改比较函数以在优先级相等时考虑“到达时间”。

于 2012-06-22T17:32:02.847 回答
0

我想你想改变这个：

while(aux != NULL && novo->prioridade < aux->prioridade)

到：

while(aux->prox != NULL && novo->prioridade <= aux->prox->prioridade)

这样，它将超越所有具有相同优先级的优先级，并靠近列表的末尾。当您遍历到列表末尾时，这将保留对 aux 的引用。

我假设在您的搜索中，一旦找到最高优先级，您就会停止。

这假设进入列表的顺序与到达的顺序相同。

于 2012-06-22T17:38:26.677 回答
0

因此，假设我们有优先级，项目元组(priority, item)，并且item是我们示例的字符。

NULL

列表开始为空。我们开始插入。

(1, x)
NULL

...

(3, z)
(2, y)
(1, x)
NULL

现在我们插入(0, a).

评估if为假，aux = lista指向(3, z).

while前进直到aux指向。NULL

然后：

    novo->prox = aux->prox; 
    aux->prox = novo;

但是aux是NULL。

至于到达顺序，您是指调用函数的到达顺序，还是属于您数据一部分的其他到达顺序？

于 2012-06-22T17:38:43.450 回答