我在实现任何类型的通用排序算法时遇到了一些麻烦。我已经有了一般的排序,但我不知道如何为我做的结构写一个比较函数。这些结构是汽车,它们有名称、型号、年份和价格。我在比较年份,并按升序排序。
到目前为止,我已经编写了与通用算法一起工作的字符串排序函数。我相信一般排序算法写得正确,它是在sort.c
中设计的:
#include "sort.h"
#include <string.h>
/* Swap two pointers. */
static
void swap(void** left, void** right) {
void* temp = *left;
*left = *right;
*right = temp;
}
/* Sort Array
* This function sorts the data stored in the array.
* The actual sorting routine is
* Bubble-Sort.
*/
void sort_array(void* Array[], unsigned size, int (*compare)(void*,void*))
{
int i;
int have_swapped = 1;
while (have_swapped) {
have_swapped = 0;
for (i = 0; i < size - 1; ++i ){
if (compare(Array[i],Array[i+1])) {
swap(&Array[i+1], &Array[i]);
have_swapped = 1;
}
}
}
}
我想我已经为compare_structs
写了正确的代码,但是当我试图运行程序时,它在终端进入无限循环。我不知道它为什么会这样。
我试图学习C和传递指针/函数作为参数。我想编写这个compare_structs
程序,使其符合sort.c
中的一般排序算法,因此我认为它必须返回-1
才能进行交换。我找不到导致无限循环的bug。任何帮助都是感激的!
sort_structs.c
:
#include <stdio.h>
#include <string.h>
#include "sort.h"
#include <stdlib.h>
/* Automobile */
struct automobile {
const char* name;
unsigned year;
unsigned price;
};
struct automobile one = { "AMC Pacer", 1975, 12900 };
struct automobile two = { "Cadillac Fleetwood", 1981, 4995 };
struct automobile three = { "Ford Pinto", 1971, 4200 };
struct automobile four = { "Suzuki X90", 1996, 1625 };
struct automobile five = { "Chrysler TC", 1991, 2495 };
struct automobile six = { "Cadillac Cimarron", 1986, 4990 };
struct automobile seven = { "Plymouth Prowler", 1997, 60000 };
struct automobile eight = { "Ford Edsel", 1958, 17000 };
struct automobile nine = { "Yugo", 1985, 3990 };
struct automobile ten = { "Pontiac Aztek", 2001, 603 };
/* Test Data
* Here I'm creating an array that points to the structures defined
*/
unsigned data_size = 10;
struct automobile* data[10] = {
&one,
&two,
&three,
&four,
&five,
&six,
&seven,
&eight,
&nine,
&ten
};
static
int compare_structs(void* left, void* right) {
struct automobile *x = left;
struct automobile *y = right;
int xYear = x->year;
int yYear = y->year;
if (xYear > yYear) return -1;
}
/* Test program
*
* This program tests sort_array with an array of automobile objects. Or
* rather, an array of pointers to automobile objects.
*/
int main() {
int i;
int status = EXIT_SUCCESS;
sort_array((void**)data, data_size, &compare_structs);
for(i = 0; i < data_size - 1; ++i) {
if (data[i]->year > data[i+1]->year) {
fprintf(stderr, ""%s" and "%s" are out of ordern",data[i]->name, data[i+1]->name);
status = EXIT_FAILURE;
}
}
return status;
}
为了使代码正常工作,我做了相当多的更改。我将尽我所能回忆并解释每一个错误。
1。调用sort_array
您最初像这样调用sort_array:
sort_array((void**)data, data_size, &compare_structs);
虽然它只需要(a)将数据变量强制转换为void*,并且(b)不需要在比较函数之前使用地址操作符。(如果你引用了一个函数,但没有调用它,语句作为函数的地址计算)
结果是:
sort_array((void*)data, data_size, compare_structs);
2。compare_structs的返回值只有当左侧的年份值大于右侧的年份值时,才返回compare_structs
的值。您应该返回3个值中的1个。-1、0和1便于升序/降序排序,0表示不需要交换。
if (xYear > yYear) return -1;
是
return (xYear - yYear);
3。检查compare的返回值你最初只检查退货是否有问题。您可以检查是否大于0或小于0,以允许升序/降序排序。因此,
if (compare(Array[i],Array[i+1]))
变成(对于升序排序)
if (compare(Array[i],Array[i+1]) > 0)
整理这些修改并使用一个小mod运行结果以打印输出,结果将以下内容打印到控制台。
0. - 1958
1. - 1971
2. - 1975
3. - 1981
4. - 1985
5. - 1986
6. - 1991
7. - 1996
8. - 1997
9. - 2001
最后,这里是完整的代码:
#include <stdio.h>
#include <string.h>
//#include "sort.h"
#include <stdlib.h>
//#include <string.h>
/* Swap two pointers. */
static
void swap(void** left, void** right)
{
void* temp = *left;
*left = *right;
*right = temp;
}
/* Sort Array
* This function sorts the data stored in the array.
* The actual sorting routine is
* Bubble-Sort.
*/
void sort_array(void* Array[], unsigned size, int (*compare)(void*,void*))
{
int i;
int have_swapped = 1;
while (have_swapped)
{
have_swapped = 0;
for (i = 0; i < size - 1; ++i )
{
if (compare(Array[i],Array[i+1]) > 0)
{
swap(&Array[i+1], &Array[i]);
have_swapped = 1;
}
}
}
i = 100;
}
/* Automobile
*/
struct automobile
{
const char* name;
unsigned year;
unsigned price;
};
struct automobile one =
{
"AMC Pacer",
1975,
12900
};
struct automobile two =
{
"Cadillac Fleetwood",
1981,
4995
};
struct automobile three =
{
"Ford Pinto",
1971,
4200
};
struct automobile four =
{
"Suzuki X90",
1996,
1625
};
struct automobile five =
{
"Chrysler TC",
1991,
2495
};
struct automobile six =
{
"Cadillac Cimarron",
1986,
4990
};
struct automobile seven =
{
"Plymouth Prowler",
1997,
60000
};
struct automobile eight =
{
"Ford Edsel",
1958,
17000
};
struct automobile nine =
{
"Yugo",
1985,
3990
};
struct automobile ten =
{
"Pontiac Aztek",
2001,
603
};
/* Test Data
* Here I'm creating an array that points to the structures defined
*/
unsigned data_size = 10;
struct automobile* data[10] =
{
&one,
&two,
&three,
&four,
&five,
&six,
&seven,
&eight,
&nine,
&ten
};
static
int compare_structs(void* left, void* right)
{
struct automobile *x = left;
struct automobile *y = right;
int xYear = x->year;
int yYear = y->year;
//if (xYear > yYear) return -1;
return (xYear - yYear);
}
/* Test program
*
* This program tests sort_array with an array of automobile objects. Or
* rather, an array of pointers to automobile objects.
*/
int main()
{
int i;
int status = EXIT_SUCCESS;
sort_array((void*)data, data_size, compare_structs);
for(i = 0; i < data_size - 1; ++i)
{
if (data[i]->year > data[i+1]->year)
{
fprintf(stderr, ""%s" and "%s" are out of ordern",data[i]->name, data[i+1]->name);
status = EXIT_FAILURE;
}
}
for (i=0; i<data_size; i++)
printf("%d. - %dn", i, data[i]->year);
return status;
}