sorting in a struct within a struct

This is a discussion on sorting in a struct within a struct within the C Programming forums, part of the General Programming Boards category; this one has had me stuck for a few days and I am wondering if it is my idea of ...

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    17

    sorting in a struct within a struct

    this one has had me stuck for a few days and I am wondering if it is my idea of what is happening here that is askew...

    Code:
    typedef struct node *node_ptr;
    
    struct node {
            char *name;
            int n_students;
            struct student students[1000];
            node_ptr next;
    }
    
    struct student {
            int ID;
            char *name;
    }
    I have the structure working with nodes (which correspond with units the students enrol in) and they are sorted alphabetically on insertion.... but

    I'm having a hard time when I insert students to figure how to insert them in order by ID. I mean given student 1 is and ID of 123 and student 2 is 155 - what should I be doing as a general strategy to insert ID 139 for example.

    My strategy so far was to find the place it fit and then attempt to shuffle the rest up one and insert the student... which doesn't seem to work. Is this the wrong way. My issue is related to not understanding the rules perhaps - "can I" shuffle the rest of these struct members along and insert in the right spot or is there a trick to it?

    I haven't posted code yet as I'm at this point hoping my understanding of the general idea might improve. It is also a uni assignment (although I am 42yo) and I don't particularly just want to put up code here or get out of the box answers unless I have to to gain that understanding. I somehow dont' understand this one.

    could anyone offer some advice?

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    If your linked list is already sorted one way and you need to sort it a different way, couldn't you just dump the linked list to an array of pointers to each node, sort the array however you want it, and then rebuild the linked list? I believe a solution like this was already posted just recently.

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    17
    Thanks for the reply...

    The student struct doesnt have a next so only the nodes (units) are a linked list. [ADDED: -- The nodes are sorted by name in ascending order, these are courses BUT each course can have many students sorted on their student ID, so its not the resorting you expected in your reply].

    I'm trying to sort the students in a struct / array which is a part of a single linked list node. Next would be very handy at this point.

    Another consideration is I have a Big O limitation so I probably can't afford to offload into secondary data structures unless its absolutely the only way, but thanks for the input as I hadn't really considered the option.

    Obviously there must be some way to do this, for example where found is a pointer to the correct node (unit) I thought perhaps this might have worked (but it didn't) - for an insertion which is smaller than num students I would try to increment the number of the student record (kind of)... so basically all the bigger numbers might shuffle to the right and let me put in the student in the correct place.

    where the appropriate spot is...
    found->students[num++];

    then insert the new student in the hole...

    of course it didnt' work unfortunately. I'm wondering how one would actually go about inserting in order in this situation. Perhaps I do need to unload it into an array...
    Last edited by occams razor; 04-14-2007 at 10:23 PM. Reason: clarification

  4. #4
    Registered User
    Join Date
    Mar 2007
    Posts
    17
    At this point I am inserting the new student in the right place but the loop overwrites every member for the rest of the student struct... any ideas on how I might efficiently shuffle these along to fit my student in a struct without next?

    any conversation on this would be appreciated, I have to admit I'm stumped at this point.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,590
    > these are courses BUT each course can have many students
    Give it a better name than 'node' then.

    > struct student students[1000];
    This is simply a huge waste of space.
    If this were a linked list as well, then inserting new students into the list is an easy list update, no need to move any other data about to make room.

    On the other hand, an array is much easier to sort if later on you decide you want sort by name rather than sort by ID. But rather than a fixed array, use a struct student *students; and dynamically allocate what you need.

    Does the array have to be sorted all the time, or can you say add all the students, then sort it once at the end?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Registered User
    Join Date
    Mar 2007
    Posts
    17
    Hi Salem, thanks for replying. A constraint on the learning exprience of this exercise is for me to use the structs as defined so I never chose the [1000]. I'm just finding it hard to come to terms with the shuffling of the rest of the students right before inserting the next student.

    I guess I'm getting there slowly though

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,590
    OK then - it looks like you're "stuck" with the array shuffling then.
    Which end do you shuffle from?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Registered User
    Join Date
    Mar 2007
    Posts
    17
    I've tried starting from the far end but have just made myself confused... tonight I'll have to go and nut out the algorithm a bit better I think. Its dinner time here now and probably part of it is the transition from learning to hacking as I got boggled.

    Hopefully tomorrow will bring some insight. Thanks again for replying and sorry I can't post code directly. I don't want to put myself in any academic hot water. I'm pretty sure I'm on the right track though although when I posted I wasn't that sure.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Struct Pointer Problems. (Warning: Long Post.)
    By Phoenix940 in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 09:04 PM
  2. sequential file program
    By needhelpbad in forum C Programming
    Replies: 80
    Last Post: 06-08-2008, 01:04 PM
  3. Looking for constructive criticism
    By wd_kendrick in forum C Programming
    Replies: 16
    Last Post: 05-28-2008, 09:42 AM
  4. Bi-Directional Linked Lists
    By Thantos in forum C Programming
    Replies: 6
    Last Post: 12-11-2003, 09:24 AM
  5. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM

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