By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
426,083 Members | 2,237 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 426,083 IT Pros & Developers. It's quick & easy.

LOGO Linked List Sort using pointer

P: n/a
hi
this simple sorting , but it not running...please correect error for
sorting using pointer or linked list sorting , i did value sorting in
linkedlist
please correct error

#include<stdio.h>
#include<stdlib.h>
int main(void)
{
struct list
{
int a;
struct list *next;
};
struct list *head ,*curr, *top, *a1,*a2,*temp,*prev;
head=NULL;
int i;
int value;
for(i=0;i<=10;i++)
{
curr=(struct list *)malloc(sizeof(struct list *));
curr->a=rand()%100;
curr->next =NULL;
if (head==NULL)
{
head=curr;
}
else
{
top->next =curr;
}
top=curr;
}
a1=head;
prev=a1;
for(;a1;a1=a1->next)
{
for(a2=head;a2;a2=a2->next)
{
if(a1->a <a2->a)
{
/*value=a1->a;
a1->a=a2->a;
a2->a=value; */
temp=a1->next;
a1=a2;
a1->next=temp;
prev->next=a1;

}

}
prev=a1;
}
for (top = head; top; top = top->next)
printf("%d\n", top->a);
free(head);
}

Thanks
BY
CNS

Nov 15 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a

chellappa wrote:
hi
this simple sorting , but it not running...please correect error for
sorting using pointer or linked list sorting , i did value sorting in
linkedlist
please correct error

curr=(struct list *)malloc(sizeof(struct list *));

It should be curr = (struct list *)malloc(sizeof(struct list));
or curr = malloc(sizeof *curr);
You also needs to check the return value of malloc.

Nov 15 '05 #2

P: n/a

chellappa wrote:
hi
this simple sorting , but it not running...please correect error for
sorting using pointer or linked list sorting , i did value sorting in
linkedlist
please correct error

