Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Binary search in linkedlist (http://www.go4expert.com/forums/binary-search-linkedlist-t12333/)

aali 22Jul2008 13:22

Binary search in linkedlist
 
Hi guys

when I tried to search in kinked listby binary search
it's written in the output

"Segmenationfault"

I want to solv this problem
/**************************/
The code
Code:

#include<iostream>
#include <iostream>
#include <cstring>
using namespace std;

struct Node
{
        char * data;
        Node * prev;
        Node * next;

        Node( char * newData = NULL , Node * newPrev=NULL, Node * newNext=NULL)
        {
                data=NULL;
                updateData(newData);
                prev=newPrev;
                next=newNext;
        }

        ~Node()
        {
                if(data!=NULL) delete data;
        }

        void updateData(char *newData)
        {
                if(newData!=NULL)
                {
                        if(data!=NULL)
                                delete [] data;
                       
                        data=new char[strlen(newData)+1];
                        strcpy(data,newData);
                }
                else
                        data=NULL;
        }
};

class DoubleLinkedList
{
private:
        Node * first;
       
        void destroy();
public:
       
        DoubleLinkedList(const DoubleLinkedList & copy)
        {
                Node * last_ptr, * current_Copy = copy.first , *newPtr;
                first=NULL;
                while(current_Copy!=NULL)
                {
                        newPtr = new Node(current_Copy->data );
                        if (first == NULL)
                        {
                                first = newPtr;
                                last_ptr = newPtr;
                        }
                        else
                        {
                                last_ptr->next = newPtr;
                                newPtr->prev=last_ptr;
                                last_ptr = newPtr;
                        }
                        current_Copy=current_Copy->next;
                }
        }

        DoubleLinkedList();
       
        ~DoubleLinkedList();

        void BuildList(char * stringArray[],int ArrayLength);

        void addBeforeNode(char * newData,char * searchData);

        void deleteNode(char * searchData);

        int deleteOccurance(char * searchData);

        void printList();

        void reverse();

        void doublicte();
        int length()
        {
                int counter=0;
                Node* current=first;
                if(first==NULL)
                        return 0;

                while(current!=NULL)
                {
                        counter++;
                        current=current->next;
                }       
                return counter;
        }
       
        void insetSorted( char*newdata);

Node * BinarySearch_DLL ( char * searchData)
        {
        int n = length();
        Node * MyFirst=first;

        while(MyFirst!=NULL)
                MyFirst=MyFirst->next;
        //Node* prev;       
        Node* last_ptr=MyFirst;

        MyFirst=first;
               
        Node * MyLast=last_ptr;

        Node * midel;

        if( n == 0)
                return NULL;

        if( strcmp(searchData , MyFirst->data)>0 ||strcmp( searchData ,MyLast->data )<0)
                        {
                                cout<<"false";
                                return NULL;
                        }
               
        while (        MyFirst != MyLast->next)
        {
                        cout<<"true2";

                        midel=MyFirst;

                        for (int i=0 ; i<(n/2) ; i++)

                        midel=midel->next;

                        if(strcmp(searchData,midel->data)==0 )
                        {
                        return midel;
                        cout<<"true1";
                        }
        else
        {
                if(strcmp(searchData,midel->data)>0)
                {
                        n=n/2;
                        MyFirst=midel->next;
                        cout<<"true2";
                }
                else
                {
                        n=(n-1)/2;
                        MyLast=midel->prev;
                        cout<<"true3";
                }

        }
}
}       
       
};
//----------------------------------Simlar to SLL-----------------------------------------
DoubleLinkedList::DoubleLinkedList()
{
        first=NULL;
}
//----------------------------------Simlar to SLL-----------------------------------------
DoubleLinkedList::~DoubleLinkedList()
{
        destroy();
}
//----------------------------------Simlar to SLL-----------------------------------------
void DoubleLinkedList::destroy()
{
        Node *current;
        while (first != NULL)
        {
                current = first;
                first = first->next;
                delete current;
        }
        first = NULL;
}
//---------------------------------------------------------------------------------------
void DoubleLinkedList::BuildList(char* stringarray[], int arraylength)
{
        destroy();
        Node *new_ptr, *last_ptr;
    for (int i=0; i<arraylength; i++)
        {
                new_ptr = new Node();
                new_ptr->updateData( stringarray[i] );
                if (first == NULL)
                {
                        first = new_ptr;
                        last_ptr = new_ptr;
                }
        else
        {
                        last_ptr->next = new_ptr;
                        new_ptr->prev=last_ptr;
                        last_ptr = new_ptr;
        }
       
  }
}
//---------------------------------------------------------------------------------------
void DoubleLinkedList::addBeforeNode(char *newData,char *searchData)
{
        Node * current=first;
        while(current!=NULL && strcmp(current->data,searchData) != 0)
                        current=current->next;

        if(current!=NULL)
        {
                Node * newNode=new Node(newData);
                if(current == first)
                {
                        newNode->next=first;
                        first->prev=newNode; //new line
                        first=newNode;
                }
                else
                {
                        newNode->next = current;
                        newNode->prev=current->prev; //new line
                        current->prev->next=newNode; //line modified form prev -> next = newNode;
                        current->prev=newNode;      //new line       
                }
        }
}
//---------------------------------------------------------------------------------------
void DoubleLinkedList::deleteNode(char *searchData)
{
        Node * current;
        current=first;
        while(current!=NULL && strcmp(current->data,searchData)!=0)
                        current=current->next;

        if(current!=NULL)
        {
                if(current==first)
                {
                        first=first->next;
                        if(first!=NULL)  first->prev=NULL;                        //new line
                }
                else if(current->next == NULL)        //new line
                        current->prev->next = NULL;        //new line
                else
                {
                        current->prev->next=current->next;//line modified form prev -> next = current->next;
                        current->next->prev=current->prev;//new line
                }
       
                delete current;       
        }
}

//---------------------------------------------------------------------------------------
void DoubleLinkedList::printList()
{
        Node *current=first;
        cout<<"List Contains : "<<endl;
        if(current==NULL)
                cout<<"Empty List"<<endl;
        else
        {
                while(current!=NULL)
                {
                        if(current->data !=NULL)
                        cout<<current->data<<endl;
                        current=current->next;
                }
                cout<<endl;
        }
}

void DoubleLinkedList::reverse()
{
                Node * current=first,*temp;
                while(current!=NULL)
                {
                        // swap Node pointers next , prev
                        temp=current->next;
                        current->next=current->prev;
                        current->prev=temp;
                        // set first at the last node in the list
                        if(current->prev == NULL)
                                first=current;
                        // set current pointer to the next node in the list
                        current=current->prev;
                }
}

void DoubleLinkedList::doublicte()
{
                Node * current = first , *newPtr ;
                while(current!=NULL)
                {
                        newPtr= new Node (current ->data , current,current->next);
                        /*
                        newPtr= new Node;
                        newPtr->updateData(current ->data);
                        newPtr->next = current->next;
                        newPtr->prev = current;
                        */
                        if(current->next !=NULL)
                                current->next ->prev =newPtr;
                        current->next = newPtr;
                        current = newPtr->next ;
                }
}



int DoubleLinkedList::deleteOccurance(char * searchData)
{
        Node * current=first;
        int count = 0;

        while(current!=NULL)
        {
                if( strcmp(current->data,searchData)==0 )
                {
                        Node * nextNode=current->next;
                        if(current == first)
                        {
                                first=first->next;
                                if(first!=NULL)  first->prev=NULL;                        //new line
                        }
                        else if(current->next == NULL)        //new line
                                current->prev->next = NULL;        //new line
                        else
                        {
                                current->prev->next=current->next;//line modified form prev -> next = current->next;
                                current->next->prev=current->prev;//new line
                        }
                        delete current;       
                        current = nextNode;
                        count++;
                }
                else
                        current=current->next;
        }
        return count;
}
//---------------------------------------------------------------------------------------
void DoubleLinkedList::insetSorted( char*newdata)
{
        Node* current=first;
        Node* temp;
        Node* newptr=new Node;
        newptr->updateData(newdata);
       
        if(first==NULL)
        {
                first=newptr;
        }
        while(current!=NULL)
        {
                if(strcmp(newdata,current->data)<0)
                {
                        if(current==first)
                        {
               
                        newptr->next=first;
                        first->prev=newptr;
                        first=newptr;
                        return;
                        }
                        else
                        {       
                        newptr->next=current;
                        newptr->prev=current->prev;
                        current->prev->next=newptr;
                        current->prev=newptr;
                        return;
                        }
                }
                        else       
                        temp=current;               
                        current=current->next;               
                       
        }
       
}
int main()
{
        DoubleLinkedList obj1;
        char* strings[] = { "a", "b", "c", "d", "e" };

        obj1.BuildList( strings, 5 );
        DoubleLinkedList obj2 ;
        obj1.BinarySearch_DLL ("Bader" );
        obj1.printList();
        //obj2.doublicte();
        /*
        obj2.insetSorted("aali" );
        obj2.insetSorted("Bader" );
        obj2.insetSorted("careem" );
        obj2.insetSorted("Fahad" );
        obj2.insetSorted("Dema" );
        obj2.insetSorted("ali" );
        obj1.printList();
        obj2.printList();
                */
        /*cout<<"Reverse"<<endl;
        obj2.reverse();
        obj2.printList();*/
        return 0;
}

/*
int main()
{
        DoubleLinkedList obj;
        char* strings[] = { "ahmed", "yousif", "salem", "hamed", "yousif" };

        obj.BuildList( strings, 5 );
        obj.printList();
        cout<<endl;

        cout<<"Add naser Befor ahmed :"<<endl;
        obj.addBeforeNode("naser","ahmed");
        obj.printList();
       
        obj.addBeforeNode("saad","hamed");
        obj.printList();

        cout<<"Delete salem from list :"<<endl;
        obj.deleteNode("salem");
        obj.printList();

        cout<<"Delete naser from list :"<<endl;
        obj.deleteNode("naser");
        obj.printList();

        obj.reverse();
        obj.printList();
        obj.doublicte();
        obj.printList();
        obj.deleteOccurance("yousif");
        obj.printList();
        return 0;
}
*/


xpi0t0s 23Jul2008 15:37

Re: Binary search in linkedlist
 
What line does it crash on?

You can find this out (a) by stepping through the code in a debugger or (b) liberally sprinkling printf() statements throughout the code (also use fflush so that the output is displayed immediately after the printf, otherwise you'll get very confused). For example:
Code:

void DoubleLinkedList::BuildList(char* stringarray[], int arraylength)
{
printf("Entered DoubleLinkedList::BuildList()"\n");fflush(stdout);
        destroy();
printf("Back from destroy()\n");fflush(stdout);
        Node *new_ptr, *last_ptr;
    for (int i=0; i<arraylength; i++)
        {
printf("In loop, i=%d\n",i);fflush(stdout);
                new_ptr = new Node();
printf("Created new node at 0x%08x\n",new_ptr);fflush(stdout);
                new_ptr->updateData( stringarray[i] );
printf("Back from updateData()\n");fflush(stdout);

...and so on

Then if, say, it printed "Created new node at..." but not "Back from updateData" then you know it crashed somewhere in Node::updateData(); and more debug code will need adding along the same lines as above to determine where it went wrong.

This is a technique I use a lot when developing software; I find it helps a lot to see what is really going on, rather than relying on what I think is going on (because usually what I think wouldn't lead to a crash, but if it does crash then what I think *must* be wrong).

aali 23Jul2008 22:40

Re: Binary search in linkedlist
 
Sorry
my code in c++
not in c
and my compiler is g++

xpi0t0s 24Jul2008 01:43

Re: Binary search in linkedlist
 
And because of that you think you can't use printf?

abhishek_kulkarni 23May2011 14:33

Re: Binary search in linkedlist
 
Try the following code....

Code:

#include<stdio.h>
#include<malloc.h>

typedef struct node
{
        int data;
        struct node *next;
}NODE;
NODE *CreateList()
{
        int total,num,flag=0,i;
        NODE *start,*new,*last;
        printf("\nHow many Nodes? : ");
        scanf("%d",&total);

        start = NULL;
        for (i=0; i<total; i++)
        {
                printf("\nEnter Data : ");
                scanf("%d",&num);

                new = (NODE *)malloc(sizeof(NODE));
                new->data = num;
                new->next = NULL;

                if(flag == 0)
                {
                        start = new;
                        last = start;
                        flag = 1;
                }
                else
                {
                        last->next = new;
                        last = new;
                }
        }
        return start;
}
Show(NODE *head)
{
        NODE *temp;
        temp = head;

        printf("\n");
        if(temp==NULL)
        {
                printf("\nThe list is empty");
                return;
        }
        while(temp != NULL)
        {
                printf(" %d ",temp->data);
                temp = temp->next;
        }
        printf("\n");
}
int Lookup(NODE *start,NODE *end,int num)
{
        NODE *head1,*head2,*mid,*b4mid;
        int found = 0;

        head1 = start;
        head2 = start;

        while( (head2 != end) && (head2->next != end) )
        {
                head2 = head2->next->next;
                b4mid = head1;
                head1 = head1->next;
        }

        mid = head1;
        printf("\nStart = %d, Mid = %d,End = %d, Data = %d",start->data,mid->data,end->data,num);

        if(mid->data < num)
        {
                if(end->data < num || num < start->data) /*Num is beyond range*/
                        found = 0;
                else
                        found += Lookup(mid->next,end,num);
        }
        else if(mid->data > num)
        {
                if(start->data > num)
                        found = 0;
                else
                        found += Lookup(start,b4mid,num);
        }
        else if(mid->data == num)
                found += 1;
        else
                found = 0;

        return found;
}
int BinarySearch(NODE *head,int num)
{
        NODE *start,*mid,*b4mid,*end,*head1,*head2;
        int found = 0;
        head1 = head;
        head2 = head;
        start = head;

        while( (head2!=NULL) && (head2->next != NULL) )
        {
                head2 = head2->next->next;
                b4mid = head;
                head  = head->next;
        }

        mid = head;
        end = head2;
        printf("\nStart = %d, Mid = %d,End = %d, Data = %d",start->data,mid->data,end->data,num);

        if(mid->data < num)
        {
                if(end->data < num) /*Num is beyond range*/
                        found = 0;
                else
                        found += Lookup(mid->next,end,num);
        }
        else if(mid->data > num)
        {
                if(start->data > num)
                        found = 0;
                else
                        found += Lookup(start,b4mid,num);
        }
        else if(mid->data == num)
                found += 1;
        else
                found = 0;

        return found;
}
main()
{
        int val;
        NODE *head;
        head = CreateList();
        Show(head);
        printf("\nTo be searched? ");
        scanf("%d",&val);
        val = BinarySearch(head,val);
        if(val == 1)
        {
                printf("\nData found in a given list\n");
        }
        else
        {
                printf("\nData does not exist in a given list\n");
        }
}



All times are GMT +5.5. The time now is 22:05.