Programming, Problem Solving

Download 0.51 Mb.

Page	3/6
Date	05.08.2017
Size	0.51 Mb.
	#26659

1 2 3 4 5 6

The second call to function DisplayIntegerArray indicates tells us that the subprogram is successful in displaying arrays of different sizes. See below.
Array : Nos2 => & 4382382

|--------|

Nos2 [ 5 ] => 4382392 | 55 |

|--------|

Nos2 [ 4 ] => 4382390 | 44 |

|--------|

Nos2 [ 3 ] => 4382388 | 33 |

|--------| |-------|

Nos2 [ 2 ] => 4382386 | 22 | | 8 | Max

|--------| |-------|

Nos2 [ 1 ] => 4382384 | 11 | | 5 | ActNo

|--------| |-------|

The third call to function DisplayIntegerArray indicates illustrates the unknown garbage data in cells 6,7, and 8; we did not place information in these cells. This call also tested to make sure that the display never displays more that the Max (8) elements even if the programmer makes a mistake and requests 15. The following output is generated from the second call to this display function. See below.

Array : Nos2 => & 4382382
|--------|

Nos2 [ 8 ] => 4382398 | 12216 |

|--------|

Nos2 [ 7 ] => 4382396 | -3211 |

|--------|

Nos2 [ 6 ] => 4382394 | -22114 |

|--------|

Nos2 [ 5 ] => 4382392 | 55 |

|--------|

Nos2 [ 4 ] => 4382390 | 44 |

|--------|

Nos2 [ 3 ] => 4382388 | 33 |

|--------| |-------|

Nos2 [ 2 ] => 4382386 | 22 | | 8 | Max

|--------| |-------|

Nos2 [ 1 ] => 4382384 | 11 | | 5 | ActNo

|--------| |-------|

Function DisplayIntegerArray is generic. It may be used to the key components of any integer array set. It could be used for an array set involving an array of Bowling Scores, a one dimensional matrix from mathematics, an array of Exam Scores, a Vector from Physics or engineering, an array of random numbers, etc. This subprogram will be quite helpful to computer scientists during the testing phase of a program.

Example 7.10

Subprogram QuickDisplay generates a list of integers in the array. The integers are separated by a space. It is possible to display forty or more numbers on a single line. This is sometimes more desirable than the dump.

void QuickDisplay (int Array[], int NoToDisplay,int ActNo)

{

int

Index;

char

TempString[25];

if ((NoToDisplay > ActNo) || (NoToDisplay <= 0))

NoToDisplay = ActNo;

for (Index = 1; Index <= NoToDisplay; Index ++)

{

printf ("%6d ",Array[Index]);

if ( Index % 10 == 0) /* Skip a line if Index Mod 10 == 0 */

printf ("\n");

}

printf ("\n\n");

}
The following code, placed in the main,

for (ActNo1 = 0; ActNo1 < 3; )

Nos1[ActNo1] = ++ActNo1 * 5;

for (ActNo2 = 0; ActNo2 < 5; )

Nos2[ActNo2] = ++ActNo2 * 11;

for (ActNo3 = 0; ActNo3 < 21; )

Nos3[ActNo3] = ++ActNo3 * 1;

QuickDisplay (Nos1, ActNo1, ActNo1);

QuickDisplay (Nos2, ActNo2, ActNo2);

QuickDisplay (Nos3, ActNo3, ActNo3);

generates the following output:

5 10 15
11 22 33 44 55
1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

Example 7.11

Neither of the previous two subprograms altered the data in the original array. The purpose of subprogram FillArrayRandom100 is to place random integers (1-100) into elements 1,2,3,...,NoToFill of the array. The MAX is passed into this function to make sure that there is no array overflow. The ActNo must be adjusted to reflect the contents of the array.

void FillArrayRandom100 (int Array[], int NoToFill, int *ActNo, int Max)

{

int

Index;

if ((NoToFill > Max) || (NoToFill <= 0))

NoToFill = Max;

for (Index = 1 ; Index<= NoToFill; Index++)

Array[Index] = (int) rand() /32767.1 * 100 + 1;

*(ActNo) = NoToFill;

}

In order to test the FillArrayRandom100 subprogram, one might include the following code into main.

FillArrayRandom100 (Nos1, 25, &ActNo1,MAX_NOS1);

QuickDisplay (Nos1, ActNo1, ActNo1);

FillArrayRandom100 (Nos2, -25, &ActNo2,MAX_NOS2);

QuickDisplay (Nos2, ActNo2, ActNo2);

FillArrayRandom100 (Nos3, 5, &ActNo3,MAX_NOS3);