#include<stdio.h>
#include<stdlib.h>
int main(void)
{
struct list
{
int a;
struct list *next;
};
struct list *head ,*curr, *top, *a1,*a2,*temp,*prev;
head=NULL;
int i;
int value;
for(i=0;i<=10;i++)
{
curr=(struct list *)malloc(sizeof(struct list *));
curr->a=rand()%100;
curr->next =NULL;
if (head==NULL)
{
head=curr;
}
else
{
top->next =curr;
}
top=curr;
}

what is head and what is top? Check printing out list without
sorting.Then try to sort.

Nov 15 '05 #3

P: n/a
chellappa wrote:
hi
this simple sorting , but it not running...please correect error for
sorting using pointer or linked list sorting , i did value sorting in
linkedlist
please correct error

#include<stdio.h>
#include<stdlib.h>
int main(void)
{
struct list
{
int a;
struct list *next;
};
struct list *head ,*curr, *top, *a1,*a2,*temp,*prev;
head=NULL;
int i;
int value;
for(i=0;i<=10;i++)
{
curr=(struct list *)malloc(sizeof(struct list *));
curr->a=rand()%100;
curr->next =NULL;
if (head==NULL)
{
head=curr;
}
else
{
top->next =curr;
}
top=curr;
}
a1=head;
prev=a1;
for(;a1;a1=a1->next)
{
for(a2=head;a2;a2=a2->next)
{
if(a1->a <a2->a)
{
/*value=a1->a;
a1->a=a2->a;
a2->a=value; */
temp=a1->next;
a1=a2;
a1->next=temp;
prev->next=a1;

}

}
prev=a1;
}
for (top = head; top; top = top->next)
printf("%d\n", top->a);
free(head);
}
You have several problems here -- the most obvious is that your
code is not very readable and all in one chunk.
Part of that comes from your leaving tabulator indentation in your
message; for postings in usenet, replace the tabs by 2-4 spaces.

If you make use of functions, you can simplify and clarify your
intents:
---------------------------------- #include<stdio.h>
#include<stdlib.h>

#define LIST_SIZE (size_t)10

struct list
{
int a;
struct list *next;
};

..... /* function prototypes */

int main (void)
{
struct list *head = NULL;

if (LIST_SIZE != initList(&head, LIST_SIZE)) {
fprintf(stderr, "List initialisation to full size failed\n");
}

printList(head);

if (NULL == sortList(&head)) {
fprintf(stderr, "List sorting failed\n");
}

printList(head);

freeList(head);

return 0;
}
<----------------------------------

Now, let us consider what the functions have to look like;
the prototypes are
---------------------------------- /* Utilities */
size_t initList (struct list** HeadPtr, size_t Size);
void freeList (struct list* Head);
void printList (const struct list* Head);

/* Work routine */
struct list* sortList (struct list** OldHead);
<----------------------------------

The first three are intended to be small functions doing small
jobs -- however, they clean up the code enormously
---------------------------------- /* Allocate a list of Size 'struct list' nodes and store
** the list head in HeadPtr; return the number of actually
** allocated nodes */

size_t initList (struct list** HeadPtr, size_t Size)
{
size_t ret;
struct list *curr;

*HeadPtr = NULL;

for (ret=0; ret<Size; ret++) {
curr = malloc(Size * sizeof *curr);
if (curr == NULL) {
break;
}
curr->a = rand()%100;
curr->next = *HeadPtr;
*HeadPtr = curr;
}

return ret;
}

/* print the contents of the list starting at Head */
void printList (const struct list* Head)
{
const struct list *curr;

puts("List Values");
for (curr = Head; curr != NULL; curr = curr->next) {
printf(" %4d", curr->a);
}
putchar('\n');
}

/* free the list starting at Head */
void freeList (struct list* Head)
{
struct list *curr;

while ((curr = Head) != NULL) {
Head = Head->next;
free(curr);
}
}
<----------------------------------

Note that the above works even if not LIST_SIZE nodes but fewer could
be allocated.
Now, the only thing that remains is the sorting.
Your problem in sorting was a structural one: You threw
away the property that head is the first of the pointers in a list
of constant size and thus could not guarantee a finite number of
steps as loops became possible.
How can we get around that?

Sorting an array is much easier than sorting a linked list --
so we will do exactly this: We allocate an array of pointers to
the list nodes, sort this array, build a linked list from the
sorted array and return it:
---------------------------------- /*
** sortList
** sort the list starting at *HeadPtr w.r.t. 'struct list'.a
** return NULL on failure and the new head on success; the new
** head also is stored in *HeadPtr.
*/

/* Sorting routine */
void sortPtrArray(struct list **ListPtrArray, size_t Size);

struct list* sortList (struct list** HeadPtr)
{
struct list *curr, **listPtrArray = NULL;
size_t i, listSize = 0;

/* determine list size and allocate storage for an array
** listSize of struct list* */
for (curr = *HeadPtr; curr != NULL; curr = curr->next) {
listSize++;
}
listPtrArray = malloc(listSize * sizeof *listPtrArray);
if (listPtrArray == NULL)
return NULL;

/* Store pointers to the list nodes in listPtrArray */
for (curr = *HeadPtr, i=0; i<listSize; i++) {
listPtrArray[i] = curr;
curr = curr->next;
}

/* sort listPtrArray by a */
sortPtrArray(listPtrArray, listSize);

/* Build linked list from sorted listPtrArray*/
for (i=0; i<listSize-1; i++) {
listPtrArray[i]->next = listPtrArray[i+1];
}
listPtrArray[i]->next = NULL;
*HeadPtr = listPtrArray[0];

free(listPtrArray);

return *HeadPtr;
}
<----------------------------------

Last part to the puzzle: An arbitrary sorting routine for
arrays, here an insertion sort straight from the book (Sedgewick,
Algorithms in C)
----------------------------------

/* Insertion sort of ListPtrArray with Size elements */
void sortPtrArray(struct list **ListPtrArray, size_t Size)
{
size_t i;
for (i=1; i<Size; i++)
{
size_t j = i;
struct list* save = ListPtrArray[i];
while (j>0 && ListPtrArray[j-1]->a > save->a) {
ListPtrArray[j] = ListPtrArray[j-1];
j--;
}
ListPtrArray[j] = save;
}
}
<----------------------------------
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Nov 15 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.