chellappa said:
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
= 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->next = listPtrArray[i+1];
}
listPtrArray->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;
while (j>0 && ListPtrArray[j-1]->a > save->a) {
ListPtrArray[j] = ListPtrArray[j-1];
j--;
}
ListPtrArray[j] = save;
}
}
<----------------------------------
Cheers
Michael