Programming, Problem Solving
Download 0.51 Mb.
|
- Navigate this page:
- Data Structures Thomas E. Hicks Douglas W. Nance Thomas L. Naps Copyright Pending for West Publishing Co.
- One-Dimensional Arrays Character Strings
- Using Loops To Fill and Display Arrays
Introduction to Computer Science With C: Programming, Problem Solving, & Data Structures Thomas E. Hicks Douglas W. Nance Thomas L. Naps Copyright Pending for West Publishing Co.
This chapter begins a significant new stage of programming. Prior to now, we have been unable to manipulate and store large amounts of data in a convenient way. For example, if we wanted to work with a long list of numbers or names, we had to declare a separate variable for each number or name. Fortunately, C (and most other programming languages) provides several structured variables to facilitate solving problems that require working with large amounts of data. Simply put, an array is a structure that uses one identifier to reserve a large amount of memory. This memory is capable of holding several individual values. Structured variables included in this text are arrays, records, files, and sets. Arrays, the topic of this chapter, are designed to handle large amounts of data of the same type in an organized manner. Using arrays permits us to set aside a group of memory locations that we can then manipulate as a single entity or have direct access to any component. Some very standard applications for array variables include creating tabular output (tables), alphabetizing a list of names, analyzing a list of test scores, manipulating character data, and keeping an inventory. Section 7.1 introduces both character and numeric arrays; they will be filled with a variety random numbers, assigned values, and sequences. Section 7.2 examines the filling of arrays from keyboard and potential overflow problems. Section 7.3 introduces sorting with special emphasis on the selection sort. Section 7.4 studies the passing of arrays to subprograms and pointer arithmetic. Section 7.5 examines searching with special emphasis on sequential and binary techniques. Section 7.6 returns us to string processing. 7.1 Basic Idea and Notation Declaration of Arrays and Array Assignments As previously mentioned, there are many instances in which several variables of the same data type are required. Let us at this point work with a list of five integers: 18, 17, 21, 18, and 19. Prior to this chapter, we would have declared five variables--A, B, C, D, and E--and assigned them appropriate values. This would have produced five values in memory each accessed by a separate identifier. If the list was very long, this would be an inefficient way to work with these data; an alternative is to use an array. In C, we declare a variable as an integer array with 5 elements by
The five individual portions of the array are referred to as cells or components or elements of the array. When Age is declared as an integer, the contents of the two bytes of memory assigned by the memory manager are unknown. When Data is declared as an array of five integers, ten bytes (5 elements * 2 bytes/int) of contiguous memory are allocated; the contents of the ten bytes of memory are unknown. Subscripts of 0-4 are used to index the five individual cells within array Data. The individual elements of the array could be filled by
The statements above can be arranged in any order. If the individual elements of the array were printed by
the output would be
Using Loops To Fill and Display Arrays Initializing or printing 1000 items within an array, element by element as above, would require a lot of inefficient coding. A lot of the power of the array structure is related to efficient combinations of loops. Let us place the first five even numbers into an array, called EvenNos, and verify the assignments with an appropriate print loop. Example 7.1
After the declaration above, we have five integer variables with which to work. The compiler has allocated 10 bytes (5 * 2 bytes per int) of contiguous memory for the array EvenNos. Since EvenNos is the symbolic name for a contiguous chunk of memory, its base address may be referenced by combining the symbolic name and the address indicator. Either of the following lines of code may be used to print the base address of array EvenNos:
Output:
The contiguous block of memory to house array EvenNos is assigned by the memory manager; if you run the code fragment above, both lines will display the same address, but it is unlikely that your memory manager will select address &2753454 to store the array. The individual elements of the array could be filled by
or more efficiently by
To verify that our assignment statements (either of the two program fragments above) had completed their tasks properly, we could the code fragment
or (more efficiently) by
Either of the two program fragments above will produce the following output:
A good method of visualizing these variables is to assume that memory locations are aligned in a column on top of each other and the name of the column is EvenNos. The contents of the array EvenNos and the addresses associated with each of the elements may be printed by
printf ("4 : EvenNos [4] => %lu | %3i |\n",&EvenNos[4],EvenNos[4]); printf (" |--------|\n"); printf ("3 : EvenNos [3] => %lu | %3i |\n",&EvenNos[3],EvenNos[3]); printf (" |--------|\n"); printf ("2 : EvenNos [2] => %lu | %3i |\n",&EvenNos[2],EvenNos[2]); printf (" |--------|\n"); printf ("1 : EvenNos [1] => %lu | %3i |\n",&EvenNos[1],EvenNos[1]); printf (" |--------|\n"); printf ("0 : EvenNos [0] => %lu | %3i |\n",&EvenNos[0],EvenNos[0]); printf (" |--------|\n"); or more efficiently by for (Index = 4; Index >= 0; Index --) { printf (" |--------|\n"); printf ("%d : EvenNos [%d] => %lu | %3i |\n",Index, Index, &EvenNos[Index],EvenNos[Index]); } printf (" |--------|\n"); Either of the two program fragments above will produce the following output:
Notice that the address associated with EvenNos[0] is the same address associated with EvenNos and &EvenNos. We have three ways in which we can address the ten bytes of contiguous memory (bytes &2753454 – &2753463) assigned to array EvenNos. The components of an array are referred to by their relative position in the array. This relative position is called the index or subscript of the array . It is important to remember that each array component is a variable and can be treated exactly as any other declared variable of that data type; this means that EvenNos[1], or any other component of array EvenNos, may be treated like any other integer. The subscript of an array may be an integer constant, an integer variable, or an integer expression. The sizeof function can be used (inside the subprogram declaring the local array) to display the number of bytes in the array. The line
produces
Let us now examine this declaration more closely. Several comments are in order. Assume that an array has been declared by
1. "List" can be any valid identifier. As always, it is good practice to use descriptive names to enhance readability. 2. An array can be declared involving any valid data type; each of the following will allocate five blocks of contiguous blocks of memory in accordance with their respective data types:
3. "[5]" is the syntax that indicates the array consists of five memory components accessed by specifying each of the subscripts {0, 1, 2, 3, and 4}. We frequently say the array is of length five. The information inside the brackets is the index and is used to reference individual components of an array. This index is of integer type and must be in the range 0–4. Assignments to array elements outside the range 0 – 4 will not produce a compilation error, but are likely to destroy other variables in your program or crash the system. Only advanced computer scientists generally know enough about memory management to justify using an index beyond the declared boundaries of an array. Take every precaution to be sure that your array index is within normal boundaries. 4. Use the define statement for the MAX_NOS so that it is easier to change the size of your arrays as programs grow.
It is easier to change one globally defined constant than to change each and every loop in every subprogram which manipulates the arrays. Each C compiler will have a maximum number of bytes for a declared array such as the one above; common limits are 16 K and 32 K. If the compiler limit is 16K, then the maximum number of bytes for one array is32767. When you need a single structure greater than the limit, use dynamic memory allocation. Example 7.2 A die has sides numbers 1–6. Let us write a program that will display the number of times each of the numbers 1–6 are generated with 6000 randomized rolls of a die. We shall declare an array called DiceDistribution to hold the number of 1's, the number of 2's, etc. that have been rolled. If the array were declared to contain 6 integer values, then one could place the number of 1's in element 0, the number of 2's in element 1, etc.; although this does utilize space efficiently, it sacrifices logical representation. It makes more sense to place the number of 1's in element 1, the number of 2's in element 2, etc. The array below is declared to contain 7 integer values. Element 0 of the array will not be used. Some high–level languages allow computer scientists to declare an array whose valid subscript range of elements is [2..12] or [1..6]; C, however, does not permit such a subrange of elements. In the program below, the first element of array DiceDistribution (DiceDistribtion[0]) simply will not be used in the program. #include #include # define MAX_ROLLS 6000
{ int Index, Die, DiceDistribution [7] = {0,0,0,0,0,0,0}; /* Initialize the counters to 0 */ /* DiceDistribution[5] = No 5's */ for (Index = 1; Index <= MAX_ROLLS; Index ++) { /* If the Die rolled is a 5 */ Die = (int) (rand()/32768.0 * 6 + 1); /* DiceDistribution[5]++ */ DiceDistribution[Die] ++; } for (Index = 6; Index >= 1; Index --) { printf (" |--------|\n"); printf ("DiceDistribution [ %2i ] => &%lu | %4i |\n", Index, &DiceDistribution[Index],DiceDistribution[Index]); } printf (" |--------|\n"); } ]The output from the program fragment above is
Notice that the numbers selected by the random number generator were pretty close to 1000 (+/– 18). Perhaps we will wish to examine the distributions of other random numbers within other positive ranges. Using appropriate defines, we can make the program fragment above more generic. Suppose we wanted to generate 9000 random numbers in the range 5 - 13. # define MAX_EVENTS 9000 # define HIGH_NO 13 # define LOW_NO 5
{int
Index, Array [HIGH_NO+1]; for (Index = LOW_NO; Index <= HIGH_NO; Index ++) /* Initialize counters to 0 */ Array[Index] =0; for (Index = 1; Index <= MAX_ROLLS; Index ++) /* Roll & increment */ Array[((int)(rand()/32768.0 * (HIGH_NO-LOW_NO+1) + LOW_NO))] ++; for (Index = HIGH_NO; Index >= LOW_NO; Index --) { printf (" |--------|\n"); printf ("Array [ %2i ] => &%lu | %4i |\n", Index, &Array[Index],Array[Index]); } printf (" |--------|\n"); } Array was declared to contain HIGH_NO + 1 elements in order to store the number of 5's in element 5, the number of 6's in element 6, etc. Elements 0 - 4 of this array are not used in the program above. At some point the computer scientist would decide that the amount of memory wasted would justify a different solution. The output from the code fragment above would be
Some subprogramss and program fragments are going to be so specific to a particular problem that it is a waste of time to consider generic solutions to families of problems. Other subprograms and program fragments will be needed in many similar applications. As you gain more programming experience, you will become more proficient in determining the usability of code. Keep the generic programming issue in mind as you design and implement new code. Example 7.3 Each die has numbers 1–6. The sums for a Pair of Dice will be in the range 2 – 12. Let us write a program that will display the number of times each of the valid Sums are generated with 600 randomized rolls of a pair of dice. The first solution to the problem is
#include # define MAX_ROLLS 600 main (int argc, char argv[]) { int Index, Die1, Die2, Sum, DiceSum [13] = {0,0,0,0,0,0,0,0,0,0,0,0,0}; /* Initialize Sum Counters */ for (Index = 1; Index <= MAX_ROLLS; Index ++) /* Roll Dice, Calculate Sum, & */ { /* Increment Sum Counter */ Die1 = (int) (rand()/32768.0 * 6 + 1); Die2 = (int) (rand()/32768.0 * 6 + 1); Sum = Die1 + Die2; DiceSum[Sum] = DiceSum[Sum]+1; } for (Index = 12; Index >= 2; Index --) { printf (" |--------|\n"); printf ("DiceSum [ %2i ] => &%lu | %3i |\n", Index, &DiceSum[Index],DiceSum[Index]); } printf (" |--------|\n"); } Although the logic may not be as obvious, the next code fragment (below) performs identically to the previous program. Notice that three local variables (Die1, Die2, and Sum) have been eliminated; this solution saves six bytes of memory (for these three integers) and saves a very small amount of time with fewer assignment statements. The second solution is more memory efficient, but the logic is less obvious. The computer scientist must often choose between readability and efficiency. When the computer scientist is designing operating systems, compilers, or real time systems, he/she often strives toward efficiency; for most applications that must be maintained, readability is often more important than a few bytes of memory. Many of today's compilers have compiler optimization options which produce more time efficient and space efficient code; these help the computer scientist to greater efficiency while maintaining readability. As you get into higher level computer science courses, consult your compiler manual(s) and try the optimization options if they exist.
Solution one and solution two both allocated memory for a DiceSum[0] and DiceSum[1]. This was a waste of four bytes of memory. For completeness, let us provide a third solution (below) which allocates only 11 elements for array DiceSum; although this solution is more space efficient, it is also less readable than either of the other solutions.
The following program fragment could be used with to display the array contents and addresses for either of the first two solutions. for (Index = 12; Index >= 2; Index --) { printf (" |--------|\n"); printf ("%2i : DiceSum [ %2i ] => &%lu | %3i |\n", Index, Index, &DiceSum[Index],DiceSum[Index]); } printf (" |--------|\n"); The output from the program fragment above is
Each compiler selects their preferred formula to simulate random distribution. Remember that the numbers generated by your random number function may be different than those generated in the examples above. If you have used the srand function to alter the seed of the random number generator, you can get different sets of numbers almost every time.. Download 0.51 Mb. Share with your friends:
|