Tin học cơ sở 3

Tin h c c s 3

ọ ơ ở

Structure

Outline

• Structured Data types • Structures as function arguments • Self-referential types: linked list

Lê Nguyên Khôi 2

Structure

• 2nd aggregate data type: struct

• Recall: aggregate meaning "grouping"

– Recall array: collection of values of same type – Structure: collection of values of different types

• Treated as a single item, like arrays

• Major difference: Must first "define" struct

– Prior to declaring any variables

Lê Nguyên Khôi 3

Structure

• Many structured collections of data are:

– Heterogeneous (components are different types) – Fixed-size (well-defined set of components)

• For example:

Student Record

Name

Nguyen Van A

Student Id

1234567

Course

INT1005

Date of Birth

01/01/1993

Gender

Male

Lê Nguyên Khôi 4

Structured Data Types

• A structure is a collection of variables, perhaps of different types, grouped together under a single name.

• Structures:

– Help to organize complicated data into manageable

entities.

– Expose the connection between data within an entity – Are defined using the struct keyword. – Sometimes referred as records.

Lê Nguyên Khôi 5

Structured Data Types

• Define struct globally (typically) • No memory is allocated

– Just a “placeholder” for what struct will “look like”

• To define struct, we must give:

– Name of struct – Name of each field – Type of each field (could be another record/struct)

Lê Nguyên Khôi 6

Defining Struct

• Defining a new data type using struct

 name of new "type"

 member names

 “;” after “}”

struct date { int day; int month; int year; }; struct date yesterday;

• Once defined, this new data type could be used as other

data types: –Variable of this type could be assigned to another variable of the same type –Variable of this type could be passed as a parameter to a function 7

Lê Nguyên Khôi

Declare Structure Variable

• With structure type defined, now declare

variables of this new type: struct date today; – Just like declaring simple types – Variable today now of type struct date – It contains "member values" • Each of the struct "parts"

Lê Nguyên Khôi 8

Accessing Structure Members

• Dot Operator to access members

– today.day – today.month – today.year

• Called "member variables"

– The "parts" of the structure variable – Different structs can have same name member

variables

• No conflicts

Lê Nguyên Khôi 9

Defining New Type Struct

• Could use typedef to define a new type struct

typedef struct date Date;

• And then we could use Date as other basic type

without the need of including struct Date today;

• Compare to previous declaration of yesterday

struct date yesterday;

Lê Nguyên Khôi 10

Structure Example

void printData(Date today) { printf("The day is: %i", today.day); printf("The month is: %i", today.month); printf("The year is: %i", today.year); }

void getData(Date *today);

Lê Nguyên Khôi 11

Structure Initialization

• Can initialize at declaration

– Example:

struct date { int day; int month; int year; }; typedef struct date Date; Date dueDate = {31, 12, 2013};

– Declaration provides initial data to all three

member variables Lê Nguyên Khôi

Structure Assignments

• Given structure named Fruit

• Declare two structure variables:

Fruit apples, oranges; – Both are variables of type "Fruit" – Simple assignments are legal:

apples = oranges;

• Simply copies each member variable from apples

into member variables from oranges

Lê Nguyên Khôi 13

Structure Other Operations

• Operations which are NOT defined for struct type:

– compare for equality/inequality

(i.e. apples == oranges is not a legal expression)

– compare based on ordering (<, >, ...)

(i.e. apples < oranges is not a legal expression)

(i.e. apples + oranges is not a legal expression)

– arithmetic operations – reading from or writing to text files

(i.e. no printf(apples) no scanf(&oranges)) • If you need such operations, write your own

functions.

Lê Nguyên Khôi 14

Structure and Pointer

• As for other types:

– (struct x)* is a pointer to struct x – & gives the address of a structure

• There are precedence problems because . binds

•

more tightly than * If p is a pointer to a struct and a is a field of the struct: – *p.a means *(p.a) which is ILLEGAL. – You must use (*p).a – For convenience , the operator -> combines indirection and

component selection.

– p->a is equivalent to (*p).a

Lê Nguyên Khôi 15

Structure and Pointer

struct point {

int x, y;

}; struct point a; struct point ap; ap = &a; ap.x = 0; /* wrong / / equivalent to (ap.x) = 0;/ (ap).y = 0; / right / ap->x = 0; / right */

Lê Nguyên Khôi 16

Structure and Pointer

void getData(Date today) { printf("Enter day: "); scanf("%i", &((today).day)); printf("Enter month: "); scanf("%i", &(today->month)); printf("Enter year: "); scanf("%i", &today->year); }

Lê Nguyên Khôi

Structure as Function Argument

• Passed like any simple data type

– Pass-by-value – Pass-by-reference – Or combination

• Can also be returned by function

– Return-type is structure type – Return statement in function definition sends structure variable back to caller

Lê Nguyên Khôi 18

Other Type Definition

• We can use the keyword typedef to make our

own definitions: typedef float Floating;

• This means variables can be declared as

Floating but they will actually be of type float. • If we later decide we need more precision, we

can change to: typedef double Floating; without changing the codes.

Lê Nguyên Khôi 19

Combining struct and typedef

struct employee { char name[30]; int id; char position[20]; float salary; }; typedef struct employee Employee; Employee john;

• Note: we use the convention that the name of the defined type is the same as the struct modifier, but with the first letter capitalized. Lê Nguyên Khôi

Self-referential types

• A very powerful programming technique is to

create struct with fields which contain a reference to an object in the same struct. For example: struct list_node { int data; struct list_node *next; };

• This approach can be used to create some

very useful data structures.

Lê Nguyên Khôi 21

Linked Lists

• Consider the following data structure:

– A list that grow over time – Items are added one by one – Each item is a number • It might grow like this:

Lê Nguyên Khôi 22

Linked Lists

• How do you implement such a list in C++? • You can use an array but you must check the array doesn't overflow and allocate memory for a new larger array if the array fills.

• Can be implemented using a self-referential type. • Each element in the linked list need:

– some information (the data) – a connection to the next item

• The individual elements in data structures like this

are often called nodes.

Lê Nguyên Khôi 23