Transcript CISC105 - General Computer Science

CISC105 - General Computer
Science
Class 19 - 08/07/2006
Dynamic Data Structures
• Dynamic Data Structure - a structure that can
expand and contract as a program executes
• Dynamic Data structures do not require a
static declaration of how much memory we
need.
– We have studied several data structures such as
arrays which require us to declare how much
memory we need to use in advance (static data
structures)
Dynamic Data Structure
• Dynamic Data Structures are composed of
dynamically allocated structures (called
nodes) that are linked together to form the
overall data structure.
• We use pointers to connect nodes together
into an overall structure, examples include:
– Linked Lists
– Stacks
– Queues
Pointers Revisted
• Function formal parameters can be declared
as a pointer
• Actual parameter call is the address of the
variable
• The variable used to declare an array or
string is a pointer!
• The index is used to identify the size of the
data when the array is intialized
• see pointer1.c
Pointers
• We can also declare pointers to a data
structure such as a FILE structure
• See pointer3.c
Understanding Pointers and
memory
• Pointers point to memory addresses
– Pointer to an int
– Pointer to a char
– Pointer to a structure
• Variables types take a specific, system
defined amount of memory which can be
retrieved using sizeof(<var_type>)
Dynamic Memory Allocation
• We can dynamically allocate space to
an variable by using
(<var_type> *)malloc(sizeof(<var_type>))
• See malloc1.c
• Do you notice anything strange about
the dynamically allocated memory
versus the function allocated memory?
Memory heap vs. stack
• Heap - region of memory in which
function malloc() dynamically
allocates blocks of storage
• Stack - region of memory in which
function data areas are allocated and
reclaimed
Memory allocation using
calloc()
• Using malloc() will allocate space for a
single instance of a variable type - what
if we want to declare an array of a
variable type?
void *calloc(size_t nelements, size_t bytes)
• See calloc1.c
Giving back what you take!
• When memory is allocated through
malloc() or calloc() it is used until the
program terminates. What if you allocate
memory use it an no longer need it?
• You should free() it! free(<pointername>) tells the O/S that
the allocated memory is no longer needed
• See free1.c
Consequences of not giving
back memory
• A memory leak is a particular kind of
unintentional memory consumption by a
computer program where the program
fails to release memory when no longer
needed
Memory Leaks
• Memory leaks may not be serious or even
detectable by normal means. In modern
operating systems, normal memory used by
an application is released when the
application terminates. This means that a
memory leak in a program that only runs for a
short time is rarely serious.
Memory Leaks
• Cases where leaks are much more serious
include
– where the program is left running, and consumes more and
more memory over time (such as background tasks, on
servers, but especially in embedded devices which may be
left running for many years);
– where the program is able to request memory (e.g. shared
memory) that is not released, even when the program
terminates;
– where the leak is happening inside the operating system
– where memory is very limited e.g. in an embedded system or
portable device
Dynamically Allocating
Dynamically Allocated Memory
• If you need to change the amount of
memory that is dynamically allocated
(increase or decrease) use
void *realloc(void *pointer, size_t bytes)
• realloc returns a pointer to a memory
region of the specified size. If the new
size is greater than the old size, the
block is grown, otherwise it is shrunk.
• See realloc1.c
More on malloc(),
calloc() and realloc()
• In the rare occurrence that a memory
allocation function is run and there is no
memory left C will return NULL - In a
production environment you should
check the value of the return pointer to
see if it is NULL… What should you do
if memory cannot be allocated
Linked Lists
• A linked list is a data structure built by
connecting dynamically allocated nodes
• A linked list node contains a pointer to
another linked list node