HaNoi University of Technology

Week 6: Array, Collection Types, Iterators Mastering C# 2008

Week 6: Arrays, Collection Types, and Iterators

Topics
Test Array Types Homework

PART I: Test
Exercise 1 : Collections
Which of the following is an advantage of using an array? Simplicity Efficiency Type safety All of the above

1. True or false: the ArrayList class will automatically adjust its

capacity as needed? True False

2. The classes in the System.Collections namespace store what type?

Base Collection object

3. True of false: every type automatically gets a comparison method named

CompareTo that gets used for sorting. True False

4. The Hashtable class implements which abstraction?

List Set Map

Exercise 2 : Reference Types

1. True of false: using a null reference causes the program to crash. True False 2. True or false: When class types are passed by value as method parameters, the entire object is copied. True False

1/8

HaNoi University of Technology

Week 6: Array, Collection Types, Iterators Mastering C# 2008

3. Creating an An array An array An array

array of a class type yields what? of instances of that class of object references of references of the class type

4. True or false: it is considered good style to explicitly invoke the garbage collector whenever an object allocated on the heap goes out of scope. True False 5. Determining if two references refer to the same object should be done using: The == operator The Equals method The Object.ReferenceEquals method

2/8

HaNoi University of Technology

Week 6: Array, Collection Types, Iterators Mastering C# 2008

PART II: Array

Exercise 3 : Self - REVIEW EXERCISES
Fill in the blanks in each of the following statements: arrays - name, type - subscript, index or position number sorting searching - multiple-subscripted Jagged const foreach - IndexOutofRangeException a) Lists and tables of values can be stored in _____ . b) The elements of an array are related by the fact that they have the same _____ and _____. c) The number that refers to a particular element of an array is called its _____. d) The process of placing the elements of an array in order is called _____ the array. e) Determining if an array contains a certain key value is called _____ the array. f) Arrays that use two or more subscripts are referred to as _____ arrays. g) _____ arrays are maintained as arrays of arrays. h) A _____ variable must be declared and initialized in the same statement, or a syntax error will occur. i) C# provides the _____ repetition structure for iterating through values in data structures, such as arrays. j) When an invalid array reference is made, an _____ is generated. 1. State whether each of the following is true or false. If false, explain why. a) An array can store many different types of values at the same time. b) An array subscript normally should be of data type float. c) An individual array element that is passed to a method and modified in that method will contain the modified value when the called method completes execution. d) The maximum number of comparisons needed for the binary search of any sorted array is the exponent of the first power of 2 greater than the number of elements in the array. e) There are two types of multiple-subscripted arrayssquare and jagged. f) A const variable must be declared and initialized in the same statement, or a syntax error will occur. g) After each comparison, the binary search algorithm eliminates from consideration one third of the elements in the portion of the array that is being searched. h) To determine the number of elements in an array, we can use the NumberOfElements property. i) The linear search method works well for small or unsorted arrays. j) In an m-by-n array, the m stands for the number of columns and the n stands for the number of rows.

3/8

HaNoi University of Technology

Week 6: Array, Collection Types, Iterators Mastering C# 2008

Exercise 4 : Use Array Types

1. Write statements to accomplish each of the following tasks: a) Display the value of the seventh element of character array f. b) Initialize each of the five elements of single-subscripted integer array g to 8. c) Total the elements of floating-point array c of 100 elements. d) Copy 11-element array a into the first portion of array b containing 34 elements. e) Determine the smallest and largest values contained in 99-element floating-point array w.

2.

Use a single-subscripted array to solve the following problem: A company pays its salespeople on a commission basis. The salespeople receive $200 per week, plus 9% of their gross sales for that week. For example, a salesperson who grosses $5000 in sales in a week receives $200 plus 9% of $5000, or a total of $650. Write a program (using an array of counters) that determines how many of the salespeople earned salaries in each of the following ranges (assume that each salespersons salary is truncated to an integer amount): a) b) c) d) e) f) g) h) i) $200$299 $300$399 $400$499 $500$599 $600$699 $700$799 $800$899 $900$999 $1000 and over

