Блог

Главная - Вопросы по программированию - Как создать вложенный список на C, используя формат структуры единого связанного списка, который содержит указатель void и рекурсивный указатель на структуру?

Как создать вложенный список на C, используя формат структуры единого связанного списка, который содержит указатель void и рекурсивный указатель на структуру?

#c #list #recursion #casting #void-pointers

#c #Список #рекурсия #Кастинг #void-указатели

Вопрос:

Задача состоит в том, чтобы отсортировать существующий список по длине в другой вложенный список.

 ["x", "yy", "zzz", "f", "gg"] ergeben 
 [["x", "f"], ["yy",
"gg"], ["zzz"]]

Я подумываю об использовании указателя void в узле Struct для хранения другого списка, т.е. Списка в каждом узле основного списка. Но я продолжаю получать следующую ошибку

 dereferencing 'void *' pointer

Я тоже пробовал типизацию. Могут быть и другие проблемы, но я еще не добрался до них из-за вышеупомянутой проблемы.

 typedef struct Node {
    void *value;
    struct Node *next; // self-reference
} Node;

// Group elements in list. Equivalent elements (for which equivalent is true) are put
// in the same group. The result is a list of groups. Each group is itself a list.
// Each group contains items that are equivalent.

Node *group_list(Node *list, EqualFun equivalent) {
    
    Node *list_new = malloc(sizeof(Node));
    //list_new = NULL;
    list_new->next = NULL;
    (Node *)list_new->value = malloc(sizeof(Node));
    (char *)(list_new->value->value) = list->value;
    list_new->value->next = NULL;
    Node *temp1 = list->next;
    
    Node *list_tester1 = list_new;
    Node *list_tester2 = list_new;
    
    while (list_new != NULL) {
        
        while (temp1 != NULL) {  //for the list inside list_new
            list_tester2 = list_tester1;
            if (equivalent(list_new->value->value, temp1->value)) {
                list_new->value = append_list(list_new->value, temp1->value);
            } else {     
                while (list_tester2 != NULL) { // for outer list
                    if (!equivalent(list_tester2->value->value, temp1->value)) {
                        list_new = append_list(list_new->value, temp1->value);
                        list_new = append_list(list_tester2->value, temp1->value);
                        list_new = append_list(list_tester1->value, temp1->value);       
                    }        
                    list_tester2 = list_tester2->next;   
                }
            }
            list_new = list_new->next;
        }
    }
    return list_new;
}

Комментарии:

1. void* это указатель, который указывает на объект неполного типа. Вы не можете разыменовать void* указатель. У компилятора нет способа определить результирующий тип. Например. list_new->value->next=NULL; разыменования value , которые есть void* (и это делается много раз в вашем коде). Приведенное выше утверждение, которое вы приводите перед разыменованием с (char *)(list_new->value->value)=list->value; помощью — которое лишь частично решает проблему, требующую вместо этого чего-то похожего на ((char *)(list_new->value)->value=list->value; Using void* , прекрасно, но поймите ограничения.

Ответ №1:

Если во время компиляции известна максимальная длина слова (и, следовательно, максимальное количество вложенных списков), вы можете создать массив указателей на заголовки отдельных вложенных списков. Первый элемент массива будет указывать на вложенный список со словами длиной один, второй элемент массива будет указывать на вложенный список со словами длиной два и т.д.

Если вы хотите вместо этого иметь связанный список связанных списков (т. Е. Вложенный связанный список), вам придется создать два типа узлов. Один тип узла будет для основного связанного списка, а один тип узла — для вложенных списков.

Например, вы могли бы определить следующие две структуры:

 struct SubListNode
{
    char *word;
    struct SubListNode *next;
};

struct MainListNode
{
    struct SubListNode *head_of_sublist;
    struct MainListNode *next;
};

Я не вижу причин использовать указатель void в этом случае, поскольку тип ссылочного объекта всегда известен.

Хотя оба списка могут использовать один и тот же struct указатель void, так что вам нужно только объявить один struct , я не вижу в этом никакой пользы. Всякий раз, когда разыменовывается указатель void, вам нужно будет привести его к соответствующему типу, на который он указывает. Это сделает ваш код намного сложнее, чем простое объявление второго типа struct .

Метки: