Hi I am trying to make an insertion sort with Linklist.
I am sorting by the parameter time.
I think it's semi working but what is the easiest way to implement an insert sort with tail and a head pointer.
The delink() and addNode()... functions works correctly.
Insert(....) is the insert sort fcn.
Thanks for your help.
Code:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node {
int id;
int time;
struct node* next;
};
/* if it's the first item, pass in HEAD
* else pass in the TAIL
*/
void addNode(struct node** head, struct node** tail, int id)
{
struct node* new = malloc(sizeof(struct node* ));
if(*head == NULL)
{
new->id = id;
new->next = NULL;
*head = new;
*tail = new;
}
else
{
new->id = id;
new->next = NULL;
(*tail)->next = new;
*tail = new;
}
}
void insert(struct node** head, struct node** tail,int id, int time)
{
struct node* new = malloc(sizeof(struct node*));
struct node* start;
//When adding the first element.
if(*head == NULL)
{
printf("first time\n");
new->id = id;
new->next = NULL;
new->time = time;
*head = new;
*tail = new;
printf("first node %d\n", (*head)->id);
}
else
{
//insert sort
//find the correct spot to insert the new element
//
start = *head;
while(start->next != NULL && (start->next->time <= time))
{
printf("current node %d__ time %d\n", (start)->id, start->time );
start = start->next;
}
new->id = id;
new->time = time;
// if we have to insert between nodes
//then use the start pointer,
//we place the node after whatever the start pointer points to.
//*****must add node before the first node if the new node has to be the first node
if(start == *head)
{
printf("in First node statement\n");
new->next = start;
start = new;
*head = start;
}
//new node needs to placed between two nodes
else
{
printf("in Between nodes statement\n");
new->next = start->next;
start->next = new;
}
}
}
void printList(struct node* head)
{
while(head != NULL)
{
printf("ID: %d Time:> %d\n", head->id, head->time);
head = head->next;
}
}
int delink(struct node** head)
{
int id = (*head)->id;
*head = (*head)->next;
return id;
}
int main()
{
struct node* head;
struct node* tail;
head = NULL;
tail = head;
//int i;
//int t;
/*
for(i = 0; i < 5; i++);
{
if(i == 4)
t = 1;
insert(&head,&tail, i, t);
}*/
insert(&head, &tail, 2, 4);
insert(&head, &tail, 5, 3);
insert(&head, &tail, 3, 1);
insert(&head, &tail, 1, 5);
insert(&head, &tail, 4, 2);
printList(head);
return 0;
}