Skip to content

CMSC 14300: Practice Set 8 - Files, Command-Line Arguments, Shared Libraries, Trees, and Graphs

Practice for the material in Week 7: files and command-line arguments from Lecture 13, and trees and graphs from Lecture 14. None of these repeats a lecture or homework exercise; together they drill today's moves - looping over argv to open several files, an append-mode log, building and calling a shared library from both Python and C, new operations on a BST beyond insert/search, and a BFS that reports distance instead of just visit order.

Work in a fresh directory and compile everything with warnings on:

mkdir -p ~/cmsc14300/pset08 && cd ~/cmsc14300/pset08
clang -Wall -Wextra -std=c17 problem1.c -o problem1

Keep this week's rules in view: every fopen needs a NULL check and a matching fclose; "w" truncates a file, "a" keeps what is there and adds after it; argv[0] is the program name, real arguments start at argv[1]; a BST's insert and search each recurse into exactly one child; and BFS needs a queue plus a visited array marked at enqueue time, not dequeue.

Problems 1 to 3 are files, command-line arguments, and a shared library. Problems 4 to 6 are trees and graphs.

Problem 1 - Total lines across several files

Write a program that treats every command-line argument as a filename, opens each one in turn, counts its lines with the usual fgets loop, prints that file's count, and finally prints the grand total across all files. If a file will not open, perror it, skip it, and keep going with the rest.

int count_lines(const char *filename);   /* returns -1 if the file will not open */

$ ./problem1 a.txt b.txt nope.txt c.txt
a.txt: 4 lines
nope.txt: No such file or directory
b.txt: 9 lines
c.txt: 2 lines
total: 15 lines
  • Loop i from 1 to argc - 1; call count_lines(argv[i]) on each.
  • Inside count_lines, fopen in "r", return -1 immediately if it is NULL (do not try to fclose a NULL pointer), otherwise fgets-loop and return the count.
  • A file that fails to open must not stop the loop or corrupt the running total - only its own count is skipped.
  • Check your understanding: if count_lines returned 0 instead of -1 for a missing file, what would silently go wrong with the printed total, and why does that make -1 the right sentinel here?

Problem 2 - An append-only check-in log

Write a program that takes one command-line argument, a name, and appends a line "<name> checked in\n" to checkins.txt using mode "a" (creating the file the first time it is run). After appending, reopen the file in "r" and print every line back along with the total number of check-ins ever recorded, not just this run's.

FILE *f = fopen("checkins.txt", "a");   /* phase 1: append this run's line */
f = fopen("checkins.txt", "r");         /* phase 2: read back everything */

$ ./problem2 ada
ada checked in
1 check-in total
$ ./problem2 grace
ada checked in
grace checked in
2 check-ins total
  • Phase 1 opens "a" and writes exactly one fprintf line, then fcloses.
  • Phase 2 opens "r" fresh and re-reads the whole file with the usual fgets loop, counting as it prints.
  • Require argc == 2; otherwise print a usage message to stderr and return 1 without touching the file.
  • Check your understanding: run the program three times in a row from the same directory. Explain, in terms of what "a" guarantees about the write cursor, why the file never loses an earlier run's line the way "w" would.

Problem 3 - A shared library for triangle geometry, called from Python and C

Write geom.c containing two functions and no main: double tri_area(double base, double height) and double tri_perimeter(double a, double b, double c). Build it into libgeom.so, then write driver.py that loads it with ctypes and prints both results, and write usegeom.c that links against the same library and prints the same two results from C.

/* geom.c */
double tri_area(double base, double height);        /* 0.5 * base * height */
double tri_perimeter(double a, double b, double c);  /* a + b + c */

clang -Wall -Wextra -std=c17 -fPIC -shared geom.c -o libgeom.so
python3 driver.py
clang -Wall -Wextra -std=c17 usegeom.c -L. -lgeom -Wl,-rpath,. -o usegeom
./usegeom

