分类：Algorithms

The concept of recursion is fundamental in mathematics and computer science. The simple definition is that a recursive program in a programming language is one that calls itself (just as a recursive function in mathematics is one that is defined in terms of itself). A recursive program cannot call itself always, or it would never stop (just as a recursive function cannot be defined in terms of itself always, or the definition would be circular); so a second essential ingredient is that there must be a termination condition when the program can cease to call itself (and when the mathematical function is not defined in terms of itself). All practical computations can be couched in a recursive framework. The study of recursion is intertwined with the study of recursively defined structures known as trees. We use trees both to help us understand and analyze recursive programs and as explicit data structures. 继续阅读“Recursion and Trees～ Recursive Algorithms”

As a final example in ADT series, we consider in this section an application-specific ADT that is representative of the relationship between applications domains and the algorithms and data structures of the type that we consider in this series. 继续阅读“Abstract Data Types～ Application-Based ADT Example”

Our interfaces and implementations of stack and FIFO queue ADTs in Abstract Data Types～Stack ADT and Abstract Data Types～Queues and Unique Items provide clients with the capability to use a single instance of a particular generalized stack or queue, and to achieve the important objective of hiding from the client the particular data structure used in the implementation. Such ADTs are widely useful, and will serve as the basis for many of the implementations that we consider in this series. 继续阅读“Abstract Data Types～ First-Class ADTs”

Abstract Data Types～Stack ADT present a complete example of C code that captures one of our most important abstractions: the pushdown stack. The interface defines the basic operations; client programs can use those operations without dependence on how the operations are implemented; and implementations provide the necessary concrete representation and program code to realize the abstraction. 继续阅读“Abstract Data Types～Queues and Unique Items”

Of the data types that support insert and delete for collections of objects, the most important is called the pushdown stack. 继续阅读“Abstract Data Types～Stack ADT”

DEVELOPING ABSTRACT MODELS for our data and for the ways in which our programs process those data is an essential ingredient in the process of solving problems with a computer. In this series, we consider abstract data types (ADTs), which allow us to build programs that use high-level abstractions. With abstract data types, we can separate the conceptual transformations that our programs perform on our data from any particular data-structure representation and algorithm implementation. 继续阅读“Abstract Data Types～Abstract Objects and Collections of Objects”

Arrays, linked lists, and strings all provide simple ways to structure data sequentially. They provide a first level of abstraction that we can use to group objects in ways amenable to processing the objects efficiently. Having settled on these abstractions, we can use them in a hierarchical fashion to build up more complex structures. We can contemplate arrays of arrays, arrays of lists, arrays of strings, and so forth. 继续阅读“Elementary Data Structures ~ Compound Data Structures”

We use the term string to refer to a variable-length array of characters, defined by a starting point and by a string-termination character marking the end. Strings are valuable as low-level data structures, for two basic reasons. 继续阅读“Elementary Data Structures ~ Strings”

Linked lists bring us into a world of computing that is markedly different from that of arrays and structures. With arrays and structures, we save an item in memory and later refer to it by name (or by index) in much the same manner as we might put a piece of information in a file drawer or an address book; with linked lists, the manner in which we save information makes it more difficult to access but easier to rearrange. Working with data that are organized in linked lists is called list processing. 继续阅读“Elementary Data Structures ~ Linked Lists II”