head.all

来自「经典c++程序的实现」· ALL 代码 · 共 354 行

// book.h

#define DOS 0
#define VC  0
#ifdef UNIX       // Timing includes 
#include <time.h>
#include <sys/types.h>
#include <sys/times.h>
#include <sys/time.h>
#endif

#ifdef DOS        // Timing includes

#include <time.h>
    #ifdef VC
    #include <stdlib.h> 
    #endif
    #ifdef BORLAND
    #include <bios.h>
    #endif
#endif

#define FALSE 0
#define TRUE 1
#define LIST_SIZE 10  // size for lists if no size is given.

#ifdef DOS
/* typedef int bool; */
#endif

// Random number generating functions -- make consistent in both
// environments

#ifdef UNIX
    #ifdef DEC
    extern "C" { // DEC's stdlib is fouled, and does not have these prototypes
    void srandom(int);
    int random(void);
    };
    #endif
#define Randomize() srandom(1)
#define Random(n) (random() % (n)) // Return an integer in the range 0 to n-1
#endif

#ifdef DOS
    #ifdef BORLAND
    #define Randomize() randomize()
    #define Random(n) random(n)
    #endif
    #ifdef VC
    #define Randomize() ;
    #define Random(n) rand()%n
    #endif
#endif

#ifdef UNIX         // Timing defines
#define inittime()   time_t time1, time2;  struct tms t1, t2
#define starttime()  times(&t1);   time1 = time((time_t *)0)
#define stoptime()   times(&t2);   time2 = time((time_t *)0)
#define printtime()  cout << "Utime: "\          << (double)(t2.tms_utime - t1.tms_utime)/60.0\
          << ", Stime: "\
          << (double)(t2.tms_utime - t1.tms_utime)/60.0\
          << ", wall time: " << time2 - time1 << "\n"
#endif

#ifdef DOS         // Timing defines
    #ifdef BORLAND
    #define inittime()   long tinit; long tfin
    #define starttime()  tinit = biostime(0, 0L)  // get start time
    #define stoptime()   tfin = biostime(0, 0L)   // get stop time
    #define printtime()  cout << "Time is: " << (tfin - tinit) << " clock ticks\n"
    #endif	
    #ifdef VC
	/*
    #define inittime()   long tinit; long tfin
    #define starttime()  _bios_timeofday(_TIME_GETCLOCK, &tinit)  // get start time
    #define stoptime()   _bios_timeofday(_TIME_GETCLOCK, &tfin)   // get stop time
	#define inittime()   time_t time1, time2;  struct tms t1, t2
	*/
    #define inittime()   time_t time1, time2;
    #define starttime()  time1 = time((time_t *)0)
    #define stoptime()   time2 = time((time_t *)0)
    #define printtime()  cout << "Time is: " << (time2 - time1) << " second\n"
    #endif
	/*
    #ifdef VC
    #define inittime()   long tinit; long tfin
    #define starttime()  _bios_timeofday(_TIME_GETCLOCK, &tinit)  // get start time
    #define stoptime()   _bios_timeofday(_TIME_GETCLOCK, &tfin)   // get stop time
    #endif
	*/
#endif

#ifndef KEYDEF
#define key(X) (X)
#endif

#define even(X) (!((X)%2))

#define INFINITY 30000

#define ROOT -1           // used for UNION/FIND

#define VISITED 1
#define UNVISITED 0
#define NOEDGE -1



// alist.h

class list {              // Array-based list class
private:
  int msize;                  // Maximum size of list
  int numinlist;              // Actual number of ELEMs in list
  int curr;                   // Position of "current" ELEM
  ELEM* listarray;            // Array holding list ELEMs
public:
  list(const int =LIST_SIZE); // Constructor
  ~list();                    // Destructor
  void clear();               // Remove all ELEMs from list
  void insert(const ELEM&);   // Insert ELEM at current position
  void append(const ELEM&);   // Insert ELEM at tail of list
  ELEM remove();              // Remove and return current ELEM
  void setFirst();            // Set curr to first position
  void prev();                // Move curr to previous position
  void next();                // Move curr to next position
  int  length() const;        // Return current length of list
  void setPos(const int);     // Set curr to specified position
  void setValue(const ELEM&); // Set current ELEM's value
  ELEM currValue() const;     // Return current ELEM's value
  bool isEmpty() const;       // Return TRUE if list is empty
  bool isInList() const;      // TRUE if curr is within list
  bool find(const ELEM&);     // Find value (from current position)
};


