Data Structures in C++:Sample Code

By -

Sample Code

To illustrate some of the STL routines in one place, we provide an implementation of a routine that finds word ladders. A word ladder transforms one word to another by changing one character at a time, with each change always resulting in a real word. For instance, we transform those to where using the word ladder: those, these, there, where. See [2] for a description of this problem. The word ladder problem is a standard unweighted shortest path problem, and in the typical application of five-letter words, a quadratic algorithm is acceptable. Figures 42.7 to 42.9 show some of the routines (omitting error checks, function prototypes, and a main that reads the word list and prompt for word pairs), which for the most part are straightforward.

computeAdjacentWords, shown in Figure 42.7, uses the same idiom seen in Figure 42.2

(dealing with email aliases).

In Figure 42.8 we see two versions of find Chain.

The return value for find Chain is a map in which the key is a word, and the value is an adjacent word on the chain back towards

image

the first word (or "" if there is no chain, or if the key is first). The shorter version of find Chain takes a vector containing the words, computes the map of adjacent words, and then invokes the longer version of find Chain. Because the map in find Chain is passed by constant reference, operator[] is not available, and instead we access values in the map by using the iterator returned by a call to find.

image

image

Finally, in Figure 42.9 we see the routine that returns, as a vector<string>, the chain of words given the map computed by the shortest path algorithm in find Chain. The function get Chain From Previous Map passes the first parameter by reference instead of the more natural constant reference to allow the use of operator[] to access the map. Although this is simpler to code, it is arguably inferior from a software design standpoint because it changes the parameter passing mode simply to allow expedient code.

Acknowledgment

This work was supported, in part, by the National Science Foundation under grant EIA- 9906600. Parts of this chapter are based upon the author’s work in [9].

Comments

Post a Comment

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

By -
Introduction Important advances in programming languages have occurred since the early days of assembly languages and op codes, and modern programming languages have significantly simplified the task of writing computer programs. Unfortunately, tools for un d e rstanding programs have not achieved the accompanying levels of improvement. Software developers still face difficulties in understanding, analyzing, debugging, and improving code. As an example of the difficulties still evident, consider a developer who has just implemented a new algorithm and is now ready to examine the program’s behavior. After issuing a command to begin program execution, the developer examines output data and/or inter- active behavior, attempting to ascertain if the program functioned correctly, and if not, the reasons for the program’s failure. This task can be laborious and usually requires the use of a debugger or perhaps even the addition of explicit checking code, usually through output statements. Furt
Read more

Collision Detection:Penetration Depth Computation

By -
Image
Penetration Depth Computation In this section, we give a brief overview of penetration depth (PD) computation algorithms between convex polytopes and general polyhedral models. The PD of two inter-penetrating objects A and B is defined as the minimum translation distance that one object undergoes to make the interiors of A and B disjoint. It can be also defined in terms of the TCSO. When two objects are overlapping, the origin of the Minkowski sum of A and − B is contained inside the TCSO. The penetration depth corresponds to the minimum distance from the origin to the surface of TCSO [18]. PD computation is often used in motion planning [37], contact resolution for dynamic simulation [38, 39] and force computation in haptic rendering [40]. For example, computation of dynamic response in penalty-based methods often needs to perform PD queries for imposing the non-penetration constraint for rigid body simulation. In addition, many applications, such as motion planning and dynamic simula
Read more

Concurrent Data Structures:Linked Lists

By -
Linked Lists Consider implementations of concurrent search structures supporting insert, delete, and search operations. If these operations deal only with a key value, then the resulting data structure is a se t ; if a data value is associated with each key, we have a dic tionary [24]. These are closely related data structures, and a concurrent set implementation can often be adapted to implement a dictionary. In the next three sections, we concentrate on implementing sets using different structures: linked lists, hash tables, and trees. Suppose we use a linked list to implement a set. Apart from globally locking the linked list to prevent concurrent manipulation, the most popular approach to concurrent lock- based linked lists is ha nd-over-hand locking (sometimes called l o c k coupling ) [14, 89]. In this approach, each node has an associated lock. A thread traversing the linked list releases a node’s lock only after acquiring the lock of the next node in the list, thus preventin
Read more