Массив указателей, которые указывают на структуры

Question

Моя структура такова:

typedef struct celltag{
    char name[11];
    double time;
    struct celltag *next;
} celltype;

И структуры этого типа сохраняются в массиве связанных списков:

typedef celltype **Hash;

и две структуры X и Y связаны втот же список, если для некоторой заданной функции h(char x[]), h(X->name)=h(Y->name).Я пытаюсь сказать, что эти структуры сортируются в массив по их «именам».

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

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

Например, если у меня есть функция:

void sort(Hash A, celltype *PArray[MAX]){
}

, где *PArray[MAX] - это мой массив указателей, а в Hash A хранятся структуры.Как мне написать остальную часть функции?Как сделать указатель на структуру ??

Answer 1

Если вы все еще застряли, обзор того, что вам нужно будет сделать, - выполнить итерацию по вашей хеш-таблице (то есть по каждому блоку, а затем по каждому узлу списка, содержащегося в каждом блоке, чтобы ваш массив указателей указывал на каждыйзапись в вашей хеш-таблице. Неважно, как ваша хеш-таблица является ключевой, все, что вас волнует, это чтобы каждый использованный указатель в PArray указывал на celltype.

Я полагаю, вы знаете, какВыполните итерацию по вашей хеш-таблице. Просто выполните цикл от 0 до ht_size (где htsize - количество сегментов, например, элементов массива, в вашей хеш-таблице). Затем вы просто объявляете указатель celltype *p и повторяете списокуказывается записью сегмента (это может быть просто celltype*, где указатель next равен NULL, или это может быть любое число, основанное на столкновении хэшей, которое привело к более чем одному celltype* разрешению вbucket hashtable[x])

После того, как вы заполнили PArray, чтобы некоторое количество указателей nptr теперь указывало на celltype* в вашей хэш-таблице, все, что осталось, это вызвать qsort для сортировки указателей по элементу celltype->time.Единственная хитрость заключается в том, что вы должны написать функцию сравнение для сравнения смежных значений celltype->time.

Функция сравнения qsort имеет прототип:

int compare (const void *ap, const void *bp);

(где a и b - это указатели на сравниваемых соседних элементов. Я добавил p только для того, чтобы обозначить их как указатели)

Что мы сортируем? массив указателей от до celltype.Таким образом, каждый член массива уже является указателем, и если каждый параметр является указателем на ваши соседние элементы, то каждый параметр будет представлять указатель на указатель на celltype.

После того, как вы выяснили, что представляют ваши сравнительные указатели, вам нужно просто разыменовать параметры, чтобы получить доступ к элементу time в каждой структуре.Когда каждый параметр является указателем на указатель , вы можете преобразовать параметр в type * const * и разыменовать, чтобы предоставить вам указатель на тип , который можно использовать для сравнения timeзначения, например,

/* qsort compare for array of pointers to celltype */
int compare (const void *ap, const void *bp)
{
    celltype *a = *((celltype * const *)ap);
    celltype *b = *((celltype * const *)bp);

    return (a->time > b->time) - (a->time < b->time);
}

(для любого числового типа, возвращая результат двух условных выражений (a > b) - (a < b) для восходящей сортировки, просто избегает потенциального переполнения, которое может произойти, если вы вернете a - b, например, где a может быть большим отрицательным значением и b большим положительным значением, приводящим к переполнению)

Хотя вы не показываете, как объявляется A, вы показываете typedef для Hashчто при разыменовании будет указатель на celltype.Используя ht_size для представления количества сегментов в вашей хеш-таблице, ваша функция sort будет выглядеть примерно так:

void sort(Hash A, celltype *PArray[MAX]){

    size_t nptr = 0;

    for (size_t i = 0; i < ht_size; i++) {  /* loop over buckets */
        celltype *p = A[i];                 /* pointer to celltype */
        while (p) {                         /* iterate over all chained nodes */
            PArray[nptr++] = p;             /* assigning pointer to PArray */
            p = p->next
        }
    }

    qsort (PArray, ntpr, sizeof *PArray, compare);   /* call qsort */
}

Вот и все в двух словах.Если вам все еще не удается обернуть голову вокруг концепции qsort в приведенном выше частичном примере, короткий полный пример должен устранить путаницу, например

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

typedef struct celltag{
    char name[11];
    double time;
    struct celltag *next;
} celltype;

int compare (const void *ap, const void *bp)
{
    celltype *a = *((celltype * const *)ap);
    celltype *b = *((celltype * const *)bp);

    return (a->time > b->time) - (a->time < b->time);
}

int main (void) {

    celltype    c1 = { .name = "three", .time = 127.21 },
                c2 = { .name = "one", .time = 127.1 },
                c3 = { .name = "two", .time = 127.19 },
            *pc[] = { &c1, &c2, &c3 };
    size_t n = sizeof pc / sizeof *pc;

    qsort (pc, n, sizeof *pc, compare);

    for (size_t i = 0; i < n; i++)
        printf ("%-5s  %6.2f\n", pc[i]->name, pc[i]->time);
}

Пример использования / вывода

$ ./bin/qsort_ptp_struct
one    127.10
two    127.19
three  127.21

Посмотрите вещи и дайте мне знать, если у вас есть дополнительные вопросы.