סדנא תרגיל 6 שאלה 1

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

תרגיל ברשימות, מחלקה "רשימה מעגלית היא היורשת מהמחלקה הכללית "רשימה"

תכנית ראשית

#include "RoundList.h"
#include <iostream>
using namespace std;

enum CHOICES{
	EXIT, ADD, ADD_TO_END, REMOVE_FIRST, SEARCH, CLEAR, EMPTY
//    0     1     2           3             4       5     6
};
int main(){
	
	RoundList ls1;
	int choice;
	cout << "Enter your choice: "; 
	cin >> choice;
	while(choice != EXIT)
{
		int num;
		switch(choice){
			case ADD : 	cout << "Enter 5 numbers: ";
				  	for(int i=0; i < 5; i++)
					{
					   	cin >> num;
						ls1.add(num);
					}
					
                    /**************/
					//cout<<ls1<<endl;
					//cout<< "the numbers of the element is:"<<ls1.ListLong()<<endl;
					/***************/
					break;

			case ADD_TO_END :cout << "Enter 5 numbers: ";
						for(int i=0; i < 5; i++)
						{
							cin >> num;
							ls1.addToEnd(num);
						}
					//	        /**************/
					//cout<<ls1<<endl;
					//cout<< "the numbers of the element is:"<<ls1.ListLong()<<endl;
					///***************/
						break;

			case REMOVE_FIRST : ls1.removeFirst();
					///**************/
					//cout<<ls1<<endl;
					//cout<< "the numbers of the element is:"<<ls1.ListLong()<<endl;
					///***************/
						break;

			case SEARCH: cout << "Enter a number: ";
					  cin >> num; 
					  cout << ls1.search(num)<<endl	;
					  break;
		
			case CLEAR: ls1.clear();
					break;

			case EMPTY: if(ls1.isEmpty())
						cout << "Empty"<<endl;
					else
						cout << "Not empty" << endl;
					break;

			default: cout<< "ERROR!"<<endl;
		}
		cout << "Enter your choice: "; 
		cin >> choice;
	}
	return 0;
}

המחלקה List

#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;
	int search( int value) ;
	bool isEmpty() const;
	void removeFirst();
	void print() const;
	void operator=(const List& other);
	void clear();
	void setCin(int);
	List reverse1(List src);
	int ListLong();

	friend istream& operator>>(istream&,  List&);
	friend ostream& operator<<(ostream&, const List&);

	void insert (int key);
	void remove (int key);
	void makeSet (List); // delet dubbls
	void addToEnd(int);

};

מימוש המחלקה List

#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;
}



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(list1.firstElement() < list2.firstElement())
		{
			num = list1.firstElement();
			list1.removeFirst();
		}
		else
		{
			num = list2.firstElement();
			list2.removeFirst();
		}
		list3.add(num);
		
	}
	while(!list1.isEmpty())
	{
		num = list1.firstElement();
		list3.add(num);
		list1.removeFirst();
		
	}
	while(!list2.isEmpty())
	{
		num = list2.firstElement();
		list3.add(num);
		list2.removeFirst();
		
	}
	// Reverse the list
	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:: makeSet (List list1)
{
	//cout<<"enterd\n";
	Link*p = head;
	int m=0;
	while (p->next!=NULL)
	{
		if (p->value==(p->next)->value)
		{
			//cout<<"dasdsdsdasd\n";
			p->next=(p->next)->next;
		}
		p=p->next;
	}
	
	//cout<<"outred\n";

}



List reverse1(List src)
{
	
	List dest;
	// Reverse the list
	while(!src.isEmpty())
	{
		int num = src.firstElement();
		dest.add(num);
		src.removeFirst();
	}
	return dest;
}

void List::setCin(int val)
{
	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)
	{
		//cout<<"put in the begining\n";

		head=new Link(key,head);

		return;
	}

	while (p->next!=NULL)
		{

			if (key>p->value&&key<(p->next)->value)
			{
				//cout<<"put in the middle\n";
				p->next=new Link(key,p->next);
				return;
			}

			p=p->next;
		}

	while (p->next!=NULL)
		{

			p=p->next;
		}

	if (key>p->value)
			{
				//cout<<"put in the end\n";

				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;
	

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


int List::ListLong()
{
	Link*p=head;
	int count=0;
	if (this->isEmpty())
	{
		return 0;
	}


	/*if (this->ListLong()==1)
	{
		return 0;
	}*/
	while (p->next!=NULL)
	{
		count++;
		//cout<<p->value<<" ()";
		p=p->next;
		
	}
	return count+1;
}


void List::addToEnd(int key)
{
	Link*p=head;
	if (this->isEmpty())
	{
		this->add(key);
	}
	else
	{
		while (p->next!=NULL)  // go to the end
		{

			p=p->next;
		}

		p->next=new Link(key,p->next);   // add in the end end
	}
	

}


int List::search(int index) 
{
	int key;
	//cout<<	 "the long insude the fun is:"<<this->ListLong()<<endl;
	int i=0;
	if (this->isEmpty())
	{
		return -1;
	}
	if (index>=this->ListLong())
	{
		for (Link* p = head; p != NULL ; p = p->next)
			{
				if (i==index%this->ListLong())
				{
					key=p->value;
					//cout<<"the index is:"<<index<<" the i is:"<<i<<" the key is: "<<key<<endl;
				}
				i++;
			}
			
			return key;
	}
	else
	{
		for (Link* p = head; p != NULL ; p = p->next)
			{
				if (i==index)
				{
					key=p->value;
					//cout<<"the index is:"<<index<<" the i is:"<<i<<" the key is: "<<key<<endl;
					return key;
				}
				i++;
			}
		return key;
	}
}

// לבדוק אם צריך להפוך

List List:: reverse1(List src)
{
	List dest;
	// Reverse the list
	while(!src.isEmpty())
	{
		int num = src.firstElement();
		dest.add(num);
		src.removeFirst();
	}
	return dest;
}

המחלקה RoundList

#include "List.h"
#pragma once
class RoundList:public List
{
public:
	//void addToEnd(int);
	RoundList(void);
	~RoundList(void);
};


מימוש המחלקה RoundList

#include "RoundList.h"


RoundList::RoundList(void)
{
	//cout<<"RoundList c-tor on\n";
}



RoundList::~RoundList(void)
{
}


כתיבת תגובה

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