CPS 125
Alexander Ferworn
Week 9
Structures and Linked Lists
What we will cover this week
----------------------------
o Dynamic Memory Allocation
o Structures
o Singly Linked Lists--the directors cut
o Singly linked lists--the "Reader's Digest" version
Dynamic Memory Allocation
-------------------------
o DMA allows you to allocation memory at run time rather
than compile time.
o Compile time memory is fine but you might not know how
much to ask for. If you ask for too little you will
run out of space and have to recompile and if you ask
for too much some will be wasted.
o This means that after the program has been compiled you
can create things like arrays of different sizes using
only as much space as you need.
o Remember all those examples where you had to declare an
array to be bigger than anything you might encounter
...those days may be over.
o There are several library function (all in <stdlib.h>)
which can help you.
malloc() Allocate a specified number of bytes in memory. Returns a
pointer to the beginning of those bytes.
calloc() Same as malloc but set the bytes to zero
realloc() (not covered). Changes the size of a previously
allocated block
free() Frees up memory that was previously allocated
An example using DMA to do sorting;
#include <stdio.h>
#include <stdlib.h>
void main()
{
int *list, sort_num,j;
printf("How many numbers would you like to sort?\n");
scanf("%d",&sort_num);
list = (int *) malloc(sort_num * sizeof(int));
/* could use
list = (int *) calloc(sort_num, sizeof(int)); */
for(i=0;i<sort_num;i++)
scanf("%d",list+j);
<put call to bubble_sort routine here>
}
o DMA works for arrays because all the locations in the
block of memory are contiguous.
o If you made more than one call to malloc() there is no
guarantee that the new block will be contiguous to
the old block and probably is not!
o The way to get around this problem is to use something
called a linked list (discussed later).
another example this time using a function and
treating the pointer to the block of memory like an
array.
#include <stdio.h>
#include <stdlib.h>
/* program to ask user how big they want an array.
Dump fives into it and call a function to output
the array */
void output(int array[],int size);
void main()
{
int size,j;
int *block;
printf("Enter the size of the array you want: ");
scanf("%d",&size);
block = (int *) malloc(size * sizeof(int));
if(block == NULL) exit(0); /* malloc() returns
NULL if no memory
was allocated */
for(j=0;j<size;j++)
*(block + j) = 5;
output(block,size);
}
void output(int array[],int size)
{
int j;
for(j=0;j<size;j++)
printf("%d ",array[j]);
}
Structures in C
---------------
o A structure is a collection of variables under a single name.
o These variables can be of different types, and each has a
name which is used to select it from the structure.
o A structure is a convenient way of grouping several pieces
of related information together.
o A structure can be defined as a new named type, thus
extending the number of available types.
o It can use other structures, arrays or pointers as some
of its members, though this can get complicated unless
you are careful.
Defining a Structure
--------------------
o A structure is called an aggregate type meaning that you can
add other types to it to form bundles of related
information. For example, you could create a structure
containing all the information about your car and
treat it as a single variable.
o A structure type is usually defined at the start of a
file using a typedef statement.
o typedef defines and names a new type, allowing its use
throughout the program.
o typedefs usually occur just after the #define and #include
statements in a file.
Here is an example structure definition.
typedef struct student_tag{
char name[64];
char course[128];
int age;
int year;
} STUDENT;
o This defines a new type STUDENT.
o The "student_tag" name is call a structure tag and is
optional for now but will be used when we talk about
linked lists...basically it is another way of referring
to the structure.
o Variables of type STUDENT can be declared as follows.
STUDENT st_rec;
o Notice how similar this is to declaring an int or float.
o The variable name is st_rec, it has members called name,
course, age and year.
Accessing Members of a Structure
--------------------------------
o Each member of a structure can be used just like a
normal variable, but its name will be a bit longer.
o member "name" of structure st_rec will behave just like
a normal array of char, however we refer to it by
the name
st_rec.name
Here the dot is an operator which selects a member from a
structure.
o Where we have a pointer to a structure we could
dereference the pointer and then use dot as a member
selector.
o This method is a little clumsy to type. Since selecting
a member from a structure pointer happens frequently,
it has its own operator -> which acts as follows.
o Assume that st_ptr is a pointer to a structure of type
STUDENT We would refer to the name member as
st_ptr -> name
Structures as Function Arguments
--------------------------------
o A structure can be passed as a function argument just like
any other variable.
o Where we wish to modify the value of members of the
structure, we must pass a pointer to that structure.
This is just like passing a pointer to an int type
argument whose value we wish to change.
o If we are only interested in one member of a structure,
it is probably simpler to just pass that member.
This will make for a simpler function, which is easier
to re-use.
o Of course if we wish to change the value of that member,
we should pass a pointer to it.
o When a structure is passed as an argument, each member
of the structure is copied.
o This can prove expensive where structures are large or
functions are called frequently.
o Passing and working with pointers to large structures
may be more efficient in such cases.
An example of an array of structures being passed into a
function.
/* Function to count the number of students of
a particular age (treating structure like array)*/
typedef struct student_tag{
char name[64];
char course[128];
int age;
int year;
} STUDENT;
int agecount(STUDENT student[],int age,int num_students)
{
int count=0,k;
for(k=0;k<num_students;k++)
if(student[k].age == age)count++;
return count;
}
The same example but this time using pointers
int agecount(STUDENT *student,int age,int num_students)
{
int count=0,k;
for(k=0;k<num_students;k++)
{
if(student->age == age)count++;
student++;
}
return count;
}
Nested Structures
-----------------
o When one of the fields in a structure is a structure,
you have a nested structure.
for example
typedef struct {
int year;
int month;
int day;
int hour;
int minute;
int second;
} TIME;
typedef struct {
char[30+1] name;
TIME birth_time;
} BIRTHDAY_BOY;
o we refer to elements of the nested structure with
the dot or -> notation as follows
...
BIRTHDAY_BOY tom;
BIRTHDAY_BOY *ed;
ed = &tom;
tom.birth_time.year = 1997;
ed->birth_time.minute = 30;
Further Uses of Structures
--------------------------
o As we have seen, a structure is a good way of storing
related data together.
o It is also a good way of representing certain types
of information.
o Complex numbers in mathematics inhabit a two dimensional
plane (stretching in real and imaginary directions).
o These could easily be represented here by
typedef struct {
double real;
double imag;
} complex;
o doubles have been used for each field because their range
is greater than floats and because the majority of
mathematical library functions deal with doubles by
default.
o Apart from holding data, structures can be used as members
of other structures.
o Arrays of structures are possible, and are a good way
of storing lists of data with regular fields, such
as databases.
o Another possibility is a structure whose fields include
pointers to its own type.
o These can be used to build chains (programmers call
these linked lists as we will see)
Linked Lists
------------
o Structures are capable of handling grouped data and so
far we have used arrays to group together structures.
o If we don't kow how big an array might be at compile
time we know we can use DMA
o Successive calls to malloc() will not provide us with
contiguous space.
o It would be nice to be able to link these blocks of memory
in some way so that we can move from the first block
to the second and so on.
o A linked list can be used to do this.
o A linked list is a chain of structures that is linked one
to another, like sausages.
o In the simplest linking scheme each structure contains an
extra field called a "link" which is used to point
to the next structure.
An example :
o Here is a revised STUDENT type using this notion
typedef struct student{
char name[64];
char course[128];
int age;
int year;
struct student *next;
} STUDENT;
o In this case we modify our usual typedef statement to
include "struct student".
o student is called a "tag name" and allows us to refer
back to the structure (recursively).
o the pointer field "next" allows us to point at other
variables of type STUDENT (struct student)
Logical Representation
----------------------
o Pictorially, a linked list looks like the diagram below.
[DATA][NEXT]------->[DATA][NEXT]------->[DATA][NEXT]------->...
Typical Operations
------------------
o In a typical linked list you need to perform the
following operations;
o Create a list
o Add elements to the end of the list
o Insert elements into the middle of the list
o Remove elements from the list
o Find a particular element in the list
Stuff you need
o First we need to create a file called "student.h" which
will contain the stuff we need to create the functions
we need.
o The contents of this file are given below
#define NULL (void *) 0
typedef struct student{
char name[64];
char course[128];
int age;
int year;
struct student *next;
} STUDENT;
Creating a list of students
#include "student.h"
STUDENT *create_list_element()
{
STUDENT *p;
p = (STUDENT *) malloc(sizeof(STUDENT));
p->next = NULL;
return p;
}
o Pictorially this looks like
[DATA][NULL]
Adding Elements
---------------
/* a global variable that needs to be */
static STUDENT *head = NULL;
#include "student.h"
/* add the student pointed to by "e" into the list
pointed to by "head" */
void add_element(STUDENT *e)
{
STUDENT *p;
/* If there is no head make it */
if(head == NULL)
{
head = e;
return;
}
/* Otherwise find the last element in the list */
for(p=head;p->next != NULL; p = p->next);
p->next = e;
}
o Pictorially this looks like this after adding one node.
[head]----->[DATA][NULL]
Stopping for a moment
---------------------
o Now we can do wierd stuff like the following which creates 10
STUDENTS and adds them to the list.
#include "student.h"
static STUDENT *head = NULL;
void main()
{
int j;
for(j=0;j<10;j++)
add_element(create_list_element() );
}
Inserting an Element
--------------------
o To insert a new element you must say where you want
to insert it.
o The following function accepts 2 pointer args p and q,
it inserts p after q.
#include "student.h"
void insert_after(STUDENT *p, STUDENT *q)
{
/* sanity check */
if(p==NULL || q==NULL || p==q ||q->next==p)
{
printf("Can't insert after\n");
return;
}
p->next = q->next;
q->next = p;
}
Pictorially this looks like;
q q->next
Before: ...----->[ ][ ]-------------->[ ][NULL]
q q->next->next
After: ...----->[ ][ ]-+ +-->[ ][NULL]
| p |
+->[ ][ ]-+
Deleting an Element
-------------------
o This is a bit tricky since you need to find the element
before the one you want to delete so that you can
assemble the list after the delete.
o You need to use the free() function.
#include "student.h"
static STUDENT head;
void delete_element(STUDENT *goner)
{
STUDENT *p;
if(goner == head)
head = goner->next;
else
{
/* find preceding element */
for(p=head;(p!=NULL) && (p->next!=goner);
p=p->next);
if(p==NULL)
{
printf("Can't find element to delete\n");
return;
}
p->next = p->next->next;
/* same as (p->next)->next */
}
free(goner);
}
o Pictorially this looks like
p goner p->next->next
Before: ...----->[ ][ ]------->[ ][ ]------->[ ][NULL]
p p->next
After: ...----->[ ][ ]--------------------->[ ][NULL]
Finding an Element
------------------
o There is no general purpose find because you normally
search for an element based on its data fields.
o The following function searches for a student name.
#include "student.h"
static STUDENT head;
STUDENT *find(char *name)
{
STUDENT *p;
for(p=head;p!=NULL;p=p->next)
if(!strcmp(p->name,name))
return p;
return NULL;
}
Ok Ok Ok...you don't get it...try this example
----------------------------------------------
/**************************************************************
An example of creating a simple singly linked
list using both standard variables and pointers. The way to
use this thing is to clip it out of this file and
compile it up to see what it does. More importantly--do it
by hand and draw the associated linked diagram so you can
what is going on.
**************************************************************/
/*************************************************************
THINGS WE NEED TO START THE PROBLEMS
**************************************************************/
#include <stdio.h>
#include <stdlib.h>
/* This is the structure type that we will use to make the list */
typedef struct tagname
{
int data;
struct tagname *next;
} LIST;
void traverse(char *title,LIST *q)
{
/* traverse the list starting at head and going until
we run out of nodes at NULL. */
printf("%s\n",title);
printf("head->");
while(q)
{
printf("%d-> ",q->data);
q = q->next;
}
printf(" NULL\n\n");
}
void main()
{
int j;
/* This will point to the head of the list we will make.
Since initially the list is empty we make it point
to NULL*/
LIST *head=NULL;
/* Let's create two variables of LIST type which
will add to our list */
LIST first, second;
/* We will also make a pointer to the LIST type which
will allow us to malloc() a node */
LIST *third,*p;
/*************************************************************
STEP 1: DUMP THE EMPTY LIST
**************************************************************/
traverse("DUMP EMPTY LIST",head);
/*************************************************************
STEP 2: ADDING ONE ELEMENT TO THE LIST
**************************************************************/
/* We make head point to first and since we have a
variable (as opposed to an address) we can use the
dot notation and assign a value of 1 to the data
field. */
head = &first;
first.data = 1;
first.next = NULL;
traverse("ADD ONE ELEMENT TO LIST",head);
/*************************************************************
STEP 2: ADDING ANOTHER ELEMENT TO THE LIST
**************************************************************/
/* We make the first node point to the second node
We put 2 in the data field of second and again terminate
the list */
first.next = &second;
second.data = 2;
second.next = NULL;
traverse("ADD SECOND ELEMENT TO LIST",head);
/*************************************************************
STEP 3: ADDING ANOTHER ELEMENT TO THE LIST
(THIS TIME SPACE FROM MALLOC()
**************************************************************/
/* Since third is a pointer which currently points at nothing
we must malloc() some space before the next field of second
can point to it.*/
third = (LIST *) malloc(sizeof(LIST));
second.next = third; /* note we don't need the & since third is already
an address since it is a pointer */
third->data = 3; /* note the use of pointer notations */
third->next = NULL;
traverse("ADD THIRD ELEMENT TO LIST USING POINTER",head);
/*************************************************************
STEP 4: DELETE second FROM THE LIST
**************************************************************/
first.next = third; /* link first to third via the
next field (DON'T CALL free()) */
traverse("DELETE THE SECOND ELEMENT FROM THE LIST",head);
/*************************************************************
STEP 5: DELETE third FROM THE LIST AND ADD second
**************************************************************/
first.next = &second;
second.next = NULL;
free(third);
traverse("DELETE THE LAST AND REPLACE IT",head);
/*************************************************************
STEP 6: ADDING THREE MORE NODES TO THE LIST
**************************************************************/
p = &second;
for(j=4;j<=6;j++)
{
third = (LIST *) malloc(sizeof(LIST));
third->data = j;
third->next = NULL;
p->next = third;
p = p->next;
traverse("ADD ANOTHER NODE",head);
}
/*************************************************************
STEP 7: INSERTING AN ELEMENT BETWEEN second AND
THE NEXT ELEMENT
**************************************************************/
third = (LIST *) malloc(sizeof(LIST));
third->data = 3;
third->next = second.next;
second.next = third;
traverse("INSERT AN ELMENT BETWEEN SECOND AND NEXT NODES",head);
}