Notice: Constant FORCE_SSL_ADMIN already defined in /nfs/unixspace/linux/accounts/COURSES/cs206/public_html/sp17/wp-config.php on line 94
Lab 8 – Prelab | CSCI 206 Computer Organization & Programming

Lab 8 – Prelab

Linked lists

All work for this prelab should be done in your Lab08 folder.

Objectives

  • Write programs with structures, pointers, and dynamic memory allocation in C.
  • Learn to split functionality between header and C files.

A Brief Intro to Structures in C

Structures in C are used to help organize our programs (and memory) by keeping related items together in a group. This is similar to a class with no class methods in other languages. For example, if you’re creating a BMI calculator, you would like a simple way to refer to a single person. Each entry might have fields like: name, age, weight, etc. Structures allow you to group any number of data elements together to create a custom datatype in C.

To declare a structure use the struct keyword. An example might look like:

Note the struct declaration ends with a semicolon (;) and this does not allocate storage for any instances of the structure!

After we have defined the structure, we can use it just like any other datatype.

The line above creates one person struct (named kevin_bacon) and allocates memory to store the contents (this could be in the stack or data segments, depending if the line is inside a function or not). This does not initialize the contents of memory. If you were to  printf("Hi %s!\n", kevin_bacon.name);  you would get garbage on the output and your program might crash. Incidentally, the period is used as the selection operator. It tells the compiler you want to access the name member of the keven_bacon structure.

We might want to access members of the structure for assignment or to do calculations as shown below.

Now if we create the function float compute_bmi (struct person *p);  we only require one argument, the struct of person’s information to compute the BMI. As shown in this example, we usually pass structures into functions with a pointer to the instance of the structure for good reason. Remember that C (and assembly) passes parameters by value, so if you instead wrote  float compute_bmi (struct person p); the C compiler would create a copy of the entire person structure (onto the stack) to pass to the function. That is pretty inefficient, especially if we were dealing with a very large structure (several KB). Passing a pointer only takes 4 or 8 bytes if we are on a 32 or 64-bit system.

A quick note about pointers to a struct. In the compute_bmi function we have a person * (that is a pointer to a person). To access members of the struct we cannot use the . selection operator. The selection operator (.) only works on structures. Inside of compute_bmi we have a pointer to a structure. One option is to de-reference the pointer with a *, but if you do this, you need to add extra parenthesis, as shown below:

This syntax is a bit ugly, so C has a shorthand for accessing members of a struct through a pointer. This is to use the -> operator (it looks like an arrow). Using this shortcut, the previous example becomes:

This is the preferred way to access members of a struct through a pointer.

Exercise 1: Create a linked list node

One of the most common (and fundamental) data structures is the listIf you remember your introductory classes, you will have seen two kinds of lists: singly-linked and doubly-linked. The singly-linked list is the simplest of the two: each node in the list contains some amount of information and a pointer (or reference, if you’re are talking about a language other than C or C++) to the next node.

Applying what you have learned about the struct in C, create a new data type in the file snode.h that implements a struct snode (which means, node in a singly-linked list) containing the following:

  • a field called str which can store up to 100 characters
  • a field called length of type int which tells you the actual length of the string stored in str
  • a field called next which is a pointer to a struct snode

The figure below illustrates how the struct snode can be instantiated multiple times to build a singly-linked list. Each instance of a struct snode correspond to one of the “bubbles” in the figure. In this example, each node has been initialized with a string, the length of the string (not including the 0-byte terminator), and the address value that links to another node. The next field in the last node in the list (the one containing the string “prof“, in this example) contains the NULL pointer value, which is a sentinel used to mark the end of the list.

In Unix, C programs follow a naming convention that places .h at the end of the names of header files. We use these files to store specifications, that is, declarations (not runnable code!) You’ve used headers before when you wrote  #include <stdio.h> in your programs. The counterpart to a specification file is an implementation file, which by convention has a name ending in .c – the corresponding .c file can simply  #include "snode.h", which allows us to avoid mixing up specifications and implementations in the same file.

Exercise 2: Write a function to allocate a node

Now, create a new file called snode.c into which you will write a new C function called snode_create — the function will accept the following parameters:

  • a pointer to a string s
  • an integer value denoting the length of the string s

The function will allocate dynamically (on the heap) a new instance of struct snode and return a pointer to a new node that has been initialized with the values passed as parameters. (The field next must be initialized with value NULL.)

The function prototype you should use is as follows:

       struct snode *snode_create(char *s, int length);

Copy the declaration of snode_create into snode.h after the struct snode declaration. Now when we  #include "snode.h"  our main program can call the function snode_create.

We will place the implementation for snode_create in the snode.c file. There’s a little more to coding this function than meets the eye. First, the function needs to call malloc to create space for the new struct snode. Note that you have to tell malloc how many bytes you need to allocate! This means, you need to figure out how many bytes the struct snode occupies in memory using sizeof. Be careful, if you do sizeof( struct snode *) it will return only 4 (or 8) bytes, as it is the size of a pointer. You want the size of the actual struct, that is sizeof(struct snode). Finally, the function must return to the caller the address of the chunk of memory allocated for the struct snode, which is returned by the call to malloc. Use Linux manual page to find out how to use malloc or any others that are needed.

Your function needs to copy the string pointed to by s into the str field of the struct snode – this copying needs to be done character by character up to and including the 0-byte that terminates the C string. Yes, there are C functions for that purpose in the string library and you may use them (it will save you trouble) or you can write your own code (if want to reinvent the wheel so to speak). You can find the scoop on the C string library by doing man 3 string. Also, your function needs to copy the value of parameter length into the field with the corresponding name in the newly created struct snode.

When your snode.h/.c files are complete you need to test your implementation. Below is a simple driver program to unit test your snode implementation:

Save this to a file called snode-test.c.

Create a Makefile to compile everything using the appropriate object files (snode.o and snode-test.o).

If all is correct with your implementation, the output you should see is:

When you are done with this, you need to add snode.* and snode-test.c to git and push to gitlab.

Grading Rubric

Pre-Lab [25 points]

  • [10 points] snode.h has a working definition of struct snode and declaration for rsnode_create.
  • [10 points] snode.c has a correct snode_create that uses malloc and strcpy; -3 if it does not set length, str, or next.
  • [5 points] snode-test works and compiles with a valid Makefile.
Print Friendly
Posted in Lab Tagged with: , ,

Leave a Reply

Your email address will not be published. Required fields are marked *

*