Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 179
  • Last Modified:

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
0
mags2000
Asked:
mags2000
  • 3
  • 3
  • 2
1 Solution
 
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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
 
mags2000Author Commented:
you did it! Thanks a lot gj62, I was near a solution like your one, but this is better!
mags
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

  • 3
  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now