pex11_7.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "node.h"
#include "nodelib.h"
#include "treenode.h"
#include "bstree.h"
#include "array.h"
#include "random.h"
#include "ticks.h"

// sort A using the linked list sort
void LinkedSort(Array<int>& A)
{
	Node<int> *ordlist = NULL, *currPtr;

	// insert each element of A into an ordered linked list
	for(int i=0;i < A.ListSize();i++)
		// maintain linked list using Node class utility
		// function InsertOrder
		InsertOrder(ordlist,A[i]);
		
	// traverse the linked list and copy each element back
	// into the array
	i = 0;
	currPtr = ordlist;
	while(currPtr != NULL)
	{
		A[i++] = currPtr->data;
		currPtr = currPtr->NextNode();
	}

	// delete the memory occupied by the linked list
	ClearList(ordlist);
}

// traverse tree t inorder and assign the data values into
// array A. sequence through A using index i
void InorderAssign(TreeNode<int> *t, Array<int>& A, int& i)
{
	// if t is NULL, return
	if (t != NULL)
	{
		// fill A with values from left subtree of t
		InorderAssign(t->Left(),A,i);
		// assign A[i] the value at the current node. advance
		// i for the next assignment to A
		A[i++] = t->data;
		// fill A with values from right subtree of t
		InorderAssign(t->Right(),A,i);
	}
}

// sort A using the tree sort
void TreeSort(Array<int>& A)
{
	BinSTree<int> tree;
	
	// insert each element of A into a binary search tree
	for(int i=0;i < A.ListSize();i++)
		tree.Insert(A[i]);

	// use InorderAssign to traverse the tree inorder
	// and assign the elements into A
	i = 0;
	InorderAssign(tree.GetRoot(), A, i);
}

// prints the first 5 and last 5 items in the array a.
// assume that n >= 5
void PrintFirst_Last(int a[], int n)
{
    int i;
    
    for(i=0;i < 5;i++)
        cout << a[i] << "  ";
    cout << ". . .  ";
    for(i= n-5; i < n; i++)
        cout << a[i] << "  ";
    cout << endl;
}

void main(void)
{
	// use rnd to generate 10000 random numbers
    RandomNumber rnd;
    // A and B hold 10000 identical random numbers
    Array<int> A(10000), B(10000);
    long ticks;
    
	// print timings with exactly one decimal place
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(1);
	
    // initialize the two arrays to have the same sequence of random
    // integers
    for(int i=0;i < 10000;i++)
		// generate random integers in range 0..32767
		A[i] = B[i] = rnd.Random(32768L);
    
	// time the linked sort with array A. print the first
	// and last 5 values of the sorted array
	ticks = TickCount();
	LinkedSort(A);
	ticks = TickCount() - ticks;
	cout << "Linked Sort: " << ticks/60.0 << " seconds" << endl;
	PrintFirst_Last(A,10000);

	// time the tree sort with array B, which is identical to A.
	// print the first and last 5 values of the sorted array
    ticks = TickCount();
	TreeSort(B);
	ticks = TickCount() - ticks;
	cout << "Tree Sort: " << ticks/60.0 << " seconds" << endl;
	PrintFirst_Last(B,10000);
}

/*
<Run>

Linked Sort: 78.8 seconds
12  19  21  23  29  . . .  32756  32763  32763  32766  32766
Tree Sort: 1.0 seconds
12  19  21  23  29  . . .  32756  32763  32763  32766  32766
*/