Download to read offline
implement the ListLinked ADT (the declaration is given in ListLinked.pdf
- 1. implement the ListLinkedADT (the declaration is given in ListLinked.h)(60 points) - implement the following operations: - constructor, assignment operator, destructor - insert, remove, replace, clear - isFull, isEmpty - gotoBeginning, gotoEnd, gotoNext, gotoPrior, getCursor implement the function moveToBeginning() that removes the data item marked by the cursor and reinserts it at the beginning of the list - implement the function insertBefore(..) that will insert the new data item before the cursor or if the list is empty as the first element of the list #include "ListLinked.h" // ListNode member functions template List::ListNode::ListNode(const DataType& nodeData, ListNode* nextPtr) { this->dataItem = nodeData; this->next = nextPtr; } // List member functions template List::List(int ignored = 0) { } template List::List(const List& other) { } template List& List::operator=(const List& other) { } template List::~List() { }
- 2. template void List::insert(const DataType&newDataItem) throw (logic_error) { } template void List::remove() throw (logic_error) { } template void List::replace(const DataType& newDataItem) throw (logic_error) { } template void List::clear() { } template bool List::isEmpty() const { return false; } template bool List::isFull() const { return false; } template void List::gotoBeginning() throw (logic_error) { } template void List::gotoEnd() throw (logic_error) { } template bool List::gotoNext() throw (logic_error)
- 3. { return false; } template bool List::gotoPrior()throw (logic_error) { return false; } template DataType List::getCursor() const throw (logic_error) { DataType t; return t; } template void List::moveToBeginning () throw (logic_error) { } template void List::insertBefore(const DataType& newDataItem) throw (logic_error) { } #include "show5.cpp" Solution #include #include #include using namespace std; struct Node { int data; Node *next; }; Node *tail=NULL;
- 4. Node* Insert_atHead(Node *head,int data) { Node *temp=new Node; temp->data=data; temp->next=head; head=temp; return head; } Node* Insert_atTail(Node *head, int data) { Node *tail=head; if(tail==NULL) { Node *temp = new Node; temp->data=data; temp->next=NULL; head=temp; return head; } while(tail!= NULL) { if(tail->next==NULL) { Node *temp=new Node; temp->data=data; temp->next=NULL; tail->next=temp; return tail; } else { tail=tail->next; } } } Node *Insert_atPosition(Node *head, int data, int position)
- 5. { int i=0; int j=position-1; if(position==0) { Node*temp = new Node; temp->data=data; temp->next=head; head=temp; return head; } else { Node *temp=head; while(inext; i++; } Node *temp1 = new Node; temp1->data=data; temp1->next=temp->next; temp->next=temp1; return head; } return head; } Node* Delete(Node *head, int position) { Node *temp=head; int i=1; int j=position; if(j==0) { head=head->next; return head; } Node *temp1 = new Node;
- 6. while(j>0) { temp1=temp; temp=temp->next; j--; } temp1->next=temp->next; delete temp; return head; } intGetNode(Node *head,int positionFromTail) { Node *tail=head; int l=0; while(tail->next!=NULL) { tail=tail->next; l++; } int i=(l-positionFromTail); Node *temp=head; while(i>0) { temp=temp->next; i--; } return temp->data; } int Size_ofLinkedList(Node *head) { int S=0; Node *temp = head; while(temp!= NULL) { S++;
- 7. temp=temp->next; } return S; } Node *Reverse_LinkedList(Node*head) { Node *temp1 = head; Node *tail = NULL; Node *head1= new Node; while(head!=NULL) { head1=head; temp1=temp1->next; head->next=tail; tail=head; head=temp1; } head=head1; } int CompareLists(Node *headA, Node* headB) { Node *tempA=headA; Node *tempB=headB; while(tempA!=NULL && tempB!=NULL) { if(tempA->data==tempB->data) { tempA=tempA->next; tempB=tempB->next; } else { return 0;
- 8. } } if(tempA==NULL && tempB==NULL) { return1; } else { return 0; } } int FindMergeNode(Node *headA, Node *headB) { Node *tempA=headA; Node *tempB=headB; int m=0; int n=0;; while(tempA!=NULL) { tempA=tempA->next; m++; } while(tempB!=NULL) { tempB=tempB->next; n++; } tempA=headA; tempB=headB; int Data; if(m>n) { int p=m-n; while(p>0) {
- 9. tempA=tempA->next; p--; } while(tempA!=tempB) { tempA=tempA->next; tempB=tempB->next; } Data=tempA->data; } else { int p =n-m; while(p>0) { tempB=tempB->next; p--; } while(tempA!=tempB) { tempA=tempA->next; tempB=tempB->next; } Data=tempA->data; } return Data; } Node* RemoveDuplicates(Node *head) { Node *temp=head; Node *temp1 = new Node; while(temp->next!=NULL) { if(temp->data!=(temp->next)->data) {
- 10. temp=temp->next; } else { temp1=temp->next; temp->next=temp1->next; delete temp1; } } return head; } Node*MergeLists(Node *headA, Node* headB) { Node *temp = new Node; Node *head = new Node; if(headA==NULL || headB==NULL) { if(headA==NULL) { head=headB; } else { head=headA; } return head; } if(headA->data<=headB->data) { temp=headA; headA=headA->next; } else { temp=headB;
- 11. headB=headB->next; } head=temp; while(headA!=NULL && headB!=NULL) { if(headA->data<=headB->data) { temp->next=headA; temp=temp->next; headA=headA->next; } else { temp->next=headB; temp=temp->next; headB=headB->next; } } if(headA==NULL&& headB!=NULL) { temp->next=headB; } if(headA!=NULL && headB==NULL) { temp->next=headA; } return head; } int HasCycle(Node* head) { Node *temp1=head; Node *temp2=head;
- 12. int X=0; if(head==NULL ||head->next==NULL) { X=0; } else { temp1=temp1->next; temp2=(temp2->next)->next; while(temp1!=temp2) { if(temp2->next==NULL || (temp2->next)->next==NULL) { X=0; break; } temp1=temp1->next; temp2=(temp2->next)->next; X=1; } } if(X==0) { return 0; } else { return 1; } } void Print(Node *head) {
- 13. Node *temp =head; while(temp!= NULL) { cout<data<< " --> "; temp=temp->next; } cout<< "NULL"; } void ReversePrint(Node *head) { Node *temp1 = head; Node *tail = NULL; Node *head1= new Node; if(head!=NULL) { while(head!=NULL) { head1=head; temp1=temp1->next; head->next=tail; tail=head; head=temp1; } Node *temp=head1; while(temp!= NULL) { cout<data<< " "; temp=temp->next; } } } int main() { int data;
- 14. Node *head=NULL; int H; cout<<"No. of Node Insertion at Head: "; cin>>H; while(H>0) { cin>>data; head=Insert_atHead(head, data); H--; } int T; cout<< "No. of Node Insertion at Tail: "; cin>>T; while(T>0) { cin>>data; Insert_atTail(head,data); T--; } int P; cout<< " "; cout<< "Add Node at Position: "; cin>>P; cout<< " "; cout<< "data: "; cin>>data; Insert_atPosition(head,data,P); cout<< " "; cout<< "Delete Node at Position: "; cin>>P; Delete(head,P); cout<< " "; Print(head); Reverse_LinkedList(head); head=tail; cout<< " ";
- 15. Print(head); cout<< " "; cout<<"Size of LinkedList: "<