// link.h
class 
link
 {                       // A singly-linked list node
public:
  ELEM element;                    // ELEM value for this node
  link *next;                      // Pointer to next node in list
  link(const ELEM& elemval, link* nextval =NULL) // Constructor 1
    { element = elemval;  next = nextval; }      // Given ELEM value
  link(link* nextval =NULL) { next = nextval; }  // Constructor 2
  ~link() { }                                    // Destructor
};

// llist.h

class list {                  // Linked list class
private:
  link* head;                 // Pointer to list header
  link* tail;                 // Pointer to last ELEM in list
  link* curr;                 // Position of "current" ELEM
public:
  list(const int =LIST_SIZE); // Constructor
  ~list();                    // Destructor
  void clear();               // Remove all ELEMs from list
  void insert(const ELEM&);   // Insert ELEM at current position
  void append(const ELEM&);   // Insert ELEM at tail of list
  ELEM remove();              // Remove and return current ELEM
  void setFirst();            // Set curr to first position
  void next();                // Move curr to next position
  void prev();                // Move curr to previous position
  int  length() const;        // Return current length of list
  void setPos(const int);     // Set curr to specified position
  void setValue(const ELEM&); // Set current ELEM's value
  ELEM currValue() const;     // Return current ELEM's value
  bool isEmpty() const;       // Return TRUE if list is empty
  bool isInList() const;      // TRUE if curr is within list
  bool find(const ELEM&);     // Find value (from current position)
};


// astack.h

class Stack {                    // Array-based stack class
private:
  int size;                      // Maximum size of stack
  int top;                       // Index for top ELEM
  ELEM *listarray;               // Array holding stack ELEM's

public:
  Stack(const int sz =LIST_SIZE) // Constructor: initialize
    { size = sz;  top = 0; listarray = new ELEM[sz]; }
  ~Stack()                       // Destructor: return array space
    { delete [] listarray; }
  void clear()                   // Remove all ELEM's from stack
    { top = 0; }
  void push(const ELEM& item)    // Push ELEM onto stack
    { assert(top < size);  listarray[top++] = item; }
  ELEM pop()                     // Pop ELEM from top of stack
    { assert(!isEmpty());  return listarray[--top]; }
  ELEM topValue() const          // Return value of top ELEM
    { assert(!isEmpty()); return listarray[top-1]; }
  bool isEmpty() const           // Return TRUE if stack is empty
    { return top == 0; }
};



// lstack.h

class Stack {                 // Linked stack class
private:
  link *top;                  // Pointer to top stack ELEM
public:
  Stack(const int sz =LIST_SIZE) // Constructor: initialize
    { top = NULL; }
  ~Stack() { clear(); }       // Destructor: return ELEMs
  void clear();               // Remove all ELEM's from stack
  void push(const ELEM& item) // Push ELEM onto stack
    { top = new link(item, top); }
  ELEM pop();                 // Pop ELEM from top of stack
  ELEM topValue() const       // Get value of top ELEM
    { assert(!isEmpty());  return top->element; }
  bool isEmpty() const        // Return TRUE if stack is empty
    { return top == NULL; }
};

void Stack::clear() {         // Remove all ELEM's from the stack
  while(top != NULL)          // Return link nodes to the freelist
    { link*temp = top;  top = top->next;  delete temp; }
}

ELEM Stack::pop() {           // Pop ELEM from top of stack
  assert(!isEmpty());
  ELEM temp = top->element;
  link* ltemp = top->next;
  delete top; top = ltemp;
   return temp;
 }



// aqueue.h

