C Module 4: Final Notes on C

Objectives

A bit more C
More on Linked Lists
Algorithmic thinking, APIs
Midterm exam review
Going from C to Java

Final notes on C

The benefits of C:

Low level coding
Direct access to memory
Ubiquitous
Low overhead

The dangers of C:

Direct access to memory
Minimal type checking
No support for objects
No variable initialization

Remember the memory model

This is not C specific
But other languages hide the details

Most C bugs are related to how you access memory

If in doubt… draw it out!

How to learn a new language:

Small steps!
Write code, compile, test, repeat
Look at library reference examples

The Linked List

What is a linked list?
What can it hold?
How does it compare to…
- An array from the stack? int days[365];
- or the heap? int *days=malloc(365*sizeof(int));

Strength:

Very flexible
Can grow at both ends or in the middle
Fast to add elements anywhere

Weakness:

Slow access time
Must traverse through list to find element
Memory overhead due to “next” pointers

What functions do we need?

A linked list should be able to…

Application Program Interface

We just did software engineering!
- SE is about a lot more than writing code and knowing syntax
An API describes an interface
- What functionality is exposed? What data is available?

What data do we need?

Consider the following example:

Node Data type:

List data type:

We will use two types of structs
- LList: represents the list as a whole, used by application
- LNode: used for each entry in the list, stores actual data
This gives a nicer API than requiring programmer to understand internals of LNodes

A Note on NULL

NULL is a reserved keyword in C, often used as a “sentinel” to tell whether a pointer has been initialized
Undefined variables are NOT automatically set to NULL in C.
We will have to carefully set pointers to NULL by ourselves!
Secret: NULL is actually just the number 0!

Coding a linked list

What is a linked list made of?

struct LNode {
  int data;
  LNode* next;
};

struct LList {
  LNode* head;
};

Arrays, Linked list, Pointers and Structs

Pointers:

int main(){
// create a integer value
int x = 5;

// create a integer pointer intialized with garbage data
int* y;

// ALSO creates a integer pointer intialized to point to address 10
int *z = (int*)10;

// set y's value (the address it is pointing to) to the value of x (in this case 5)
y = x;

// set y's value (the address it is pointing to) to the address of x, NOT X's VALUE
y = &x;

// dereference the value of y and set that memory address to 15
*y = 15;

// set the pointer z to point to the value of y (z and y are now pointing to the same value)
z = y;

// create a pointer to a pointer to an integer.
//NOTE: this still has a single value to a memory location
int ** w;

// set w to equal the contents of y
w = y;

// set w to equal the contents at memory address y (which y is currently at memory address of x)
w = *y;

printf("Addr x = %d\n", &x);
printf("x = %d\n", x);

//printf("%p\n", y);
printf("y = %d\n", y);

//printf("%p\n", z);
printf("z = %d\n", z);

printf("w = %d\n", w);
}

Array Tutorial and weird character stuff!

#include <stdio.h>
#include <stdlib.h>

//IN:  a 1D array of integers and the size of the array
//OUT: prints each value in the array
void printArray(int * array, int size){
	int i = 0;
	for(i=0; i < size; i++){
		printf("%d, ", array[i]);
	}
	printf("\n");
}

//IN:  a 1D character array and the size of the array
//OUT: prints each character.
//NOTE: some characters will not be printed if they are garbage characters!
void printCharArray(char * array, int size){
	int i = 0;
	for(i=0; i < size; i++){
		printf("%c, ", array[i]);
	}
	printf("\n");	
}

//IN:  a 2D square array of integers with size of row and column
//OUT: prints each value in the array
void print2DArray(int ** array, int size){
	int i = 0, j = 0;
	for(i=0; i < size; i++){
		printf("[");
		for (j=0; j < size; j++){
			printf("%d, ", array[i][j]);
		}
		printf("]\n");
	}
}

