Transcript pointed hat

Data Structures and Algorithms
Elementary Data Structures
1
Elementary Data Structures
 Static and Dynamic Data Structures
 Static Arrays
 Pointers
 Run-Time Arrays
 The Linked List Structure
 Some Linked List Operations
 Variations on Linked Lists
2
1. Static & Dynamic Data
Structures
 Static data are allocated memory at
Compile Time, i.e. before the program
is executed.
 Static data are allocated their memory
space in a place called the Data
Segment
 Static data cannot change size during
Run Time, i.e. while the program is
running.
3
Static & Dynamic Data
Structures
 The Heap ( free memory)
 A Dynamic Data Structure is allocated memory at
run-time. Consists of nodes to store data and
pointers to these nodes to access the data.
 Nodes are created (allocated) and destroyed (deallocated) at run-time.
 Using dynamic allocation allows your programs
to create data structures with sizes that can be
defined while the program is running and to
expand the sizes when needed.
4
2. Static Arrays
 Abstraction:
A homogeneous sequence of elements with a fixed size that
allows direct access to its elements.
 Elements (members):
Any type, but all elements must be of the same type
 Relationship:
Linear (One-To-one). Ordered storage with direct access.
 Fundamental Operations:
 create array (by declaring it) with a size fixed at compile
time
 store an element in the array at a given position (direct
access)
 retrieve an element from a given position (direct access)
5
Operations on Arrays
 Create Array:
Size is fixed (constant):
e.g. int x[20], string name[50];
 Retrieve an element: e.g. z = x[ i ] ;
 Store an element: e.g. name[ i ] = “Ann” ;
6
Passing to and from Functions
 Arrays are always passed by reference
e.g. int findmax ( int x [ ] , int size );
 Can use const if array elements are not to
be modified, e.g.
int findmax ( const int x [ ] , int size );
 Do not include the array size within the
brackets when defining an array parameter.
 This is because the array name is the base
address of the array, and the size is already
known.
7
2-D Arrays
 Useful in representing a variety of data,
e.g. Tables, Matrices, Graphs and Images
Day
City
Fri
Sat
Sun
j
i
Cairo
35 32 33
5
2
3
Tanta
34 31 31
4
1
1
Alex
29 28 28
9
8
8
A Table of Temp.
A Matrix of Integers
8
Declaration & Indexing
 Declaration:
<element-type> <arrayName> [size 1][size2];
e.g.
double table[NROWS] [NCOLS];
 Indexing:
table[2] [4];
Row#
0 .. NROWS
Column#
0 .. NCOLS
9
3. Pointers: The Address of a
Variable
 The & symbol is called the address operator
 The purpose of & is to return the address of a




variable in memory. For example, if x is a variable
then &x is its address in memory.
We can store the address of a variable in a special
variable called a pointer
A Pointer is a variable whose value is a memory
address of an item, not its value
A pointer knows about the type of the item it points to
All pointers have fixed size (typically 4 bytes)
11
Pointers
 A pointer variable must be declared before it is used. It must
be bound to the same type as the variable it will point to.
 The asterisk operator * must precede each pointer name in
the declaration
 For Example:
double x = 3.14; // a variable of type double
double *p; // a pointer to double
p = &x;
// p now stores the address of x
p
0012FF78
x
3.14
Starts at location 0012FF78
12
Dereferencing (Indirection)
 (*) is the dereferencing (or indirection)
operator. It can be used to access the
value stored in a location.
 For example, if (p) is a pointer, the
value of (*p) is not the address stored
in p but is instead the value stored in
memory at that address (i.e. 3.14)
13
Indirection Operator
An asterisk has two uses with regard to pointers

In a definition, it indicates that the object is a pointer
char *s;

// s is of type pointer to char
In expressions, when applied to a pointer it evaluates to the
object to which the pointer points (indirection or
dereferencing)
int k = 1;
int *p = &k;
// p points to k
*p = 2;
cout << k << endl; // display a 2
14
Nodes & Pointers
 A node is an anonymous variable (has no name)
 No name is needed because there is always a pointer
pointing to the node.
Heap
Pointer
Node
15
Creating Nodes: the “new”
Operator
 The new operator allocates memory from the heap to a node of
specified type at Run Time. It returns the address of that node.
 The statements:
int *p ;
…………………………………….
p = new int;
create a new node of type int and let a pointer p point to it. No
data is put into the node
 The node created has no name, it is called an Anonymous
Variabe. It can only be accessed via its pointer using the
indirection operator, i.e. by using (*p)
16
Accessing Data with Pointers
 * - indirection operator
*p = 15.5;
// *p reads as: contents of node pointed to by p
 Stores floating value 15.5 in the node pointed to by p
*p
p
15.5
17
Returning Nodes to the Heap
 Operation:
delete <pointer variable>;
Returns space of node pointed to by pointer
back to heap for re-use
 When finished with a node delete it
 Pointer is not destroyed but undefined:
delete
p;
 Example:
18
4. Run-Time Arrays
Drawbacks of static arrays:
 Capacity is fixed at compile time
 If size > number of elements, memory is wasted
 If size < number of elements, we suffer array overflow
Solution: Dynamic (Run-Time) Arrays:
 Capacity specified during program execution.
 Acquire additional memory as needed.
 Release memory locations when they are not
needed.
19
Run-Time Arrays
The operator new can be used in an expression of the form:
new <Type> [n]
n is an integer expression (could be a variable).
This allocates an array with n elements, each of type <Type>;
it returns the base address of that array.
n-1
The address returned by new must be assigned to a pointer of
type Type.
20
Example
int n;
cout << “Enter size of array: ";
cin >> n;
// size is entered at run-time
if (n > 0)
{ int *A = new int [n]; // A is now the base address
// process A
for (int i = 0; i < n; i++) cin >> A[i];
...
}
21
Run-Time Arrays
Because run-time arrays can take a lot of memory
from the heap, we must de-allocate that space after
we finish with it.
To return memory allocated to array pointed to by A,
use the delete operator in the form:
delete [ ] A;
22
Example
int n;
cout << “Enter size of array: ";
cin >> n;
// size is entered at run-time
if (n > 0)
{ int *A = new int [n]; // A is now the base address
// process A
for (int i = 0; i < n; i++) cin >> A[i];
………..
delete [ ] A;
// Release memory locations
}
23
5. The Linked List Structure
 Arrange dynamically allocated structures into




a new structure called a linked list
Think of a set of children’s pop beads
Connecting beads to make a chain
You can move things around and re-connect
the chain
We use pointers to create the same effect
24
The Simple Linked List
 A sequence of nodes linked by pointers:
e
head
Last NULL
First
next
cursor
 First node pointed to by head. Contains a data
element (e) and a next pointer to next node.
 Last node’s next is NULL.
 A cursor points to the current node. It can advance
in one way only to next node, e.g. to traverse whole
list.
25
Specifying Node Structure
(Example)
 Suppose each node is to contain a word from the
dictionary, and the number of times such word
occurs in a document.
struct elType // specify data element
{ string word; int count};
struct node // specify node structure
{ elType e; node *next; };
node *p, *q; // pointers to nodes of type node
26
Specifying Node Structure
 Each of the pointers p, q can point to a
struct of type node:
 e.word (string)
 e.count (int)
 next (pointer to next node)
Struct of type node
word
count
String
Integer
next
Address
27
Building Nodes
 Allocate storage of 2 nodes
p = new node;
q = new node;
 Assign data to nodes
elType el1 , el2;
el1.word = “hat”; el1.count = 2;
el2.word = “top”; el2. count = 3;
p->e = el1; q->e = el2;
28
Building Nodes
p
hat
2
?
q
top
3
?
29
Connecting Nodes: A linked
list of two nodes
Suppose the address in q is stored in next field of node
pointed to by p and NULL is stored in the last next field:
p->next = q;
q->next = NULL;
p
hat
2
next
q
top
3
NULL
30
6. Some Linked List Operations
 Insertion at head of list
 Inserting a node after a given node
 Insert at end of list
 Delete a head node
 Delete a non-head node
31
Insertion at Head of List
Last
First
hat 2
top 3
head
3
2
New
if 4
p
1
elType el;
el.word = “if”;
el.count = 4;
p = new node;
p-> e = el;
p->next = head;
head = p;
32
Inserting after a given Node
cursor
head
if 4
top 3
hat 2
3
2
el.word = “the”;
el.count = 5;
the 5
p
p = new node;
New
p-> e = el;
1
p-> next = cursor-> next;
cursor->next = p;
33
Insert at End of List
cursor
Last
hat 2
New
2
if 4
p
1
top 3
3
p = new node;
p->e = el;
p->next = NULL;
cursor->next = p;
34
Delete Head Node
1
head
if 4
cursor
hat 2
the 5
top 3
3
2
cursor = head;
head = head->next;
delete cursor;
35
Deleting a Non-Head Node
cursor
prev
cursor
q
1
the
3
hat
2
node *q;
q = cursor;
cursor = cursor->next;
prev->next = cursor;
delete q;
Successor
top
Pre:
cursor points to node
prev points to
predecessor node
36
Demo
http://www.cosc.canterbury.ac.nz/people/
mukundan/dsal/LinkListAppl.html
37
7. Variations on Linked Lists
The Circular List:
head
tail
cursor
Notice that tail->next == head
38
Variations on Linked Lists
The Doubly Linked List
back
next
cursor
To advance: cursor = cursor->next;
To back : cursor = cursor->back;
39
Variations on Linked Lists
 The Circular Doubly Linked List
 The 2-D List:
40