cSet07
[ Home ] [ Up ]

//CSet07.cpp
//Date 05/07/2003
//Author: AOU


/*
Added the following functions:

    CSet(int n);
    void sortBubble(void);

*/


////////////////////////////////////////////////////////////
// include files
////////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>


////////////////////////////////////////////////////////////
// constants
////////////////////////////////////////////////////////////
const int UNDEFINED = -99;
const int MAX_VALUE = 99;
const int MAX_COUNT = 20;


////////////////////////////////////////////////////////////
// class CNode
////////////////////////////////////////////////////////////
class CNode
  {
  private:
    int m_info;
    CNode *m_next;
  public:
    CNode(void);
    CNode(int x);
    void display(void) const;

    CNode(char ch);

    int get(void);
    void set(int x);
    friend ostream & operator << (ostream & tom, CNode node);
    bool operator == (CNode node);

    bool operator < (CNode node);
    bool operator <= (CNode node);
    bool operator != (CNode node);

    friend class CSet;

    CNode * addressOfNext(void);
  };


////////////////////////////////////////////////////////////
// class CSet
////////////////////////////////////////////////////////////
class CSet
  {
  private:
    CNode *m_first;
    int m_n;
  public:
    CSet(void);

    void display(void) const;
    void insertAtHead(int x);
    friend ostream & operator << (ostream & tom, const CSet &set);

    CSet(char ch);
    ~CSet(void);

    CSet(int n);
    void sortBubble(void);


    CNode* seqSearch(int x);
    void sortSelection(void);
    void sortInsertion(void);
  };


////////////////////////////////////////////////////////////
// main
////////////////////////////////////////////////////////////
void main(void)
  {
  /*
  CNode myNode;
  myNode.display();
  cout << endl;

  CNode myNode1(55);
  myNode1.display();
  cout << endl;

  CNode myNode2('r');
  myNode2.display();
  cout << endl;

  cout << "info=" << myNode2.get() << endl;

  myNode2.set(32);

  cout << "info=" << myNode2.get() << endl;

  cout << myNode2 << endl;

  if (myNode1 == myNode2)
      cout << "myNode1 is equal to myNode2\n";
    else
      cout << "myNode1 is NOT equal to myNode2\n";

  myNode1 = myNode2;
  if (myNode1 == myNode2)
      cout << "myNode1 is equal to myNode2\n";
    else
      cout << "myNode1 is NOT equal to myNode2\n";
  */




  /*
  {
  cout << "Testing operator < \n";
  cout << "-------------------\n";

  CNode n1('r'), n2('r');
  cout << n1 << endl << n2 << endl;
  if (n1 < n2) 
      cout << "n1 is less than n2\n";
    else
      cout << "n1 is NOT less than n2\n";

  CNode m1('r'), m2('r');
  cout << m1 << endl << m2 << endl;
  if (m1 < m2) 
      cout << "m1 is less than m2\n";
    else
      cout << "m1 is NOT less than m2\n";
  }

  {
  cout << "Testing operator <= \n";
  cout << "--------------------\n";

  CNode n1('r'), n2('r');
  cout << "n1=" << n1 << endl << "n2=" << n2 << endl;

  if (n1 <= n2) 
      cout << "n1 is <=  n2\n";
    else
      cout << "n1 is NOT <= n2\n";

  if (n2 <= n1) 
      cout << "n2 is <=  n1\n";
    else
      cout << "n2 is NOT <= n1\n";
  }

  
  {
  cout << "Testing operator != \n";
  cout << "--------------------\n";

  CNode n1('r'), n2('r');
  cout << "n1=" << n1 << endl << "n2=" << n2 << endl;

  if (n1 != n2) 
      cout << "n1 is !=  n2\n";
    else
      cout << "n1 is = n2\n";

  n1 = n2;
  if (n1 != n2) 
      cout << "n1 is !=  n2\n";
    else
      cout << "n1 is = n2\n";
  }
  */
    /*
    {
    CSet set1;
    set1.display();
    cout << endl;
    cout << set1;
    cout << endl;

    set1.insertAtHead(5);
    set1.display();
    cout << endl;
    cout << set1;
    cout << endl;

    set1.insertAtHead(6);
    set1.display();
    cout << endl;
    cout << set1;
    cout << endl;

    }
    */
  /*
  {
  for (int i=1; i<=10; i++)
    {
    CSet set1('r');
    cout << set1 << endl;
    }
  }
  */

  /*
  {
  for (int i=1; i<=10; i++)
    {
    CSet set1(i);
    cout << set1 << endl;
    }
  }
  */

  {
  for (int i=1; i<=10; i++)
    {
    CSet set1(i);
    cout << set1 << endl;
    set1.sortBubble();
    cout << set1 << endl;
    }
  }
  
  }

void CSet::sortBubble(void)
  {
  if (this->m_n <= 1)
      return;

  bool somethingChanged;
  CNode *p;

  do
    {
    somethingChanged = false;
    for (p=this->m_first; p->m_next!=NULL; p=p->m_next)
      {
      if (p->m_info > p->m_next->m_info)
          {
          int temp = p->m_next->m_info;
          p->m_next->m_info = p->m_info;
          p->m_info = temp;
          somethingChanged = true;
          }
      }
    } while (somethingChanged == true);
  
  }


CSet::CSet(int n)
  {
  this->m_n = 0;
  this->m_first = NULL;

  for (int i=1; i<=n; i++)
    {
    int x = rand()%(MAX_VALUE+1);
    this->insertAtHead(x);
    }
  }