int main(){

	// Create a 1D array of size 5 on the heap
	int * arr = (int *) malloc (sizeof(int) * 5);
	printf("arr (on heap) = %d\n", arr);

	arr[0] = 1;
	arr[1] = 2;
	arr[2] = 3;
	arr[3] = 4;
	arr[4] = 5;

	printArray(arr,5);

	// Create a 1D array of size 5 on the stack
	int arr2[5];
	printf("arr2 (on stack) = %d\n", arr2);

	arr2[0] = 6;
	arr2[1] = 7;
	arr2[2] = 8;
	arr2[3] = 9;
	arr2[4] = 10;

	printArray(arr2,5);

	// Lets create a 2D square array with row and column size 2
	int ** matrix;

	matrix = (int **) malloc (sizeof(int *) * 2);
	matrix[0] = (int *) malloc (sizeof(int) * 2);
	matrix[1] = (int *) malloc (sizeof(int) * 2);

	matrix[0][0] = 1;
	matrix[0][1] = 2;
	matrix[1][0] = 3;
	matrix[1][1] = 4;

	print2DArray(matrix,2);

	// Create a pointer to a character array
	char * word;

	// create a string in READ ONLY MEMORY and then point to that string
	word = (char*)"Hello";

	printf("word = %s\n", word);

	// CAN'T DO IT, STRING IN READ ONLY MEMORY!!!!!
	// WILL CAUSE A SEGFAULT!
	//word[1] = 'W';

	// But we can create a character array on the stack that we can change each value seperately
	// This will not be in Read only Memory
	char newWord[20];

	// Weird thing where if we set letters on every other character, it will stop printing after
	// the first character because newWord[1] has '\0' character.
	newWord[0] = 'H';
	newWord[2] = 'e';
	newWord[4] = 'l';
	newWord[6] = 'l';
	newWord[8] = 'o';
	newWord[10] = '\0';

	printf("newWord = %s\n", newWord);

	printCharArray(newWord,20);

	// Take Away Message: Characters are weird.

	return 0;
}

Totally awesome and weird example of pointers and structs

#include <stdlib.h>
#include <stdio.h>

struct Node{
	int value;
	struct Node * prev;
	struct Node * next;
};

struct LinkedList{
	struct Node * front;
	struct Node * rear;
};

//IN:  take as input a data value we want to make as a node
//OUT: make a Node object on the heap.
//      returns a node with value = data, and prev and next set to NULL
//      since we are not pointing to anything (yet).
struct Node * makeNode(int data){
	struct Node * newNode;
	newNode = (struct Node *) malloc (sizeof(struct Node));
	newNode->value = data;
	newNode->prev = NULL;
	newNode->next = NULL;

	return newNode;

}

//IN:  take a linked list we want to add our node to, and the data we want to add.
//OUT: Add that node to the back of the linked list. The Linked list is always connected.
//NOTE: if we have only one node in our linked list, both front and rear will be pointing
//      to that node.
void addNode(struct LinkedList * LL, int data){
	if (LL->front == NULL){
		// That means it is empty
		struct Node * newNode = makeNode(data);
		LL->front = newNode;
		LL->rear = newNode;
	}else{
		// There is stuff in there! lets modify some pointers!
		struct Node * newNode = makeNode(data);
		// newNode will be our new rear, so lets set its prev to the old rear...
		newNode->prev = LL->rear;
		// Then lets change the old rear's next pointer to our new node...
		LL->rear->next = newNode;
		// and finally lets make rear our new node!
		LL->rear = newNode;
	}
}

//IN:  
//OUT: make a linked list object on the heap.
//      returns a linked list with front and rear pointing to NULL
//      since we are not pointing to anything (yet).
struct LinkedList * makeLinkedList(){
	struct LinkedList * newLinkedList;
	newLinkedList = (struct LinkedList *) malloc (sizeof(struct LinkedList));
	newLinkedList->front = NULL;
	newLinkedList->rear = NULL;

	return newLinkedList;
}

//IN:  a LinkedList we want to print
//OUT: prints each value in the linked list starting with front and going in order
//      until rear.
void printLinkedList(struct LinkedList * LL){
	struct Node * curNode = LL->front;
	while(curNode != NULL){
		printf("%d -> ", curNode->value);
		curNode = curNode->next;
	}
	printf("\n");
}

int main()
{
	int tableSize = 5;
	int i = 0, j = 0;

	// Make a pointer to an array of Linked List Pointers
	struct LinkedList ** table;
	table = (struct LinkedList **) malloc (sizeof(struct LinkedList *) * tableSize);

	// Make Linked Lists on the heap for each index
	for(i=0; i < tableSize; i++){
		table[i] = makeLinkedList();
	}

	// For index 0, I want values between 1-10
	// For index 1, I want values between 11-20
	// ...

	// Add values to the first Linked List
	addNode(table[0],1);
	addNode(table[0],2);
	addNode(table[0],5);
	addNode(table[0],8);

	printLinkedList(table[0]);

	// Note: memory should be freed before return to avoid memory leaks
		// free the nodes
		// Linked Lists
		// free the table

	return 0;
}

This class was done with slides.

Previous - Next