C Lab 1 - Introduction to Memory in C

CS3410 Spring 2015

Due in lab section.

Overview

Welcome to CS3410 C Lab 1! This lab will introduce you to dealing with memory in C. There are two sections to this lab, focusing on arrays and pointers, respectively. After completing each section, have a TA check over your work before you proceed.

To begin, download the clab1.c file to your VM or CSUG account. It contains some C functions as well as function stubs you will need to implement. By the end of this lab, you will have completed a working implementation of the selection sort algorithm, and will have a working program that demonstrates the sort running on arrays of different sizes.

After completing each function, compile your program with gcc -std=c99 -Wall -Werror clab1.c -o clab1. When you're done, you can run it with ./clab1.

Part 1: Arrays in C

Arrays in C are similar to arrays in other programming languages you may be familiar with, but with one important difference. In C, arrays are simply contiguous bytes of memory. In general, there is no way to determine the length of an array from the array itself. Therefore, it is the programmer's responsibility to make sure the length of the array is known and respected so the program does not try to access an index that is outside the valid range of the array.

Arrays in C are indexed using brackets. arr[idx] accesses the idxth element of array arr. C arrays are zero-indexed, so the first element in an array is arr[0]. Since one cannot find the length of an array from the array alone, array handling functions in C usually receive the array's length as a separate parameter.

Step 1: Implement smallest_idx

Using your new knowledge of arrays in C, implement the smallest_idx function to return the index of the smallest element in an array. Be careful not to step out of bounds!

Part 2: Pointers

Pointers are central to C programming, yet often are one of the most foreign concepts to new C coders. A pointer is an integer that represents the address of an object in memory. Pointers in C are typed which means associated with the pointer is the type of the object which it points to. Pointer types are declared with a * appended to the type of the pointer. For example, int* ptr; declares a pointer to int, or "int pointer". This is also commonly written as int *ptr;

To access the value (memory location) referenced by a pointer, the * character is again used, as the "dereference" operator. The following simple function returns the int value pointed to by an int pointer:

int get_val(int *ptr) {
	return *ptr;
}

The dereference (*) operator is also used to assign a value to the memory location pointed to by a pointer, as seen in the below function;

void set_val(int *ptr, int val) {
	*ptr = val;
}

int main() {
	int x = 5;
	int *ptr = &x; // obtain a pointer to x
	printf("%d\n", get_val(ptr));
	set_val(ptr, 4);
	printf("%d\n", x);
}

Step 2: Implement the swap function

Using your new knowledge of pointers in C, implement the swap function, which takes in two int pointers as parameters and swaps the ints stored at the two addresses.

Step 3: Implement the selection_sort function

Selection sort is a sorting algorithm that does an in-place comparison sort. The algorithm divides the input array into two parts: the subarray of items already sorted, which is built up from left to right at the front of the array, and the subarray of items remaining to be sorted that occupy the rest of the array. Initially, the sorted subarray is empty and the unsorted subarray is the entire array. The algorithm proceeds by finding the smallest element in the unsorted subarray, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the subarray boundaries one element to the right. Here is an example of this sort algorithm sorting five elements:

64 25 12 22 11 // this is the initial, starting state of the array

11 25 12 22 64 // sorted sublist = {11}

11 12 25 22 64 // sorted sublist = {11, 12}

11 12 22 25 64 // sorted sublist = {11, 12, 22}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

Implement the selection_sort function using your smallest_idx and swap functions, following the outline in the clab1.c file.

Step 4: Have a TA check over your final program

*** Note: Do not forget to upload your program on CMS. ***

More Information

Sections 5.3 and 5.4 of the assigned book "C: A Reference Manual" provide a good overview of pointers and arrays in C.