3.

Use a single-subscripted array to solve the following problem: Read in 20 numbers, each of which is between 10 and 100, inclusive. As each number is read, print it only if it is not a duplicate of a number already read. Provide for the worst case (in which all 20 numbers are different). Use the smallest possible array to solve this problem.

4/8

HaNoi University of Technology

Week 6: Array, Collection Types, Iterators Mastering C# 2008

Exercise 5 : SPECIAL SECTION

1.
(Palindromes) A palindrome is a string that is spelled the same forward and backward. Some examples of palindromes are radar, able was i ere i saw elba and, if blanks are ignored, a man a plan a canal panama. Write a recursive method testPalindrome that returns true if the string stored in the array is a palindrome and false otherwise. The method should ignore spaces and punctuation in the string. (Linear Search) Modify Fig. 7.11 to use recursive method LinearSearch to perform a linear search of the array. The method should receive an integer array and the size of the array as arguments. If the search key is found, return the array subscript; otherwise, return 1.

2.

3.

(Binary Search) Modify the program in Fig. 7.12 to use a recursive method Binary- Search to perform the binary search of the array. The method should receive an integer array and the starting and ending subscript as arguments. If the search key is found, return the array subscript; otherwise, return 1.

4.

(Quicksort) In this chapter, we discussed the sorting technique bubble sort. We now present the recursive sorting technique called Quicksort. The basic algorithm for a single-subscripted array of values is as follows: a) Partitioning Step. Take the first element of the unsorted array and determine its final location in the sorted array (i.e., all values to the left of the element in the array are less than the element, and all values to the right of the element in the array are greater than the element). We now have one element in its proper location and two unsorted subarrays. b) Recursive Step. Perform step 1 on each unsorted subarray. Each time Step 1 is performed on a subarray, another element is placed in its final location of the sorted array, and two unsorted subarrays are created. When a subarray consists of one element, it must be sorted; therefore, that element is in its final location. The basic algorithm seems simple, but how do we determine the final position of the first element of each subarray? Consider the following set of values (partitioning element in boldit will be placed in its final location in the sorted array): 37 2 6 4 89 8 10 12 68 45 a) Starting from the rightmost element of the array, compare each element to 37 until an element less than 37 is found, then swap 37 and that element. The first element less than 37 is 12, so 37 and 12 are swapped. The new array is 12 2 6 4 89 8 10 37 68 45 Element 12 is italicized to indicate that it was just swapped with 37. b) Starting from the left of the array, but beginning with the element after 12, compare each element to 37 until an element greater than 37 is found, then swap 37 and that element. The first element greater than 37 is 89, so 37 and 89 are swapped. The new array is 12 2 6 4 37 8 10 89 68 45

5/8

HaNoi University of Technology

Week 6: Array, Collection Types, Iterators Mastering C# 2008

c) Starting from the right, but beginning with the element before 89, compare each element to 37 until an element less than 37 is found, then swap 37 and that element. The first element less than 37 is 10, so 37 and 10 are swapped. The new array is 12 2 6 4 10 8 37 89 68 45 d) Starting from the left, but beginning with the element after 10, compare each element to 37 until an element greater than 37 is found, then swap 37 and that element. There are no more elements greater than 37, so when we compare 37 to itself, we know that 37 has been placed in its final location of the sorted array. Once the partition has been applied to the previous array, there are two unsorted subarrays. The subarray with values less than 37 contains 12, 2, 6, 4, 10 and 8. The subarray with values greater than 37 contains 89, 68 and 45. The sort continues with both subarrays being partitioned in the same manner as the original array. Using the preceding discussion, write recursive method QuickSort to sort a singlesubscripted integer array. The method should receive as arguments an integer array, a starting subscript and an ending subscript. Method Partition should be called by QuickSort to perform the partitioning step.

5.

