pex12_5.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#pragma hdrstop

#include "list.h"

enum ErrorType
  {invalidArraySize, memoryAllocationError, indexOutOfRange};

char *errorMsg[] =
{
    "Invalid array size", "Memory allocation error",
    "Invalid index: "
};

template <class T> 
class Array: public List<T>
{
    private:
        // a dynamically allocated list containing size items
        T*  alist;
        int size;

        // error handling method
        void Error(ErrorType error,int badIndex=0) const;

    public:
        // constructors and destructor
        Array(int sz = 50);                         
        Array(const Array<T>& A);   
        ~Array(void);

        // assignment, indexing and pointer conversion
        Array<T>& operator= (const Array<T>& rhs);
        T& operator[](int i);
        operator T* (void) const;

        // virtual functions we must override
        virtual int ListSize(void) const;   // return the array size
        virtual int ListEmpty(void) const;	// list never empty
        virtual int Find(T& elem);			// search for elem in array
        virtual void Insert(const T&);		// error! does not apply to array
        virtual void Delete(const T&);		// error! does not apply to array
        virtual void ClearList(void);		// error! does not apply to array
        
        void Resize(int sz);        		// modify the size
};

// prints the message corresponding to error
template <class T>
void Array<T>::Error(ErrorType error, int badIndex) const
{
    cerr << errorMsg[error];
    // for indexOutOfRange, print the bad index
    if (error == indexOutOfRange)
        cerr << badIndex;
    cerr << endl;
    exit(1);
}

// constructor
template <class T>
Array<T>::Array(int sz)
{
    // check for an invalid size parameter  
    if (sz <= 0) 
        Error(invalidArraySize);
    // assign the size and dynamically allocate memory
    size = sz;
    alist = new T[size];    
    // make sure that system allocates the desired memory, 
    if (alist == NULL)
        Error(memoryAllocationError);
}

// destructor
template <class T>
Array<T>::~Array(void)
{ 
    delete [] alist;
}

// copy constructor
template <class T>
Array<T>::Array(const Array<T>& X)
{
    // get size from object X and assign to current object 
    int n = X.size;

    size = n;

    // allocate new memory for object and do error checking
    alist = new T[n];           // allocate dynamic array
    if (alist == NULL)
        Error(memoryAllocationError);
    
    // copy array items from x to current object  
    T* srcptr = X.alist;    // address at start of X.alist
    T* destptr = alist;     // address at start of alist
    while (n--)             // copy list
        *destptr++ = *srcptr++;
}

// assignment operator. assign rhs to the current object
template <class T>
Array<T>& Array<T>::operator= (const Array<T>& rhs)
{
    // record the size of rhs
    int n = rhs.size;

    // if sizes not the same, delete memory and reallocate
    if (size != n)
    {
        delete [] alist;        // destroy original memory
        alist = new T[n];       // allocate a new array
        if (alist == NULL)
            Error(memoryAllocationError);
        size = n;
    }
 
    // copy array items from rhs to current object
   T* destptr = alist;
   T* srcptr = rhs.alist;
    while (n--) 
        *destptr++ = *srcptr++;

    // return reference to the current object
    return *this;
}

// overloaded index operator
template <class T>
T& Array<T>::operator[] (int n)
{
   // do array bounds checking
   if (n < 0 || n > size-1)
      Error(indexOutOfRange,n);
   // return the element from the private array list
   return alist[n];
}

// pointer conversion operator
template <class T>
Array<T>::operator T* (void) const
{
    // return address of private array in the current object
    return alist;
}

// return the number of elements in the array
template <class T>
int Array<T>::ListSize(void) const
{
    return size;
}

// the list is never empty. return False
template <class T>
int Array<T>::ListEmpty(void) const
{
    return 0;	// always return FALSE
}

// use the sequential search to look for elem within
// the size elements of the array. return 1 (True) if
// elem is located and False (0) otherwise
template <class T>
int  Array<T>::Find(T& elem)
{
	T *p = alist;
	
	for(int i=0;i < size;i++,p++)
		if (*p == elem)
		{
			elem = *p;
			return 1;
		}
	return 0;
}

// error. Insert is not defined for this class
template <class T>
void  Array<T>::Insert(const T&)
{
	cerr << "Error: Insert is not a valid Array operation" << endl;
}

