1.2: A Look Ahead

A nucleus of commonly used data structures will be introduced. These include arrays and records, which are static structures that change only their values, and stack, lists, trees, and files, which are dynamic structures whose size and shape change as well as their values. Specific ways to implement each structure will be explained and typical and important operations on them investigated. These operations include selection, traversal, insertion, deletion, searching, and sorting. Although particular methodologies and data structures are important, it is more important to acquire skill in applying a methodology and in determining which data structures are appropriate for a given problem.

Programs are built from data structures. Yet the methodology an expert programmer uses makes the data structures invisible and makes the program structure clear and understandable. Neither good program structure nor good data structure selection alone produces good programs. Both must be done well, but they cannot be done independently. Obtaining a good program requires a well-designed solution, expressed first as an algorithm. The final step is writing the program in a programming language.

Determining what information is required to implement the algorithm and how to store it for efficient use and processing are perhaps the most crucial aspects of that facet of problem solving that is commonly called computer programming. The aim of this text is to illustrate good algorithm design, data structure selection, and programs.

If you do not know how to solve a given problem, then you cannot magically write a program to do so. In other words, if you don't know where you are going, then it doesn't matter how you get there. Moreover, as H. L. Mencken said, "Every complex problem has a simple easy-to-understand wrong answer." So before you begin writing a program, you will need to understand the problem and write a step-by-step solution, or algorithm.

Unfortunately, there is no algorithm for finding algorithms. There isn't even an algorithm for checking a candidate to see if it really is an algorithm. But there are some helpful techniques for developing algorithms. For example, it is useful to recognize when a known algorithm or program can be modified to give a solution to a new problem. One way to enhance this recognition is to solve problems in general or abstract terms. Sometimes a problem requires finding an object stored in computer memory that has certain properties. One technique is to search through the set of all objects until one with the desired properties is found. Alternatively, objects without the desired properties may be eliminated. The latter approach is used to develop a prime number algorithm in Section 1.3. At other times it may be possible to avoid searching altogether by constructing the desired object directly. Thinking up an algorithm is usually more difficult than programming it.