Transcript CSCI 210 Data Structures & Algorithms

CSCE 210
Data Structures and Algorithms
Prof. Amr Goneid
AUC
Part R2. Elementary Data
Structures
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
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.
Prof. Amr Goneid, AUC
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.
Prof. Amr Goneid, AUC
4
2. Static Arrays
 Abstraction:
A homogenous 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)
Prof. Amr Goneid, AUC
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” ;
Prof. Amr Goneid, AUC
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.
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
9
2-D Arrays as Parameters
 In 1-D arrays, it is not necessary to specify the size:
void display (int A[ ], int n);
To follow the same convention with 2-D arrays:
void display (int B[ ] [ ] , int n , int m);
 This will not work, because 2-D arrays are stored as
1-D arrays of arrays (1-D arrays of rows)
 Hence, beside the base address (name) we must
also specify the number of columns, e.g.
void display (int B[ ][Ncol], int n, int m);
Prof. Amr Goneid, AUC
10
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)
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
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)
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
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)
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
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:
 Example:
delete
Prof. Amr Goneid, AUC
p;
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.
Prof. Amr Goneid, AUC
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.
Prof. Amr Goneid, AUC
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];
...
}
Prof. Amr Goneid, AUC
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;
Prof. Amr Goneid, AUC
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];
// process A
// A is now the base address
for (int i = 0; i < n; i++) cin >> A[i];
………..
delete [ ] A;
// Release memory locations
}
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
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.
Prof. Amr Goneid, AUC
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
{ string word;
struct node
{ elType e;
node *p, *q;
// specify data element
int count};
// specify node structure
node *next; };
// pointers to nodes of type node
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
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;
Prof. Amr Goneid, AUC
28
Building Nodes
p
hat
2
?
q
top
3
?
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
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
Prof. Amr Goneid, AUC
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;
Prof. Amr Goneid, AUC
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;
Prof. Amr Goneid, AUC
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;
Prof. Amr Goneid, AUC
34
Delete Head Node
1
head
if 4
cursor
hat 2
the 5
top 3
3
2
cursor = head;
head = head->next;
delete cursor;
Prof. Amr Goneid, AUC
35
Deleting a Non-Head Node
cursor
prev
cursor
q
Successor
1
the
3
hat
2
node *q;
q = cursor;
cursor = cursor->next;
prev->next = cursor;
delete q;
top
Pre:
cursor points to node
prev points to
predecessor node
Prof. Amr Goneid, AUC
36
Demo
http://www.cosc.canterbury.ac.nz/people/
mukundan/dsal/LinkListAppl.html
Prof. Amr Goneid, AUC
37
7. Variations on Linked Lists
The Circular List:
head
tail
cursor
Notice that tail->next == head
Prof. Amr Goneid, AUC
38
Variations on Linked Lists
The Doubly Linked List
back
next
cursor
To advance: cursor = cursor->next;
To back : cursor = cursor->back;
Prof. Amr Goneid, AUC
39
Variations on Linked Lists
 The Circular Doubly Linked List
 The 2-D List:
Prof. Amr Goneid, AUC
40