Создание упорядоченного связанного списка в C

Question

Я ищу, чтобы создать способ вставки структуры в порядке возрастания по PID.

Я проверял другие темы, и я написал что-то, как это упоминали другие, но я получаю ошибки при компиляции относительно Next_PCB и типа конфликтов.

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

struct PCB *ptr, *tmp; 

void insert_ordered (struct PCB *, struct PCB *); 
void print_list(struct PCB *); 

main() 
{ 
    int num_structs, i; 
    ptr = (struct PCB *) malloc (sizeof (struct PCB)); 
    num_structs = 10 + (rand() % 10); 
    for (i = 0; i < num_structs; i++) 
    { 
     tmp = (struct PCB *) malloc (sizeof(struct PCB)); 
     tmp->PID = rand() % 20; 
     tmp->Next_PCB = NULL; 
     insert_ordered(ptr, tmp); 
    } 
    print_list(ptr); 
} 

void insert_ordered (struct PCB *Head, struct PCB *Add) 
{ 
    struct PCB* new; 
    if(*Head == NULL || *Head->PID >= Add->PID) 
    { 
     Add->Next_PCB = *Head; 
     *Head = Add; 
    } 
    else 
    { 
     new = *Head; 
     while (new ->Next_PCB!=NULL && new->Next_PCB->PID < Add -> PID) 
     { 
      new = new->Next_PCB; 
     } 
     Add->Next_PCB = new->Next_PCB; 
     new->Next_PCB = Add; 
    } 
} 

Функция insert_ordered где проблема происходит, и то, как я работаю с структурами является то, что вызывает проблемы, так что я интересно, что я делаю неправильно в отношении самого метода, а также структуры.

Answer 1

Вы спрашиваете, почему компилятору не понравится код в insert_ordered().

Когда я передал ваш код GCC, у него было 5 проблем с функцией, и все они были связаны с тем, что вы обрабатывали *Head в качестве указателя, когда он является экземпляром struct PCB.

*Head не является указателем, чтобы сделать его указателем, у прототипа функции должно быть struct PCB **Head. Затем Head является указателем на указатель: он указывает на переменную, принадлежащую вызывающей стороне, которая в свою очередь является указателем на головку списка.

Таким образом, код будет:

void insert_ordered (struct PCB **Head, struct PCB *Add) 
{ 
    struct PCB* new; 
    if ((*Head == NULL) || ((*Head)->PID >= Add->PID)) 
    { 
    Add->Next_PCB = *Head; 
    *Head = Add; 
    } 
    else 
    { 
    new = *Head; 
    while ((new->Next_PCB != NULL) && (new->Next_PCB->PID < Add->PID)) 
    { 
     new = new->Next_PCB; 
    } 
    Add->Next_PCB = new->Next_PCB; 
    new->Next_PCB = Add; 
    } 
} 

Конечно, вызов insert_ordered() должен быть изменен на insert_ordered(&ptr, tmp) ;

Это работает, но, как сказал Бенджи, это не большой алгоритм. Я предполагаю, что это учебное упражнение, и что в следующем уроке вам будет показано двоичное дерево.

Кстати, в if ((*Head == NULL) || ((*Head)->PID >= Add->PID)) Я добавил несколько ненужных скобок. Это потому, что, хотя код без скобок недвусмыслен для компилятора, он смущает некоторых моих коллег. Дополнительные скобки делают его более читабельным ... если вы не получаете слишком много из них. Но нужны скобки в (*Head)->PID.

Answer 2

Там, по крайней мере несколько проблем, которые я, возможно, не нашел их все, но вот что я вижу:

• Вы должны быть в состоянии изменить значение указателя головки во вставке рутина. Ваша процедура вставки, похоже, написана для этого, поскольку вы уже выполняете операции типа «* Head == NULL». Что вам нужно знать, это правильно объявить «struct PCB ** Head» и передать его правильно «insert_ordered» (& ptr, tmp) ».
• Вы должны правильно обрабатывать начальное значение ptr. Вы занимаете место для этого, но ничего не вкладываете в него. Вместо этого вы должны заменить этот malloc назначением на NULL: «ptr = NULL».