Main with Merge Sort Function - Help Please

This is a discussion on Main with Merge Sort Function - Help Please within the C Programming forums, part of the General Programming Boards category; Hi, could someone please help me with my main function that has merge sort in it? I'm not sure how ...

  1. #1
    Registered User
    Join Date
    Feb 2010
    Posts
    25

    Main with Merge Sort Function - Help Please

    Hi, could someone please help me with my main function that has merge sort in it?
    I'm not sure how to call it or how this should be set up. I read in a file that has students and they are supposed to be sorted by their birthday, like JANUARY 5, and we find who has the closest birthday to someone else. The file reads in first name, last name, month, day, and year on the same line, but year is not used in the sorting. The queried students are part of the class, and I'm supposed to find the name of the student not queried with the closest birthday to the queried student.

    This is what I have for main:
    Code:
    #include <stdio.h>
    #include <string.h>
    
    #define MAXLENGTH 30
    
    struct student {
    	char first_name[MAXLENGTH];
    	char last_name[MAXLENGTH];
    	int month[12];
    	int day;
    	int year; //not used for sorting the birthdays
    };
    
    int Is_Sorted(struct student *val[], int length);
    void MergeSort(struct student *val[], int low, int high);
    void Merge(struct student *val[], int low, int middle, int high);
    void Print_Array(struct student *val[], int length);
    
    int main ()
    {
    	int num_classes;
    	int month[12] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 394, 334};
    	FILE* ifp;
    	ifp = fopen("birthday.txt", "r");
    	
    	struct student *info;
    	info = (struct student*)(malloc(sizeof(struct student)*MAXLENGTH));
    	
        fscanf(ifp, "%d ", &num_classes);
        
        int i, j;
        
        // Loop through each class
        for (i=1; i<=num_classes; i++) 
    	{
    		//Beginning Output
            printf("Class #%d:\n\n", i);
            
            int num_students;
            fscanf(ifp, "%d", &num_students);
             
            for(j=0; j<num_students; j++)
            {
                
                char first_name[MAXLENGTH];
                char last_name[MAXLENGTH];
                char month[MAXLENGTH];
                
                int day, year;
                fscanf(ifp, "%s ", first_name);
                fscanf(ifp, "%s ", last_name);
                fscanf(ifp, "%s ", month);
                fscanf(ifp, "%d ", &day);
                fscanf(ifp, "%d ", &year);
            }
            
            int num_queries;
            char queried_firstname[MAXLENGTH];
            char queried_lastname[MAXLENGTH];
            
            fscanf(ifp, "%d", &num_queries);
            
            for(j=0; j<num_queries; j++)
            {
                fscanf(ifp, "%s ", queried_firstname);
                fscanf(ifp, "%s ", queried_lastname);
            }
    	}
    	
    	// Sort the Values
        MergeSort(&info, 0, MAXLENGTH-1);
        	//Print_Array(val, SIZE);
    
        // Check if it's sorted.
        if (Is_Sorted(&info, MAXLENGTH))
            //printf("Sorted correctly.\n");
            
        /*
    	int dayofyear;
        for(i=0; i<12; i++)
    	{
    		dayofyear = month[i] + day;
       		differenceleft = month[i] - month[i-1];
       		differenceright = month[i+1] - month[i];
    
       		if (differenceleft < differenceright)
       			//middle person closest to person on left
       			printf("%s %s has closest birthday to %s %s", first_name, last_name, 
                            queried_firstname, queried_lastname);
       		else if(differenceright < differenceleft)
          	//middle person closest to person on right
    	}
    	*/
    	
    	free(info);
    	fclose(ifp);
    	system ("PAUSE");
    	return 0;
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Aparently your MergeSort function takes an array of pointers and you're trying to pass it an array of objects. You'll first have to create an array of pointers, where each pointer points to an item from the array of objects.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Feb 2010
    Posts
    25
    Your saying the &info part of the Mergesort is wrong right? I already have this

    struct student *info;
    info = (struct student*)(malloc(sizeof(struct student)*MAXLENGTH));

    Are you saying I should make another array that's not part of the struct?

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    First thing to fix is this:

    You need to #include <stdlib.h> so you can use malloc().

    Further down, it looks like you've read in all the students data from the file, but then you somehow begin reading the queried students data, from the file??

    Code:
             
            for(j=0; j<num_students; j++)
            {
                
                char first_name[MAXLENGTH];
                char last_name[MAXLENGTH];
                char month[MAXLENGTH];
                
                int day, year;
                fscanf(ifp, "%s ", first_name);
                fscanf(ifp, "%s ", last_name);
                fscanf(ifp, "%s ", month);
                fscanf(ifp, "%d ", &day);
                fscanf(ifp, "%d ", &year);
            }
            
            int num_queries;
            char queried_firstname[MAXLENGTH];
            char queried_lastname[MAXLENGTH];
            
            fscanf(ifp, "%d", &num_queries);
            
            for(j=0; j<num_queries; j++)
            {
                fscanf(ifp, "%s ", queried_firstname);
                fscanf(ifp, "%s ", queried_lastname);
            }
    	}
    Maybe you meant the part in blue to use scanf() instead or is there still num_queries students data to be read in the data file?

    And you'll want to use a for loop probably, to make your array of pointers point to each struct, after you malloc the pointer array very similarly to how you malloc'd the array of structs, except you add the extra * so each pointer is just the size of a struct pointer, and not the size of a struct.

    And if you even THINK about using Soul's mergesort algorithm, we'll have to ship you off to the North Pole, never to be heard from again!

  5. #5
    Registered User
    Join Date
    Feb 2010
    Posts
    25
    yeah, the file shows the number of classes, then number of students, then the students firstname, lastname, month, day, year on same line, then next line is number of queried students, and then the queried students with just firstname and lastname. For example, if in one of the classes, 1 of the 4 students is a queried student, then I have to say which of the non-queried students has the closest b-day to the queried student.
    Oh, and I used the mergesort algorithm that was given, but I changed it a little because I have a struct.
    Last edited by Hikaru90; 03-29-2010 at 03:57 AM.

  6. #6
    Registered User
    Join Date
    Feb 2010
    Posts
    25
    Code:
            struct student *info;
    	info = (struct student*)(malloc(sizeof(struct student)*MAXLENGTH));
    	
    	for (i=0; i<MAXLENGTH-1; i++)
    	{
    		int *value[i];
        	        value[i] = (int*)(malloc(sizeof(int)*MAXLENGTH));
    	}
    Did you mean using two *? Do I set value[i] equal to struct student *info?

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Hikaru90 View Post
    Code:
            struct student *info;
    	info = (struct student*)(malloc(sizeof(struct student)*MAXLENGTH));
    	
    	for (i=0; i<MAXLENGTH-1; i++)
    	{
    		int *value[i];
        	        value[i] = (int*)(malloc(sizeof(int)*MAXLENGTH));
    	}
    Did you mean using two *? Do I set value[i] equal to struct student *info?
    I thought info was your array of structs, (almost), and value was going to be your array of pointers to the structs.

    So every element of value would need a malloc(sizeof( struct student *) * MAXLENGTH).
    One * next to student, inside the ), and one for multiplication just outside the ).

    Or did you have something else in mind?

    Trust me, when you get to ** pointers and especially *** pointers, my head starts complaining!

  8. #8
    Registered User
    Join Date
    Jan 2010
    Posts
    104
    Hey dude, did you see my topic on this board? You and I have the exact same assignment. Is it possible we have the same teacher/class/university? lol

  9. #9
    Registered User
    Join Date
    Feb 2010
    Posts
    25
    Code:
            struct student *info;
    	info = (struct student*)(malloc(sizeof(struct student)*MAXLENGTH));
    	
    	for (i=0; i<MAXLENGTH-1; i++)
    	{
    		int *value[i];
        	        value[i] = (struct student*)(malloc(sizeof(struct student)*MAXLENGTH));
    	}
    Does it matter if I have it this way instead of malloc(sizeof(struct student*)*MAXLENGTH)?

    @ Soul, lol I don't know, maybe.

  10. #10
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Hikaru90 View Post
    Does it matter if I have it this way instead of malloc(sizeof(struct student*)*MAXLENGTH)?
    If you mean is that the same as:
    Code:
    (struct student*)(malloc(sizeof(struct student)*MAXLENGTH));
    No, it isn't. The one above is just wrong and should not compile.

    You don't need to use a cast on malloc in C. It serves no purpose. Furthermore, the difference between that and
    Code:
    malloc(sizeof(struct student*)*MAXLENGTH);
    Is that this one allocates and array of pointers to structs. The other one allocates an array of structs.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,660
    I recommend:
    Code:
    struct student *info = malloc(sizeof(*info) * MAXLENGTH);
    By the way, this probably does not do what you intend:
    Code:
    int *value[i];
    It defines a variable length array named value, local to the for loop, that has i number of pointers to int.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Feb 2010
    Posts
    25
    ok so
    Code:
    struct student *info;
    info = malloc(sizeof(struct student)*MAXLENGTH));
    	
    for (i=0; i<MAXLENGTH-1; i++)
    {
         int *value[i];
         value[i] = malloc(sizeof(struct student*)*MAXLENGTH);
    }

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Close, but you only need to malloc two times, once for the array of structs (which you have already) and then for the array of pointers. Then after that you loop over the array and assign the address of each item into the pointer array.
    Your pointer array will be a double-star variable.

    And yes, it wont be &info that you pass into MergeSort; It will be the array of pointers.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Jan 2010
    Posts
    104
    not to keep distracting with posts that dont actually help your function, but do you go to arup's class? lol just by off-chance

  15. #15
    Registered User
    Join Date
    Feb 2010
    Posts
    25
    yeah I don't think that's what I'm supposed to do, and I didn't realize that it mattered that I do the dayofyear now. I created a function for the day of year, so like if month = January, dayofyear = day. So February 4 would be the 35th day of the year.
    For example:
    Code:
    void CalculateDayofYear(struct student *info[])
    {
        for(i=0; i<num_students; i++)
        {
            if(strcmp(info[i]->month, "JANUARY")==1)
                info[i].dayofyear == info[i]->day;
            else if ...
        }
    }
    Then I guess the people would be sorted according to their dayofyear, so I'm not really sure how to put that into mergesort or make sure mergesort sorts that.

    @ Soul - Well, I don't really wanna give out my info.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 01:28 PM
  2. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  3. pointers
    By InvariantLoop in forum C Programming
    Replies: 13
    Last Post: 02-04-2005, 08:32 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 09:18 AM
  5. qt help
    By Unregistered in forum Linux Programming
    Replies: 1
    Last Post: 04-20-2002, 09:51 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21