8.7 Subprograms

When we examined recursion, we introduced the concept of a named subalgorithm. Here we look at these in the nonrecursive context and discuss how we pass information back and forth between algorithm and subalgorithm. Because we are talking about actual language constructs, we call these structures subprograms rather than subalgorithms.

Many subprograms are available as part of a high-level language or as part of the library that comes with the language. For example, mathematical problems often need to calculate trigonometric functions. Subprograms that calculate these values are available in most high-level languages in one way or another. When a program needs to calculate one of these values, the programmer looks up the name of the subprogram that calculates the value and just calls the subprogram to perform the calculation.

If one of these subprograms needs to have information passed to it, the calling unit sends over the values for the subprogram to use. For example, the following two statements set x to m times the sine function of t and y to the absolute value of z. The sine function and the absolute value function are built into many languages. The information sent to the sine function is t; the information sent to the absolute value function is z. Both of these functions are value-returning subprograms.

The same is true when you write your own subprograms. We now look at the mechanism used for passing information back and forth between the calling program and subprogram.

We have assumed these capabilities in the algorithms relating to the abstract data types we have examined. Take, for example, the following list algorithm:

Insert needs a list and a value to insert into it. Reset needs the list to reset. MoreItems needs the list to see if more items remain to be returned. GetNext needs the list as input and returns the next item in the list. This communication is done through the concept of a parameter list.

Parameter Passing

A parameter list is a list of the identifiers or values with which the subprogram is to work; it appears in parentheses beside the subprogram name. Because a subprogram is defined before it is called, it does not know with which variables from the calling unit it is to work. To solve this dilemma, we specify a list of variable names in parentheses beside the subprogram name. These identifiers are called parameters. When the subprogram is called, the calling unit lists the subprogram name, followed by a list of identifiers in parentheses. These identifiers are called arguments. The arguments represent actual variables in the calling unit with which the subprogram is to work.

You can think of a parameter as being a temporary identifier that is used within a subprogram. When a subprogram is called, the calling unit sends the names of the actual identifiers the subprogram is to use. The action in the subprogram is defined using the parameters; the action is executed using the arguments. When the action takes place, the arguments are substituted one by one for the parameters. This substitution can be done in several ways, but the most common practice is by position. The first argument substitutes for the first parameter, the second argument substitutes for the second parameter, and so on.

We have promised not to look at too many implementations, but this one is easy. We can implement a list using an array and a length field. When we add an item to the list, we store it in the array (values) at the length – 1 position and increment length. We bind the values and the length together into a record called list, which we pass to the subprogram that needs it.

list is the parameter and mylist is the argument. When Insert is executed, myList replaces list.

The substitution mechanism acts much like a message board. When a subprogram is called, a list of the arguments is given to the subprogram (put on the subprogram’s message board). These arguments tell the subprogram where to find the values to use. When a parameter is used in the body of the subprogram, the subprogram accesses the argument through its relative position on the message board. That is, the subprogram looks for its first parameter in the first position on the message board and for its second parameter in the second position on the message board.

The number of arguments in the call must match the number of parameters in the subprogram heading. Because the arguments and parameters are matched by position, their names don’t have to be the same. This is very helpful when a subprogram is called more than once, with different arguments in each call. Parameters passed in this fashion are often called positional parameters.

Value and Reference Parameters

There are two basic ways of passing parameters: by value and by reference (or address). If a parameter is a value parameter, the calling unit gives a copy of the argument to the subprogram. If a parameter is a reference parameter, the calling unit gives the address of the argument to the subprogram. This very fundamental difference means that a subprogram cannot change the content of a value argument because it receives only a copy of the argument. The subprogram can modify the copy, but the original variable will not be changed. In contrast, any argument passed by the calling unit to a reference parameter can be changed by the subprogram because the subprogram manipulates the actual variable, not a copy of it. In the previous example, the record being passed as list must be a reference parameter. If it is not, items would be inserted into the copy, not the original.

Think of the difference this way: To access a reference parameter, the subprogram accesses the contents of the address listed on the message board. To access a value parameter, the subprogram accesses the contents of the message board. Clearly, both the calling unit and the subprogram must know which parameter/argument is to be passed by value and which is to be passed by reference. Not all high-level languages allow both kinds of parameters, but those that do have some syntactic schemes to label parameters as value or reference.

Before we leave subprograms, let’s look at an example that illustrates the difference between value and reference parameters. We have already written an algorithm that swaps the contents of two places in memory. Here is the solution without problem-dependent variable names:

Now suppose that the calling unit (the part of the program that wants the contents of the two places exchanged) calls Swap with data1 and data2 as parameters.

Now let’s say that data1 is stored in location 0002 and data2 is stored in location 0003. These locations contain the values 30 and 40, respectively. FIGURE 8.15 shows the content of the message board when the parameters are passed by value and passed by reference. When a parameter is a value parameter, the subprogram knows to manipulate the value on the message board. When a parameter is a reference parameter, the subprogram knows to manipulate the contents of the address on the message board. Should the parameters for subprogram Swap be value or reference parameters?

