Question about DLists

This is a discussion on Question about DLists within the C Programming forums, part of the General Programming Boards category; In my last exam, i had an assignment, one of five, which refers to dynamic lists. I had a single ...

  1. #1
    Sometimes so stupid... shardin's Avatar
    Join Date
    Jul 2007
    Location
    Dalmatia/CRO
    Posts
    78

    Question about DLists

    In my last exam, i had an assignment, one of five, which refers to dynamic lists. I had a single dynamic list, and I was asked to write a function which will add a element in the list. The thing is that list is sorted, and i have to add that element on the exact place, so that list remains sorted.

    I looked on forum for sorting a dynamic list and found lots of posts which are about sorting dynamic lists. I want to know is it possible to do this assignment without need for sorting? If it isn't, I assume it isn't, do I need to use binary trees?
    ...and aprentice shall become master...or not...

    "Never let your sense of moral prevent you from doing what is right!" Salvor Hardin, mayor of Terminus

  2. #2
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    If I understand you correctly, you have a sorted Single-Linked-List?
    To insert an element in the correct position, you would just have to traverse the list until you find the first element that has a key greater than the value you're trying to insert, and then insert it before that element.
    If you have a SLL of unordered elements and you want to order them, then you'll need some sort of sorting algorithm, and yes, a binary tree could be used for that.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  3. #3
    Sometimes so stupid... shardin's Avatar
    Join Date
    Jul 2007
    Location
    Dalmatia/CRO
    Posts
    78
    Yes, I already have sorted list. Aha, I get you!

    Thanks
    ...and aprentice shall become master...or not...

    "Never let your sense of moral prevent you from doing what is right!" Salvor Hardin, mayor of Terminus

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I want to know is it possible
    Whenever you want to ask this question, the answer is likely going to be yes. There's very little that you can't do in C.

    >to do this assignment without need for sorting?
    Yes, you insert into the list in the sorted position. You can find details on that and other list operations here.
    My best code is written with the delete key.

  5. #5
    Sometimes so stupid... shardin's Avatar
    Join Date
    Jul 2007
    Location
    Dalmatia/CRO
    Posts
    78
    Ok, this is my function....

    Code:
    struct student *dodaj_di_triba(struct student *head, int mb,char *ime){
    
    	struct student *temp;
    	struct student *dodaj;
    	
    	dodaj = (struct student *)malloc(sizeof(struct student));
    	        dodaj->mbr=mb;
    			strcpy(dodaj->ime,ime);
    			temp = head;
    	while(temp->next<=dodaj->mbr){
    		
    		if(temp>dodaj->mbr){
    			temp->next=dodaj;
    			}
    		temp=temp->next;
    		}
    			return dodaj;
    }
    My d. list is NOT sorted. But i just wnated to see will this work. If i enter smaller MBR then put it in front bigger one. When im going to print it, i does print it on the first place but then crashes. Does list have to be sorted for this to work?
    example, i enter: John 7, Ivan 9, Mike 5, when i print this it will print in order how it was entered, in my list it enters on the first place. With this function, when I enter John 7, Ivan 9, Mike 5, and Steve 2, it does print Steve 2 first but then crashes.
    ...and aprentice shall become master...or not...

    "Never let your sense of moral prevent you from doing what is right!" Salvor Hardin, mayor of Terminus

  6. #6
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Well for a start you have a typo here:
    Code:
    if(temp->dodaj->mbr)

  7. #7
    Registered User
    Join Date
    Sep 2007
    Posts
    9
    Quote Originally Posted by shardin View Post
    Ok, this is my function....

    Code:
    struct student *dodaj_di_triba(struct student *head, int mb,char *ime){
    
    	struct student *temp;
    	struct student *dodaj;
    	
    	dodaj = (struct student *)malloc(sizeof(struct student));
    	        dodaj->mbr=mb;
    			strcpy(dodaj->ime,ime);
    			temp = head;
    	while(temp->next<=dodaj->mbr){
    		
    		if(temp>dodaj->mbr){
    			temp->next=dodaj;
    			}
    		temp=temp->next;
    		}
    			return dodaj;
    }
    My d. list is NOT sorted. But i just wnated to see will this work. If i enter smaller MBR then put it in front bigger one. When im going to print it, i does print it on the first place but then crashes. Does list have to be sorted for this to work?
    example, i enter: John 7, Ivan 9, Mike 5, when i print this it will print in order how it was entered, in my list it enters on the first place. With this function, when I enter John 7, Ivan 9, Mike 5, and Steve 2, it does print Steve 2 first but then crashes.

    Plz write down the elements of structure to understand it easily. I really don't understand...why are u comparing an int with a pointer?
    Last edited by PrashantVaidwan; 09-24-2007 at 10:56 AM.

  8. #8
    Sometimes so stupid... shardin's Avatar
    Join Date
    Jul 2007
    Location
    Dalmatia/CRO
    Posts
    78
    Code:
    struct student{
    char ime[20];
    int mbr;
    struct student *next;
    };
    What i want to do is compare mbr i enter with mbr that are already entered, and to put it on the right place.
    ...and aprentice shall become master...or not...

    "Never let your sense of moral prevent you from doing what is right!" Salvor Hardin, mayor of Terminus

  9. #9
    Sometimes so stupid... shardin's Avatar
    Join Date
    Jul 2007
    Location
    Dalmatia/CRO
    Posts
    78
    Well for a start you have a typo here:
    Code:

    if(temp->dodaj->mbr)
    no, mike, that is a if(temp>dodaj->mbr)
    ...and aprentice shall become master...or not...

    "Never let your sense of moral prevent you from doing what is right!" Salvor Hardin, mayor of Terminus

  10. #10
    Registered User
    Join Date
    Sep 2007
    Posts
    9
    [QUOTE=shardin;673572]
    Code:
    struct student{
    char ime[20];
    int mbr;
    struct student *next;
    };

    Ok i understand it..as earlier u have considered it a sorted list. Please see my function to insert in sorted list
    Code:
    struct student *dodaj_di_triba(struct student *head, int mb,char *ime){
    
    	struct student *temp;
    	struct student *dodaj;
                    struct student *successor;
                    dodaj = (struct student *)malloc(sizeof(struct student));
    	        dodaj->mbr=mb;
    	        strcpy(dodaj->ime,ime);
    	        temp = head;
             if((head->mbr)<=(dodaj->mbr))
             {
                      dodaj->next=head;
                      /* we are returning the head pointer  to traverse the whole list*/
                      return dodaj;
             }
            else
            {              
                  while((temp->mbr)<(dodaj->mbr))
                  {
                      successor = temp->next;
                      if(successor == NULL)
                      {
                         temp->next = dodaj;
                         dodaj->next = NULL;
                         /* returning the head pointer */
                         return head;
                       }
                     if((successor->mbr)>=(dodaj->mbr))
                     {
                        temp->next=dodaj;
                        dodaj->next=successor;
                          return head;
                     }
                     temp= temp->next;
                 }
              }
    Last edited by PrashantVaidwan; 09-25-2007 at 01:57 AM.

  11. #11
    Sometimes so stupid... shardin's Avatar
    Join Date
    Jul 2007
    Location
    Dalmatia/CRO
    Posts
    78
    At this moment, i am not working with sorted list. And please, can anyone who is using Bloodshed Dev C++, tell me where the f*** is <>!?
    ...and aprentice shall become master...or not...

    "Never let your sense of moral prevent you from doing what is right!" Salvor Hardin, mayor of Terminus

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    What do you mean "where is <>"?

    If you are building the list in a sorted fashion, the task is relatively easy:
    Case 1: The new element needs to become the head of the list (it is BEFORE the current head) -
    current->next = head
    head = current
    Case 2: It inserts into the lest: find the last element that is smaller than current, insert after the last smaller: current->next = smaller->next; smaller->next = current;

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Sometimes so stupid... shardin's Avatar
    Join Date
    Jul 2007
    Location
    Dalmatia/CRO
    Posts
    78
    no, not that, i meant on the keyboard, when i press AltGr+: in visual it gives me > or < and in Dev it starts comment. I know it is stupid, but i cant find it.
    ...and aprentice shall become master...or not...

    "Never let your sense of moral prevent you from doing what is right!" Salvor Hardin, mayor of Terminus

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by shardin View Post
    no, not that, i meant on the keyboard, when i press AltGr+: in visual it gives me > or < and in Dev it starts comment. I know it is stupid, but i cant find it.
    This is probably a problem with the combination of DevC++ and the Croatian keyboard layout - you may find switching to a US keyboard layout where <> are on the shifted version of the keys next to M (bottom row, second "<" and third ">" key from the right).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    Sometimes so stupid... shardin's Avatar
    Join Date
    Jul 2007
    Location
    Dalmatia/CRO
    Posts
    78
    zes, thanks man!
    ...and aprentice shall become master...or not...

    "Never let your sense of moral prevent you from doing what is right!" Salvor Hardin, mayor of Terminus

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

Similar Threads

  1. Alice....
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 06-20-2005, 02:51 PM
  2. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  3. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 12:47 AM

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