C代写：CMPS101 Graph

代写数据结构中的Graph的邻接表，需要编写Vec和List两个版本。

Program Requirements

This program (named graph02) will perform the same functions as pa01, but will be able to use the ADT IntList OR the ADT IntVec for the data structure that stores one adjacency list.

Give your binary compiled C program the name graph02.

Your main source file should be named graph02.c.

Your source file that IMPLEMENTS the IntList ADT should be named intList.c.

Your source file that IMPLEMENTS the IntVec ADT should be named intVec.c.

The ADT header file is intVec.h, supplied in the class locker, a directory named cmps101-avg. The complete path is given in the syllabus and on the class web page and later in this handout.

Your submission will also include intList.c and intList.h, whose requirements are the same as in pa01 (ho04.txt).

In this assignment, your intList.o AND intVec.o will be tested with other students’ programs and their intList.o AND intVec.o will be tested with yours. So use the standard names in this class.

A starter intList.h is in the course locker, but by now you should have added pre- and post-conditions.

A starter intVec.h is in the course locker, but you should replace the questions with your own comments.

The file graph01.c, etc., can be used right from pa01, except that the “main” procedure will be changed to check for some command-line flags and call different procedures depending on whether the graph is stored
using IntLists or InVecs.

Thus, the loadGraph functionality will be separated if it has not been separated in an earlier assignment. See HOW TO PROCEED below for more details.

Allocating all the arrays in graph02.c makes it easier to pass them as arguments to functions in other files, without making any global arrays.

However, if you already have working code that allocates and returns an array from a different file (such as loadGraph.c), it is okay to use and build upon that code.

Aside from intList.h, intList.c, intVec.h, intVec.c, graph02.c and graph02, the names of files, functions and arrays should be understandable but do not need to be strictly the same as this handout.

Command-line Arguments

If your program receives no command-line arguments, it should print a usage message and exit.

Command-line arguments of the form “-something” are often called “flags”, and provide the means for varying the way the program runs, or varying the form of the output. (“-“ by itself denotes stdin.)

The final command-line argument is the name of the input file, and this name will not begin with a “-“ unless it is “-“ by itself.

The command-line flag “-L” instructs the program to build the (directed, unweighted) graph from the input using ADT IntList.

The command-line flag “-V” instructs the program to build the (directed, unweighted) graph from the input using ADT IntVec.

If both flags are present or neither flag is present, print an error message on stderr (use fprintf(stderr, …)) and exit with code 1.

Note that the Unix convention is that an exit code of 0 means “normal completion” and non-zero exit codes denote various errors.

The exit code of 0 is established “return 0” from main() or by calling exit(0) anywhere. Similarly, non-zero codes may be established.

If one flag is present, but the program cannot get the file name from the command line or cannot open the input file, then a non-zero exit code should be returned.

Input Format

Just like pa01, input consists of a sequence of lines on “standard input” or in an ascii file (also called text file).

The line formats are as described in the text appendix for graph.c.

Part of the assignment is to create a set of useful test files on disk.

In the class locker (see below) gr01_test1.in is an example input.

Output Format

Print information on stdout.

Just like pa01. See ho04.txt and related mailing list messages. What is most important is that the correct numbers
in the correct sequence appear on each line. The punctuation like commas and brackets is for human readability.

A common convention in programming languages is that lists print as [4, 5, 1] for a list whose first element is 4, etc. [] is the empty list.

For this assignment the entire list should print on a single line.

When you run graph.java you will notice that a number appears on each line BEFORE the list. That is explained in the reading material.

If the program is using the IntList ADT (-L), the adjacencies are ordered from the beginning of the list to the end.
If the program is using the IntVec ADT (-V), you want the order to be the same as it WOULD BE if -L had been specified.

Print an informative error message if the input contains a bad vertex number, outside 1,…,n, or has the wrong number of words on a line.

This is for your own protection. It is not a grading issue and submitting a lot of tests to check bad input is not asked or desired.

Example 1 input, unweighted

6
1 4
5 4
1 3
2 3
3 3
5 6
6 5
4 3
1 2

Example 2, with weights:

6
1 4 2.7
5 4 -3
1 3 0.0

The weights should be parsed to prepare for future programs, but they are not entered into the data structure for the graph.

Remember that graphs want to start on index 1, not index 0. So allocate 1 extra space in the array and start loading at 1.

Do not worry if edges are not unique. The algorithms will work anyway.

Example 2 output would look something like this:

1 [3, 4]
2 []
3 []
4 []
5 [4]
6 []

