yann.bohbot.9 0 Light Poster

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);
}