QuickDisplay (Nos3, ActNo3, ActNo3);

FillArrayRandom100 (Nos3, 15, &ActNo3,MAX_NOS3);

QuickDisplay (Nos3, ActNo3, ActNo3);

FillArrayRandom100 (Nos3, MAX_NOS3, &ActNo3,MAX_NOS3);

QuickDisplay (Nos3, ActNo3, ActNo3);

The following output indicates that the overflow test in function FillArrayRandom100 is working, but does little to assure that random numbers are in the range 1-100 because there is such a small population of data. One should also test this module with a much larger array.

52 18 31 54 95
18 71 23 50 13 9 39 28
37 99 54 77 65
77 79 83 16 63 32 35 92 52 41

61 79 94 87 87

68 76 59 39 36 21 83 42 47 98

13 22 96 74 41 79 76 96 3 32

The test data above indicates that the FillArrayRandom100 works with at least two different sized integer arrays.

Example 7.12

Subprogram SelectionSort uses sorts the array with the same logic found in program SortFloat.c. Placing the generic code into a module makes it possible to sort a variety of different sized one dimensional integer arrays with a single function.

void SelectionSort (int Array[], int ActNo)

{
int

IndexSmallestNo,

TempInt,

Pass,

Subscript;

for (Pass = 1; Pass <= ActNo-1; Pass++ )

{

IndexSmallestNo = Pass;

for (Subscript = Pass + 1;Subscript <= ActNo;Subscript++)

if (Array[Subscript] < Array[IndexSmallestNo])

IndexSmallestNo = Subscript;

TempInt = Array[IndexSmallestNo];

Array[IndexSmallestNo] = Array[Pass];

Array[Pass] = TempInt;

}

}
When the following code

FillArrayRandom100 (Nos1, 4, &ActNo1,MAX_NOS1);

QuickDisplay (Nos1, ActNo1, ActNo1);

SelectionSort (Nos1, ActNo1);

QuickDisplay (Nos1, ActNo1, ActNo1);
FillArrayRandom100 (Nos2, -5, &ActNo2,MAX_NOS2);

QuickDisplay (Nos2, ActNo2, ActNo2);

SelectionSort (Nos2, ActNo2);

QuickDisplay (Nos2, ActNo2, ActNo2);

FillArrayRandom100 (Nos3, 25, &ActNo3,MAX_NOS3);

QuickDisplay (Nos3, ActNo3, ActNo3);

SelectionSort (Nos3, ActNo3);

QuickDisplay (Nos3, ActNo3, ActNo3);

is placed into the main function to test SelectSort, the output might appear as follows:

52 18 31 54
18 31 52 54
95 18 71 23 50 13 9 39
9 13 18 23 39 50 71 95
28 37 99 54 77 65 77 79 83 16

63 32 35 92 52 41 61 79 94 87

87
16 28 32 35 37 41 52 54 61 63

65 77 77 79 79 83 87 87 92 94

The test data above indicates that the sort will work correctly on different sized arrays.

Example 7.13

Function SumArray1 explicitly returns the sum of all elements 1+2+3+...+ActNo. A message is printed and zero returned for an empty array.

int SumArray1 (int Array[], int ActNo)

{

int

Subscript,

Sum = 0;

if (ActNo <= 0 )

printf ("\n The Array is Empty in Function SumArray1 \n");

for (Subscript = 1; Subscript <= ActNo; Subscript++)

Sum = Sum + Array[Subscript];

return (Sum);

}
When the following code

ActNo2 = 0;

printf ("The Sum1 = %d\n\n",SumArray1(Nos2,ActNo2));

FillArrayRandom100 (Nos2, 3, &ActNo2,MAX_NOS2);

QuickDisplay (Nos2, ActNo2, ActNo2);

printf ("The Sum1 = %d\n\n",SumArray1(Nos2,ActNo2));

FillArrayRandom100 (Nos2, 1, &ActNo2,MAX_NOS2);

QuickDisplay (Nos2, ActNo2, ActNo2);

TempInt = SumArray1(Nos2,ActNo2);

printf ("The Sum1 = %d\n\n",TempInt);

FillArrayRandom100 (Nos3, 13, &ActNo3,MAX_NOS3);

QuickDisplay (Nos3, ActNo3, ActNo3);

printf ("The Sum1 = %d\n\n",SumArray1(Nos3,ActNo3));

is placed into the main function to test SelectSort, the output might appear as follows:

The Array is Empty in Function SumArray1

The Sum1 = 0

52 18 31
The Sum1 = 101
54
The Sum1 = 54
95 18 71 23 50 13 9 39 28 37

