262: Programming and Data Structures

Continuation of foundational CS concepts, covering elementary file handling and abstract data types.

Topics

• Linked lists, stacks, queues, and trees

• Abstract data type (ADT) design

• File I/O in C

• Dynamic memory management

Projects

Sparse Matrix (262/list.c)

A 2D linked-list implementation of a sparse matrix. Each non-zero element is stored as a node with row/column coordinates, linked both horizontally and vertically to enable efficient traversal without allocating memory for zero entries.

For example, the matrix:

     col0  col1  col2  col3
row0 [  0     0     3     0  ]
row1 [  0     0     0     0  ]
row2 [  7     0     0     0  ]
row3 [  0     0     0     5  ]

is stored as three nodes linked in two dimensions:

        HEAD
       /    \
(row=0,col=2,val=3) ──next_row──▶ (row=2,col=0,val=7) ──next_row──▶ (row=3,col=3,val=5)
       │                                  │                                  │
  next_col                          next_col                           next_col
       │                                  │                                  │
      NULL                              NULL                               NULL

Only the three non-zero entries are allocated; all zero cells consume no memory.

struct element {
  int value;
  int row;
  int col;
  struct element *next_row;
  struct element *next_col;
};

struct element *insert_row(struct element *new_node, struct element *head) {
  struct element *current = head;
  struct element *prev = head;

  while (current->next_row != head) {
    current = current->next_row;
    if (new_node->row == current->row && new_node->col == current->col) {
      current->value = new_node->value;
      free(new_node);
      return (NULL);
    }
    if (new_node->row < current->row) {
      new_node->next_row = current;
      prev->next_row = new_node;
      return (new_node);
    }
    prev = current;
  }
  current->next_row = new_node;
  new_node->next_row = head;
  return (new_node);
}

Statistics Calculator (262/avg.c)

Reads a list of integers from a file or stdin and computes the mean and standard deviation.

for (i = 0; i < num_values; i++)
    sum += values[i];
mean = sum / num_values;

for (i = 0; i < num_values; i++)
    sum_sq_diff += pow(values[i] - mean, 2);
stdev = sqrt(sum_sq_diff / (num_values - 1));

printf("Mean: %f\n", mean);
printf("Standard Deviation: %f\n", stdev);

Character Frequency Counter (262/counter.c)

Reads a text file and counts the frequency of each letter, outputting percentages sorted by frequency — an early exploration of frequency analysis.

/* count letters */
for (; (fscanf(infile, "%c", &letter)) != EOF;)
    counts[(unsigned char)(toupper(letter) - 'A')]++;

/* sort by frequency (selection sort) */
for (i = 0; i < 26; i++)
    for (j = i + 1; j < 26; j++)
        if (counts[i] < counts[j]) {
            temp_count = counts[i]; counts[i] = counts[j]; counts[j] = temp_count;
            temp_char = char_codes[i]; char_codes[i] = char_codes[j]; char_codes[j] = temp_char;
        }

for (i = 0; i < 26; i++)
    fprintf(stderr, "%c = %5.2f\n", char_codes[i], ((float)counts[i] / sum) * 100);

Roach Simulator (262/roach.c)

Simulates a random walk of a “roach” on a 2D grid, tracking which squares have been visited. Demonstrates random number generation, 2D arrays, and simulation loops.

/* 7 possible move directions as (Δrow, Δcol) */
int imove[] = {-1, 0, 1, 1, 1, 0, -1};
int jmove[] = { 1, 1, 1, 0,-1,-1,-1};

/* pick a random move; retry if it would leave the grid */
do {
    move = rand() % 7;
    imaybe = ibug + imove[move];
    jmaybe = jbug + jmove[move];
} while (imaybe < 0 || imaybe >= cols || jmaybe < 0 || jmaybe >= rows);

count[imaybe][jmaybe]++;
ibug = imaybe;
jbug = jmaybe;

Trapezoidal Integration (262/trapezoid.c)

Implements numerical integration of a quadratic function using the trapezoidal rule, illustrating how continuous mathematics can be approximated computationally.

/* integrate ax² + bx + c from lower_bound to upper_bound in `number` sub-intervals */
base = (upper_bound - lower_bound) / number;
for (count = 0; count < number; count++) {
    left_height  = a * pow(lower_bound, 2)        + b * lower_bound        + c;
    right_height = a * pow(lower_bound + base, 2) + b * (lower_bound+base) + c;
    answer += base * (left_height + right_height) / 2.0;
    lower_bound += base;
}
printf("AREA OF TRAPEZOID: %f\n", answer);