(Maze Traversal) The following grid of #s and dots (.) is a doublesubscripted array representation of a maze: # # . # # # # # # # # # # . . # . # . # . # . # # . # # . # . . . # . # # . . . . # # # . # . # # # # # . . . . . # . # # . . . # # # # . # . # # . # . # . . . . . . # # . # . # # # # . # # # # . # . . . . . . # . # # . # # # # # # # # . # # . . . . . . . . . . # # # # # . # # # # # # #

The #s represent the walls of the maze, and the dots represent squares in the possible paths through the maze. Moves can be made only to a location in the array that contains a dot. There is a simple algorithm for walking through a maze that guarantees finding the exit (assuming there is an exit). If there is not an exit, you will arrive at the starting location again. Place your right hand on the wall to your right and begin walking forward. Never remove your hand from the wall. If the maze turns to the right, you follow the wall to the right. As long as you do not remove your hand from the wall, eventually you will arrive at the exit of the maze. There may be a shorter path than the one you have taken, but you are guaranteed to get out of the maze if you follow the algorithm. Write recursive method MazeTraverse to walk through the maze. The method should receive as arguments a 12-by-12 character array representing the maze and the starting location of the maze. As MazeTraverse attempts to locate the exit from the maze, it should place the character X in each square in the path. The method should display the maze after each move so the user can watch as the maze is solved.

6/8

HaNoi University of Technology

Week 6: Array, Collection Types, Iterators Mastering C# 2008

PART III: Types

Exercise 6 : Types
In this exercise two techniques for examining the type of a class are examined. This project consists of a base class and a class that inherits from the base class. An array of assorted base and inherited classes is generated, the array is then examined using two methods to demonstrate two techniques for examining the class type. You should also examine the use of the foreach keyword on the array.

1. 2.

Set the TypeChecking project active Examine the Base, Level1 and TypeChecking classes and contained methods closely. 3. Execute the project and observe the output.

2.

Based on the inspiration from the accompanying example, you are in this exercise supposed to experiment with some simple C# arrays. First, consult the documentation of the class System.Array. Please notice the properties and methods that are available on arrays in C#. Declare, initialize, and print an array of names (e.g. array of strings) of all members of your group. Sort the array, and search for a given name using System.Array.BinarySearch method. Reverse the array, and make sure that the reversing works.

3.

Consult the documentation of type type System.Enum, and get a general overview of the methods in this struct. Be sure that you are able to find the documentation of System.Enum. See also the exercise about the type char. Test drive the example EnumTest, which is part of MicroSoft's documentation. Be sure to understand the program relative to its output. Write your own program with a simple enumeration type. Use the Enum.CompareTo method to compare two of the values of your enumeration type.

7/8

HaNoi University of Technology

Week 6: Array, Collection Types, Iterators Mastering C# 2008

PART IV: HOMEWORK

Exercise 7 : A Summary Exercise
1.Creates an array of Employees and an array of integers, populates the
Employee array and thenprints the values of both

2.Declares, instantiates, initializes, and prints the contents of a twodimensional array. In this example, a for loop is used to initialize the elements of the array.

3.Declares, instantiates, initializes, and prints the contents of a

Rectangular arrays and a Jagged array.

4.Conversion of an array of user-defined Employee types to an array of

objects.

5.Use of these two methods to manipulate String objects: Array.Sort and

Array.Reverse

6.Declares a list box control (ListBoxTest), which contains a simple

array (myStrings) and a simple indexer for accessing its contents.

7. Making a ListBox an enumerable class.

8.Add to the ArrayList using the Add( ) method, and the list takes care
of its own internal bookkeeping.

9.Creates an integer array and an Employee array, populates them both

with random numbers, and prints their values. It then sorts both arrays and prints the new values.

10. Sorting an array by employees' IDs. 11. Demonstrates adding items to a Hashtable and then retrieving them
with the Item property.

12. Using the IDictionaryEnumerator interface provides properties to

access both the key and value for each item in the dictionary.

8/8