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