Transcript Slide 1

Data Type planet_t and Basic Operations
• Abstract Data Type
(ADT) is a data type
combined with a set
of basic operations
CP104 Introduction to Programming
Structure II
Lecture 32 __ 1
Case Study: Complex Number ADT
• Complex data type
typedef struct{
double real, imag;
} complex_t;
• Operations
1. int scan_complex(complex_t *c);
2. void print_complex(complex_t c);
3. complex_t add_complex(complex_t c1, complex_t c2);
4. complex_t subtract_complex(complex_t c1, complex_t
c2);
5. complex_t multiply_complex(complex_t c1, complex_t
c2);
6. complex_t divide_complex(complex_t c1, complex_t c2);
7. complex_t abs_complex(complex_t c);
CP104 Introduction to Programming
Structure II
Lecture 32 __ 2
Partial Implementation of Complex ADT (I)
CP104 Introduction to Programming
Structure II
Lecture 32 __ 3
Partial Implementation of Complex ADT (II)
CP104 Introduction to Programming
Structure II
Lecture 32 __ 4
Partial Implementation of Complex ADT (III)
CP104 Introduction to Programming
Structure II
Lecture 32 __ 5
Partial Implementation of Complex ADT (IV)
CP104 Introduction to Programming
Structure II
Lecture 32 __ 6
Partial Implementation of Complex ADT (V)
CP104 Introduction to Programming
Structure II
Lecture 32 __ 7
Parallel Array vs. Array of Structures
•
Assume that there are three records
first_name
Tom
Alice
Jane
•
last_name
Black
Smith
White
ID
12345
23456
14567
payment
300.00
1200.50
900.00
date
980130
980220
980701
Two ways to store the records
– Parallel array:
char first_name[3][20];
char last_name[3][20];
int id[3];
double payment[3];
int date[3];
– Array of Structures
typedef struct{
char first_name[20];
char first_name[20];
int id;
double payment;
int date;
} customer_t;
customer_t record[3];
•
Advantages and disadvantages
CP104 Introduction to Programming
Structure II
Lecture 32 __ 8
Structures with Pointer Components
typedef struct node {
char data;
struct node *next;
};
• The structure type node contains a pointer member of the
same type
• This type of structure can be used to form a linked list data
structure
• A linked list is a sequence of nodes each contains the address
of the next node except the last node
p
a
CP104 Introduction to Programming
b
c
Structure II
d
Lecture 32 __ 9
Use linked list to implement a Stack ADT
•
Node structure type
typedef struct node {
char data;
struct node *next;
};
•
Operations
1.
2.
3.
4.
5.
6.
node *create(void);
Void freeStack(node *stack);
Void push(char inputdat, node *stack);
Char pop(node *stack);
Char top(node *stack);
Int isempty(node *stack);
See demo
•
Advantages: assign memory location dynamically
–
–
•
•
•
assign when needed, while array can not, must assign fixed length before using it
Nodes of a linked list may not stored in continuous in memory, while an array is stored
continuously in memory
Disadvantages:
Linear access not random access
More overhead and relatively slower
CP104 Introduction to Programming
Structure II
Lecture 32 __ 10
Functions related to memory allocation in stdlib
•
Memory allocation function call will assign memory location to variables,
arrays in Heap region of memory.
•
void *malloc(size_t size);
–
•
void *calloc(size_t nitems, size_t size);
–
•
Allocates the requested memory and returns a pointer to it. The requested size is
nitems each size bytes long (total memory requested is nitems*size). The space is
initialized to all zero bits. On success a pointer to the requested space is returned.
On failure a null pointer is returned.
void free(void *ptr);
–
•
Allocates the requested memory and returns a pointer to it. The requested size is
size bytes. The value of the space is indeterminate. On success a pointer to the
requested space is returned. On failure a null pointer is returned.
Deallocates the memory previously allocated by a call to calloc, malloc, or realloc.
The argument ptr points to the space that was previously allocated. If ptr points to a
memory block that was not allocated with calloc, malloc, or realloc, or is a space
that has been deallocated, then the result is undefined. No value is returned.
sizeof
–
Is a key word, not a function. e.g.
CP104 Introduction to Programming
sizeof(int)
Structure II
Lecture 32 __ 11