Remember, the punctuation can be to taste, but the numbers should be in the same order as shown, line by line.

When running the program on a large input file remember to use “>” to redirect the stdout to a file. We will supply some large files.

Standard Vec Data Structure

Section 6.2 explains array doubling. There is a fairly simple C data structure to support this. This example need not be followed exactly.

struct IntVecNode
{
 int * data;
 int sz;
 int capacity;
};

The constructor callocs one “struct IntVecNode”. calloc() returns a pointer to it (which is type IntVec).

Say the constuctor stores the value of that point in a local variable named newVec. This struct never moves.

The constructor now callocs space for 4 ints (based on the value in intVec.h) and stores THAT pointer in newVec->data.

The value of newVec->data CAN change when the array size is doubled.

Now newVec->sz si initialized to 0 and newVec->capacity is initialized to 4.

ADT operations pass in myvec with the value returned by the constructor (i.e., newVec) to specify which IntVec ADT object they are operating on.

When array doubling is needed, call realloc as follows:

newCap = 2 * myvec->capacity;
newData = realloc(myvec->data, newCap);

Assuming not, continue by updating the struct fields:

if (newData != myvec->data) { myvec->data = newData; }
myvec->capacity = newCap;

Read “man realloc” for more details.

How To Proceed

Make a new directory to work in. Do this first. Assuming pa01 was in pretty good shape, copy those files into your new directory as starters for pa02.

Updating files from a previous assignment is VERY BAD practice.

Copy them to a new directory and work in the new directory.

If your pa01 was incomplete, you might need to refer to ho04.txt for how to complete it. This file does not repeat that information.

The function names in the intList ADT must be as given in the intList.h starter file for pa01.

The function names in the intVec ADT must be as given in the intVec.h starter file for pa02.

These names must be spelled and capitalized as shown in that file.

Use the mouse to cut and paste, if necessary.

But try to use query-replace to find and replace all the names in one file whose spelling will change from pa01.

Use egrep or grep to find which files have list-related names.

For this program, loadGraph.c should be a separate file, although that was not required before. loadGraph.h will provide the interface.

Functions in loadGraph.c that are only called within loadGraph.c should not appear in loadGraph.h.

The loadGraph is NOT required to be an ADT, so the functions and prototypes do not need to agree with other students.

It is probably easiest to rename loadGraph() from pa01 into loadGraphL() and then make a copy of it called loadGraphV().

The logic will be very similar, but loadGraphV() will handle IntVec for the type, instead of IntList, and use different ADT functions.

Similarly, if you had printGraph() in pa01 you probably want to make printGraphL() and printGraphV().

Start with loadGraphV() and printGraphV() as “stubs” until your program is working correctly for the -L flag. Then make copies of the now-correct loadGraphL() and printGraphL() into loadGraphV() and printGraphV().

While planning, keep in mind that you need two different types for adjVertices[] so probably use adjVerticesL[] and adjVerticesV[].

You only need to call calloc() for the one you actually need.

Call the main program graph02.c.

Hint: Think about the command-line flags -L and -V.
Do you want to “share” these values or pass them to all functions?
Both decisions have merit, but stick to one or the other.

Submitting

The assignment name is pa02. An example (but incomplete) submit command is:

submit cmps101-avg.f16 pa02 graph02.c intVec.c README Makefile

Submit ALL the work you want to be considered for grading, but do not summit files produced by compilers, such as *.o and binaries.

You can list as many files as you want to submit. If you update files, just submit them again. Don’t resubmit unchanged files needlessly.

Simply typing “make” should compile your program, creating a binary named after the main program, graph02.

To accomplish this, simply list graph02 as the first “target” in Makefile.

Your Makefile should have an entry for each file that needs to be compiled. A “generic” that just compiles everything it can find will lose credit.

The example mentioned in pa01 is a guide. It is in the CMake directory.

The example found in the class locker is NOT a good guide, (although it worked for pa01) and it has been removed.

You should understand your own Makefile.

Do not use fancy features, as the grading script will not recognize that you understand Makefile structure.

Submit a README that briefly describes your program with a few sentences, mainly to tell the reader how to compile it, how to run it, what test inputs and outputs you supplied, any known bugs.

Pleading for a nice grade is bad form.

If the purpose of some files might be mysterious, here is the place to explain them.

Programming Standards

All code to be graded should follow good style practices including appropriate indentation, descriptive names, consistent capitalization, and useful comments. Comments should indicate the purpose, preconditions, and postconditions of important procedures. Avoid comments of self-explanatory code. The reader may grade your program low if it is sloppily done, making it hard to understand or follow.