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; 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 ); }
搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新经管营销服务计算概论作业报告 全文阅读和word下载服务。
相关推荐：
光风霁月