99 54 77
The Sum1 = 613

The test data above indicates that the sum function will work correctly on at least two different sized arrays. The testing includes arrays that contain 0, 1, and Max.

Pointer Arithmetic

Pointer Arithmetic allow pointers to be incremented or decremented. Let us assume that the value stored in an integer pointer Ptr is &2753456. One form of pointer arithmetic is pointer incrementation (Ptr++); pointer incrementation increments the address stored in the pointer by the sizeof the data type. An integer is two bytes.

int

Ptr;
Ptr++;

Ptr++;
Another form of pointer arithmetic is pointer decrementation (Ptr--); pointer decrementation decrements the address stored in the pointer by the sizeof the data type. An float is four bytes.
float

Ptr;
Ptr––;

Ptr––;

Example 7.14

All of the previous subprograms have used array indexing to work with the individual cells within an array. Function SumArray2 uses pointer arithmetic to explicitly return the sum of all elements.

A message is printed and zero returned for an empty array. In Function SumArray2, the address of element 1 of the array is passed to the function. Within the function, the pointer will be incremented to calculate the sum.
int SumArray2 (int *Ptr, int ActNo)

{

int

Counter,

Sum = 0;
if (ActNo <= 0 )

printf ("\n The Array is Empty in Function SumArray2 \n");
for (Counter = 1; Counter <= ActNo; Counter++)

{

Sum = Sum + (*Ptr);

Ptr++;

}

return (Sum);

}
When the following code

ActNo2 = 0;

printf ("The Sum2 = %d\n\n",SumArray2(&Nos2[1],ActNo2));

FillArrayRandom100 (Nos2, 3, &ActNo2,MAX_NOS2);

QuickDisplay (Nos2, ActNo2, ActNo2);

printf ("The Sum2 = %d\n\n",SumArray2(&Nos2[1],ActNo2));
FillArrayRandom100 (Nos2, 1, &ActNo2,MAX_NOS2);

QuickDisplay (Nos2, ActNo2, ActNo2);

TempInt = SumArray2(&Nos2[1],ActNo2);

printf ("The Sum2 = %d\n\n",TempInt);

FillArrayRandom100 (Nos3, 13, &ActNo3,MAX_NOS3);

QuickDisplay (Nos3, ActNo3, ActNo3);

printf ("The Sum2 = %d\n\n",SumArray2(&Nos3[1],ActNo3));

is placed into the main function to test SumArray2 the output might appear as follows:

The Array is Empty in Function SumArray2

The Sum2 = 0

31 54 95
The Sum2 = 180
18
The Sum2 = 18
71 23 50 13 9 39 28 37 99 54 77 65
The Sum2 = 565

If one wanted to include element 0 in the sum, the function call would simply pass &Nos3[0]. Let us examine the logic behind SumArray2 more in depth. FillArrayRandom100 has placed three random numbers into Nos2

--------------------------------------------------------------------------------------------------------------------------------------

Exercises 7.4
1. Assume the following declarations have been made in function main:

int

List1[100], List2[100],

ActNo1=0, ActNo2=0, High, Low;

float

Scores [30], Average;

char

Ch;

boolean

Valid, Error;

Indicate which of the following are valid subprogram headers. Write an appropriate line of code that will call each of those that are valid. Include an explanation for those that are invalid.

a. void NewList (int List);

b. void NewList (int List[], ActNo);

c. void NewList (int List[], int * ActNo);

d. void InitializeList (int * List, int * ActNo);

e. void InitializeList (List, &ActNo);

f. int HighValue (int List[]);

g. int LowValue (int * PtrList);

h. float Average (float Data[]);

i. void Average (float Data[], float * Avr);

j. void Average (float * PtrData, float * Avr);

2. Complete the following C program:
FillListWithRandomIntegers1 (List1,&ActNo1,MAX1,20,1,100);

Void-function FillListWithRandomIntegers1 shall place 20 random integers [range 1-100] into array List1. Do not place more than MAX1 integers into array. Do not use element 0.

DisplayList ( List1, ActNo1);

Void-function DisplayList shall display the memory associated with the

appropriate array in the same form as that illustrated in the DiceDistribution of Example 7.3. Do not display element 0. Display and label ActNo.

# define MAX1 25

# define MAX2 8

main(int argc, char *argv[])

