Thread: 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?

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

Yes, I already have sorted list. Aha, I get you!

Thanks

>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.

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.

Originally Posted by shardin

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?

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.

Well for a start you have a typo here:
Code:

if(temp->dodaj->mbr)

no, mike, that is a if(temp>dodaj->mbr)

[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;
             }
          }

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 <>!?

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

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.

Originally Posted by shardin

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

zes, thanks man!