服务计算概论作业报告

2016-2017-1慕测平台测试报告

慕测平台测试报告（二）

学 院： 业： 计算机学院 软件工程 1301 姓 名： 赵红娜 学 号： 3130608003 完成日期： 2016-10-22 专 班 级：

1

2016年10月22日

2016-2017-1慕测平台测试报告

1.题目

针对以下4个项目编写测试用例进行测试。代码如下： 题目（1）

// BinaryHeap class //

// CONSTRUCTION: with optional capacity (that defaults to 100) //

// ******************PUBLIC

OPERATIONS********************* // void insert( x ) --> Insert x // int deleteMin( )--> Return and remove smallest item

// int findMin( ) --> Return smallest item // boolean isEmpty( ) --> Return true if empty; else false

// boolean isFull( ) --> Return true if full; else false

// void makeEmpty( ) --> Remove all items //

******************ERRORS********************************

// Throws Overflow if capacity exceeded /**

* Implements a binary heap.

* Note that all \compareTo method.

* @author Mark Allen Weiss */

public class BinaryHeap {

//@ invariant wellFormed(); /**

* Construct the binary heap. */

public BinaryHeap( ) {

this( DEFAULT_CAPACITY ); }

2

/**

* Construct the binary heap.

* @param capacity the capacity of the binary heap. */

//@ requires capacity > 0; //@ ensures isEmpty();

public BinaryHeap( int capacity ) {

currentSize = 0;

array = new int[ capacity + 1 ]; }

/**

* Insert into the priority queue, maintaining heap order.

* Duplicates are allowed.

* @param x the item to insert.

* @exception Overflow if container is full. */

public void insert( int x ) throws Overflow {

if( isFull( ) )

throw new Overflow( );

// Percolate up

int hole = ++currentSize;

for( ; hole > 1 && x< array[ hole / 2 ]; hole /= 2 )

array[ hole ] = array[ hole / 2 ]; array[ hole ] = x; }

/**

* Find the smallest item in the priority

2016-2017-1慕测平台测试报告

queue.

* @return the smallest item, or null, if empty. */

public int findMin( ) {

if( isEmpty( ) ) return -1; return array[ 1 ]; }

boolean wellFormed() {

if(array==null) {//array!=null return false; }

if(currentSize<0 ||

currentSize>=array.length) {//currentSize>=0; currentSize

for(int i=1; iarray[2*i]) {

return false; }

if(i*2 + 1<= currentSize && array[i]>array[2*i+1]) {

return false; } }

return true; } /**

* Remove the smallest item from the priority queue.

* @return the smallest item, or null, if empty. */

public int deleteMin( ) {

if( isEmpty( ) ) return -1;

int minItem = findMin( );

array[ 1 ] = array[ currentSize-- ];

percolateDown( 1 );

return minItem; }

/**

* Establish heap order property from an arbitrary

* arrangement of items. Runs in linear time. */

public void buildHeap( ) {

for( int i = currentSize / 2; i > 0; i-- ) percolateDown( i ); }

/**

* Test if the priority queue is logically empty.

* @return true if empty, false otherwise. */

public boolean isEmpty( ) {

return currentSize == 0; }

/**

* Test if the priority queue is logically full.

* @return true if full, false otherwise. */

public boolean isFull( ) {

return currentSize == array.length - 1; }

/**

* Make the priority queue logically empty. */

//@ ensures isEmpty();

3

2016-2017-1慕测平台测试报告

public void makeEmpty( ) {

currentSize = 0; }

private static final int DEFAULT_CAPACITY = 100;

private int currentSize; // Number of elements in heap

private int [ ] array; // The heap array

/**

* Internal method to percolate down in the heap.

* @param hole the index at which the percolate begins. */

private void percolateDown( int hole ) {

int child;

int tmp = array[ hole ]; /**

* Exception class for access in full containers * such as stacks, queues, and priority queues. * @author Mark Allen Weiss */

public class Overflow extends Exception { }

题目（2）

import java.util.Comparator; import java.util.Random; /**

* A class that contains several sorting routines,

* implemented as static methods.

* Arrays are rearranged with smallest item first,

* using compareTo.

* @author Mark Allen Weiss */

4

for( ; hole * 2 <= currentSize; hole = child ) { child = hole * 2;

if( child != currentSize && array[ child + 1 ]< array[ child ] )

child++; if( array[ child ]< tmp ) array[ hole ] = array[ child ];

else

break; }

array[ hole ] = tmp; } }

public final class Sorting {

/**

* Simple insertion sort.

* @param a an array of Comparable items. */

public void insertionSort( int[ ] a ) {

int j;

for( int p = 1; p < a.length; p++ )

2016-2017-1慕测平台测试报告

{

int tmp = a[ p ];

for( j = p; j > 0 && tmp

a[ j ] = a[ j - 1 ]; a[ j ] = tmp; } }

public boolean isSorted(int[] a) { for(int i=0; ia[i+1]) { return false; } }

return true; }

public static void quicksort( int[ ] a ) {

quicksort( a, 0, a.length - 1 ); }

private static final int CUTOFF = 10;

public static final void

swapReferences( Object [ ] a, int index1, int index2 ) {

Object tmp = a[ index1 ]; a[ index1 ] = a[ index2 ]; a[ index2 ] = tmp; }

public static final void swap(int[] a,int index1,int index2) {

int tmp = a[ index1 ]; a[ index1 ] = a[ index2 ]; a[ index2 ] = tmp; }

private static int median3( int[ ] a, int left, int right ) {

int center = ( left + right ) / 2;

5

if( a[ center ]

// Place pivot at position right - 1 swap( a, center, right - 1 ); return a[ right - 1 ]; }

private static void quicksort( int[ ] a, int left, int right) {

if( left + CUTOFF <= right ) {

int pivot = median3( a, left, right );

int i = left, j = right - 1; for( ; ; ) {

while( a[ ++i ] < pivot ) { }

while( a[ --j ] > pivot ) { } if( i < j )

swap( a, i, j ); else

break; }

swap( a, i, right - 1 ); // Restore pivot

quicksort( a, left, i - 1 ); // Sort small elements

quicksort( a, i + 1, right ); // Sort large elements }

else // Do an insertion sort on the subarray

insertionSort( a, left, right ); }

本文来源：https://www.bwwdw.com/article/biyd.html