pex14_1.cpp

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

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

#include "dnode.h"
#include "random.h"

// insert item into ordered doubly linked list dheader
// to the left of currPtr. until the header is reached,
// each data value going left is <= its predecessor
template <class T>
void InsertLower(DNode<T> *dheader, DNode<T>* &currPtr, T item)
{
    DNode<T> *newNode= new DNode<T>(item), *p;
    
    // look for the insertion point
    p = currPtr;
    while (p != dheader && item < p->data)
        p = p->NextNodeLeft();

    // insert the item
    p->InsertRight(newNode);

    // reset currPtr to the new node
    currPtr = newNode;
}

// insert item into ordered doubly linked list dheader
// to the right of currPtr. until the header is reached,
// each data value going right is >= its predecessor
template <class T>
void InsertHigher(DNode<T>* dheader, DNode<T>* & currPtr, T item)
{
    DNode<T> *newNode= new DNode<T>(item), *p;
    
    // look for the insertion point
    p = currPtr;
    while (p != dheader && p->data < item)
        p = p->NextNodeRight();

    // insert the item
    p->InsertLeft(newNode);

    // reset currPtr to the new node
    currPtr = newNode;
}

// sort array A of n items using the doubly linked
// list sort
template <class T>
void DoubleSort(T a[], int n)
{
    // set up the doubly linked list to hold array items
    DNode<T> dheader, *currPtr;
    int i;
    
	// if no list, return
	if ( n <= 0)
		return;

    // insert the first element in dlist 
    DNode<T>  *newNode = new DNode<T>(a[0]);
    dheader.InsertRight(newNode);
    currPtr = newNode;

    // insert the remaining elements in dlist 
    for (i=1;i < n;i++)
        if (a[i] < currPtr->data)
            InsertLower(&dheader,currPtr,a[i]);
        else
            InsertHigher(&dheader,currPtr,a[i]);

    // scan the list and copy the data values back to the array
    currPtr = dheader.NextNodeRight();
    i = 0;
    while(currPtr != &dheader)
    {
        a[i++] = currPtr->data;
        currPtr = currPtr->NextNodeRight();
    }
    
    // delete all nodes in the list
    while(dheader.NextNodeRight() != &dheader)
    {
        currPtr = (dheader.NextNodeRight())->DeleteNode();
        delete currPtr;
    }
}

// scan the array and print its elements
void PrintArray(int a[], int n)
{
    for(int i=0;i < n;i++)
    {
        cout << setw(6) << a[i];
    	if ((i+1) % 10 == 0)
    		cout << endl;
    }
	cout << endl;
}

void main(void)
{
    // initialize dynamic array A with n integer values
	int n;
    int *A;
    RandomNumber rnd;
    
	// read n, create and initialize an array
	// of n random numbers in the range 0..1000
	cout << "Enter n: ";
	cin >> n;
	cout << endl;
	A = new int [n];
	if (!A)
	{
		cerr << "Memory allocation failure!" << endl;
		exit(1);
	}
	for(int i=0;i < n;i++)
		A[i] = rnd.Random(1001);
	cout << "Initial array:" << endl;
	// print the initial array
    PrintArray(A,n);   

	// sort A and print the array
    DoubleSort(A,n);
    cout << "Sorted array:" << endl;
    PrintArray(A,n);   
}

/*
<Run>

Enter n: 53

Initial array:
   449   474   542   715   269   521   552   102    64    72
   629   186   886   388   519   312   922   466   590   442
   472   215   922    58   116   875   400   540   942   483
   442   911    63   474   146   569    81   422   288   724
    85   565   705   555   372   863   616   626   846   136
     1   618   365
Sorted array:
     1    58    63    64    72    81    85   102   116   136
   146   186   215   269   288   312   365   372   388   400
   422   442   442   449   466   472   474   474   483   519
   521   540   542   552   555   565   569   590   616   618
   626   629   705   715   724   846   863   875   886   911
   922   922   942
*/