Hi there everyone,
I'm a bit new to see and I need your help please.
I'm stuck with a merge sort problem where it's support to sort my nodes in lexicographical order.
Can you please have a look on my code because i've posted everywhere and i'm not getting the answers i'm looking
I'm a newbie so sorry if i don't explain myself correctly. It's just not running my case 8 on my main.
Any ideas how to fix that?
//
// main.c
// Double Linked List
//
// Created by Yann Bohbot on 12/22/13.
// Copyright (c) 2013 Yann Bohbot. All rights reserved.
//
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node
{
char data[100];
struct node *previous; // Points to the previous node
struct node *next; // Points out to the next node
}*head, *last;
void insert_beginning(char words[99]);
void insert_end(char words[99]);
char insert_after(char words[99], char loc[99]);
char delete_from_end();
char delete_from_middle(char words[99]);
void display();
struct node *merge(struct node *head_one, struct node *head_two);
void insert_beginning(char words[99])
{
struct node *var, *temp;
var=(struct node *)malloc(sizeof(struct node)); //explination about the (node *)
strncpy(var->data, words,99);
if (head==NULL)
{
head=var;
head->previous=NULL;
head->next=NULL;
last=head;
}
else
{
temp=var;
temp->previous=NULL;
temp->next=head;
head->previous=temp;
head=temp;
}
}
void insert_end(char words[99])
{
struct node *var, *temp;
var=(struct node *)malloc(sizeof(struct node));
strncpy(var->data, words,99);
if (head==NULL)
{
head=var;
head->previous=NULL;
head->next=NULL;
last=head;
}
else
{
last=head;
while (last!=NULL)
{
temp=last;
last=last->next;
}
last=var;
temp->next=last;
last->previous=temp;
last->next=NULL;
}
}
char insert_after(char *words, char *loc)
{
struct node *temp, *var;
var=(struct node *)malloc(sizeof(struct node));
strcpy(var->data, loc);
if (head==NULL)
{
head=var;
head->previous=NULL;
head->next=NULL;
}
else
{
temp=head;
while ((temp!=NULL) && (strcmp(temp->data, words)))
{
temp=temp->next;
}
if (temp==NULL)
{
printf("\n %s not presented at list\n", words);
}
else
{
struct node * followingNode = temp->next;
temp->next=var;
var->previous=temp;
var->next= followingNode;
if (followingNode)
followingNode->previous = var;
}
}
return 0;
}
char delete_from_end()
{
struct node *temp;
temp=last;
if (temp->previous==NULL)
{
free(temp);
head=NULL;
last=NULL;
return 0;
}
printf("\n Data deleted from list %s\n", last->data);
last=temp->previous;
last->next=NULL;
free(temp);
return 0;
}
char delete_from_middle(char words[99])
{
struct node *h;
h = head;
while ( h != last) {
if ( strcmp(h->data, words) == 0)
{
if ( h->previous == NULL )
{
if( head == last )
{
head = NULL;
last = NULL;
}
else
{
head = head->next;
head->previous = NULL;
}
}
else
{
if( h->next!=NULL ) h->next->previous = h->previous;
h->previous->next = h->next;
}
printf(" Data deleted from list is %s \n", words);
free(h);
return 0;
}
h = h->next;
}
printf(" Data not found");
return 0; }
void display()
{
struct node *temp;
temp=head;
if(temp==NULL)
{
printf("List is Empty");
}
while(temp!=NULL)
{
printf("-> %s ",temp->data);
temp=temp->next;
}
}
/* preform merge sort on the linked list */
struct node *merge_sort(struct node *head)
{
struct node *head_one;
struct node *head_two;
if((head == NULL) || (head->next == NULL))
return head;
head_one = head;
head_two = head->next;
while((head_two != NULL) && (head_two->next != NULL))
{
head = head->next;
head_two = head->next->next;
}
head_two = head->next;
head->next = NULL;
return merge(merge_sort(head_one), merge_sort(head_two));
}
/* merge the lists.. */
struct node *merge(struct node *head_one, struct node *head_two)
{
struct node *head_three;
if(head_one == NULL)
return head_two;
if(head_two == NULL)
return head_one;
if(head_one->data < head_two->data)
{
head_three = head_one;
head_three->next = merge(head_one->next, head_two);
}
else
{
head_three = head_two;
head_three->next = merge(head_one, head_two->next);
}
return head_three;
}
int main()
{
char loc[99];
char words[99];
int i, dat;
head=NULL;
printf("Select the choice of operation on link list");
printf("\n1.) Insert At Begning\n2.) Insert At End\n3.) Insert At Middle");
printf("\n4.) Delete From End\n5.) Reverse The Link List\n6.) Display List\n7.)Exit");
while(1)
{
printf("\n\n Enter the choice of operation you want to do ");
scanf("%d",&i);
switch(i)
{
case 1:
{
printf("Enter a word you want to insert in the 1st node ");
scanf(" %s",words);
insert_beginning(words);
display();
break;
}
case 2:
{
printf("Enter a word you want to insert in the last node ");
scanf(" %s",words);
insert_end(words);
display();
break;
}
case 3:
{
printf("After which data you want to insert your new data ");
scanf(" %s",words);
printf("Enter the data you want to insert in list ");
scanf(" %s",loc);
insert_after(words, loc);
display();
break;
}
case 4:
{
delete_from_end();
display();
break;
}
case 5:
{
printf("Enter the value you want to delete");
scanf(" %s",words);
delete_from_middle(words);
display();
break;
}
case 6 :
{
display();
break;
}
case 7 :
{
exit(0);
break;
}
case 8:
{
head = merge_sort(head);
display();
break;
}
}
}
printf("\n\n%s",last->data);
display();
scanf("%d", &dat);
}