CSet::~CSet(void)
  {
  //cout << "Destructor working\n";
  CNode *p, *q;

  p = this->m_first;
  if (NULL == p) return;

  do
    {
    q = p->addressOfNext();
    //cout << "about to eliminate " << *p << " at " << p << endl;
    delete p;
    p = q;
    }
    while (p != NULL);

  this->m_first = NULL;
  this->m_n = 0;
  }

  
CSet::CSet(char ch)
  {
  if (('r' == ch) || ('R' == ch))
    {
    int n = rand()%(MAX_COUNT+1);
    
    this->m_n = 0;
    this->m_first = NULL;

    for (int i=1; i<=n; i++)
      {
      int x = rand()%(MAX_VALUE+1);
      this->insertAtHead(x);
      }
    }

  }


////////////////////////////////////////////////////////////
// void CSet::insertAtHead(int x)
////////////////////////////////////////////////////////////
void CSet::insertAtHead(int x)
  {
  CNode *p;
  
  p = new CNode;

  p->m_info = x;
  p->m_next = this->m_first;
  this->m_first = p;
  this->m_n++;
  }


////////////////////////////////////////////////////////////
// ostream & operator << (ostream & tom, const CSet &set)
////////////////////////////////////////////////////////////
ostream & operator << (ostream & tom, const CSet &set)
  {
  cout << "CSet[" << set.m_n << "]=";

  CNode *p;

  p = set.m_first;
  while (p != NULL)
    {
    cout << *p << ' ';
    p = p->addressOfNext();
    }

  return tom;
  }


////////////////////////////////////////////////////////////
// void CSet::display(void) const
////////////////////////////////////////////////////////////
void CSet::display(void) const
  {
  cout << "CSet[" << this->m_n << "]=";

  CNode *p;

  p = this->m_first;
  while (p != NULL)
    {
    cout << *p << ' ';
    p = p->addressOfNext();
    }
  }


////////////////////////////////////////////////////////////
// CSet::CSet(void)
////////////////////////////////////////////////////////////
CSet::CSet(void)
  {
  this->m_first = NULL;
  this->m_n = 0;
  }


////////////////////////////////////////////////////////////
// CNode * CNode::addressOfNext(void)
////////////////////////////////////////////////////////////
CNode * CNode::addressOfNext(void)
  {
  return this->m_next;
  };


////////////////////////////////////////////////////////////
// bool CNode::operator != (CNode node)
////////////////////////////////////////////////////////////
bool CNode::operator != (CNode node)
  {
  return (this->m_info != node.m_info);
  }


////////////////////////////////////////////////////////////
// bool CNode::operator <= (CNode node)
////////////////////////////////////////////////////////////
bool CNode::operator <= (CNode node)
  {
  return (this->m_info <= node.m_info);
  }


////////////////////////////////////////////////////////////
// bool CNode::operator < (CNode node)
////////////////////////////////////////////////////////////
bool CNode::operator < (CNode node)
  {
  return (this->m_info < node.m_info);
  }


////////////////////////////////////////////////////////////
// bool CNode::operator == (CNode node)
////////////////////////////////////////////////////////////
bool CNode::operator == (CNode node)
  {
  return (this->m_info == node.m_info);
  }


////////////////////////////////////////////////////////////
// ostream & operator << (ostream & tom, CNode node)
////////////////////////////////////////////////////////////
ostream & operator << (ostream & tom, CNode node)
  {
  tom << node.m_info;

  return tom;
  }


////////////////////////////////////////////////////////////
// void CNode::set(int x)
////////////////////////////////////////////////////////////
void CNode::set(int x)
  {
  this->m_info = x;
  }


////////////////////////////////////////////////////////////
// int CNode::get(void)
////////////////////////////////////////////////////////////
int CNode::get(void)
  {
  return this->m_info;
  }


////////////////////////////////////////////////////////////
// CNode::CNode(char ch)
////////////////////////////////////////////////////////////
CNode::CNode(char ch)
  {
  if ('r' == ch)
      this->m_info = rand()%(MAX_VALUE+1);
    else
      this->m_info = UNDEFINED;
  }


////////////////////////////////////////////////////////////
// CNode::CNode(void)
////////////////////////////////////////////////////////////
CNode::CNode(void)
  {
  this->m_info = UNDEFINED;
  this->m_next = NULL;
  }


////////////////////////////////////////////////////////////
// void CNode::display(void) const
////////////////////////////////////////////////////////////
void CNode::display(void) const
  {
  cout << this->m_info;
  }


////////////////////////////////////////////////////////////
// CNode::CNode(int x)
////////////////////////////////////////////////////////////
CNode::CNode(int x)
  {
  this->m_info = x;
  this->m_next = 0;
  }


/*
SAMPLE RUN:
CSet[1]=41
CSet[1]=41
CSet[2]=34 67
CSet[2]=34 67
CSet[3]=24 69 0
CSet[3]=0 24 69
CSet[4]=64 62 58 78
CSet[4]=58 62 64 78
CSet[5]=61 27 81 45 5
CSet[5]=5 27 45 61 81
CSet[6]=91 36 27 42 95 91
CSet[6]=27 36 42 91 91 95
CSet[7]=16 21 82 92 53 2 4
CSet[7]=2 4 16 21 53 82 92
CSet[8]=12 69 38 71 26 47 95 18
CSet[8]=12 18 26 38 47 69 71 95
CSet[9]=73 33 22 11 3 94 35 99 67
CSet[9]=3 11 22 33 35 67 73 94 99
CSet[10]=37 57 62 44 47 68 53 11 41 64
CSet[10]=11 37 41 44 47 53 57 62 64 68
Press any key to continue
*/