DSortedList02
[ Home ] [ Up ]

//DSortedList02.cpp
//date: 11/04/2002
//author: AOU


//Dynamic sorted list

////////////////////////////////////////////////////////////
// Include files
////////////////////////////////////////////////////////////
#include<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>


////////////////////////////////////////////////////////////
// Constants
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
const int MAX_SIZE    = 10; //maximum entries allowed in a list
const int UNDEFINED   = -9999;
const int MAX_VALUE   = 5;
const int TEST_COUNT  = 20;

const int INFINITY    = 32000;


////////////////////////////////////////////////////////////
//class CNode
////////////////////////////////////////////////////////////
class CNode
  {
  private:
    int m_key;
    // int age;
    // char name[20];
    // char socsec[10];
    CNode *m_next;
  public:
    CNode(void);        //2002.10.30
    void display(void); //2002.10.30
    CNode(int x);       //2002.11.04
    CNode(char ch);     //2002.11.04
    //...
  friend class CDSortedList;
  };


////////////////////////////////////////////////////////////
//class CDSortedList
////////////////////////////////////////////////////////////
class CDSortedList
  {
  private:
    int m_count;
    CNode *m_first;
  public:
    CDSortedList(void);   //2002.10.30
    void display(void);   //2002.10.30
    bool insert(int x);   //2002.11.04

    CDSortedList(int n);
    CDSortedList(char ch);
  };


////////////////////////////////////////////////////////////
//void main(void)
////////////////////////////////////////////////////////////
void main(void)
  {
    {
    CNode n1;
    n1.display();
    cout << endl;
    }

    {
    CNode n1('r');
    n1.display();
    cout << endl;
    }

    {
    CNode n1(3);
    n1.display();
    cout << endl;
    }

  CDSortedList myList;
  myList.display();

  myList.insert(55);
  myList.display();

  myList.insert(25);
  myList.display();

  myList.insert(65);
  myList.display();
  }


////////////////////////////////////////////////////////////
// bool CDSortedList::insert(int x)
////////////////////////////////////////////////////////////
bool CDSortedList::insert(int x)
  {
  if (this->m_count >= MAX_SIZE)
    return false;

  CNode *p, *p1, *p2;

  p = new CNode(x);
  if (NULL == p) 
    return false;

  p1 = this->m_first;
  p2 = p1->m_next;

  while(true)
    {
    if ((x >= p1->m_key) && (x <= p2->m_key))
      {
      p1->m_next = p;
      p->m_next = p2;
      this->m_count++;
      return true;
      }
    else
      {
      p1 = p1->m_next;
      p2 = p1->m_next;
      }
    }
  }


////////////////////////////////////////////////////////////
//void CDSortedList::display(void)
////////////////////////////////////////////////////////////
void CDSortedList::display(void)
  {
  cout << "List[" << this->m_count << "] = \n";
  CNode *p;

  p = this->m_first;

  while (p != NULL)
    {
    p->display();
    p = p->m_next;
    cout << endl;
    }

  cout << endl;
  }


////////////////////////////////////////////////////////////
//CDSortedList::CDSortedList(void)
////////////////////////////////////////////////////////////
CDSortedList::CDSortedList(void)
  {
  /*
  create two nodes 
    one pointed to by p1, 
    other pointed to by p2

  make first point to p1
  make p1 point to p2
  make p2 point to nothing

  put -infin in p1 node
  put +infin in p2 node

  set count = 0
  */
  CNode *p1 = new CNode;
  CNode *p2 = new CNode;

  this->m_first = p1;
  p1->m_next = p2;
  p2->m_next = NULL;

  p1->m_key = -INFINITY;
  p2->m_key = +INFINITY;

  this->m_count = 0;
  }


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


////////////////////////////////////////////////////////////
// CNode::CNode(int x)
////////////////////////////////////////////////////////////
CNode::CNode(int x)
  {
  this->m_key = x;
  this->m_next = NULL;
  }


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


////////////////////////////////////////////////////////////
//void CNode::display(void)
////////////////////////////////////////////////////////////
void CNode::display(void)
  {
  cout << "[" << this << " " 
    << this->m_key << " " 
    << this->m_next << "] ";
  }


/*
SAMPLE RUN:
[0x0012FF78 -9999 0x00000000]
[0x0012FF70 5 0x00000000]
[0x0012FF68 3 0x00000000]
List[0] =
[0x00321280 -32000 0x003212B8]
[0x003212B8 32000 0x00000000]

List[1] =
[0x00321280 -32000 0x00322868]
[0x00322868 55 0x003212B8]
[0x003212B8 32000 0x00000000]

List[2] =
[0x00321280 -32000 0x003228A0]
[0x003228A0 25 0x00322868]
[0x00322868 55 0x003212B8]
[0x003212B8 32000 0x00000000]

List[3] =
[0x00321280 -32000 0x003228A0]
[0x003228A0 25 0x00322868]
[0x00322868 55 0x003228D8]
[0x003228D8 65 0x003212B8]
[0x003212B8 32000 0x00000000]

Press any key to continue

*/