使用 qsort 和结构对列表进行排序
Using qsort and structs to sort a list
我是 C 语言的初学者,我正在使用 structs.I 尝试创建一个对日期列表进行排序的程序。用户首先输入日期数,然后输入日期本身,即月、日和年。然后使用 qsort 我想按时间顺序排序(首先按年然后按月然后按天)。我试图首先对年份进行排序,但我只得到我的输出为“0”。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char* month;
int day;
int year;
} date;
int sort(const void* a, const void* b)
{
date* date1 = (date*)a;
date* date2 = (date*)b;
if (date2->year != date1->year) {
int year2 = date2->year;
int year1 = date2->year;
if (year1 < 14) {
year1 = year1 + 100;
}
if (year2 < 14) {
year2 = year2 + 100;
}
int yearcompare = year2 - year1;
return -yearcompare;
}
}
output(date* ar, int i, int n)
{
for (i = 0; i < n; i++) {
//printf("Enter the date (month day year) i n the following format: text number number");
// printf("%s ", ar[i].month);
//printf("%d ", ar[i].day);
printf("%d\n", ar[i].year);
}
}
int main()
{
int n;
int i;
int MIN_SIZE = 0;
int MAX_SIZE = 1000;
while (1) {
printf("Enter number of dates you want to enter (between 1 and 10000):\n");
scanf("%d", &n);
if (n < MIN_SIZE) {
printf("You have entered a number lower than 0\n");
}
if (n > MAX_SIZE) {
printf("You have entered a number higher than 1000\n");
}
else {
break;
}
}
date* ar = malloc(sizeof(int) * n);
//ALLOCATE MEMORY
printf("Enter the date (month day year) in the following format: text, number(between 1 and 31), number(between 00 and 12): \n");
for (i = 0; i < n; i++) {
scanf("%s", ar[i].month);
scanf("%d", &ar[i].day);
scanf("%d", &ar[i].year);
}
qsort(ar, n, sizeof(date), sort);
output(ar, i, n);
}
看来您需要很多帮助才能将拼图的所有部分拼在一起。首先,在 date
的 typedef
中,包含 char *month
。这是一个在您分配 ar
时将未初始化的指针,这意味着您将需要为 ar[i].month
单独分配。你可以自由地这样做,(在这种情况下你可以有效地使用 strdup
),但是为什么呢?如果您要输入月份的字符串,则最大长度为 10 个字符 (September
+ nul-byte
)。只需使用静态声明的 month
或 10
或更多字符,并避免在 month
.
上动态分配
例如,您可以使用单独的 #define
指令声明在代码中使用的有用常量,或者您可以使用全局 enum
来完成相同的事情,例如
/* constants for max chars, max day, max year, max size */
enum { MAXC = 12, MAX_DAY = 31, MAX_YEAR = 2017, MAX_SIZE = 1000 };
typedef struct {
char month[MAXC]; /* either make static or allocate separately */
unsigned day;
unsigned year;
} date;
您将 运行 遇到的下一个问题是在 scanf
中混合字符和数字输入,这不会清空 输入缓冲区 (例如 stdin
) 每次调用。这意味着如果用户为 'n'
输入了除有效小数以外的其他内容(例如,如果他不小心点击了 'q'
而不是 '1'
),"q\n"
将保留在输入缓冲区中,这将作为您在下方 ar[0].month
的输入。为了防止这种情况发生,您需要手动清空输入缓冲区(或者使用 fgets
后跟 sscanf
来解析用户输入——使用 scanf
进行用户输入有很多陷阱).
尽管如此,您还是可以很轻松地清空 stdin
。您可以使用 int c; while ((c = getchar()) != '\n' && c != EOF) {}
内联或创建一个短函数,如果您将重复调用它以减少输入,例如:
/* empty character remaining in stdin */
void empty_stdin ()
{
int c;
while ((c = getchar ()) != '\n' && c != EOF) {}
}
当您接受输入时(无论是使用 scanf
函数族还是使用 fgets
(或任何其他方式),总是 验证 用户输入.据你所知,一只猫可能正在踩键盘。另外,请始终检查 EOF
,这表明用户通过 Ctrl+d 或 取消了输入Ctrl+z (在windoze上) 例如:
while (1) { /* obtain valid 'n', compare with using fgets below */
int rtn; /* varaible to save return of scanf -- always validate */
printf ("Enter number of dates to be entered (between 1 & 1000): ");
if ((rtn = scanf ("%d", &n)) != 1) { /* if conversion failed */
if (rtn == EOF) { /* test for user cancelation of input */
fprintf (stderr, "note: user canceled input, exiting.\n");
return 0;
} /* otherwise simply an invalid input */
fprintf (stderr, "error: invalid input.\n");
goto tryagain;
}
if (n < 0) { /* invalid input < 0 */
fprintf (stderr, "error: invalid input (n < 0).\n");
goto tryagain;
}
if (n > MAX_SIZE) { /* invalid input > MAX_SIZE */
fprintf (stderr, "error: invalid input (n > %d).\n", MAX_SIZE);
goto tryagain;
}
break; /* if we are here - we have a good value, break */
tryagain:; /* label for goto to jump over break */
empty_stdin (); /* empty characters that remain in input buffer */
}
与使用 fgets
和 sscanf
与 read/parse month
、day
、year
输入进行比较。您可以做一些简单的事情:
for (i = 0; i < n;) { /* loop until all elements filled */
char buf[MAX_DAY + 1] = "", ans[MAXC] = "";
/* if fgets return is NULL, EOF encountered */
if (fgets (buf, MAX_DAY + 1, stdin) == NULL) {
fprintf (stderr, "note: user canceled input, exiting.\n");
return 0;
}
/* parse with sscanf, validate 3 conversion took place */
if (sscanf (buf, "%11s %u %u", ar[i].month, &ar[i].day, &ar[i].year) != 3)
{
fprintf (stderr, "error: invalid input.\n");
continue;
}
i++; /* only increment if valid sscanf conversion took place */
}
不需要将int i
作为参数传递给函数output
,只需在本地声明即可,例如:
/* output n elements of array of struct date */
void output (date *ar, int n)
{
int i;
printf ("\nOutput sorted by year:\n\n");
for (i = 0; i < n; i++)
printf (" %s %d %d\n", ar[i].month, ar[i].day, ar[i].year);
}
接下来,虽然您的 sort
函数可能有效,但您可以通过使用不等式代替按年压缩排序,同时避免潜在的溢出:
/* sort struct date on year */
int sort (const void *a, const void *b)
{
date *date1 = (date *) a;
date *date2 = (date *) b;
if (date2->year != date1->year)
return (date1->year > date2->year) - (date1->year < date2->year);
return 0;
}
最后,如果您分配内存,您有责任保留指向块开头的指针,然后在不再需要时指向 free
内存。虽然它将在 exit
上释放,但请养成跟踪和释放您分配的所有内存的习惯。当您从事更复杂的项目时,良好的习惯会对您大有裨益。
如果用户只是点击 Enter 而不是输入日期,则将其放在一起并添加退出提示,您可以执行以下操作:
#include <stdio.h>
#include <stdlib.h>
/* constants for max chars, max day, max year, max size */
enum { MAXC = 12, MAX_DAY = 31, MAX_YEAR = 2017, MAX_SIZE = 1000 };
typedef struct {
char month[MAXC]; /* either make static or allocate separately */
unsigned day;
unsigned year;
} date;
/* empty character remaining in stdin */
void empty_stdin ()
{
int c;
while ((c = getchar ()) != '\n' && c != EOF) {}
}
/* sort struct date on year */
int sort (const void *a, const void *b)
{
date *date1 = (date *) a;
date *date2 = (date *) b;
if (date2->year != date1->year)
return (date1->year > date2->year) - (date1->year < date2->year);
return 0;
}
/* output n elements of array of struct date */
void output (date *ar, int n)
{
int i;
printf ("\nOutput sorted by year:\n\n");
for (i = 0; i < n; i++)
printf (" %s %d %d\n", ar[i].month, ar[i].day, ar[i].year);
}
int main (void) {
int i, n;
date *ar = NULL;
while (1) { /* obtain valid 'n', compare with using fgets below */
int rtn; /* varaible to save return of scanf -- always validate */
printf ("Enter number of dates to be entered (between 1 & 1000): ");
if ((rtn = scanf ("%d", &n)) != 1) { /* if conversion failed */
if (rtn == EOF) { /* test for user cancelation of input */
fprintf (stderr, "note: user canceled input, exiting.\n");
return 0;
} /* otherwise simply an invalid input */
fprintf (stderr, "error: invalid input.\n");
goto tryagain;
}
if (n < 0) { /* invalid input < 0 */
fprintf (stderr, "error: invalid input (n < 0).\n");
goto tryagain;
}
if (n > MAX_SIZE) { /* invalid input > MAX_SIZE */
fprintf (stderr, "error: invalid input (n > %d).\n", MAX_SIZE);
goto tryagain;
}
break; /* if we are here - we have a good value, break */
tryagain:; /* label for goto to jump over break */
empty_stdin (); /* empty characters that remain in input buffer */
}
empty_stdin (); /* empty characters that remain in input buffer */
/* allocate array of struct ar, n elements */
if ((ar = malloc (sizeof *ar * n)) == NULL) {
fprintf (stderr, "error: virtual memory exhausted.\n");
return 1;
}
/* provide format instructions */
printf ("Enter the date (month day year)\n"
" format, e.g.: Jan 18 2017\n\n");
for (i = 0; i < n;) { /* loop until all elements filled */
char buf[MAX_DAY + 1] = "", ans[MAXC] = "";
printf (" date[%2d] : ", i + 1); /* prompt for input */
/* if fgets return is NULL, EOF encountered */
if (fgets (buf, MAX_DAY + 1, stdin) == NULL) {
fprintf (stderr, "note: user canceled input, exiting.\n");
return 0;
}
if (*buf == '\n') { /* if first char is '\n', user just hit enter */
printf ("no input provided, quit (y/n)? ");
if (fgets (ans, MAXC, stdin) && (*ans == 'y' || *ans == 'Y'))
return 0;
else if (!*ans) { /* if ans NULL, EOF encountered */
fprintf (stderr, "note: user canceled input, exiting.\n");
return 0;
}
}
/* parse with sscanf, validate 3 conversion took place */
if (sscanf (buf, "%11s %u %u", ar[i].month, &ar[i].day, &ar[i].year) != 3)
{
fprintf (stderr, "error: invalid input.\n");
continue;
}
i++; /* only increment if valid sscanf conversion took place */
}
qsort (ar, n, sizeof (date), sort); /* sort by year */
output (ar, n); /* output results */
free (ar); /* free ar - you allocate it, you free it */
return 0;
}
注意:有很多很多方法可以接近代码的每一部分。如果您查看大部分行的位置,它们将用于 验证 输入。这只是最低限度的验证。理想情况下,您可以将每个 day
和 year
的值与 max/min 值进行比较,并将每个 month
与查找(或散列)table 进行比较验证每个月是否为有效月份(您也可以使用 date/time 函数,但这留给另一个问题)
例子Use/Output
$ ./bin/qsortstruct
Enter number of dates to be entered (between 1 & 1000): 4
Enter the date (month day year)
format, e.g.: Jan 18 2017
date[ 1] : September 11 2001
date[ 2] : April 22 2010
date[ 3] : June 2 1968
date[ 4] : February 13 1979
Output sorted by year:
June 2 1968
February 13 1979
September 11 2001
April 22 2010
仔细检查,确保您了解正在发生的事情的每个部分,如果您还有其他问题,请询问。
我是 C 语言的初学者,我正在使用 structs.I 尝试创建一个对日期列表进行排序的程序。用户首先输入日期数,然后输入日期本身,即月、日和年。然后使用 qsort 我想按时间顺序排序(首先按年然后按月然后按天)。我试图首先对年份进行排序,但我只得到我的输出为“0”。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char* month;
int day;
int year;
} date;
int sort(const void* a, const void* b)
{
date* date1 = (date*)a;
date* date2 = (date*)b;
if (date2->year != date1->year) {
int year2 = date2->year;
int year1 = date2->year;
if (year1 < 14) {
year1 = year1 + 100;
}
if (year2 < 14) {
year2 = year2 + 100;
}
int yearcompare = year2 - year1;
return -yearcompare;
}
}
output(date* ar, int i, int n)
{
for (i = 0; i < n; i++) {
//printf("Enter the date (month day year) i n the following format: text number number");
// printf("%s ", ar[i].month);
//printf("%d ", ar[i].day);
printf("%d\n", ar[i].year);
}
}
int main()
{
int n;
int i;
int MIN_SIZE = 0;
int MAX_SIZE = 1000;
while (1) {
printf("Enter number of dates you want to enter (between 1 and 10000):\n");
scanf("%d", &n);
if (n < MIN_SIZE) {
printf("You have entered a number lower than 0\n");
}
if (n > MAX_SIZE) {
printf("You have entered a number higher than 1000\n");
}
else {
break;
}
}
date* ar = malloc(sizeof(int) * n);
//ALLOCATE MEMORY
printf("Enter the date (month day year) in the following format: text, number(between 1 and 31), number(between 00 and 12): \n");
for (i = 0; i < n; i++) {
scanf("%s", ar[i].month);
scanf("%d", &ar[i].day);
scanf("%d", &ar[i].year);
}
qsort(ar, n, sizeof(date), sort);
output(ar, i, n);
}
看来您需要很多帮助才能将拼图的所有部分拼在一起。首先,在 date
的 typedef
中,包含 char *month
。这是一个在您分配 ar
时将未初始化的指针,这意味着您将需要为 ar[i].month
单独分配。你可以自由地这样做,(在这种情况下你可以有效地使用 strdup
),但是为什么呢?如果您要输入月份的字符串,则最大长度为 10 个字符 (September
+ nul-byte
)。只需使用静态声明的 month
或 10
或更多字符,并避免在 month
.
例如,您可以使用单独的 #define
指令声明在代码中使用的有用常量,或者您可以使用全局 enum
来完成相同的事情,例如
/* constants for max chars, max day, max year, max size */
enum { MAXC = 12, MAX_DAY = 31, MAX_YEAR = 2017, MAX_SIZE = 1000 };
typedef struct {
char month[MAXC]; /* either make static or allocate separately */
unsigned day;
unsigned year;
} date;
您将 运行 遇到的下一个问题是在 scanf
中混合字符和数字输入,这不会清空 输入缓冲区 (例如 stdin
) 每次调用。这意味着如果用户为 'n'
输入了除有效小数以外的其他内容(例如,如果他不小心点击了 'q'
而不是 '1'
),"q\n"
将保留在输入缓冲区中,这将作为您在下方 ar[0].month
的输入。为了防止这种情况发生,您需要手动清空输入缓冲区(或者使用 fgets
后跟 sscanf
来解析用户输入——使用 scanf
进行用户输入有很多陷阱).
尽管如此,您还是可以很轻松地清空 stdin
。您可以使用 int c; while ((c = getchar()) != '\n' && c != EOF) {}
内联或创建一个短函数,如果您将重复调用它以减少输入,例如:
/* empty character remaining in stdin */
void empty_stdin ()
{
int c;
while ((c = getchar ()) != '\n' && c != EOF) {}
}
当您接受输入时(无论是使用 scanf
函数族还是使用 fgets
(或任何其他方式),总是 验证 用户输入.据你所知,一只猫可能正在踩键盘。另外,请始终检查 EOF
,这表明用户通过 Ctrl+d 或 取消了输入Ctrl+z (在windoze上) 例如:
while (1) { /* obtain valid 'n', compare with using fgets below */
int rtn; /* varaible to save return of scanf -- always validate */
printf ("Enter number of dates to be entered (between 1 & 1000): ");
if ((rtn = scanf ("%d", &n)) != 1) { /* if conversion failed */
if (rtn == EOF) { /* test for user cancelation of input */
fprintf (stderr, "note: user canceled input, exiting.\n");
return 0;
} /* otherwise simply an invalid input */
fprintf (stderr, "error: invalid input.\n");
goto tryagain;
}
if (n < 0) { /* invalid input < 0 */
fprintf (stderr, "error: invalid input (n < 0).\n");
goto tryagain;
}
if (n > MAX_SIZE) { /* invalid input > MAX_SIZE */
fprintf (stderr, "error: invalid input (n > %d).\n", MAX_SIZE);
goto tryagain;
}
break; /* if we are here - we have a good value, break */
tryagain:; /* label for goto to jump over break */
empty_stdin (); /* empty characters that remain in input buffer */
}
与使用 fgets
和 sscanf
与 read/parse month
、day
、year
输入进行比较。您可以做一些简单的事情:
for (i = 0; i < n;) { /* loop until all elements filled */
char buf[MAX_DAY + 1] = "", ans[MAXC] = "";
/* if fgets return is NULL, EOF encountered */
if (fgets (buf, MAX_DAY + 1, stdin) == NULL) {
fprintf (stderr, "note: user canceled input, exiting.\n");
return 0;
}
/* parse with sscanf, validate 3 conversion took place */
if (sscanf (buf, "%11s %u %u", ar[i].month, &ar[i].day, &ar[i].year) != 3)
{
fprintf (stderr, "error: invalid input.\n");
continue;
}
i++; /* only increment if valid sscanf conversion took place */
}
不需要将int i
作为参数传递给函数output
,只需在本地声明即可,例如:
/* output n elements of array of struct date */
void output (date *ar, int n)
{
int i;
printf ("\nOutput sorted by year:\n\n");
for (i = 0; i < n; i++)
printf (" %s %d %d\n", ar[i].month, ar[i].day, ar[i].year);
}
接下来,虽然您的 sort
函数可能有效,但您可以通过使用不等式代替按年压缩排序,同时避免潜在的溢出:
/* sort struct date on year */
int sort (const void *a, const void *b)
{
date *date1 = (date *) a;
date *date2 = (date *) b;
if (date2->year != date1->year)
return (date1->year > date2->year) - (date1->year < date2->year);
return 0;
}
最后,如果您分配内存,您有责任保留指向块开头的指针,然后在不再需要时指向 free
内存。虽然它将在 exit
上释放,但请养成跟踪和释放您分配的所有内存的习惯。当您从事更复杂的项目时,良好的习惯会对您大有裨益。
如果用户只是点击 Enter 而不是输入日期,则将其放在一起并添加退出提示,您可以执行以下操作:
#include <stdio.h>
#include <stdlib.h>
/* constants for max chars, max day, max year, max size */
enum { MAXC = 12, MAX_DAY = 31, MAX_YEAR = 2017, MAX_SIZE = 1000 };
typedef struct {
char month[MAXC]; /* either make static or allocate separately */
unsigned day;
unsigned year;
} date;
/* empty character remaining in stdin */
void empty_stdin ()
{
int c;
while ((c = getchar ()) != '\n' && c != EOF) {}
}
/* sort struct date on year */
int sort (const void *a, const void *b)
{
date *date1 = (date *) a;
date *date2 = (date *) b;
if (date2->year != date1->year)
return (date1->year > date2->year) - (date1->year < date2->year);
return 0;
}
/* output n elements of array of struct date */
void output (date *ar, int n)
{
int i;
printf ("\nOutput sorted by year:\n\n");
for (i = 0; i < n; i++)
printf (" %s %d %d\n", ar[i].month, ar[i].day, ar[i].year);
}
int main (void) {
int i, n;
date *ar = NULL;
while (1) { /* obtain valid 'n', compare with using fgets below */
int rtn; /* varaible to save return of scanf -- always validate */
printf ("Enter number of dates to be entered (between 1 & 1000): ");
if ((rtn = scanf ("%d", &n)) != 1) { /* if conversion failed */
if (rtn == EOF) { /* test for user cancelation of input */
fprintf (stderr, "note: user canceled input, exiting.\n");
return 0;
} /* otherwise simply an invalid input */
fprintf (stderr, "error: invalid input.\n");
goto tryagain;
}
if (n < 0) { /* invalid input < 0 */
fprintf (stderr, "error: invalid input (n < 0).\n");
goto tryagain;
}
if (n > MAX_SIZE) { /* invalid input > MAX_SIZE */
fprintf (stderr, "error: invalid input (n > %d).\n", MAX_SIZE);
goto tryagain;
}
break; /* if we are here - we have a good value, break */
tryagain:; /* label for goto to jump over break */
empty_stdin (); /* empty characters that remain in input buffer */
}
empty_stdin (); /* empty characters that remain in input buffer */
/* allocate array of struct ar, n elements */
if ((ar = malloc (sizeof *ar * n)) == NULL) {
fprintf (stderr, "error: virtual memory exhausted.\n");
return 1;
}
/* provide format instructions */
printf ("Enter the date (month day year)\n"
" format, e.g.: Jan 18 2017\n\n");
for (i = 0; i < n;) { /* loop until all elements filled */
char buf[MAX_DAY + 1] = "", ans[MAXC] = "";
printf (" date[%2d] : ", i + 1); /* prompt for input */
/* if fgets return is NULL, EOF encountered */
if (fgets (buf, MAX_DAY + 1, stdin) == NULL) {
fprintf (stderr, "note: user canceled input, exiting.\n");
return 0;
}
if (*buf == '\n') { /* if first char is '\n', user just hit enter */
printf ("no input provided, quit (y/n)? ");
if (fgets (ans, MAXC, stdin) && (*ans == 'y' || *ans == 'Y'))
return 0;
else if (!*ans) { /* if ans NULL, EOF encountered */
fprintf (stderr, "note: user canceled input, exiting.\n");
return 0;
}
}
/* parse with sscanf, validate 3 conversion took place */
if (sscanf (buf, "%11s %u %u", ar[i].month, &ar[i].day, &ar[i].year) != 3)
{
fprintf (stderr, "error: invalid input.\n");
continue;
}
i++; /* only increment if valid sscanf conversion took place */
}
qsort (ar, n, sizeof (date), sort); /* sort by year */
output (ar, n); /* output results */
free (ar); /* free ar - you allocate it, you free it */
return 0;
}
注意:有很多很多方法可以接近代码的每一部分。如果您查看大部分行的位置,它们将用于 验证 输入。这只是最低限度的验证。理想情况下,您可以将每个 day
和 year
的值与 max/min 值进行比较,并将每个 month
与查找(或散列)table 进行比较验证每个月是否为有效月份(您也可以使用 date/time 函数,但这留给另一个问题)
例子Use/Output
$ ./bin/qsortstruct
Enter number of dates to be entered (between 1 & 1000): 4
Enter the date (month day year)
format, e.g.: Jan 18 2017
date[ 1] : September 11 2001
date[ 2] : April 22 2010
date[ 3] : June 2 1968
date[ 4] : February 13 1979
Output sorted by year:
June 2 1968
February 13 1979
September 11 2001
April 22 2010
仔细检查,确保您了解正在发生的事情的每个部分,如果您还有其他问题,请询问。