根据两个字段的值对链表中的结构进行排序

Question

我想对优先级队列中具有相同优先级的值进行排序。一切都从一个简单的 .txt 文件加载。我已经对所有优先级进行了排序，但现在我想对具有相同优先级的值进行排序。

我的代码比较简单。它有 push 和 pop 功能，你猜对了，push 和 pop 哈哈。

ispis 函数专为打印而设计。我也知道声明一个虚拟节点不是一个好主意，但他们在大学里教过我们这种方式，所以我对它很满意。

这是我想如何对元素进行排序的示例：

例如

10 1 
2 1
3 1

至

2 1 
3 1
10 1

我的代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct cvor* Red;
struct cvor {
    int el, pr;
    Red next;
};
void push(Red R, int b, int p);
void print(Red R);
void pop(Red R);

int main() {
    FILE* dat;
    int br, pr;
    struct cvor Head;
    Head.next = NULL;
    dat = fopen("redsp.txt", "r");

    if (!dat) {
        printf("No file!\n");
    }
        
    while (fscanf(dat, "%d %d", &br, &pr) != EOF) {
        push(&Head, br, pr);
    }
        
    printf("Printing:\n");
    print(Head.next);

    /*printf("\n\n\n");
    printf("poppin:D\n");
    for (int i = 0; i < 14;i++) {
        pop(&Head);
        printf("\n\n\n");
        print(Head.next);
    }*/

    fclose(dat);    
}

void push(Red R, int b, int p) {
    Red q;
    q = (Red)malloc(sizeof(struct cvor));

    q->el = b;
    q->pr = p;

    /*if (q->pr >p) {
        q->next = R;
        R = q;
    }*/

        while (R->next != NULL && R->next->pr < p)
        {   
            R = R->next;
        }
            
        q->next = R->next;
        R->next = q;    
    
}

void pop(Red R) {
    Red temp, pre;
    temp = R->next;
    pre = NULL;

    while (temp && temp->next) {
        pre = temp;
        temp = temp->next;
    }
    if (pre) {
        free(pre->next);
        pre->next = NULL;
    }

}


void print(Red R) {
    while (R != NULL)
    {
        printf("%d %d\n", R->el, R->pr);
        R = R->next;
    }
}

Answer 1

据我了解你的问题，问题是如何比较基于两个值的数据。

行

    while (R->next != NULL && R->next->pr < p)

检查列表的末尾并比较节点结构的一个字段。

为了让代码更清晰，我建议用函数调用来代替比较。

void push(Red R, int b, int p) {
    Red q;
    q = (Red)malloc(sizeof(struct cvor));

    q->el = b;
    q->pr = p;

    while (R->next != NULL && compare_nodes(R->next, q) < 0)
    {   
        R = R->next;
    }
            
    q->next = R->next;
    R->next = q;    
}

您当前的比较可以实现为

/**
 * Compare two nodes.
 *
 * This implementation compares only the pr fields.
 *
 * @param a Pointer to node A.
 * @param b Pointer to node B.
 *
 * @retval <0 if A < B
 * @retval 0  if A == B
 * @retval >0 if A > B
 */
int compare_nodes(const struct cvor *a, const struct cvor *b) {
    /* here only the "pr" element is compared */
    int retval = a->pr - b->pr;
    return retval;
}

您可以扩展该功能以比较其他结构字段，如果第一个字段的比较结果是“相等”。

int compare_nodes(const struct cvor *a, const struct cvor *b) {
    /* compare pr field first */
    int retval = a->pr - b->pr;
    /* compare el field if necessary */
    if (retval == 0) retval = a->el - b->el;
    return retval;
}

请注意，在生产代码中，函数应确保参数不是 NULL 指针，而不是依赖调用者。

根据两个字段的值对链表中的结构进行排序

Sorting structures in a linked list based on the values of two fields

c

queue

linked-list

priority-queue