Hi there, long time no bother
I am trying to sort a singly linked list using pointer manipulation using a "selection sort"-ish algorithm and I'm having problems.
My idea is this:
1. find the smallest (by age) node
2. move it to the head of the list
3. check if the list is sorted and if it isn't go back to 1.
Not highly efficient but it should work. Of course, it doesn't. If I have 3 or more nodes it causes a segmentation fault.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* WHAT IS A PERSON? */
typedef struct node
{
char name[10];
int age;
int id;
struct node *next;
} person;
/* MAIN MENU */
void Menu()
{
printf("\n\n*** SORT SINGLY LINKED LIST ***\n\n");
printf(" 1. Add\n");
printf(" 2. Printout\n");
printf(" 3. Sort\n");
printf("\n************************************\n");
printf("\nChoose :> ");
}
/* CREATE NEW PERSON */
person* NewPerson (int id)
{
person *new = malloc(sizeof(person));
char name[10];
printf("\nEnter name: ");
scanf("%s", name);
strcpy(new->name, name);
printf("Enter age: ");
scanf("%d", &new->age);
new->id = id;
return (new);
}
/* ADD TO THE BEGINNING OF THE LIST */
void Add (person **head, person **nova)
{
person *new = *nova;
if (*head == NULL)
{
*head = new;
new->next = NULL;
}
else
{
new->next = *head;
*head = new;
}
}
/* PRINTOUT THE LIST */
void Printout (person *head)
{
person *temp = head;
int i = 1;
printf("\nList contents: \n\n");
if (temp == NULL)
printf("\nList is empty!!\n");
else
{
while (temp)
{
printf("No: %2d NAME: %9s AGE: ", i, temp->name);
printf("%2d ID: %3d\n", temp->age, temp->id);
temp = temp->next;
i++;
}
}
}
/* GET NODE BY ID */
person* GetByID (person **head, int id)
{
person *temp = *head;
while (temp->mb != mb && temp->next != NULL)
temp = temp->next;
if (temp->mb == mb)
return temp;
else
return NULL;
}
/* MOVE NODE TO BEGINING OF LIST */
int MoveNode (person **head, int id)
{
person *temp = *head;
person *theone;
int success = 0;
if (temp != NULL)
{
theone = GetByID(&(*head), id);
if (theone == NULL)
success = -1;
else
{
while (temp->next != theone)
temp = temp->next;
temp->next = theone->next;
theone->next = *head;
*head = theone;
success = 1;
}
}
return success;
}
/* SORT LIST BY POINTER MANIPULATION */
void SortList (person **head)
{
person *temp = *head;
person *min;
int id, success, test;
if (temp == NULL)
printf("\nList empty, sorting is pointless!");
else if (temp->next == NULL)
printf("\nJust one node, sorting is pointless");
else
{
do {
test = 0;
// find the smallest
min = *head;
while (temp)
{
if (temp->age < min->age)
min = temp;
temp = temp->next;
}
id = min->id;
// move it to the beginning of the list
success = MoveNode(&(*head), id);
// check if list is sorted
temp = *head;
while (temp->next)
{
if (temp->id > temp->next->id)
{
test = 1;
break;
}
temp = temp->next;
}
} while (test != 0);
}
}
/* MAIN */
int main (int argc, const char * argv[])
{
person *head = NULL;
person *nova;
int choice, n, id = 1;
do {
Menu();
scanf("%d", &choice);
switch (choice)
{
// Add nodes
case 1:
new = NewPerson(id);
id++;
Add(&head, &nova);
Printout(head);
break;
// Printout the list
case 2:
Printout(head);
break;
// Sort te list
case 3:
if (head == NULL)
printf("\nList empty, sorting is pointless");
else
{
SortList(&head);
Printout(head);
}
break;
default:
break;
}
} while (choice!=0);
return 0;
}