Recursion Exercises


[Page 400 ( continued )]

Recursion Exercises

7.31

( Selection Sort ) A selection sort searches an array looking for the smallest element. Then, the smallest element is swapped with the first element of the array. The process is repeated for the subarray beginning with the second element of the array. Each pass of the array results in one element being placed in its proper location. This sort performs comparably to the insertion sortfor an array of n elements, n 1 passes must be made, and for each subarray, n 1 comparisons must be made to find the smallest value. When the subarray being processed contains one element, the array is sorted. Write recursive function selectionSort to perform this algorithm.

7.32

( Palindromes ) A palindrome is a string that is spelled the same way 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 function testPalindrome that returns true if the string stored in the array is a palindrome, and false otherwise . The function should ignore spaces and punctuation in the string.

7.33

( Linear Search) Modify the program in Fig. 7.19 to use recursive function linearSearch to perform a linear search of the array. The function 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.

7.34

( Eight Queens) Modify the Eight Queens program you created in Exercise 7.26 to solve the problem recursively.

7.35

( Print an array ) Write a recursive function printArray that takes an array, a starting subscript and an ending subscript as arguments and returns nothing. The function should stop processing and return when the starting subscript equals the ending subscript.

7.36

( Print a string backward ) Write a recursive function stringReverse that takes a character array containing a string and a starting subscript as arguments, prints the string backward and returns nothing. The function should stop processing and return when the terminating null character is encountered .

7.37

( Find the minimum value in an array ) Write a recursive function recursiveMinimum that takes an integer array, a starting subscript and an ending subscript as arguments, and returns the smallest element of the array. The function should stop processing and return when the starting subscript equals the ending subscript.



[Page 400 ( continued )]

vector Exercises

7.38

Use a vector of integers to solve the problem described in Exercise 7.10.

7.39

Modify the dice-rolling program you created in Exercise 7.17 to use a vector to store the numbers of times each possible sum of the two dice appears.

7.40

( Find the minimum value in a vector ) Modify your solution to Exercise 7.37 to find the minimum value in a vector instead of an array.



[Page 401]

Chapter 8. Pointers and Pointer-Based Strings

Addresses are given to us to conceal our whereabouts.

Saki (H. H. Munro)

By indirection find direction out .

William Shakespeare

Many things, having full reference

To one consent , may work contrariously.

William Shakespeare

You will find it a very good practice always to verify your references, sir!

Dr. Routh

OBJECTIVES

In this chapter you will learn:

  • What pointers are.

  • The similarities and differences between pointers and references and when to use each.

  • To use pointers to pass arguments to functions by reference.

  • To use pointer-based C-style strings.

  • The close relationships among pointers, arrays and C-style strings.

  • To use pointers to functions.

  • To declare and use arrays of C-style strings.


[Page 402]

Outline

8.1 Introduction

8.2 Pointer Variable Declarations and Initialization

8.3 Pointer Operators

8.4 Passing Arguments to Functions by Reference with Pointers

8.5 Using const with Pointers

8.6 Selection Sort Using Pass-by-Reference

8.7 sizeof Operators

8.8 Pointer Expressions and Pointer Arithmetic

8.9 Relationship Between Pointers and Arrays

8.10 Arrays of Pointers

8.11 Case Study: Card Shuffling and Dealing Simulation

8.12 Function Pointers

8.13 Introduction to Pointer-Based String Processing

8.13.1 Fundamentals of Characters and Pointer-Based Strings

8.13.2 String Manipulation Functions of the String-Handling Library

8.14 Wrap-Up

Summary

Terminology

Self-Review Exercises

Answers to Self-Review Exercises

Exercises

Special Section: Building Your Own Computer

More Pointer Exercises

String-Manipulation Exercises

Special Section: Advanced String-Manipulation Exercises

A Challenging String-Manipulation Project