Binary search in linkedlist

Discussion in 'C' started by aali, Jul 22, 2008.

  1. aali

    aali New Member

    Joined:
    Jul 16, 2008
    Messages:
    18
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    student
    Location:
    Riyadh
    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;
    }
    */
     
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    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).
     
  3. aali

    aali New Member

    Joined:
    Jul 16, 2008
    Messages:
    18
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    student
    Location:
    Riyadh
    Sorry
    my code in c++
    not in c
    and my compiler is g++
     
  4. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    And because of that you think you can't use printf?
     
  5. abhishek_kulkarni

    abhishek_kulkarni New Member

    Joined:
    May 23, 2011
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    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");
            }
    }
    
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice