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.

Well for a start you have a typo here:

Code:

---

if(temp->dodaj->mbr)

---

Quote:

---

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.

Quote:

---

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.

Quote:

---

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!

Or get this: A keyboard with an LCD for each key

Quote:

---

Or get this: A keyboard with an LCD for each key

---

Very cool!

Code:

---

struct student{

        char ime[20];
        struct student *next;
};
        struct student *head=NULL;

---

I have troubles with my function. I want to put a name in list, but, if the name is already there then let it prints that name already exists, if no, put name into list. Here is mine function...

Code:

---

struct student *dodajAN(struct student *head){
                          struct student *novi;
                          novi = (struct student *)malloc(sizeof(struct student));
                          struct student *temp;
                          temp = head;
                          while(temp!=NULL){
                                            if(novi->ime==temp->ime){
                                                                    printf("Vec ima...");
                                                                   
                                                                    }
                                                                    temp=temp->next;
                                            }
                                           
                                            novi->next=head;
                                            head=novi;
                          }

---

When I type the name that already is in the list, it prints nothing, when i print the list, that name is just bunch of symbols. So it puts something inside but....
I know that I need to have a pointer on the list that has names inside, head is a pointer to first element of the list so i m missing that other pointer to list with names? help :confused:

To compare two strings, use strcmp() from <string.h>. http://www.cplusplus.com/reference/c...ng/strcmp.html
Don't use ==.

no, same thing. It has to do something with a pointer on a fulfilled list.

Code:

---

if(novi->ime==temp->ime){

---

You see that? It will always be false, no matter what is contained in the imes, unless novi and temp both point to the same structure, in which case it will always be true. You might as well write

Code:

---

if(novi == temp) {

---

If your intent was to compare the strings for equality, use

Code:

---

if(strcmp(novi->ime, temp->ime) == 0) {

---

No, it does not work! I try to compare strings but nothing. It puts something inside the list anyway! (symbols mess)!

Code:

---

struct student *dodajAN(struct student *head){
                          struct student *novi;
                          novi = (struct student *)malloc(sizeof(struct student));
                          struct student *temp;
                          temp = head;
                          while(temp!=NULL){
                                            if(strcmp(novi->ime,temp->ime)==0)
                                            printf("Vec ima ime!");
                                            return;
                                            temp=temp->next;
                                            }
                                            novi->next=head;
                                            head=novi;
                                            return novi;
                          }

---

Code:

---

  case 5:
                  printf("Upisi ime: ");
            scanf("%s", &ime);
            head = dodajAN(head);

---

Program crashes after all with some nasty warning 'could not write in memory 00000000x6.....'...

Code:

---

scanf("%s", &ime);

---

If ime is a char[] or a char*, drop the &.

Code:

---

                                            if(strcmp(novi->ime,temp->ime)==0)
                                            printf("Vec ima ime!");
                                            return;
                                            temp=temp->next;
                                            }

---

You're not returning anything, whilst the function is supposed to return a structure . . .

Quote:

---

You're not returning anything, whilst the function is supposed to return a structure . . .

---

shardin
Sometimes so stupid... - i think that says it all!!!

Everyone makes mistakes. :) Besides, your compiler should tell you about that particular mistake. Perhaps you should enable warnings. In Dev-C++, add -W -Wall to the "Extra compiler options" textbox in the Compiler Options dialog.

I have to disappoint you Dwks, now when i return "head", it doesn't break but it's not working also. It wont print my text, and name i enter is messed up. I want to make it to exit function if my condition is true. If not then add new name and exit function. I tried whith "return head"...Also if I type the new name that is not in the list it wont add it.

Returning head from here is probably not the best idea:

Code:

---

struct student *dodajAN(struct student *head){
                          struct student *novi;
                          novi = (struct student *)malloc(sizeof(struct student));
                          struct student *temp;
                          temp = head;
                          while(temp!=NULL){
                                            if(strcmp(novi->ime,temp->ime)==0)
                                            printf("Vec ima ime!");
                                            return;
                                            temp=temp->next;
                                            }
                                            novi->next=head;
                                            head=novi;
                                            return novi;
                          }

---

I think you should return novi or temp (either would probably work, since their imes are the same).

Actually, now that I look at your code again, it seems that the contents of novi are not initialized. So comparing it with temp is probably a bad idea as well.

Finally, I see something else. Your indentation may have caused you to miss this, so here is your while loop re-indented:

Code:

---

while(temp!=NULL){
    if(strcmp(novi->ime,temp->ime)==0)
        printf("Vec ima ime!");
    return;
    temp=temp->next;
}

---

In other words, the return statement always executes on the first iteration of the while loop. You probably meant to use curly braces around the if statement to include the if statement in there:

Code:

---

while(temp!=NULL){
    if(strcmp(novi->ime,temp->ime)==0) {
        printf("Vec ima ime!");
        return;
    }
    temp=temp->next;
}

---

Also, I'm sure this has already been mentioned, but you shouldn't cast malloc().