CSc 352, Fall 2002: Programming Assignment 7: Some Systems Programming, and more Dynamic Data Structures

Out: Thu Oct 24

Due: 12:00 Noon Thu Oct 31


You are to create a number of files, as directed below, and then submit them electronically on host lectura.cs.arizona.edu using the command

turnin cs352_hw7 files

Please follow the directions below carefully: submissions that don't follow directions will be penalized heavily.

Note: As before, your programs should compile with no errors or warnings when compiled with gcc -Wall. Moreover, each program should exit with a status of 0 if execution proceeds normally, and a status of -1 if any sort of error occurs.

In addition, your programs will be expected to follow the coding guidelines for this class.


The Problems

  1. The purpose of this problem is to implement the basic functionality of the Unix command ls that lists the files in a directory. The goal is to give you both practice working with command line arguments, and also some experience manipulating Unix system data structures.

    Write a C program, in a file myls.c, that behaves as follows:

    Invocation:
    Your program will be invoked with a single optional argument. If more than one command line argument is specified, your program should give a descriptive error message and exit with status -1.
    Behavior:
    Your program should list the contents of the directory specified on the command line. If no command line argument is provided, the contents of the current directory (i.e., the directory in which the program is being executed) should be listed.

    If the directory to be processed cannot be opened successfully (this can happen if the file specified does not exist, or is not a directory, or does not have appropriate permissions), your program should give an error message and exit with status -1.

    Output:
    The file names should be listed, one per line, sorted in the order specified by strcmp (i.e., f1 should come before f2 if f1 precedes f2 according to strcmp). All of the file names in the directory, possibly including hidden files, should be listed. No other output other than that specified here should be generated.
    A discussion of how directories are represented and can be read is given here.

    The file

    /home/cs352/FALL02/hw7_stuff/myls
    is a SPARC executable that implements the behavior expected of your program.

  2. This problem can be thought of, conceptually, as an elaboration of a previous programming problem involving reachability in graphs, i.e., determining whether there is a path between two vertices in an undirected graph (however, the actual programming is quite different in many respects). In this case, we assume that the input graph is connected and our goal is to compute the shortest distance between two cities.

    Write a C program, in a file shortest_path.c, that behaves as follows:

    Invocation:
    Your program will be invoked with a single argument, which is the name of a file specifying distances between pairs of cities, as described below. If there are too few or too many arguments, or if the argument does not correspond to a readable file, the program should give a descriptive error message indicating the problem (use perror() in the latter case) and exit with status -1.

    Format of the Input File:
    You may assume that the input file consists of a series of lines where each line has the form

    str1 str2 dist12
    wherestr1 and str2 represent city names and dist12 the distance between them. You may assume that city names are alphanumeric strings of length at most 64, while distances are nonnegative integers.

    Example:

    The input file
    tucson albuquerque 318
    chandler tucson 95
    elPaso tucson 262
    tucson phoenix 116
    phoenix flagstaff 117
    yuma elPaso 481
    phoenix yuma 159
    tucson yuma 220
    lasCruces tucson 242
    lasCruces elPaso 38
    chandler phoenix 21
    lasCruces santafe 285
    santafe albuquerque 54

    specifies these distances:

    Behavior:
    After reading the file giving distances between cities, your program will repeatedly read pairs of city names from stdin, until end-of-file is encountered. For each pair
    c1 c2
    so read, your program should compute the shortest distance from c1 to c2 and print it out on a line by itself.

    Restrictions:

    There should not be any fixed hard limits on the input, e.g., the number of states or transitions, or the number of queries allowed. Moreover, the amount of memory used by your program should be proportional to the size of the input.

    Please do not use realloc for dynamic memory allocation: I would like you to use malloc.

    Miscellaneous:

    • An algorithm for computing shortest paths in an undirected graph is given here.
    • The file
      /home/cs352/FALL02/hw7_stuff/shortest_path
      is a SPARC executable that implements the behavior expected of your program.