Home | | **An Introduction to Parallel Programming** | | **Multi - Core Architectures and Programming** | Data structures for the serial implementations

Our principal data structures are the tour, the digraph, and, in the iterative implemen-tations, the stack. The tour and the stack are essentially list structures.

**Data structures for the serial implementations**

Our principal data structures are the tour, the
digraph, and, in the iterative implemen-tations, the stack. The tour and the
stack are essentially list structures. In problems that we’re likely to be able
to tackle, the number of cities is going to be small— certainly less than
100—so there’s no great advantage to using a linked list to represent the tours
and we’ve used an array that can store *n* ** +** 1 cities. We repeat-edly need both the number of cities in the
partial tour and the cost of the partial tour. Therefore, rather than just
using an array for the tour data structure and recomput-ing these values, we
use a struct with three members: the array storing the cities, the number of
cities, and the cost of the partial tour.

To improve the readability and the performance
of the code, we can use prepro-cessor macros to access the members of the
struct. However, since macros can be a nightmare to debug, it’s a good idea to
write “accessor” functions for use during initial development. When the program
with accessor functions is working, they can be replaced with macros. As an
example, we might start with the function

The stack in the original iterative version is
just a list of cities or **int**s. Further-more, since there can’t be more than *n*^{2}/2 records on the stack (see Exercise 6.17) at
any one time, and *n* is likely to be small, we can just use an array, and like the tour
data structure, we can store the number of elements on the stack. Thus, for
example, Push can be implemented with

In the second iterative version, the version
that stores entire tours in the stack, we can probably still use an array to
store the tours on the stack. Now the push function will look something like
this:

Once again, element access for the stack can be
implemented with macros.

There are many possible representations for
digraphs. When the digraph has rela-tively few edges, list representations are
preferred. However, in our setting, if vertex *i *is different from vertex* j*, there are directed, weighted edges from* i *to* j *and from* j *to* i*, so we need to store a weight for each ordered pair of distinct
vertices* i
*and* j*. Thus,* *in our setting, an **adjacency matrix** is almost certainly preferable to a list
structure. This is an *n x n* matrix, in which the weight of the edge from vertex *i* to vertex *j* can be the entry in the *i*th row and *j*th column of the matrix. We can access this weight directly, without
having to traverse a list. The diagonal elements (row *i* and column *i*) aren’t used, and we’ll set them to 0.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.