area = 24.0
perimeter = 18.0
  • In driver.py, set .argtypes = [ctypes.c_double, ctypes.c_double] and .restype = ctypes.c_double for each function before calling it.
  • In usegeom.c, declare both functions (no need to #include "geom.c") and call them like any other C function; the linker flags are what find the .so at compile and run time.
  • Check your understanding: usegeom.c needed -L., -lgeom, and -Wl,-rpath,. to run, while driver.py needed none of those. What is each of the three flags doing, and why does ctypes.CDLL("./libgeom.so") sidestep that whole problem in Python?

Problem 4 - BST: minimum, maximum, and node count

Extend a BST with three new functions that each recurse into at most one child (the same shape as insert/search, not a full traversal).

int find_min(tnode_t *root);    /* leftmost key; undefined on an empty tree */
int find_max(tnode_t *root);    /* rightmost key */
int count_nodes(tnode_t *root); /* 0 for empty, else 1 + both children - the one case that visits both */

tree built from: 50 30 70 40 90 20
min   : 20
max   : 90
count : 6
  • find_min: while root->left != NULL, move to it; return the last node's key. (Iterative or recursive both work - recursive is root->left == NULL ? root->key : find_min(root->left).)
  • find_max: the mirror image, following right.
  • count_nodes is the one function here that must look at both children, since every node counts regardless of which side it is on.
  • Check your understanding: find_min and find_max each look at only one child at every step, the same as search. What property of a BST (not a general binary tree) guarantees the leftmost node is the minimum, without ever comparing keys?

Problem 5 - Sum of keys at a given depth

Write depth_sum(tnode_t *root, int depth), which returns the sum of the keys of every node exactly depth edges below the root (the root itself is depth 0). Use it to print the sum at every depth from 0 up to the tree's height.

int depth_sum(tnode_t *root, int depth);   /* sum of keys at that depth, 0 if none */

tree built from: 50 30 70 40 90 20 60 80
depth 0: 50
depth 1: 100
depth 2: 270
  • Base case: root == NULL returns 0.
  • If depth == 0, return root->key (do not recurse further).
  • Otherwise return depth_sum(root->left, depth - 1) + depth_sum(root->right, depth - 1) - both children matter here, unlike find_min/find_max.
  • Check your understanding: depth_sum recurses into both children even though most of those calls will return 0 once depth runs out on an empty branch. Is that wasted work asymptotically, or does it stay proportional to the number of real nodes at that depth? Explain in one sentence.

Problem 6 - Shortest distance from a source vertex (BFS)

Add bfs_distances(graph_t *g, int start, int *dist) to a Lecture 14-style adjacency-list graph. Fill dist[v] with the number of edges on the shortest path from start to v (0 for start itself), or -1 if v is unreachable. This is the same traversal as Lecture 14's BFS, but it records a distance array instead of printing a visit order.

void bfs_distances(graph_t *g, int start, int *dist);  /* caller callocs dist, size nverts */

edges: {0,1} {0,2} {1,3} {2,3} {3,4}
bfs_distances from 0: dist = [0, 1, 1, 2, 3]
  • calloc or initialize dist to all -1 first, then set dist[start] = 0 before enqueuing it.
  • Whenever you enqueue a neighbor v of the current vertex u (because it was still -1), set dist[v] = dist[u] + 1 before enqueuing - the same moment you would otherwise just mark it visited.
  • Delete the {3,4} edge and confirm dist[4] comes back -1.
  • Check your understanding: why does the first time a vertex is reached by BFS always give its shortest distance, when a vertex could in principle be reached again later, at a greater distance, through some other path?

Self-check

You're ready for later material if you can, without looking it up:

  • Explain what each fopen mode string ("r", "w", "a", and their b variants) does to a file that already exists, and to one that does not.
  • Loop over argv[1] through argv[argc - 1] from memory, and say what argv[0] and argv[argc] hold.
  • Say what flags a shared library needs to build, and what two ctypes attributes you must set before calling one of its functions.
  • Write insert or search on a BST from memory, and explain why each recurses into exactly one child while count_nodes must look at both.
  • Explain why BFS marks a vertex visited (or records its distance) at enqueue time rather than at dequeue.