סדנא תרגיל 5 שאלה 3

benny++C, נכתב ע"י Benny, סדנא ב++C, תרגיליםLeave a Comment


Doubly-Linked-List-in-C-and-C-

רשימה מקושרת

סדנא תרגיל 5 שאלה 3 מיזוג רשימות ופעולות נוספות

list.h

#pragma once
#include <iostream>
using namespace std;


class List
{
	private:
	
	class Link
	{
	public:
		// constructor
		Link(int linkValue, Link *nextPtr);
		Link (const Link &);
		// data areas
		int value;
		Link * next;
	};	

	public:
	Link* head;    //  prt to first elemant on the list

	// constructors
	List();
	List(const List&);
	~List();
	
	// operations
	void add( int value);
	int firstElement() const;
	bool search(const int &value) const;
	bool isEmpty() const;
	void removeFirst();
	void print() const;
	void operator=(const List& other);
	void clear();
	void setCin(int);
	friend istream& operator>>(istream&,  List&);
	friend ostream& operator<<(ostream&, const List&);

	void insert (int key);
	void remove (int key);
	


};
	 	  	 	   	   		   	 	    	 	

list.cpp

#include "List.h"
//------------------------------------------------
//  class Link implementation
//------------------------------------------------
List::Link::Link( int val, Link* nxt) : value(val), next(nxt)   {}

List::Link::Link(const Link& source) : value(source.value),next(source.next)  {}
 
//--------------------------------------------
//  class List implementation
//--------------------------------------------

List::List(): head(NULL)
{
	//cout << "CTOR\n";
}

// Copy constructor
List::List(const List &l) 
{
	//cout << "Copy CTOR\n";
	Link *src, *trg;
	if(l.head == NULL)
		head = NULL;
	else
	{  // copy the list
		head = new Link((l.head)->value, NULL);
		src = l.head;
		trg = head;
		while(src->next != NULL)
		{
			trg->next = new Link((src->next)->value, NULL);
			src = src->next;
			trg = trg->next;
		}
	}
}	 	  	 	   	   		   	 	    	 	

void List::operator=(const List& l)
{
	//cout << "ASSIGNMENT OPERATOR\n";

	if(&l != this)                          // prevent self hasama
	{
		this->clear();
		Link *src, *trg;
		if(l.head == NULL)
			head = NULL;
		else
		{  // copy the list
			head = new Link((l.head)->value, NULL);
			src = l.head;
			trg = head;
			while(src->next != NULL)
			{
				trg->next = new Link((src->next)->value, NULL);
				src = src->next;
				trg = trg->next;
			}
		}
	}
}





// Destructor
List::~List()
{
	//cout << "DTOR: ";
	//print();
	clear();
}	 	  	 	   	   		   	 	    	 	

void List::clear()
{
	// empty all elements from the List
	Link* next;
	for (Link *p = head; p != NULL; p = next)
	{
		// delete the element pointed to by p
		next = p->next;
		p->next = NULL;
		delete p;
	}
	// mark that the List contains no elements
	head=NULL;
}

// test to see if the List is empty
// List is empty if the pointer to the head
// Link is null
bool List::isEmpty() const
{
	return head == NULL;
}
 
//Add a new value to the front of a Linked List
void List::add(int val)
{
	head = new Link(val, head);
	if(head == NULL) 
		throw "failed in memory allocation";
}

// return first value in List
int List::firstElement() const
{
	if (isEmpty())
		throw "the List is empty, no first Element";
	return head->value;
}	 	  	 	   	   		   	 	    	 	

bool List::search(const  int &val) const
{
	// loop to test each element
	for (Link* p = head; p != NULL ; p = p->next)
		if (val == p->value)
			return true;
	// not found
	return false;
}

void List::print() const
{
	
	for (Link* p = head; p != NULL ; p = p->next)
		cout << p->value <<" "; 
}

void List::removeFirst()
{
	// make sure there is a first element
	if(isEmpty())
		throw "the List is empty, no Elements to remove";
	// save pointer to the removed node
	Link* p = head;
	// reassign the first node
	head = p->next;
	p->next = NULL;
	// recover memory used by the first element
	delete p;
} 

List merge(List& list1, List& list2)
{
	List list3,list4;
	int num;

	while(!list1.isEmpty() && !list2.isEmpty())   //if to lists is not empty
	{	 	  	 	   	   		   	 	    	 	
		if(list1.firstElement() < list2.firstElement())  
		{
			num = list1.firstElement();        // take the smallest element between to lists
			list1.removeFirst();              // and delete him
		}
		else
		{
			num = list2.firstElement();    // take the smallest element between to lists
			list2.removeFirst();            // and delete him
		}
		list3.add(num);                   //put the smallest element on anew list
		
	}
	while(!list1.isEmpty())   //if list1 is not empty but list2 is empty(list1>list2)
	{
		num = list1.firstElement();   // take the firstElement (sorted allredy)
		list3.add(num);
		list1.removeFirst();
		
	}
	while(!list2.isEmpty())  //if list2 is not empty but list1 is empty(list2>list1)
	{
		num = list2.firstElement();  // take the firstElement (sorted allredy)
		list3.add(num);
		list2.removeFirst();
		
	}
	// Reverse the list (becauze when we copy the list1 to list2 the order is reverse so we need to reverse again)
	while(!list3.isEmpty())
	{
		num = list3.firstElement();
		list4.add(num);
		list3.removeFirst();
	}
	return list4;
}	 	  	 	   	   		   	 	    	 	


