BIL 221 - Veri Yapıları
1998-99 Güz  Yarıyılı
Arasınav-2 Cevap Anahtarı
--------------------------

Soru 1)
Ford&Topp, Written Exercise 7.5)  (Solution is in the book)

template <class T>
void InsertOrder (T  A [],  int size, const T& elem)
{
	int i=0;	// assume size > 0

	while (i<size && A[i]<elem) i++; // locate insertion point
	   
	if (i < n)
	   for (int j = n; j > i; j--) // move tail to right
	       A[j] = A[j-1];
	A[i] = elem; 	// insert the element
}

int operator< (Student s1, Student s2)
{
	return strcmp(s1.name, s2.name) < 0;
}

ostream& operator<< (ostream& ostr, Student s)
{
	cout<<s.name;
	for (int i=0; i<3; i++) cout<<s.grades[i];
}

Soru 2)
Ford&Topp, Similar to Written Exercise 8.5) 

template <class T>
class   DummyType
{
	private:
		T   sval;				// stored value	 
		T   *dval;				// points the a second stored value
	public:
		// Constuctor and copy constructor
		DummyType(T svalue, T dvalue);
		DummyType(const DummyType<T>& x);

		// Assignment operator
		DummyType<T>& operator= (const DummyType<T>&  x);

		// Destructor
		~DummyType( );

		// Data handling methods
		void SetValue(T svalue, T dvalue);	// sets the stored values

		// Stream input and output
   		friend ostream& operator<< (ostream& ostr, 
 					    const DummyType<T>& x);
		friend ostream& operator>> (istream& istr, 
				            const DummyType<T>& x);
}
	
template <class T>
DummyType<T>::DummyType(T svalue, T dvalue)
{
	sval = svalue;
	dval = new T(dvalue);
}

template <class T>
DummyType<T>::DummyType(const DummyType<T>& x)
{
	sval = x.svalue;
	dval = new T(*x.dvalue);
}

template <class T>
DummyType<T>& DummyType<T>::operator= (const DummyType<T>&  x)
{
	sval = x.svalue;
	*dval = *x.dvalue;
}

template <class T>
DummyType<T>::~DummyType( )
{
	delete dval;
}

template <class T>
void DummyType<T>::SetValue(T svalue, T dvalue)
{
	sval = svalue;
	*dval = dvalue;
}

template <class T>
friend ostream& operator<< (ostream& ostr, const DummyType<T>& x)
{
	ostr << sval;
	ostr << *dval;
}
		
template <class T>
friend ostream& operator>> (istream& istr, const DummyType<T>& x)
{
	istr >> sval;
	istr >> *dval;
}

Soru 3)
Ford&Topp, Similar to Written Exercise 9.12) 

template <class T>
void DeleteKey(Node<T>* &head, T key)
{
	//maintain pointers to previous and current nodes
	Node<T> *prevPtr=NULL, *currPtr=head, *p;

	//traverse the list, performing the deletions
	while (currPtr != NULL) {
	   if (currPtr->data == key) { //check for a match with key
	      p = currPtr;   // remember the current node address in p
	      currPtr = currPtr->NextNode();  //move currPtr forward
	      
	      if (prevPtr == NULL) {//see if deletion occured at front of list
		 head = currPtr; 
	      else 
	         prevPtr->DeleteAfter();
	      delete p;
	   }
	   else {  //no match, advance the pointers
	      prevPtr = currPtr;
	      currPtr = currPtr->NextNode();
	   }
	}
}
     	
Soru 4)
Ford&Topp, Similar to Written Exercise 9.8) 

template <class T>
void MergeLists(Node<T> *L1, Node<T> *L2, Node<T>* &L3)
{
	L3 = NULL;   

	Node<T> *pL1=L1, *pL2=L2, *pL3=L3;

	while (pL1 != NULL && pL2 != NULL) {
	   if (pL1->data <= pL2->data) {
	      Append(L3, pL3, pL1, 1);
	      pL1 = pL1->NextNode();
	   }
	   else {
              Append(L3, pL3, pL2, 1);
	      pL2 = pL2->NextNode();
	   }
	}

        // add remaining nodes of the longer list to the end of L3
	if (pL1 != NULL)
	   Append(L3, pL3, pL1, 0);
	else	
	   Append(L3, pL3, pL2, 0);
}

template <class T>
void Append(Node<T>* &headL3, Node<T>* &rearL3, Node<T>* pL12, int onenode)
{
	Node<T> *newNode;

	if (pL12 == NULL) return;  //source list (L1 or L2) is empty

	if (headL3 == NULL) {	//destination list (L3) is empty
	   headL3 = new Node<T>(pL12->data);
	   rearL3 = headL3;

	   if (onenode) return;

	   pL12 = pL12->NextNode();
	}

	// if destination list (L3) is not empty.
	// L3 is empty but onenode is false then append the remainder of list L.
	while (pL12 != NULL) {
	   newNode = new Node<T>(pL12->data);
	   rearL3->InsertAfter(newNode);
	   rearL3 = newNode;

	   if (onenode) return;

	   pL12 = pL12->NextNode();
	}
}