如何按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;in_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 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; } 

Answer 1

我想你想改变这个：

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

至：

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

通过这种方式，它将超过所有具有相同优先级的优先级，并且更接近列表的末尾。 当您遍历到列表末尾时，这将保留对aux的引用。

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

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

Answer 2

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

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

Answer 3

因此，假设我们有优先级，项目元组(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 。

至于到货订单，您是指在函数调用方面的到货订单，还是作为您数据的一部分的其他到货订单？