如何按C中的优先级对列表项进行排序？

我想根据用户输入的优先顺序对列表项进行排序，并且它做得很好。但是，当有多个具有相同优先级的项目时，它不会按照它应该的到达顺序对它们进行排序。如何按C中的优先级对列表项进行排序？

对不起，如果我没有足够清楚，以便您能理解。变量的名字是用葡萄牙语的，所以如果你不明白的话，请问。

下面是代码：

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; 
}

来源

2012-06-22 Rodrigo

你的代码应该如何知道什么时候到了？ – Joe

我询问请求的细节，并将它们放入列表中，当函数再次被调用时，列表已经有了。因此，在第一个菜单出现后，问菜单后问问吧？ – Rodrigo

我想你想改变这一点：

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

要：

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

这样就会晃过所有相同的优先级的那些，并放在接近结束的名单。当您遍历到列表的末尾时，这将保持对aux的引用。

我认为在您的搜索中，只要您找到最高优先级，就会停下来。

此处假设进入清单的顺序与到货顺序相同。

来源

2012-06-22 17:38:26 Justin

就是这样！它像我想要的那样工作！谢谢。 – Rodrigo

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

您可能需要切换到稳定排序，或者在优先级相同时更改比较功能以考虑“到达时间”。

来源

2012-06-22 17:32:02

所以，假设我们有优先权，项目元组(priority, item)和item是我们示例的一个字符。

NULL

列表从NULL开始。我们开始插入。

(1, x) 
NULL

...

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

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

if评估为false，aux = lista指向(3, z)。

while前进直到aux指向NULL。

然后：

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

但aux是NULL。

至于到货订单，是指到达订单的函数调用，还是其他到达订单的数据的一部分？

来源

2012-06-22 17:38:43

我的意思是调用函数。 – Rodrigo

你想要后进先出还是先进后出？ –

如何按C中的优先级对列表项进行排序？

回答

相关问题