Reputation: 69
Using qsort and structs to sort a list
I'm a beginner at C and using structs.I'm trying to create a program which sorts a list of dates. The user first inputs the number of dates, then the dates themselves, being the month, day and the year. Then using qsort I want to sort it chronologically (first by year then month then day). I've tried to first sort the year however I'm only getting my output as "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);
}
Upvotes: 1
Views: 677
Answers (1)
Reputation: 84559
It looks as if you need quite a bit of help putting all the pieces of the puzzle together. First, in your typedef of date, you include char *month. That is a pointer that will be uninitialized when you allocate ar meaning you will need a separate allocation for ar[i].month. You are free to do that, (you can use strdup effectively in this case), but why? If you are taking string inputs of the month, then the maximum length is 10-characters (September + nul-byte). Just use a statically declared month or 10 or more characters and avoid the dynamic allocation on month.
For example, you can declare helpful constants for use in your code with either individual #define directives, or you can use a global enum to accomplish the same thing, e.g.
/* 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;
The next train-wreck you will run into is mixing character and numeric input in scanf which does not empty the input buffer (e.g. stdin) each time it is called. That means if the user enters something other than a valid decimal for 'n', (e.g. if he accidentally hits 'q' instead of '1'), the "q\n" remains in the input buffer, which will be taken as your input for ar[0].month below. To prevent this from occurring, you need to empty the input buffer manually (or use fgets followed by sscanf to parse user input instead -- there are many pitfalls in using scanf for user input).
That notwithstanding, you can empty stdin quite easily. You can do it inline with int c; while ((c = getchar()) != '\n' && c != EOF) {} or create a short function if you will call it repeatedly to cut down on typing, e.g.:
/* empty character remaining in stdin */
void empty_stdin ()
{
int c;
while ((c = getchar ()) != '\n' && c != EOF) {}
}
When you take input (whether with the scanf family of functions or with fgets (or any other means), always validate the user input. For all you know a cat may be stepping on the keyboard. Also, always check for EOF which indicates the user canceled input by Ctrl+d or Ctrl+z (on windoze). For example:
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 */
}
Compare with using fgets and sscanf to read/parse the month, day, year input. You can do something as simple as:
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 */
}
There is no need to pass int i as a parameter to function output, just declare it locally, e.g.:
/* 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);
}
Next, while your sort function may work, you can condense the sort by year, while avoiding potential overflow, by using inequalities instead:
/* 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;
}
Lastly, if you allocate memory, it is your responsibility to preserve a pointer to the starting of the block, and then to free the memory when it is no longer needed. While it will be freed on exit, get in the habit of tracking and freeing all memory you allocate. Good habits will serve you well when you are working on more complex projects.
Putting it altogether and adding a prompt to quit if the user simply hits Enter instead of entering a date, you could do something like the following:
#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;
}
Note: there are many, many ways to approach pretty much each part of the code. If you look at where a bulk of the lines are, they are used in validating the input. This is just a bare minimum of validation. You would ideally compare the values for each day and year against max/min values, and you would compare each month against a lookup (or hash) table to validate each month is a valid month (you can also use date/time functions, but that is left for another question)
Example 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
Look things over, make sure you understand each part of what is taking place, and ask if you have further questions.
Upvotes: 1
Related Questions
- How to sort an array of structs using qsort
- Issue with Qsort-ing a Struct
- How to sort struct using qsort
- Using qsort() with Structs
- Sorting an struct array in C with qsort function
- Using qsort() and Structs in C
- How to sort Struct using qsort in C programming
- Sorting structure with C qsort()
- How to sort a struct using qsort?
- Sorting structs in C with qsort