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;
}
*/