p003
[ Home ] [ Up ]

//file: p003.cpp
//Author: AOU
//Date 08/27/2004

#include <iostream.h>

int const MAX_SIZE = 20+2;
int const INFINITY = 9999; 

//Problem:  
//  List of values (duplicates allowed) kept in order 
//  with several operations:
//  initialize, insert, delete, modify, search, ...
//Example: 
//  {}, {50}, {25,50}, {25,36,50}, {25,36,50,76},
//  {25,36,50,76}
//Algorithms:


////////////////////////////////////////////////////////
//void initialize(int a[], int &n)
////////////////////////////////////////////////////////
/*
Description:
Initializes the list of values by setting n=0, and
a[0..MAX_SIZE-1] = 0;
Algorithm:
  n = 2
  a[0] = -INFINITY
  for i=1 to MAX_SIZE-2
    a[i] = 0;

  a[MAX_SIZE-1] = +INFINITY


*/
void initialize(int a[], int &n)
  {
  n = 2;
  a[0] = -INFINITY;
  a[1] = +INFINITY;
  for (int i=2; i<=MAX_SIZE-1; i++)
    a[i] = 0;

  }


////////////////////////////////////////////////////////
//bool insert(int a[], int &n, int x)
////////////////////////////////////////////////////////
/*
Description: inserts x into the list and maintains the order
Example: 
  {}, {50}, {25,50}, {25,36,50}, {25,36,50,76},
  {25,36,50,76}
Algorithm:
  Case0: list is full

  Case1: x goes to empty list

  x Case3: x > all the values in the list
  x Case2: x < all the values in the list
  Case4: x goes between two values and handle duplicates

  m = n
  s1: if (x >= a[m-1]) then
      a[m] = x
      n++
      exit function
    else
      a[m] = a[m-1]
      m--
      goto s1


  m = n
  while x < a[m-1])
    a[m] = a[m-1]
    m--
    wend

  a[m] = x
  n++

*/
bool insert(int a[], int &n, int x)
  {
  if (n >= MAX_SIZE)
    return false;

  int m = n;

  while (x < a[m-1])
    {
    a[m] = a[m-1];
    m--;
    }

  a[m] = x;
  n++;
  return true;
  }


////////////////////////////////////////////////////////
//void display(int a[], int n)
////////////////////////////////////////////////////////
/*
Description:
Algorithm:
*/
void display(int a[], int n)
  {
  for (int i=0; i<=MAX_SIZE-1; i++)
    cout << a[i] << ' ';

  cout << endl;
  }

void main(void)
  {
  int myArray[MAX_SIZE];
  int m;

  initialize(myArray, m);
  display(myArray, m);

  insert(myArray, m, 56);
  display(myArray, m);

  insert(myArray, m, 25);
  display(myArray, m);

  insert(myArray, m, 2);
  display(myArray, m);

  insert(myArray, m, 58);
  display(myArray, m);

  }