Solved

# How to sort a linked list like this?

Posted on 2003-03-07
Medium Priority
173 Views
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;

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

{
int a;
char *no;
char *co;
scanf("%d %s %s", &a, &no, &co);

if (a != 0)
{
}
}
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
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
• 3
• 3
• 2

LVL 1

Expert Comment

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

ID: 8087288
0

Author Comment

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

LVL 6

Expert Comment

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

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

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)
{
}

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

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

ID: 8089149
mags,

go to here:

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

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

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)
{

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

/* 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()
{
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);

}

}

int main()
{
{
}
return 0;
}
0

Author Comment

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

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
Course of the Month9 days, 15 hours left to enroll