List makeSet (List list1)
{
	List list2,list3;

	int num;
	num = list1.firstElement();    // take the first element from the list1 ...
	list2.add(num);                 //... insert the first element to list2
	list1.removeFirst();            //delete the first element from list1.

	while(!list1.isEmpty())
	{
		num = list1.firstElement(); 
		                               // ...  the first 
		if (num!=list2.firstElement())  // if the number is NOT allredy exsit un list2, put him on the list2
		{
			list2.add(num);
			list1.removeFirst();
		}
		else   // its mean: the number allredy exsit. so delete the number from list1.
		{
			list1.removeFirst();
		}

		
	}
	
	//revres the list (becauze when we copy the list1 to list2 the order is reverse so we need to reverse again)
	while(!list2.isEmpty())
	{
		num = list2.firstElement();
		list3.add(num);
		list2.removeFirst();
	}

	return list3;
}	 	  	 	   	   		   	 	    	 	


void List::setCin(int val)  // help function for operator >>
{
	if (head==NULL)
	{
		head = new Link(val,head);
	}
	else
	{
		Link*p=head;
		while (p->next!=NULL)
		{
			p=p->next;
		}
		p->next=new Link(val,p->next);
	}
}


void List::insert (int key)
{
	Link*p=head;     //pointer to the head of the list

	if (key<p->value)     // if key is small from the first one (samllet in the all list)
	{

		head=new Link(key,head);  // put him on the first place

		return;
	}

	while (p->next!=NULL)
		{

			if (key>p->value&&key<(p->next)->value)
			{	 	  	 	   	   		   	 	    	 	
				p->next=new Link(key,p->next);
				return;
			}

			p=p->next;
		}

	while (p->next!=NULL)
		{

			p=p->next;
		}

	if (key>p->value)
			{

				p->next=new Link(key,p->next);

				return;
			}

}


 void List::remove (int key)
 {

	 bool flag = false;       //  to know if throw exeption is necessary

	Link*p=head;

	if (key==p->value)        //if the key (the element to remove) is the first one on the list
	{
		head=head->next;      // promote the head to the next element

		flag=true;            // Match found so dont throw exeption
		return;               // exit now !!
		
	}	 	  	 	   	   		   	 	    	 	


	while (p->next!=NULL)
	{
		if (key==(p->next)->value)     // compare the key to the (p->next)->value is nessesery for deleting 
		{                              // .. becauze the p pointer need to be jump (skip) on the deleting element
			p->next=(p->next)->next;

			flag=true;     //Match found so dont throw exeption

			return;
		}

		p=p->next;
	}
	
	 // in order thae the key(the element to remove) us the last element on the list

	while (p->next!=NULL)
		{

			p=p->next;           // go to the end of the list ...
		}

	if (key==p->value)
		{
			

			p->next=NULL;        // delete the last one

			flag=true;    //Match found so dont throw exeption

			return;
		}
	
	if (!flag)     //Match NOT found so throw exeption
	{	 	  	 	   	   		   	 	    	 	
		throw "value not found";
	}

 }


istream& operator>>(istream& in,  List& list)
{
	int val1,val2;    // initialize to values to compare and only if the second value is bigger..
	in >> val1;       //.. then the first one continue to get input
	
	list.setCin(val1);
	
	in >> val2;
	
                          // input loop to make : if the next num is not biger from the first, stop
	while (val2>val1)    // if the next element > from the erlier
	{
			list.setCin(val2);
			val1=val2;
			in >> val2;
	}

	return in;
}


ostream& operator<<(ostream& out, const List& list)
{
	list.print();            // go to the print function
	return out;
	
}


	 	  	 	   	   		   	 	    	 	

main.cpp



/******************************

targil: 5/3
lecturer: david Cohen
discription: linkd list advence oprations (merge) 

*******************************/
#include <iostream>
#include "List.h"
using namespace std;
List makeSet(List);
List reverse1(List);
List merge(List&, List&);
int main()
{
	List lst1, lst2, mergedList;
	
	cout<<"enter sorted values for the first list:"<< endl;
	cin>>lst1;
	cout<<"enter sorted values for the second list:"<< endl;
	cin>>lst2;

	mergedList = merge(lst1,lst2);
	cout <<"the new merged list: " << mergedList <<endl;

	//mergedList.makeSet(mergedList);
	mergedList= makeSet(mergedList);
	cout<<"the new merged set: " << mergedList << endl;
	
	//system ("pause");
	return 0;
}


/***********OUTPUT***********

enter sorted values for the first list:
1 2 56 4
enter sorted values for the second list:
2 3 5 6 4 7 1 0
the new merged list: 1 2 2 3 5 6 56
the new merged set: 1 2 3 5 6 56
Press any key to continue . . .

*******************************/	 	  	 	   	   		   	 	    	 	

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *