У меня слишком много случаев при реализации кругового связанного списка в c

Question

Я реализую круговой связанный список в C, центральной частью которого является функция add2list(), которая добавляет узлы на основе поля int data в порядке возрастания. У меня есть 5 различных сценариев того, когда добавлять узел в функцию, что заставляет меня думать, что это слишком много. Большинство реализаций, которые я видел в google, имеют 2 или 3 случая. Однако большинство из этих реализаций также используют несколько функций для добавления узла (отдельная функция для добавления узла в начало/конец списка). Я был бы признателен за ваши отзывы, есть ли у меня случаи, которые могут быть объединены (например, случаи 2 и 4 очень похожи). Я добавил printList() функцию, если вы хотите распечатать список.

Это мой код:

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

typedef struct node * ptr; 
typedef struct node { 
    int data; 
    ptr next; 
}item; 

void add2list(ptr *head, int num); 
void printList(ptr p); 

int main() { 
    ptr head = NULL; 

    add2list(&head, 1); 
    add2list(&head, 2); 
    add2list(&head, 5); 
    add2list(&head, 3); 
    add2list(&head, 0); 
    add2list(&head, 4); 
    add2list(&head, -2); 
    printList(head); 

    return 0; 
} 


void add2list(ptr *head, int num) { 
    ptr p1, p2, t; 

    t = (ptr) malloc(sizeof(item)); 

    if(!t) { 
     printf("not enough memory\n"); 
     exit(0); 
    } 

    t -> data = num; 
    p1 = *head; 

    while(p1 != NULL && p1 -> next != *head && p1 -> data < num) { 
     p2 = p1; 
     p1 = p1 -> next; 
    } 

    if(!p1) { 
     //case 1 - if the list is empty 
     *head = t; 
     t -> next = *head; 
    } else if(p1 == *head) { 
     if(p1 -> data < t -> data) { 
      //case 2 - if we need to add a node to the end of the list if there was only one node before 
      (*head) -> next = t; 
      t -> next = *head; 
     } else { 
      //case 3 - if we need to add a node to the beginning of the list 
      while(p1 -> next != *head) { 
       p1 = p1 -> next; 
      } 
      p1 -> next = t; 
      t -> next = *head; 
      *head = t; 
     } 
    } else if(p1 -> data < t -> data){ 
     //case 4 - need to add a node at the end of the list if there's more than one node 
     p1 -> next = t; 
     t -> next = *head; 
    } else { 
     //case 5 - need to add a node in the middle 
     p2 -> next = t; 
     t -> next = p1; 
    } 
} 

void printList(ptr head) { 
    ptr tmp; 

    tmp = head; 
    while(tmp -> next != head) { 
     printf("%d ->\n", tmp -> data); 
     tmp = tmp -> next; 
    } 
    printf("%d ->\n", tmp -> data); 
} 

Answer 1

Вот моя попытка (предупреждение, код не тестировался):

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

typedef struct Node Node; 
struct Node { 
    int data; 
    Node *next; 
}; 

void add2list(Node **proot, int value) { 
    Node **pcur; 
    Node *new; 

    if (!(new = malloc(sizeof *new))) { 
     fprintf(stderr, "malloc(%zu): %s\n", sizeof *new, strerror(errno)); 
     exit(EXIT_FAILURE); 
    } 
    new->data = value; 

    if (!*proot) { 
     // case 1: insert into empty list 
     new->next = new; 
     *proot = new; 
     return; 
    } 

    if ((*proot)->data >= value) { 
     // case 2: insert at beginning of list 
     pcur = &(*proot)->next; 
     while (*pcur != *proot) { 
      pcur = &(*pcur)->next; 
     } 
     new->next = *proot; 
     *proot = *pcur = new; 
     return; 
    } 

    // case 3: insert elsewhere 
    pcur = &(*proot)->next; 
    while (*pcur != *proot && (*pcur)->data < value) { 
     pcur = &(*pcur)->next; 
    } 
    new->next = *pcur; 
    *pcur = new; 
} 

Функция первого выделяет новый узел и устанавливает его data элемент. Это является общим для всех трех случаев, как в вашем коде.

Корпус 1 вставляется в пустой список. Это довольно тривиально.

Дело 3 является «нормальным» случаем и почти идентично вставке в некруглый список (единственная разница - это проверка конца списка, которая включает NULL для некруглого списка). (Это относится к вашим случаям 2, 4, 5).

Случай 2 (ввод в начале) - это то, где он становится сложным. Этот случай является особенным, потому что здесь мы должны обновить две переменные, а не одну: переменную в вызывающем, *proot (потому что она должна быть обновлена ​​до новой главы списка), а также указатель next последнего узла в списке (чтобы держать его правильно круговым). В этом случае у нас есть дополнительный цикл, который просматривает весь список, чтобы найти адрес последнего next указателя в списке (хранится в pcur). В конце мы обновляем *proot и *pcur вместе. (Это ваш случай 3.)

Answer 2

Да, есть, безусловно, слишком много случаев. Вам следует избегать ситуаций, подобных этим, и использовать подход сверху вниз, когда это возможно. Выполнение этого кода будет более чистым и более удобным. Кроме того, вы можете повторно использовать функции всякий раз, когда вам это нужно, и если вы обнаружите ошибку внутри функции, это вопрос исправления функции, чтобы все было нормально.