Before we leave the topic of subprograms and parameters, let’s implement three more of the list subprograms: getLength, IsThere, and Delete. If the list items are not to be kept in sorted order, we can just put the first one in the length position and increment length. For this example, let’s assume that only one copy of each item can be in the list.

A figure depicts the difference between value parameters and reference parameters.

FIGURE 8.15 The difference between value parameters and reference parameters

IsThere is a subprogram that returns a value—in this case, a Boolean value. Thus it would be used in an expression such as

This type of subprogram is called a value-returning subprogram. Delete and Insert, in contrast, do not return a specific value. However, they do return the changed list through its parameters. If we assume that the item to be deleted is in the list, the implementation is simple: When we find the item to be deleted, we just exchange it with the last item in the list and decrement length.

IsThere can be used to make sure that the item to be deleted is in the list.

Value-returning subprograms include the RETURN statement followed by a value to be returned. Non-value-returning subprograms may have a RETURN statement, but it is unnecessary. To conclude this section, here is a code segment that reads values into the list and then deletes some values:

SUMMARY

Lists, stacks, queues, trees, and graphs are all useful abstract composite structures. Each has its own defining property and the operations that guarantee that property. All of these abstract structures include operations to insert items and to remove items. Lists and trees also have operations to find items within the structure.

Lists and trees have the same properties: Items can be inserted, deleted, and retrieved. Items can be inserted in a stack, but the item removed and returned is the last item inserted into the stack—that is, the item that has been in the stack the shortest time. Items can be inserted into a queue, but the item removed and returned is the first item put into the queue—that is, the item that has been in the queue the longest time.

Lists, stack, queues, and trees are merely holding structures, but graphs are more complex. A wealth of mathematical algorithms can be applied to information in a graph. We examined three of these: the breadth-first search, the depth-first search, and the single-source shortest-path search.

Subprogram statements allow subalgorithms to be implemented independently. A subprogram may be value returning, in which case it is called by placing its name and arguments within an expression. Alternatively, a subprogram may be non-value-returning (void), in which case the subprogram name is used as a statement in the calling program. Data sent to and from subprograms are transmitted by the use of parameter lists. Parameters may be either reference or value parameters. An argument is passed to a value parameter by sending a copy of the argument to the subprogram. An argument is passed to a reference parameter by sending the address of the argument to the subprogram.

KEY TERMS

EXERCISES

For Exercises 1–10, indicate which structure would be a more suitable choice for each of the following applications by marking them as follows:

  1. Stack

  2. Queue

  3. Tree

  4. Binary search tree

  5. Graph

  1.   1. A bank simulation of its teller operation to see how waiting times would be affected by adding another teller.

  2.   2. A program to receive data that is to be saved and processed in the reverse order.

  3.   3. An electronic address book, kept ordered by name.

  4.   4. A word processor with a PF key that causes the preceding command to be redisplayed; every time the PF key is pressed, the program is to show the command that preceded the one currently displayed.

  5.   5. A dictionary of words used by a spell checker to be built and maintained.

  6.   6. A program to keep track of patients as they check into a medical clinic, assigning patients to doctors on a first-come, first-served basis.

  7.   7. A program keeping track of where canned goods are located on a shelf.

  8.   8. A program to keep track of the soccer teams in a city tournament.

  9.   9. A program to keep track of family relationships.

  10. 10. A program to maintain the routes in an airline.

For Exercises 11–30, mark the answers true or false as follows:

  1. True

  2. False

  1. 11. A binary search cannot be applied to a tree.

  2. 12. A stack and a queue are different names for the same ADT.

  3. 13. A stack displays FIFO behavior.

  4. 14. A queue displays LIFO behavior.

  5. 15. A leaf in a tree is a node with no children.

  6. 16. A binary tree is a tree in which each node can have zero, one, or two children.

  7. 17. Binary search tree is another name for a binary tree.

  8. 18. The value in the right child of a node (if it exists) in a binary search tree will be greater than the value in the node itself.

  9. 19. The value in the left child of a node (if it exists) in a binary search tree will be greater than the value in the node itself.

  10. 20. In a graph, the vertices represent the items being modeled.

  11. 21. Algorithms that use a list must know whether the list is array-based or linked.

  12. 22. A list may be linear or nonlinear, depending on its implementation.

  13. 23. The root of a tree is the node that has no ancestors.

  14. 24. Binary search trees are ordered.

  15. 25. On average, searching in a binary search tree is faster than searching in an array-based list.

  16. 26. On average, searching in a binary search tree is faster than searching in a list.

  17. 27. A binary search tree is always balanced.

  18. 28. Given the number of nodes and the number of levels in a binary search tree, you can determine the relative efficiency of a search in the tree.

  19. 29. Insertion in a binary search tree is always into a leaf node.

  20. 30. A binary search tree is another implementation of a sorted list.