// error. Delete is not defined for this class
template <class T>
void  Array<T>::Delete(const T&)
{
	cout << "Error: Delete is not a valid Array operation" << endl;
}

// error. ClearList is not defined for this class
template <class T>
void  Array<T>::ClearList(void)
{
	cout << "Error: ClearList is not a valid Array operation" << endl;
}

// resize operator
template <class T>
void Array<T>::Resize(int sz)
{
    // test new size parameter; terminate if size <= 0
    if (sz <= 0) 
        Error(invalidArraySize);
    // nothing to do if size hasn't changed
    if (sz == size)
        return;

    // request new memory and verify system response
    T* newlist = new T[sz];
    if (newlist == NULL)
        Error(memoryAllocationError);

    // declare n with value sz (truncating list)
    // or otherwise declare n to be the current size
    int n = (sz <= size) ? sz : size;

    // copy n array items from old to new memory
    T* srcptr = alist;      // address at start of alist
    T* destptr = newlist;   // address at start of newlist
    while (n--)             // copy list
        *destptr++ = *srcptr++;
    
    // delete old list
    delete[] alist;

    // reset alist to point at newlist and update the size
    alist = newlist;
    size = sz;
}

#define ARRAY_CLASS	// do not allow "arriter.h" to include "array.h"
#include "arriter.h"

// copy values in one array to another by using their iterators
void Copy(ArrayIterator<int>& Source, ArrayIterator<int>& Dest)
{
    while (!Source.EndOfList())
    {
        Dest.Data() = Source.Data();
        Source.Next();
        Dest.Next();
    }
}

// merge the sorted runs in array A. the first run spans indices
// lowIndex..endOfRun-1 and the second endOfRun..highIndex
void Merge(Array<int>& A,int lowIndex, int endOfRunIndex,
             int highIndex)
{
    // array in which the runs are combined. has same size as In
    Array<int> Out(A.ListSize());

    // left traverses 1st run, right traverses 2nd
    ArrayIterator<int> left(A,lowIndex,endOfRunIndex-1);
    ArrayIterator<int> right(A,endOfRunIndex,highIndex);
    
    // output puts sorted data to Out.
    ArrayIterator<int> output(Out);

    // copy until we hit the end of one or both runs
    while (!left.EndOfList() && !right.EndOfList())
    {
        // if left run data value smaller or equal, assign it to
        // Out. advance to next left run element
        if(left.Data() <= right.Data())
        {
            output.Data() = left.Data();
            left.Next();
        }
        // assign data from right run and advance right
        else
        {
            output.Data() = right.Data();
            right.Next();
        }
        output.Next();	// advance output
    }

    // if one of the runs is not complete, copy it to Out
    if (!left.EndOfList())
        Copy(left,output);
    else if (!right.EndOfList())
        Copy(right,output);

    // reset the iterator for Out and copy from Out to A
    output.Reset();
    
    ArrayIterator<int> final(A);    // use for copying back to A.
    
    Copy(output, final);
}

void main(void)
{
    // array to contain the sorted runs read from stream fin
    Array<int> A(20);
    ifstream fin;
    int i;
    int endOfRun = 0;
    
    // open data file "rundata"
    fin.open("rundata", ios::in | ios::nocreate);
    if (!fin)
    {
        cerr << "Cannot open the file 'rundata'" << endl;
        exit(1);
    }
    
    // read 20 data values in two sorted runs
    fin >> A[0];

    for(i=1;i < 20;i++)
    {
        fin >> A[i];
        if (A[i] < A[i-1])
            endOfRun = i;
    }
    
    // merge runs A[0]..A[endOfRun-1], A[endOfRun]..A[19]
    Merge(A,0,endOfRun,19);
    
    // print the sorted runs, 10 data values per line
    for(i=0;i < 20;i++)
    {
        cout << A[i] << "  ";
        if (i == 9)
            cout << endl;
    }
    cout << endl;
}

/*
<File "rundata">

1 3 6 9 12 23 33 45 55 68 88 95
2 8 12 25 33 48 55 75

<Run of Program 12.5>

1  2  3  6  8  9  12  12  23  25
33  33  45  48  55  55  68  75  88  95
*/