c - 指向结构的指针数组

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] 是我的指针数组，哈希 A 是存储结构的地方。我该如何编写其余的功能？如何让一个指针指向一个结构体？？

Answer 1

如果您仍然卡住，您需要做的概述是遍历哈希表(即遍历每个桶，然后遍历每个桶中包含的列表的每个节点，以使您的指针数组指向每个哈希表中的条目。哈希表的键控方式无关紧要，您所关心的只是使 PArray 中的每个使用指针指向 celltype。

我假设您知道如何遍历哈希表。只需从 0 循环到 ht_size(其中 htsize 是哈希表中桶的数量，例如数组元素)。然后，您只需声明一个 celltype *p 指针并迭代存储桶条目指向的列表(它可以只是单个 celltype*，其中 next 指针为 NULL，或者它可以是基于哈希冲突的任何数字，该哈希冲突导致多个 celltype*解析到桶 hashtable[x] )

一旦您填充了 PArray 以便一些指针 nptr 现在指向哈希表中的 celltype*，剩下的就是调用 qsort 以按 celltype->time 成员对指针进行排序。唯一的技巧是您必须编写 compare 函数来比较相邻的 celltype->time 值。

qsort比较函数原型(prototype):

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

检查一下，如果您还有其他问题，请告诉我。