The following algorithm (used for Exercises 31–33) is a count-controlled loop going from 1 through 5. At each iteration, the loop counter is either printed or put on a stack, depending on the result of Boolean function RanFun(). (The behavior of RanFun() is immaterial.) At the end of the loop, the items on the stack are popped and printed. Because of the logical properties of a stack, this algorithm cannot print certain sequences of the values of the loop counter. You are given an output and asked if the algorithm could generate the output. Respond as follows:

  1. True

  2. False

  3. Not enough information

  1. 31. The following output is possible using a stack: 1 3 5 2 4.

  2. 32. The following output is possible using a stack: 1 3 5 4 2.

  3. 33. The following output is possible using a stack: 1 3 5 1 3.

The following algorithm (used for Exercises 34–36) is a count-controlled loop going from 1 through 5. At each iteration, the loop counter is either printed or put on a queue, depending on the result of Boolean function RanFun(). (The behavior of RanFun() is immaterial.) At the end of the loop, the items on the queue are dequeued and printed. Because of the logical properties of a queue, this algorithm cannot print certain sequences of the values of the loop counter. You are given an output and asked if the algorithm could generate the output. Respond as follows:

  1. True

  2. False

  3. Not enough information

  1. 34. The following output is possible using a queue: 1 3 5 2 4.

  2. 35. The following output is possible using a queue: 1 3 5 4 2.

  3. 36. The following output is possible using a queue: 1 3 5 1 3.

Exercises 37–50 are short-answer questions.

  1. 37. What is written by the following algorithm?

  1. 38. What is written by the following algorithm?

  1. 39. Write an algorithm that sets bottom equal to the last element in the stack, leaving the stack empty.

  2. 40. Write an algorithm that sets bottom equal to the last element in the stack, leaving the stack unchanged.

  3. 41. Write an algorithm to create a copy of myStack, leaving myStack unchanged.

  4. 42. Write an algorithm that sets last equal to the last element in a queue, leaving the queue empty.

  5. 43. Write an algorithm that sets last equal to the last element in a queue, leaving the queue unchanged.

  6. 44. Write an algorithm to create a copy of myQueue, leaving myQueue unchanged.

  7. 45. Write an algorithm replace that takes a stack and two items. If the first item is in the stack, replace it with the second item, leaving the rest of the stack unchanged.

  8. 46. Write an algorithm replace that takes a queue and two items. If the first item is in the queue, replace it with the second item, leaving the rest of the queue unchanged.

  9. 47. Draw the binary search tree whose elements are inserted in the following order:

    50 72 96 107 26 12 11 9 2
    10 25 51 16 17 95

  10. 48. If Print is applied to the tree formed in Exercise 47, in which order would the elements be printed?

  11. 49. Examine the following algorithm and apply it to the tree formed in Exercise 47. In which order would the elements be printed?

  1. 50. Examine the following algorithm and apply it to the tree formed in Exercise 47. In which order would the elements be printed?

Exercises 51–55 are short-answer questions based on the following directed graph.

A figure shows a problem which represents a search tree path.

  1. 51. Is there a path from Oregon to any other state in the graph?

  2. 52. Is there a path from Hawaii to every other state in the graph?

  3. 53. From which state(s) in the graph is there a path to Hawaii?

  4. 54. Show the table that represents this graph.

  5. 55. Can you get from Vermont to Hawaii?

Exercises 56–60 are short-answer questions based on the following directed graph.

A figure shows a problem which represents a depth-first traversal tree.

  1. 56. Show the depth-first traversal from Jean to Sandler.

  2. 57. Show the depth-first traversal from Lance to Darlene.

  3. 58. Show the breadth-first traversal from Jean to Sandler.

  4. 59. Show the breadth-first traversal from Lance to Darlene.

  5. 60. Show the table that represents this graph.

Exercises 61–69 are short-answer exercises.

  1. 61. Given the record List containing the array values and the variable length, write the algorithm for GetLength.

  2. 62. Assume that record List has an additional variable currentPosition, initialized to the first item in the list. What is the initial value of currentPosition?

  3. 63. Write the algorithm for MoreItems, which returns TRUE if there are more items in the list and FALSE otherwise.

  4. 64. Write the algorithm for GetNext(myList, item) so that item is the next item in the list. Be sure to update currentPosition.

  5. 65. Exercises 61–64 create the algorithms that allow the user of a list to see the items one at a time. Write the algorithm that uses these operations to print the items in a list.

  6. 66. What happens if an insertion or deletion occurs in the middle of an iteration through the list? Explain.

  7. 67. Can you think of a way to keep the user from doing an insertion or deletion during an iteration?

  8. 68. Distinguish between value and reference parameters.

  9. 69. How are arguments and parameters matched?

THOUGHT QUESTIONS

  1. A spreadsheet is a table with rows and columns. Think about an ADT spreadsheet. Which operations would you need to construct the table? Which operations would you need to manipulate the values in the table?

  2. Binary trees, binary search trees, and graphs are visualized as nodes and arrows (pointers) that represent the relationships between nodes. Compare these structures in terms of the operations that are allowed. Can a list ever be a tree? Can a tree ever be a list? Can a tree ever be a graph? Can a graph ever be a tree? How do the structures all relate to one another?

  3. Before computers, water-cooler conversations were thought to be private. How has computer technology changed this assumption?

  4. How do the rights of employees collide with privacy rights in the workplace?

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.191.223.123