Lab 2: Working with Linked Lists

Due Date: Tue 7 Nov, 23:59.

Background:

Lab 2 will allow you to get some familiarity with linked lists. You will re-implement the graph class using an adjacency list format instead of an adjacency matrix. Once you're done, you will use the Intro-CS Assignment Dropoff form to hand in your finished program.

What You'll Need

Download the lab2.zip file from the 15-113 course web site. Save the zip file to your temp directory and unzip the files. You should see the following files:

Open the lab2.mcp file and look at the filenames listed inside. If you open up the graph-main-2.cpp file, you'll notice that it no longer includes graph-adj.h, but now includes graph-list.h. You should copy your graph-adj files from lab1 into the lab2 folder and then rename your graph-adj.h to graph-list.h and graph-adj.cpp to graph-list.cpp. You should then add graph-list.cpp to your project file.

Assignment

You are re-implementing the Graph class with an adjacency list, in essence a vector of pointers to edges emanating from each vertex. Thus, your Edge struct will need a destination field (an int), a cost field (a double) and a pointer to the next edge that exits that vertex. Inside the newly renamed graph-list.h, you should remove the #include "matrix.h". and declare an Edge struct (above the Graph class declaration). You will also need to remove the adjacency matrix declaration (Matrix myA) and replace it with an adjacency list (vector myList). By the way, you need not worry about cleaning up memory in this lab (i.e., implement a destructor). That's for Lab 3! Your Edge struct should resemble the following: 

	struct Edge
	{
	    int dest;
	    double cost;
	    Edge* next;

	    Edge(int d = -1, double c = 0, Edge* link = NULL)
		: dest(d), cost(c), next(link) {}
	};
Once you've changed the private data member, you should see what changes this causes in the declarations of the member functions (in particular, the one-parameter constructor). Then it's on to the implementation of all the member functions! Inside the renamed graph-list.cpp, you will need to change the #include "graph-adj.h" to #include "graph-list.h" and then you will need to modify the implementations of the member functions.

As in the Adjacency Matrix implementation, you may NOT assume that an edge is not already present between the two vertices in your new implementation of AddEdge (if it is, overwrite its cost with the new value) and you may NOT assume that an edge is in the graph in your new implementation of RemoveEdge. Your code should behave analagously to that which was present in the Adjacency Matrix implementation. Also, you MUST delete any edges that are removed by RemoveEdge().

You should make no changes to graph-main-2.cpp! When you've completed your re-implementation of the Graph class, graph-main-2.cpp will exercise your implementation. To run your program, open a DOS window, cd into the directory where you're working and type the following command: 113.exe graph.txt. This time, since we're removing some edges, the correct answers are

  • Max Out Degree - 2
  • Min Out Degree - 0
  • Max In Degree - 2
  • Min In Degree - 0
  • Max Degree - 3
  • Min Degree - 1

Handing in your Solution

Your solution should be in the form of a .zip file. When we grade your solution we will unzip the folder and execute the project.

Your Solution zip file must contain (only) the following files

  1. lab2.mcp (the project)
  2. graph-list.cpp
  3. graph-list.h
Do not include a copy of the datafile (graph.txt) or the graph-main-2.cpp file as neither of these are changed.

Use the Intro Programming dropoff form to submit your zip file.