Data structures for the serial implementations

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 ints. Further-more, since there can’t be more than n²/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 ith row and jth 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.