C Insert Element At Beginning of Linked List

问题:

I have written a program in C that is designed to insert structures in an ascending order into a Linked List.

The problem is that is is not inserting my two lowest values (1 and 2). This is because I don't currently have a working handler to check if the first value of the linked list is already greater than the given.

Here is my function:

struct PCB
{
    struct PCB *Next_PCB ;
    int PID ;
};

void insert_ordered (struct PCB *Head, struct PCB *Add)
{
    tmp = Head;
    if (Head->PID == 0) {
        Head->PID = Add->PID;
    } else {
        if (Head->Next_PCB == NULL) {
            Head->Next_PCB = Add;
        } else {
            int count = 0;
            while (Head != NULL) {
                if (Add->PID > Head->PID) {
                    if (Head->Next_PCB != NULL) {
                        Head = Head->Next_PCB;
                        count++;
                    } else {
                        Head->Next_PCB = Add;
                        break;
                    }
                } else if (Add->PID == Head->PID) {
                    Add->Next_PCB = Head->Next_PCB;
                    Head->Next_PCB = Add;
                    break;
                } else if (Add->PID < Head->PID) {
                    if (Add->PID == 1 || Add->PID == 2) {
                        printf("found 1 or 2");
                        printf("count: %d", count);
                    }
                    int ct = 0;
                    while (tmp != NULL) {
                        if (count == 0) {
                            printf("made it, %d", ct);
                            Add->Next_PCB = tmp;
                            break;
                        } else if (ct == (count - 1)) {
                            Add->Next_PCB = Head;
                            tmp->Next_PCB = Add;
                            break;
                        }
                        tmp = tmp->Next_PCB;
                        ct++;
                    }
                    break;
                }
            }
        }
    }
    printf("pid : %d\n", Add->PID);
}

Here is my output after printing out the list:

pid : 6
pid : 17
pid : 15
pid : 13
pid : 15
pid : 6
pid : 12
pid : 9
found 1 or 2count: 0made it, 0pid : 1
found 1 or 2count: 0made it, 0pid : 2
pid : 7
pid : 10
pid : 19

-------------------
PID: 6
PID: 6
PID: 7
PID: 9
PID: 10
PID: 12
PID: 13
PID: 15
PID: 15
PID: 17
PID: 19

The output SHOULD have a 1 and a 2 before the two sixes. Can anybody help me out? Thanks.

回答1:

void insert_ordered (struct PCB *Head, struct PCB *Add) : It is not possible to replace the head of the elements in this interface. So, you need to the first element in the dummy elements(Anchor node that is not intended contents of the holding).
The following is a specific example:

#include <stdio.h>
#include <stdlib.h>

struct PCB{
    struct PCB *Next_PCB ;
    int PID ;
};

struct PCB *new_PCB(int PID){
    struct PCB *pcb = malloc(sizeof(*pcb));
    if(pcb != NULL){
        pcb->Next_PCB = NULL;
        pcb->PID = PID;
    }
    return pcb;
}

void insert_ordered (struct PCB *Head, struct PCB *Add){
    if(Head == NULL)
        return ;//can't

    struct PCB *prev = Head, *curr = Head->Next_PCB;
/*  this is reduced to following while-loop
    if(Head->Next_PCB == NULL){//empty list
        Head->Next_PCB = Add;
        return ;
    }
    if(Add->PID <= curr-> PID){//Add node <= Top node
        prev->Next_PCB = Add;
        Add->Next_PCB = curr;
        return ;
    }
*/
    while(curr != NULL && curr->PID < Add->PID){
        prev = curr;
        curr = curr->Next_PCB;
    }
    prev->Next_PCB = Add;
    Add->Next_PCB = curr;
}

void print(struct PCB *Head){
    if(Head == NULL)
        return ;
    else
        Head = Head->Next_PCB;
    while(Head != NULL){
        printf("PID: %d\n", Head->PID);
        Head = Head->Next_PCB;
    }
}

//alias
#define Make_list() new_PCB(-1)

int main(void){
    struct PCB *head = Make_list();
    //struct PCB *head = new_PCB(-1);//dummy node, This is intended to holds a list.
    insert_ordered (head, new_PCB( 6));
    insert_ordered (head, new_PCB(17));
    insert_ordered (head, new_PCB(15));
    insert_ordered (head, new_PCB(13));
    insert_ordered (head, new_PCB(15));
    insert_ordered (head, new_PCB( 6));
    insert_ordered (head, new_PCB(12));
    insert_ordered (head, new_PCB( 9));
    insert_ordered (head, new_PCB( 1));
    insert_ordered (head, new_PCB( 2));
    insert_ordered (head, new_PCB( 7));
    insert_ordered (head, new_PCB(10));
    insert_ordered (head, new_PCB(19));

    print(head);
    //release list
    return 0;
}

Or you need to swap the contents like a sort.