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,

print

, right

D, G, B, A, H, E, I, C, F

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

PRE-ORDER

print

, left, right

A, B, D, G, C, E, H, I, F

POST-ORDER

left, right,

print

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 */

}
}