LECTURE 10
Structures – multiple (compound) variables
Static and dynamic data structures
list, queue, stack, tree
Programs: c5_1.c, c5_2, c5_3, c5_4, c5_5
Tomasz Zieliński
LECTURE 10
Structures – multiple (compound) variables
Static and dynamic data structures
list, queue, stack, tree
Programs: c5_1.c, c5_2, c5_3, c5_4, c5_5
Tomasz Zieliński
VARIABLES HAVING COMPLEX STRUCTURE (1)
Simple variables:
char, short, int, long, float, double
(unsigned) char, short, int, long
Examples:
char c,
s[10];
int
i, j, k, l, m[3][3], n[5][5][5];
float
x, y, z
c = getchar();
strcpy(s, ”Smith”);
i = 10; j = 20;
k = i+j; l = i*j;
m[0][1] = 1;
n[0][1][2] = m[1][2] + 128;
VARIABLES HAVING COMPLEX STRUCTURE (2)
Multiple (compound) variables = structures
Example:
struct
person
{ <------- variable type
person
char
surname
[20];
char
name
[10];
int
age
;
int
height
;
}
student
;
<------- declaration of variable
student
of type
person
strcpy(
student
.
surname
, ”Smith” );
// initialization of
strcpy(
student
.
name
, ”John” );
// a multiple variable
student
.
age
=
23;
//
(its
sub-variables)
student
.
height
=
187;
//
struct person
patient, student
= {”Smith”, ”John”, 23, 187};
VARIABLES HAVING COMPLEX STRUCTURE (3)
Example:
struct
person
{
<---------- variable type
person
char
surname
[20];
char
name
[10];
int
age
;
int
height
;
}
*pstudent
;
<--------- declaration of pointer to variable
student
WRITING CONVENTION:
*xxx.yyy = xxx->yyy
strcpy(
pstudent->
surname
, ”Smith” );
// initialization of sub-variables
strcpy(
pstudent->
name
, ”John” );
//
pstudent->
age
=
23; //
pstudent->
height
=
187;
//
struct osoba
*ppatient, *pstudent
= {”Smith”, ”John”, 23, 187};
DATA STUCTURES (1) –
static and dynamic
List:
of computer users, excursion participants, students,
patients, ...
Queue:
documents waiting for printing by a network printer
Stack:
of stored data with information concerning interrupted
programs, waiting for execution (processor time)
Tree:
of directories on a computer hard disc
Static:
a table consisting of many elements of the same type,
often not fully filled with data,
sometimes pack-full (overloaded)
Dynamic:
chain of nodes (block of memory cells) that are
pointed out to each other
DATA STRUCTURES (2) –
static and dynamic
Static queue
Dynamic queue
A B C D E
beginning
end
G
H
end
beginning
I
J K
L
F
A
adr
end
B
adr
C
adr
beginning
node #1
memory
cells
address of the
first node
address of the
last node
node #2
memory
cells
node #3
memory
cells
|
struct
queue
{
struct
queue
{
| int beginning;
int
beginning;
|
int end;
int
end;
| }
struct
person
table[ MAX ]; | struct
node
{
}
|
struct
person
student;
| struct
node
*next;
|
}
DYNAMIC DATA STRUCTURES (1)
Nodes
=====================================================
struct
node1
{
struct
node2
{
struct
element
info;
struct
element
info;
struct
node1
*next;
struct
node2
*previous;
};
struct
node2
*next;
};
=====================================================
Example:
struct
element
{
// in each node is placed
int
number;
// one number, e.g. 230
char letter;
// and one letter, e.g. V (volt)
};
Dynamic memory allocation for a node and its freeing:
pnode
= (struct
node
*)
malloc
( sizeof( struct
node
) );
free
(
pnode
);
DYNAMIC DATA STRUCTURES (2)
One-way (unidirectional) list
info A
adr
info B
adr
info X
adr
info Y
beginning
info A
adr
info B
adr
beginning
info C
adr
info X
adr
info Y
ADD, APPEND
info A
adr
info B
adr
info X
adr
info Y
beginning
REMOVE
DYNAMIC DATA STRUCTURES (3)
Two-way (bi-directional) list
info A
adr
pointer
info X
adr
adr
info B
adr
adr
info Y
adr
info A
adr
pointer
info X
adr
adr
info B
adr
adr
info Y
adr
adr
adr
info B
adr
info X
adr
adr
info C
adr
adr
info A
adr
info X
adr
adr
info B
adr
adr
ADD,
APPEND
REMOVE
DYNAMIC DATA STRUCTURES (4)
FIFO (First In First Out) QUEUE in static circular buffer
A
B
C
D
E
beginning
end
A
B
C
D
E F
beginning
end
A
B
C
D
E F
beginning
end
G
H
beginning
end
I
J
K
L
F
DYNAMIC DATA STRUCTURES (5)
Dynamic FIFO (First In First Out) QUEUE
A
adr
end
B
adr
C
adr
D
adr
beginning
A
adr
end
B
adr
C
adr
beginning
A
adr
end
B
adr
C
adr
D
adr
beginning
DYNAMIC DATA STRUCTURES (6)
STACK statically and dynamically
Static
table
Dynamic
structure
A B C D E
last
A B C D E
last
F
A B C D
last
D
adr
C
adr
B
adr
A
adr
last
C
adr
B
adr
A
adr
last
D
adr
C
adr
B
adr
A
adr
last
DYNAMIC DATA STRUCTURES (7) –
binary tree
A
adr L adr P
14
B
adr L
9
C
adr L adr P
21
D
adr P
5
G
6
I
20
H
15
E
adr L adr P
16
F
30
WRITING OUT ELEMENTS:
5, 6, 9, 14, 15, 16, 20, 21, 30
IN-ORDER
left,
, right
D, G, B, A, H, E, I, C, F
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PRE-ORDER
, left, right
A, B, D, G, C, E, H, I, F
POST-ORDER
left, right,
G, D, B, H, I, E, F, C, A
DYNAMIC DATA STRUCTURES (8) –
binary tree
See previous page:
struct
node
{
struct element {
struct element info;
e.g. ------>
char letter;
struct
node
*left;
int numbers;
struct
node
*right;
}
};
Example:
A
+
*
-
+
B
C D
E
A + (B - C) * (D + E)
/* Example 5.5 - BINARY TREE - as a dynamic structure
*/
/*
input integer numbers from the keyboard
*/
/*
quickly find the first repetition
*/
/*
finally, print numbers from the smallest to the biggest one */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct node
{
/* node structure */
int
info;
struct node *left;
struct node *right;
};
typedef struct node
*ADRnode;
/* declare address to a node */
ADRnode
MemForNode
( void );
/* take memory for a new node */
ADRnode
NewBranch
( int x );
/* make new branch
*/
void
ToLeft
( ADRnode p, int x);
/* put number x into left branch */
void
ToRight
( ADRnode p, int x);
/* put number x into right branch */
void
Preorder
( ADRnode p );
/* ordering #1 */
void
Inorder
( ADRnode p );
/* ordering #2 */
void
Postorder
( ADRnode p );
/* ordering #3 */
/* main program -------------------------------------------------------------------------- */
void main()
{
int number;
ADRnode ptree;
ADRnode p, q;
printf( "\n Input integer numbers. End with any letter! \n\n ");
scanf( "%d", &number );
/* take the first number */
ptree =
NewBranch
( number );
/* it will be putted into tree trunk */
while ( scanf("%d", &number ) != NULL )
// read next numbers
{
p = q = ptree;
while( number != p->info && q != NULL )
// repeat if:
{
// 1. different numbers
p = q;
// 2. there is a tree below
if ( number < p->info )
q = p->left;
// if lower, then go left
else
q = p->right;
// if greater, the go right
}
if ( number == p->info )
// given number is already in the tree
printf(" Number %d has been read already !\n", number );
else if ( number < p->info )
// end of tree branch
ToLeft
( p, number );
// store number in a left sub-branch
else
ToRight
( p, number);
// store number in a right sub-branch
}
printf("\n Inorder :\n");
// Different methods for “walking”
Inorder
( ptree );
// in binary trees
printf("\n Preorder :\n");
Preorder
( ptree );
printf("\n Postorder :\n");
Postorder
( ptree );
printf("\n");
}
/* Auxiliary functions ------------------------------------------------------------------- */
ADRnode
MemForNode
( void )
/* allocate memory for a new node */
{
ADRnode p;
p = (ADRnode) malloc( sizeof( struct
node
) ) ;
return( p );
}
/*------------------------------------------------------------------------------------------------*/
ADRnode
NewBranch
( int x )
/* create a new branch */
{ ADRnode p;
p = MemForNode();
p->info = x;
p->left = NULL; p->right = NULL;
return( p );
}
/*------------------------------------------------------------------------------------------------*/
void
ToLeft
( ADRnode p, int x )
/* put number x into the left branch */
{
if ( p == NULL )
printf( "Out of memory !\n" );
else if ( p->left != NULL )
printf( "Left node already exists! \n" );
else
p->left = NewBranch( x );
}
/*------------------------------------------------------------------------------------------------*/
void
ToRight
( ADRnode p, int x)
/* put number x into the right branch */
{
if ( p == NULL )
printf( " Out of memory !\n");
else if ( p->right != NULL )
printf( "Right node already exists!\n");
else
p->right = NewBranch( x );
}
/*------------------------------------------------------------------------------------------------*/
void
Preorder
( ADRnode p )
/* ordering #1 */
{ if ( p != NULL )
{
printf(" %5d ", p->info);
/* info */
Preorder
( p->left );
/* go left */
Preorder
( p->right );
/* go right */
}
}
/*------------------------------------------------------------------------------------------------*/
void
Inorder
( ADRnode p )
/* ordering #2 */
{
if ( p != NULL )
{
Inorder
( p->left );
/* go left */
printf(" %5d ", p->info);
/* info */
Inorder
( p->right );
/* go right */
}
}
/*------------------------------------------------------------------------------------------------*/
void
Postorder
( ADRnode p )
/* ordering #3 */
{
if ( p != NULL )
{
Postorder
( p->left );
/* go left */
Postorder
( p->right );
/* go right */
printf(" %5d ", p->info);
/* info */
}
}