c - 你如何在 C 中将结构成员排序到队列中？

Question

我有一个名为 patients 的结构需要组织。它应该按照患者 ID 给定的顺序将患者添加到队列中。然而，那些严重程度较高的人可以插在队列前面。我正在处理的任务要求我们为队列使用 C 和结构。目标是创建离散事件模拟示例。

我不确定如何合并结构。我试图查找使用结构的代码，但它们似乎都使用数组。到目前为止，我已经基本实现了 FIFO。

例如，我如何使用我创建的这个结构:

struct patients{
    int id;
    int severity;
    char *firstName;
    char *lastName;
    char *state;
    double time_spent;
};

按ID入队/按严重性调整

ListNode* startPtr = malloc(sizeof(ListNode));
    struct patients p1;
    struct patients p2;
    struct patients p3;
    struct patients p4;
    /*patient 1 specification */
    p1.id=1;
    p1.severity=2;
    p1.firstName="Joe";
    p1.lastName="C";
    p1.state="Patient has arrived";
    p1.time_spent = 0;
    /*patient 2 specification */
    p2.id=2;
    p2.severity=3;
    p2.firstName="Sam";
    p2.lastName="W";
    p2.state="Patient has arrived";
    p2.time_spent = 0;
    /*patient 3 specification */
    p3.id=3;
    p3.severity=2;
    p3.firstName="Mary";
    p3.lastName="L";
    p3.state="Patient has arrived";
    p3.time_spent = 0;
    enqueue(p1.id);
    enqueue(p2.id);
    enqueue(p3.id);

鉴于这些规范，我希望队列返回这样的顺序:Sam (severity=3) -> Joe (Severity=2, but id=1) -> Mary (Severity=2, id=3 )

void enqueue(ListNode* *startPtr, char value){
    ListNode* newPtr = malloc(sizeof(ListNode));
    if(newPtr == NULL){
        printf("Not enough memory");
        return;
    }
    newPtr->data = value;
    newPtr->nextPtr = NULL;
    ListNode* currentPtr = *startPtr;
    //shifting current ptr until we find the last element
    while(currentPtr->nextPtr!=NULL){
        currentPtr = currentPtr->nextPtr;
    }
    //currentPtr is now the last Node of the queue
    currentPtr->nextPtr = newPtr;
}

Answer 1

您可以将指向每个结构的指针传递到入队函数中，或者，如果患者结构不是持久的，则传递整个结构。您需要确保入队函数具有每个患者的 ID 和严重程度值，以便它可以基于这两个值进行插入。

enqueue(&p1);

或

enqueue(p1);

以下未经测试 的代码将假设您正在传递一个指向入队函数的指针，因为如果结构是持久的，这是首选。

接下来，您的入队函数需要先根据严重性插入，然后根据 ID 插入。反之则不然，因为严重性用作主要排序键，而 id 是次要排序键。我们可以通过遍历列表直到找到不大于要插入节点的严重性的严重性来完成此操作。如果 severity 相等，那么我们需要继续迭代，直到找到一个 id 大于要插入的节点的 id，或者直到 severity 降低。至此，插入点已经找到。

void enqueue(ListNode** startPtr, struct patients* p){
    ListNode* newPtr = malloc(sizeof(ListNode));
    if(newPtr == NULL){
        printf("Not enough memory");
        return;
    }

    newPtr->data = p;
    newPtr->nextPtr = NULL;
    ListNode* currentPtr = *startPtr;

    //shifting current ptr until we find where severity is equal to the new node's severity 
    // AND until the id is larger than the following node
    // OR until the end of the list is reached
    while(currentPtr->nextPtr != NULL &&
        currentPtr->nextPtr->data->severity > p->severity ||
        (
            currentPtr->nextPtr->data->severity == p->severity && // the severity is the same, but the ids are out of order still
            currentPtr->nextPtr->data->id < p->id
        )
    ){
        currentPtr = currentPtr->nextPtr;
    }

    // currentPtr is now the node directly before the node to be inserted
    // now we insert newPtr into the list
    newPtr->next = currentPtr->nextPtr;
    currentPtr->nextPtr = newPtr;
}

如果您不将结构作为指针传递给入队函数，那么您需要记住为数据分配内存。此外，此实现可能会根据您如何实现链表(是否使用虚拟头节点)而改变

还要记住将 ListNode 结构中“data”的数据类型从 int 更改为 struct patients*