?
Solved

How to sort a linked list like this?

Posted on 2003-03-07
8
Medium Priority
?
173 Views
Last Modified: 2010-04-15
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
Comment
Question by:mags2000
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 3
  • 2
8 Comments
 
LVL 1

Expert Comment

by:sarda_ramesh
ID: 8087278
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
 
LVL 1

Expert Comment

by:sarda_ramesh
ID: 8087288
0
 

Author Comment

by:mags2000
ID: 8087695
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
Independent Software Vendors: 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!

 
LVL 6

Expert Comment

by:gj62
ID: 8088819
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
 

Author Comment

by:mags2000
ID: 8088985
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
 
LVL 6

Expert Comment

by:gj62
ID: 8089149
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
 
LVL 6

Accepted Solution

by:
gj62 earned 300 total points
ID: 8090581
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
 

Author Comment

by:mags2000
ID: 8093377
you did it! Thanks a lot gj62, I was near a solution like your one, but this is better!
mags
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
Suggested Courses

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question