CODL02
[ Home ] [ Up ]

//file: CODL02.cpp
//Author: AOU
//Date 10/15/2004

// Ordered Dynamic Lisr
////////////////////////////////////////////////////////
// includes
////////////////////////////////////////////////////////
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>



////////////////////////////////////////////////////////
// constants
////////////////////////////////////////////////////////
int const MAX_SIZE = 20+2;
int const INFINITY = 9999; 
int const TEST_COUNT = 10;
int const MAX_VALUE = 10;
int const MAX_LENGTH = 20+1;

char *test_data[]=
  {
  "John", "James", "Bob", "Karen",
  "Zack", "Ann", "Camry", "Alero"
  };
int TEST_SIZE = sizeof(test_data)/sizeof(test_data[0]);

class CNode
  {
  private:
    char key[MAX_LENGTH];
    CNode *next;
  public:
    CNode(void)
      {
      strcpy(key, "");
      next = NULL;
      };

    CNode(char value[])
      {
      strcpy(key, value);
      next = NULL;
      };
    void display(void)
      {
      cout << key;
      }
  friend class CODL;
  };


class CODL
  {
  private:
    CNode *head;
    int n;
  public:
    CODL(void)
      {
      CNode *p, *q;
      p = new CNode("$");
      q = new CNode("z");
      head = p;
      p->next = q;
      q->next = NULL;
      n = 0;
      }

    void display(void)
      {
      cout << "List[" << n << "] = ";
      CNode *p = head;
      while (p != NULL)
        {
        p->display();
        cout << ' ';
        p = p->next;
        }
      
      cout << endl;
      }
    bool insert(char x[]);
  };

void test_insert(void);

void main(void)
  {
  for (int i=0; i<TEST_SIZE; i++)
    cout << test_data[i] << endl;

  test_insert();
  }

bool CODL::insert(char x[])
  {
  if (n >= MAX_SIZE)
    return false;

  CNode *p;
  p = new CNode(x);

  CNode *q;
  
  q = head;

  //while (q->next->key <= x)
  while (strcmp(q->next->key, x) <= 0)
    q = q->next;

  p->next = q->next;
  q->next = p;
  n++;
  return true;
  }


////////////////////////////////////////////////////////
// void test_insert(void)
////////////////////////////////////////////////////////
void test_insert(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_insert\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  CODL myList;
  myList.display();

  for (int i=1; i<=TEST_COUNT; i++)
    {
    int r = rand()%TEST_SIZE;
    myList.insert(test_data[r]);
    myList.display();
    }

  }