{

int

List1[MAX1+1], List2[MAX2+1],

ActNo1=0, ActNo2=0;

FillListWithRandomIntegers1 (List1,&ActNo1,MAX1,20,1,100);

DisplayList ( List1, ActNo1);

FillListWithRandomIntegers1 (List2,&ActNo2,MAX2,20,50,100);

DisplayList1 ( List2, ActNo2);

3. Complete the following C program:

FillListWithRandomIntegers2 (&List1,&ActNo1,MAX1,20,1,100);

Void-function FillListWithRandomIntegers shall place 20 random integers [range 1- 100] into array List1. Do not place more than MAX1 integers into array. Do not use element 0.

DisplayList ( List1, ActNo1);

Void-function DisplayList shall display the memory associated with the

appropriate array in the same form as that illustrated in the DiceDistribution of Example 7.3. Do not display element 0. Display and label ActNo.

# define MAX1 25

# define MAX2 8

main(int argc, char *argv[])

{

int

List1[MAX1+1], List2[MAX2+1],

ActNo1=0, ActNo2=0;

FillListWithRandomIntegers2 (&List1,&ActNo1,MAX1,15,60,100);

DisplayList ( List1, ActNo1);

FillListWithRandomIntegers1 (&List2,&ActNo2,MAX2,20,-5,+5);

DisplayList1 ( List2, ActNo2);

4. Complete the following C program:

FillListWithRandomIntegers (List1,&ActNo1,MAX1,20,1,100);

Void-function FillListWithRandomIntegers shall place 20 random integers [range 1- 100] into array List1. Do not place more than MAX1 integers into array. Do not use element 0.

DisplayList ( List1, ActNo1);

Void-function DisplayList shall display the memory associated with the

appropriate array in the same form as that illustrated in the DiceDistribution of Example 7.3. Do not display element 0. Display and label ActNo.

High (List1, ActNo1);

Explicit-function High shall explicitly return the highest integer in the List.

Low (List1, ActNo1);

Explicit-function Low shall explicitly return the lowest integer in the List.
# define MAX1 25

# define MAX2 8

main(int argc, char *argv[])

{

int

List1[MAX1+1], List2[MAX2+1],

ActNo1=0, ActNo2=0,LowNum;

FillListWithRandomIntegers (List1,&ActNo1,MAX1,20,1,100);

DisplayList ( List1, ActNo1);

printf ("The High Value = %d\n",High (List1, ActNo1); printf ("The Low Value = %d\n",Low (List1, ActNo1); FillListWithRandomIntegers (&List2,&ActNo2,MAX2,20,1,1000); DisplayList1 ( List2, ActNo2);

printf ("The High Value = %d\n",High (List2, ActNo2));

LowNum = Low (List2, ActNo2);

printf ("The Low Value = %d\n",LowNum);

5. Complete the following C program:
InitializeList (&List1,&ActNo1);

Function InitializeList shall place -1 in all elements of the list and set the ActNo to 0.

InteractivelyAppendList (&List1,&ActNo1,MAX1);

Function InteractivelyAppendList shall allow the user to enter valid integers into the array while there is available room; the user will exit the module by entering the Exit value. Valid Integers are in the range 0-100. The Exit shall be -1. The prompt shall display the index and the range in the form:

Enter Value for List [1] : __

If the score is Valid, place it into the array and increment the actual number counter. Do not ever overflow an array! If this function is evoked with a full array, display an "Array Overflow" message. Place the first integer in element 1.

DisplayList ( List1, ActNo1);

Function DisplayList shall display the memory associated with the

appropriate array in the same form as that illustrated in the DiceDistribution of Example 7.3. Do not display element 0. Display and label ActNo.

# define MAX1 25

# define MAX2 8

main(int argc, char *argv[])

{

int

List1[MAX1+1], List2[MAX2+1],

ActNo1=0, ActNo2=0;

InitializeList (&List1,&ActNo1,);

InteractivelyAppendIntegers (&List1,&ActNo1,MAX1);

DisplayList ( List1, &ActNo1);

InitializeList (&List2,&ActNo2,);

InteractivelyAppendIntegers (&List2,&ActNo2,MAX2);

DisplayList ( List2, ActNo2);

InteractivelyAppendIntegers (&List2,&ActNo2,MAX2);

DisplayList ( List2, ActNo2);

InteractivelyAppendIntegers (&List2,&ActNo2,MAX2);

DisplayList ( List2, ActNo2);

Test Data:

On the first call to InteractivelyAppendIntegers try to input the sequence:

80 90 70 -1

On the second call to InteractivelyAppendIntegers try to input the sequence:

80 90 70 80 90 70 -1

On the third call to InteractivelyAppendIntegers try to input the sequence:

100 50 -1

On the fourth call to InteractivelyAppendIntegers try to input the sequence:

100 50 -1
6. Complete the following C program:
FillListWithRandomIntegers (List1,&ActNo1,MAX1,20,1,100);

Function FillListWithRandomIntegers shall place 20 random integers [range 1- 100] into array List1. Do not place more than MAX1 integers into array. Do not use element 0.

DisplayList ( List1, ActNo1);

Function DisplayList shall display the memory associated with the

appropriate array in the same form as that illustrated in the DiceDistribution of Example 7.3. Do not display element 0. Display and label ActNo.

SelectionSortList (List1,&ActNo1);

Function SelectionSort shall sort the integers in ascending order.

# define MAX1 50

# define MAX2 8
main(int argc, char *argv[])

{

int

List1[MAX1+1], List2[MAX2+1],

ActNo1=0, ActNo2=0;

FillListWithRandomIntegers (List1,&ActNo1,MAX1,40,1,1000);

SelectionSortList (List1,&ActNo1);

DisplayList ( List1, ActNo1);

FillListWithRandomIntegers (&List2,&ActNo2,MAX2,8,1,100);

SelectionSortList (List2,&ActNo2);

DisplayList1 ( List2, ActNo2);

7. Consult your library to find other computer science textbooks which explain the logic behind the "Bubble Sort". Substitute the BubbleSort for the SelectionSort as you complete problem 6.

8. As you complete problem 6, insert a call to QuickDisplay (List, ActNo) after each pass within the SelectionSort.
9. As you complete problem 7, insert a call to QuickDisplay (List, ActNo) after each pass within theBubbleSort.
10. Random order shall be generated with the rand() function to be in the range 1-30,000. In Order shall be in ascending order. Cluster 95 shall have the first 95% of the array in ascending order and the last 5% in random order. Cluster 90 shall have the first 90% of the array in ascending order and the last 10% in random order. Cluster 80 shall have the first 80% of the array in ascending order and the last 20% in random order. Cluster 70 shall have the first 70% of the array in ascending order and the last 30% in random order. Reverse Order shall be in descending order. Write the program necessary to produce and complete the following chart:
Internal Memory Sorting

----------------------------------------

Sort Name : Selection Sort Computer Type : _____________________

C Compiler : ________________________ Microprocessor Speed : _______________

a) ------------------------------------------------------------------------------------------------------------------------------------------

No Integers Sort Time

in Array Distribution (in seconds)

------------------------------------------------------------------------------------------------------------------------------------------

50 Random xxxxxxx.xx

100 Random xxxxxxx.xx

200 Random xxxxxxx.xx

400 Random xxxxxxx.xx

800 Random xxxxxxx.xx

1600 Random xxxxxxx.xx

3200 Random xxxxxxx.xx

6400 Random xxxxxxx.xx

12800 Random xxxxxxx.xx
b) Repeat Table a using In Order distribution:
------------------------------------------------------------------------------------------------------------------------------------------

No Integers Sort Time

in Array Distribution (in seconds)

------------------------------------------------------------------------------------------------------------------------------------------

50 In Order xxxxxxx.xx

100 In Order xxxxxxx.xx

200 In Order xxxxxxx.xx

400 In Order xxxxxxx.xx

800 In Order xxxxxxx.xx

1600 In Order xxxxxxx.xx

3200 In Order xxxxxxx.xx

6400 In Order xxxxxxx.xx

12800 In Order xxxxxxx.xx
c) Repeat Table a using Reverse Order distribution:

d) Repeat Table a using Cluster 95 distribution:

e) Repeat Table a using Cluster 90 distribution:

f) Repeat Table a using Cluster 80 distribution:

g) Repeat Table a using Cluster 70 distribution:

h) Use a spreadsheet to construct and print graphs for each of the tables (a-g above). Let he Number of items be the x-coordinate and the time in seconds be the y-coordinate. Use the spreadsheet to label the graph; include the computer, compiler, processor speed, and sort name.

11. Repeat problem 10 with the Bubble Sort.
12. Rewrite DisplayIntegerArray using pointer arithmetic as opposed to array indexing.
void DisplayIntegerArray (char ArrayTitle[], int * Ptr,

int NoToDisplay, int ActNo, int Max);

13. Rewrite QuickDisplay using pointer arithmetic as opposed to array indexing.
void QuickDisplay (int Array[], int NoToDisplay,int ActNo);
14. Rewrite FillArrayRandom100 using pointer arithmetic as opposed to array indexing.
void FillArrayRandom100 (int Array[], int NoToFill, int *ActNo,

int Max);

A NOTE OF INTEREST

Download 0.51 Mb.

Share with your friends:

1 2 3 4 5 6