• C

How to sort a linked list like this?

Hi, I need some help for this easy problem..
I defined a struct like this:
struct p_list
{
    int n;
    char *nome;
    char *cognome;
    struct p_list *next;
};

typedef struct p_list ELEMENT;
typedef *ELEMENT LINK;

and I need to have a method for creating a list of elements. Something recursive like this:

LINK crealista()
{
LINK head=NULL;
int a;
char *no;
char *co;
scanf("%d %s %s", &a, &no, &co);

if (a != 0)
    {
    head = malloc(sizeof(ELEMENT));
    head->n=a;
    head->nome=no;
    head->cognome=co;
    head->next=crealista();
    }
return head;
}
Suppose this works (not sure of it!), I need a method to put in order the list from the field cognome (italian for Surname!); if two elements have the same surname i order them from the int field..
Can anybody help???
max
mags2000Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

sarda_rameshCommented:
The first thing is that there is some problem in the createlista() function as it creating a list with only one node .. u need a loop to add more nodes.

One solution of ur problem can be that whenever u add a new record in the list u add it at a position such that the resultant list is always sorted. If u do this way ur problem is automatically solved.

Second solution , if u dont want to change the create list then u can adopt any of the sorting algorithm and modify it accordingly to suit linked lists.

Please let me know which solution will u go for so that i can help u further.

regards
ramesh
0
sarda_rameshCommented:
0
mags2000Author Commented:
thanks sarda_ramesh, the first solution is not a bad idea.. My future problem will be that i will have lot of these lists, and i need to make one out of them, and then order the whole one...
So I don't know if it is useful to order the partial lists alone. I will work on it for another while, will let you know!
mags2000
0
Introducing the "443 Security Simplified" Podcast

This new podcast puts you inside the minds of leading white-hat hackers and security researchers. Hosts Marc Laliberte and Corey Nachreiner turn complex security concepts into easily understood and actionable insights on the latest cyber security headlines and trends.

gj62Commented:
Sarda,

Excuse me, but if you look carefully at the function, he is creating a more than one element.  creatlista is being called recursively until a 0 is entered as the first element in the scanf.

Second the link you gave is for C++ code.  This is the C forum...

mags2000,

You do have a bug, though...

You define your structure as

struct p_list
{
   int n;
   char *nome;
   char *cognome;
   struct p_list *next;
};

Please note that both nome and cognome are pointers to strings - they reserve no memory for the strings themselves.

When you use scanf, you also use pointers to strings that have not been allocated - your program WILL crash.

I suggest the following...

Leave your struct definition alone.

In createlista, declare the temporary strings to be large enough to hold any name, say

char no[100];
char co[100];

then change the loop to be as follows:

if (a != 0)
   {
   head = malloc(sizeof(ELEMENT));
   head->n=a;
   head->nome=malloc(strlen(no)+1);
   strcpy(head->nome,no);
   head->cognome=malloc(strlen(co)+1);
   strcpy(head->cognome,co);
   head->next=crealista();
   }

You can't just set head->nome=no, because no is just a temporary variable on the stack - it disappears once the function returns...

If you can't use the C++ versions let us know, it is easy enough to sort a linked list in C.

One note on your code - you are returning the pointer to the last element in your list, fyi..
0
mags2000Author Commented:
thank you gj62, in effect the crealista() is recursive and it works well with your suggestion!
I can't use C++, only C is available for sorting this list. I would prefer to use only one pointer to next, avoiding a previos pointer...
0
gj62Commented:
mags,

go to here:

http://www.snippets.org/snippets/portable/portable.php3

Download LL_MSORT.C and SNIPSORT.H.

You need to make only a few modifications:

In SNIPSORT.H, replace your struct for the list_struct.

In LL_MSORT, change the compare rountine to:

/* returns < 0 if *p sorts lower than *q */
int keycmp (list *p, list *q)
{
      if (strcmp(p->cogname, q->cogname)==0)
      {
        if (p->a > p->q) return(1);
        return(-1);
      }

      return strcmp(p->cogname, q->cogname);
}

This should do the trick - remember, strcmp is case sensitive - if you need case insensitive, let me know...
0
gj62Commented:
mags,  

I noticed a bunch of typos in my instructions above, and I was bored, so here's a whole program, complete with a test print in main().  I split the entry up between 3 scanf's - a bit easier on the user that way, but nowhere near as nice as it could be...

Good luck...
#include <stdlib.h>

typedef struct p_list
{
   int n;
   char *nome;
   char *cognome;
   struct p_list *next;
}ELEMENT;

//typedef struct p_list ELEMENT;


#include <stdio.h>              /* for NULL definition */
#include <string.h>


/* returns < 0 if *p sorts lower than *q */
int keycmp (ELEMENT *p, ELEMENT *q)
{
     if (strcmp(p->cognome, q->cognome)==0)
     {
       if (p->n > q->n) return(1);
       return(-1);
     }

     return strcmp(p->cognome, q->cognome);
}


/* merge 2 lists under dummy head item */
ELEMENT *lmerge (ELEMENT *p, ELEMENT *q)
{
      ELEMENT *r, head;

      for ( r = &head; p && q; )
      {
            if ( keycmp(p, q) < 0 )
            {
                  r = r->next = p;
                  p = p->next;
            }
            else
            {
                  r = r->next = q;
                  q = q->next;
            }
      }
      r->next = (p ? p : q);
      return head.next;
}

/* split ELEMENT into 2 parts, sort each recursively, merge */
ELEMENT *lsort (ELEMENT *p)
{
      ELEMENT *q, *r;

      if ( p )
      {
            q = p;
            for ( r = q->next; r && (r = r->next) != NULL; r = r->next )
                  q = q->next;
            r = q->next;
            q->next = NULL;
            if ( r )
                  p = lmerge(lsort(r), lsort(p));
      }
      return p;
}

ELEMENT * createlista()
{
  ELEMENT * head=NULL;
  int a;
  char tempNo[100];
  char tempCo[100];
  printf("Enter ID (0, if end)\n");
  scanf("%d", &a);

  if (a != 0)
  {
    printf("Enter FirstName\n");
    scanf("%s", tempNo);
    printf("Enter SurName\n");
    scanf("%s", tempCo);

    head = (struct p_list *)malloc(sizeof(ELEMENT));
    head->n=a;
    head->nome=(char *)malloc(strlen(tempNo)+1);
    strcpy(head->nome,tempNo);
    head->cognome=(char *)malloc(strlen(tempCo)+1);
    strcpy(head->cognome,tempCo);
    head->next=createlista();
  }


  return head;
}

int main()
{
     ELEMENT * linkList;
     linkList = createlista();
     linkList = lsort(linkList);
     while(linkList != NULL)
     {
          printf("ID = %d, Name = %s, LastName = %s\n", linkList->n, linkList->nome, linkList->cognome);
          linkList=linkList->next;
     }
     return 0;
}
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
mags2000Author Commented:
you did it! Thanks a lot gj62, I was near a solution like your one, but this is better!
mags
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.