//DSortedList03.cpp
//date: 11/06/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 = 50;
const int TEST_COUNT = 20;
const int INFINITY = 32000;
void testInsert(void);
void testConstructorN(void);
void testConstructorChar(void);
const int sValues[] = {55, 12, 34, 71, 98, 45, 20};
const int S_SIZE = sizeof(sValues)/sizeof(sValues[0]);
////////////////////////////////////////////////////////////
//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); //2002.11.06
CDSortedList(char ch);
};
////////////////////////////////////////////////////////////
//void main(void)
////////////////////////////////////////////////////////////
void main(void)
{
srand(time(NULL));
// testInsert();
//testConstructorN();
testConstructorChar();
}
/*
{
CNode n1;
n1.display();
cout << endl;
}
{
CNode n1('r');
n1.display();
cout << endl;
}
{
CNode n1(3);
n1.display();
cout << endl;
}
*/
CDSortedList::CDSortedList(char ch)
{
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;
if (('r' == ch) || ('R' == ch))
{
//insert random number of random values to the list
int n = rand()%(MAX_SIZE+1);
for (int i=0; i<n; i++)
this->insert(rand()%(MAX_VALUE+1));
}
if (('c' == ch) || ('C' == ch))
{
//insert random number of random values to the list
for (int i=0; i<S_SIZE; i++)
this->insert(sValues[i]);
}
}
void testConstructorChar(void)
{
cout << "testConstructorChar\n";
cout << "===================\n";
CDSortedList myList('c');
myList.display();
cout << "-----------------\n";
for (int i=0; i<TEST_COUNT; i++)
{
CDSortedList myList('r');
myList.display();
cout << "-----------------\n";
}
}
CDSortedList::CDSortedList(int n)
{
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;
//insert n random values to the list
for (int i=0; i<n; i++)
this->insert(rand()%(MAX_VALUE+1));
}
void testConstructorN(void)
{
cout << "testConstructorN\n";
cout << "================\n";
for (int i=0; i<TEST_COUNT; i++)
{
CDSortedList myList(rand()%MAX_SIZE);
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 testInsert(void)
{
cout << "testInsert\n";
cout << "==========\n";
CDSortedList myList;
myList.display();
for (int i=0; i<10; i++)
{
int x = rand()%MAX_VALUE;
myList.insert(x);
cout << "After inserting " << x << endl;
myList.display();
}
}
////////////////////////////////////////////////////////////
//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:
testConstructorChar
===================
List[7] =
[0x00321100 -32000 0x003211A8]
[0x003211A8 12 0x003212C0]
[0x003212C0 20 0x003211E0]
[0x003211E0 34 0x00321288]
[0x00321288 45 0x00321170]
[0x00321170 55 0x00321218]
[0x00321218 71 0x00321250]
[0x00321250 98 0x00321138]
[0x00321138 32000 0x00000000]
-----------------
List[9] =
[0x00322A50 -32000 0x00322C48]
[0x00322C48 2 0x00322B68]
[0x00322B68 26 0x00322AF8]
[0x00322AF8 26 0x00322AC0]
[0x00322AC0 33 0x00322BA0]
[0x00322BA0 35 0x00322C80]
[0x00322C80 37 0x00322BD8]
[0x00322BD8 37 0x00322C10]
[0x00322C10 43 0x00322B30]
[0x00322B30 49 0x00322A88]
[0x00322A88 32000 0x00000000]
-----------------
List[2] =
[0x00322CB8 -32000 0x00322D28]
[0x00322D28 34 0x00322D60]
[0x00322D60 37 0x00322CF0]
[0x00322CF0 32000 0x00000000]
-----------------
List[0] =
[0x00322D98 -32000 0x00322DD0]
[0x00322DD0 32000 0x00000000]
-----------------
List[10] =
[0x00322E08 -32000 0x00323000]
[0x00323000 2 0x00322F58]
[0x00322F58 7 0x00322EE8]
[0x00322EE8 24 0x00322F90]
[0x00322F90 32 0x00322F20]
[0x00322F20 33 0x00323038]
[0x00323038 35 0x00322E78]
[0x00322E78 40 0x00323070]
[0x00323070 41 0x00322EB0]
[0x00322EB0 42 0x00322FC8]
[0x00322FC8 45 0x00322E40]
[0x00322E40 32000 0x00000000]
-----------------
List[4] =
[0x003230A8 -32000 0x003231C0]
[0x003231C0 21 0x00323188]
[0x00323188 25 0x00323118]
[0x00323118 39 0x00323150]
[0x00323150 40 0x003230E0]
[0x003230E0 32000 0x00000000]
-----------------
List[3] =
[0x003231F8 -32000 0x003232D8]
[0x003232D8 14 0x003232A0]
[0x003232A0 16 0x00323268]
[0x00323268 16 0x00323230]
[0x00323230 32000 0x00000000]
-----------------
List[1] =
[0x00323310 -32000 0x00323380]
[0x00323380 11 0x00323348]
[0x00323348 32000 0x00000000]
-----------------
List[5] =
[0x003233B8 -32000 0x00323498]
[0x00323498 11 0x00323460]
[0x00323460 21 0x00323508]
[0x00323508 35 0x00323428]
[0x00323428 38 0x003234D0]
[0x003234D0 50 0x003233F0]
[0x003233F0 32000 0x00000000]
-----------------
List[3] =
[0x00323540 -32000 0x003235B0]
[0x003235B0 3 0x00323620]
[0x00323620 10 0x003235E8]
[0x003235E8 35 0x00323578]
[0x00323578 32000 0x00000000]
-----------------
List[4] =
[0x00323658 -32000 0x003236C8]
[0x003236C8 16 0x00323738]
[0x00323738 19 0x00323770]
[0x00323770 21 0x00323700]
[0x00323700 46 0x00323690]
[0x00323690 32000 0x00000000]
-----------------
List[1] =
[0x003237A8 -32000 0x00323818]
[0x00323818 9 0x003237E0]
[0x003237E0 32000 0x00000000]
-----------------
List[2] =
[0x00323850 -32000 0x003238F8]
[0x003238F8 2 0x003238C0]
[0x003238C0 44 0x00323888]
[0x00323888 32000 0x00000000]
-----------------
List[0] =
[0x00323930 -32000 0x00323968]
[0x00323968 32000 0x00000000]
-----------------
List[9] =
[0x003239A0 -32000 0x00323B60]
[0x00323B60 7 0x00323AB8]
[0x00323AB8 7 0x00323A80]
[0x00323A80 9 0x00323A48]
[0x00323A48 10 0x00323B98]
[0x00323B98 15 0x00323B28]
[0x00323B28 28 0x00323AF0]
[0x00323AF0 39 0x00323BD0]
[0x00323BD0 43 0x00323A10]
[0x00323A10 47 0x003239D8]
[0x003239D8 32000 0x00000000]
-----------------
List[8] =
[0x00323C08 -32000 0x00323D90]
[0x00323D90 5 0x00323C78]
[0x00323C78 9 0x00323DC8]
[0x00323DC8 24 0x00323D58]
[0x00323D58 25 0x00323CE8]
[0x00323CE8 28 0x00323D20]
[0x00323D20 34 0x00323E00]
[0x00323E00 37 0x00323CB0]
[0x00323CB0 41 0x00323C40]
[0x00323C40 32000 0x00000000]
-----------------
List[7] =
[0x00323E38 -32000 0x00323F18]
[0x00323F18 28 0x00323FC0]
[0x00323FC0 33 0x00323EA8]
[0x00323EA8 34 0x00323F50]
[0x00323F50 35 0x00323EE0]
[0x00323EE0 41 0x00323F88]
[0x00323F88 42 0x00323FF8]
[0x00323FF8 49 0x00323E70]
[0x00323E70 32000 0x00000000]
-----------------
List[6] =
[0x00324030 -32000 0x003240A0]
[0x003240A0 0 0x003240D8]
[0x003240D8 6 0x00324180]
[0x00324180 11 0x00324148]
[0x00324148 35 0x00324110]
[0x00324110 40 0x003241B8]
[0x003241B8 47 0x00324068]
[0x00324068 32000 0x00000000]
-----------------
List[5] =
[0x003241F0 -32000 0x00324340]
[0x00324340 0 0x00324298]
[0x00324298 2 0x00324308]
[0x00324308 12 0x00324260]
[0x00324260 22 0x003242D0]
[0x003242D0 45 0x00324228]
[0x00324228 32000 0x00000000]
-----------------
List[7] =
[0x00324378 -32000 0x00324490]
[0x00324490 0 0x00324538]
[0x00324538 4 0x00324420]
[0x00324420 4 0x00324458]
[0x00324458 9 0x00324500]
[0x00324500 10 0x003243E8]
[0x003243E8 13 0x003244C8]
[0x003244C8 25 0x003243B0]
[0x003243B0 32000 0x00000000]
-----------------
List[0] =
[0x00324570 -32000 0x003245A8]
[0x003245A8 32000 0x00000000]
-----------------
Press any key to continue
*/
|