c - 使用指针数组对结构进行排序的函数存在问题

Question

这里我对我的作业和代码中的问题进行了非常详细的解释。作业有两部分，第一部分的代码可以工作，但是第二部分修改后就不行了。

作业:使用字典保存人名和最快运行时间(使用开放散列，即字典用哈希表表示，哈希表是一个包含 B 个元素的数组，其中每个元素该数组是 celltype 类型元素的链表。哈希表使用哈希函数 h(name)，其中 i=1,...,B-1，如果 h(name)=i，则有关该人的数据“姓名”保存在字典第 i 个元素的链表中。人员按姓名排序。)

它的样子是这样的。

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

typedef celltype **Dictionary;

int h(char name[]){
    int i, sum=0;
    for(i=0;name[i]!='\0';i++) {
        sum+=name[i];
    }
    return sum % B;
}

void DiMakeNull (Dictionary *Ap){
    int i;
    for(i=0;i<B;i++) (*Ap)[i]=NULL;
}

void DiInsert(char name[], double time, Dictionary *Ap){
    int bucket;
    celltype *oldheader;
    if(DiMember(name, *Ap)==0){
        bucket=h(name);
        oldheader=(*Ap)[bucket];
        (*Ap)[bucket]=(celltype*)malloc(sizeof(celltype));
        strcpy((*Ap)[bucket]->name, name);
        (*Ap)[bucket]->time= time;
        (*Ap)[bucket]->next=oldheader;
    }
}

(如果 person 在字典中，则 Function DiMember(char name[], Dictionary A) 返回 1，否则返回 0。)

这部分按其应有的方式工作。

现在，作业的下一部分:使用另一个指针数组对人们的运行时间进行排序，其中数组的第一个元素指向最快的人的数据，第二个元素指向第二快的人的数据人等

我的想法是制作另一个字典，我们称之为字典数组。 现在，在将新人的数据插入原始字典 Ap 时，我想调用另一个函数 void Sort(celltype *Data, Dictionary *Array) ，该函数接受存储新人数据的单元类型以及我们将在其中插入的数组它按时间排序。

因为我会在DiInsert中使用这个，所以我将其修改为

void DiInsert(char name[], double time, Dictionary *Ap, Dictionary *Array){
    int bucket;
    celltype *oldheader;
    if(DiMember(name, *Ap, 0)==0){
        bucket=h(name);
        oldheader=(*Ap)[bucket];
        (*Ap)[bucket]=(celltype*)malloc(sizeof(celltype));
        strcpy((*Ap)[bucket]->name, name);
        (*Ap)[bucket]->time= time;
        (*Ap)[bucket]->next=oldheader;

        celltype *send;
        send=(*Ap)[bucket];
        send->next=NULL;
        Sort(send, Array);
    }
}

(一切都是一样的，除了我在函数中添加了另一个参数，并且我在末尾添加了该位 (celltype *send; ... Sort(send, Array);)。)

这就是函数的样子:

void Sort(celltype* Data, Dictionary *Array){
     if ((*Array)[0]==NULL){
         (*Array)[0]=Data;
         (*Array)[0]->next=NULL;
     }

    else{
        int i;
        for(i=0;(*Array)[i]!=NULL;i++){
            if(Data->time < (*Array)[i]->time){
                celltype *new;
                new=(*Array)[i];
                (*Array)[i]=new;
                (*Array)[i]->next=NULL;
                int j=i+1;
                while((*Array)[j]!=NULL){
                    celltype *old;
                    old=(*Array)[j];
                    (*Array)[j]=new;
                    (*Array)[j]->next=NULL;
                    new=old;
                    j++;
                }
                (*Array)[j]=new;
                (*Array)[j]->next=NULL;
                break;
            }
        }
    }
}

这些是我的问题:

1. 函数Sort/函数参数的调用有问题。我在理解指针方面仍然存在一些问题，所以我不太确定如何解决它。

2. 在修改 DiInsert 之前，第一段代码有效。现在，在修改并添加 void Sort() 后，由于某种原因，它有时会将原始 Dictionary Ap 中的数据加倍并将其保存在正确的第 i 个括号中，但也会保存在其他一些括号中。

3. 它还将字典数组中的数据加倍。例如，如果我输入“Mark”作为姓名，10.1作为时间，则h(Mark)=15，因此它将Mark的数据保存在字典Ap的第15括号中。然后，它将 Mark 的数据保存在字典数组的第 0 个括号中(这是应该的，因为 Mark 的数据是第一个输入的数据，而且他目前是最快的)，但随后它也将其保存在第 16 个括号中。为什么？

Answer 1

您通常不能使用字典来存储排序结果，因为这些是为快速随机访问而不是排序访问而设计的数据结构。您应该使用一个数组并对该数组进行排序。

但是由于您已经拥有字典中的所有元素，因此生成数组然后进行排序将很简单。毕竟这是一项作业，我只会勾勒出这个想法，然后让你填写其余的:

1. 计算字典中 celltype 元素的数量并将其存储到 total_elements
2. 分配一个 celltype * 类型、长度为 total_elements、名称为 sort_array 的新数组
3. 编写一个函数，遍历字典并将每个 celltype 元素的地址添加到 sort_array
4. 编写一个合适的比较函数，使用名称 sort_compare_func() 实现您想要实现的排序顺序
5. 使用 sort_compare_func() 对 sort_array 和 total_elements 运行排序算法

我不确定您的作业是否要求您实现自己的排序算法。我的代码片段将使用标准 POSIX 函数 qsort():

// compare function for sort algorithm
static int sort_compare_func(const void *a, const void *b) {
     // called with pointers to (celltype *) elements in array
     double timeA = (*(celltype **) a)->time;
     double timeB = (*(celltype **) b)->time;

     // <  0 : a faster than b
     if (timeA < timeB) return(-1);
     // >  0 : b faster than a
     if (timeB < timeA) return( 1);
     // == 0 : a same time as b
     return(0);
}
....

unsigned int total_elements = count_elements_in_dictionary(Ap);
celltype **sort_array       = malloc(total_elements * sizeof(celltype *));

// fill the array
fill_sort_array_from_dictionary(Ap, sort_array);

// sort_array[0]                  points to the first celltype element found in Dictionary
// sort_array[total_elements - 1] points to the last  celltype element found in Dictionary

// sort array using POSIX quick sort implementation
qsort(sort_array, total_elements, sizeof(celltype *), sort_compare_func);

// sort_array[0]                  points to the celltype element with the smallest time
// sort_array[total_elements - 1] points to the celltype element with the largest time

celltype *winner = sort_array[0];
printf("and the winner is: %s with %f\n", winner->name, winner->time);

<小时/>

简单测试代码:100个元素，随机时间从0到100:

#include <stdlib.h>
#include <time.h>

.... 
unsigned int total_elements = 100;
....
//fill_sort_array_from_dictionary(Ap, sort_array);
srand(time(NULL));
celltype *data = malloc(total_elements * sizeof(celltype));
for (int i = 0; i < total_elements; i++) {
   sprintf(data[i].name, "%04d", i);
   data[i].time  = (rand() * 100.0) / RAND_MAX;
   sort_array[i] = &data[i];
}
...

一些测试运行:

$ gcc -Wall -o dummy dummy.c
$ ./dummy 
and the winner is: 0085 with 0.165149
and the looser is: 0066 with 99.612887
$ ./dummy 
and the winner is: 0044 with 0.484525
and the looser is: 0006 with 98.964099
$ ./dummy 
and the winner is: 0066 with 0.293111
and the looser is: 0016 with 99.822637

<小时/>

希望这有帮助。