class Queue {                  // Array based queue class
private:
  int size;                    // Maximum size of queue
  int front;                   // Index prior to front item
  int rear;                    // Index of rear item
  ELEM *listarray;             // Array holding the list ELEM's
public:
  Queue(const int sz =LIST_SIZE)    // Constructor
    { // Make list array one position larger for empty slot
      size = sz+1;  front = rear = 0;  listarray = new ELEM[size]; }
  ~Queue() { delete [] listarray; } // Destructor
  void clear() { front = rear; }    // Clear queue
  void enqueue(const ELEM&);        // Enqueue ELEM at rear
  ELEM dequeue();                   // Dequeue ELEM from front
  ELEM firstValue() const           // Get value of front ELEM
    { assert(!isEmpty());  return listarray[(front+1) % size]; }
  bool isEmpty() const              // TRUE if queue is empty
    { return front == rear; }
};

// Enqueue ELEM at rear of queue
void Queue::enqueue(const ELEM& item) {
  assert(((rear+1) % size) != front); // Queue must not be full
  rear = (rear+1) % size;             // Increment rear (in circle)
  listarray[rear] = item;
}

ELEM Queue::dequeue() {     // Dequeue ELEM from front of queue
  assert(!isEmpty());       // There must be something to dequeue
  front = (front+1) % size; // Increment front
  return listarray[front];  // Return value
}


// lqueue.h
class Queue {      // Linked queue class
private:
  link *front;     // Pointer to front queue node
  link *rear;      // Pointer to rear queue node

public:
  Queue(const int sz =LIST_SIZE) // Constructor: initialize
    { front = rear = NULL; }
  ~Queue() { clear(); }          // Destructor: return link ELEMs
  void clear();                  // Remove all ELEM's from queue
  void enqueue(const ELEM&);     // Enqueue ELEM at rear
  ELEM dequeue();                // Dequeue ELEM from front
  ELEM firstValue() const        // Get value of front ELEM
    { assert(!isEmpty());  return front->element; }
  bool isEmpty() const           // Return TRUE if queue is empty
    { return front == NULL; }
};

void Queue::clear() {            // Remove all ELEM's from the queue
  while(front != NULL)           // Return link nodes to freelist
    { rear = front;  front = front->next;  delete rear; }
  rear = NULL;
}

// Enqueue ELEM at rear of queue
void Queue::enqueue(const ELEM& item) {
  if (rear != NULL) {   // Queue not empty: add to end
       rear->next = new link(item, NULL);
       rear = rear->next;
     }
     else front = rear = new link(item, NULL); // Empty queue
   }
   
   ELEM Queue::dequeue() {           // Dequeue ELEM from front
     assert(!isEmpty());             // Must be something to dequeue
     ELEM temp = front->element;     // Store dequeued value
     link* ltemp = front;            // Hold onto dequeued link node
     front = front->next;            // Advance front
     delete ltemp;                   // Return link to free store
     if (front == NULL) rear = NULL; // Dequeued last element
     return temp;                    // Return element value
   }

// dlinkf.h

class link {                       // A doubly-linked list node
public:                            //   with freelist
  ELEM element;                    // ELEM value for this node
  link* next;                      // Pointer to next node in list
  link* prev;                      // Pointer to previous node
  static link* freelist;           // Link class freelist
  link(const ELEM& elemval, link* nextp =NULL, link* prevp =NULL)
    { element = elemval;  next = nextp;  prev = prevp;}
  link(link* nextp =NULL, link* prevp = NULL)
    { next = nextp;  prev = prevp; }
  ~link() { }                      // Destructor: take no action
  void* operator new(size_t);      // Overloaded new operator
  void operator delete(void*);     // Overloaded delete operator
};

// lprint.c


// Print out the elements of list "in"
void print(list& in) {
  if (in.isEmpty()) cout << "()\n";
  else {
    in.setFirst();
    cout << "( " << in.currValue();
    in.next();
    while (in.isInList()) {
      cout << ", " << in.currValue();
      in.next();
    }
    cout << " )\n";
  }
}