COMP9024: Data Structures and Algorithms
COMP9024: Data Structures and
Algorithms
Week 1: Abstract Data Types and Pointers
Contents
• Abstract Data Types
• Compilation and Makefiles
• Pointers
Abstract Data Types (1/4)
• A data type is a set of values, and a set of operations on those values
• An ADT (Abstract Data Type) is a mathematical model for data types
• An approach to implementing data types
• Separates interface from implementation
• Users of an ADT see only the interface
• Builders of the ADT provide an implementation
Abstract Data Types (2/4)
An ADT interface provides
• a user-view of the data structure
• function signatures (prototypes) for all operations
• semantics of operations (via documentation)
• ⇒ a “contract” between ADT and its clients
An ADT implementation gives
• the concrete definition of the data structure
• function implementations for all operations
Abstract Data Types (3/4)
ADT interfaces are opaque
• Clients cannot see the implementation via the interface
ADTs are important because …
• facilitate decomposition of complex programs
• make implementation changes invisible to clients
• improve readability and structuring
Abstract Data Types (4/4)
Typical operations with ADTs
• create a value of the type
• modify one variable of the type
• combine two values of the type
Collection ADTs (1/4)
A collection consist of a group of items where each item may be a simple
type or an ADT.
Items are typically of the same type and often have a key (to identify them)
Collections may be categorised by …
• structure:
linear (array, linked list), branching (tree), cyclic (graph)
• usage:
matrix, stack, queue, set, search-tree, dictionary, map, …
Collections (2/4)
Collection structures:
Collections (3/4)
• Or even a hybrid structure like:
Collection (4/4)
For a given collection type
• many different data representations are possible
For a given operation and data representation
• several different algorithms are possible
• efficiency of algorithms may vary widely
Generally,
• there is no overall “best” representation/implementation
• cost depends on the mix of operations
(e.g. proportion of inserts, searches, deletions, …)
Stack ADT (1/2)
A stack is an abstract data type that serves as a collection of elements,
with the following operations:
• createStack(), which creates an empty stack.
• push(element), which adds an element to the collection, and
• pop(), which removes the top element from the stack.
• peek(), which returns the top element without modifying the stack.
• isEmpty(), which checks if the stack is empty.
Elements come off a stack following LIFO ( Last In First Out) order.
Stack ADT (2/2)
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
An Implementation of Stack (2/3)
Interface (a file named Stack.h)
// Stack header file
void stackInit();
int isEmpty();
void push(char);
char pop();
An Implementation of Stack (3/3)
#include “Stack.h”
#define MAXITEMS 10
static struct {
char item[MAXITEMS];
int top;
} stackObject;
void push(char ch) {
assert(stackObject.top < MAXITEMS-1);
stackObject.top++;
int i = stackObject.top;
stackObject.item[i] = ch;
}
void stackInit() {
stackObject.top = -1;
}
int isEmpty() {
return (stackObject.top < 0);
}
char pop() {
assert(stackObject.top > -1);
int i = stackObject.top;
char ch = stackObject.item[i];
stackObject.top–;
return ch;
}
Applications of Stacks
• Direct applications
➢ Page-visited history in a Web browser
➢ Undo sequence in a text editor
➢ Chain of method calls in the Java Virtual Machine
• Indirect applications
➢ Auxiliary data structure for algorithms
➢ Component of other data structures
Bracket Matching (1/5)
Check whether all opening brackets such as ‘(‘, ‘[‘, ‘{‘ have matching closing brackets ‘)’, ‘]’, ‘}’
Which of the following expressions are correct?
1. (a+b) * c
2. a[i]+b[j]*c[k])
3. (a[i]+b[j])*c[k]
4. a(a+b]*c
5. void f(char a[], int n) {int i; for(i=0;i
2
3 int main(void) {
4 int *ptr1, *ptr2;
5 int i = 10, j = 20;
6
7 ptr1 = &i;
8 ptr2 = &j;
9
10 *ptr1 = *ptr1 + *ptr2;
11 ptr2 = ptr1;
12 *ptr2 = 2 * (*ptr2);
13 printf(“Val = %d\n”, *ptr1 + *ptr2);
14 return 0;
15 }
Val = 120
Examples of Pointers (3/5)
Can we write a function to “swap” two variables?
The wrong way:
void swap(int a, int b) {
int temp = a;
a = b;
b = temp;
}
int main(void) {
int a = 5, b = 7;
swap(a, b);
printf(“a = %d, b = %d\n”, a, b);
return 0;
}
Examples of Pointers (4/5)
Recall that in C, scalar parameters are passed “by-value”
• Changes made to the value of a parameter do not affect the
original
• Function swap() tries to swap the values of a and b, but fails
because it only swaps the copies, not the “real” variables in main()
We can achieve “simulated call-by-reference” by passing pointers as
parameters
Examples of Pointers (5/5)
Can we write a function to “swap” two variables?
The right way:
void swap(int *p, int *q) {
int temp = *p;
*p = *q;
*q = temp;
}
int main(void) {
int a = 5, b = 7;
swap(&a, &b);
printf(“a = %d, b = %d\n”, a, b);
return 0;
}
Pointers and Arrays (1/3)
An alternative approach to iteration through an array:
• determine the address of the first element in the array
• determine the address of the last element in the array
• set a pointer variable to refer to the first element
• use pointer arithmetic to move from element to element
• terminate loop when address exceeds that of last element
Example:
int a[6];
int *p = &a[0];
while (p <= &a[5]) {
printf("%2d ", *p);
p++;
}
Pointers and Arrays (2/3)
Pointer-based scan written in more typical style
Note: because of pointer/array connection a[i] == *(a+i)
Pointers and Arrays (3/3)
argv can also be viewed as double pointer (a pointer to a pointer)
Alternative prototype for main():
int main(int argc, char **argv)
{
...
}
Can still use argv[0], argv[1], …
Pointer Arithmetic (1/7)
A pointer variable holds a value which is an address.
C knows what type of object is being pointed to
• It knows the sizeof that object
• It can compute where the next/previous object is located
Example:
int a[6];
int *p;
p = &a[0];
p = p + 1;
Pointer Arithmetic (2/7)
For a pointer declared as T *p; (where T is a type)
• if the pointer initially contains address A
o executing p = p + k; (where k is a constant)
▪ changes the value in p to A + k*sizeof(T)
The value of k can be positive or negative.
Example:
int a[6]; char s[10];
int *p; char *q;
p = &a[0]; q = &s[0];
p = p + 2; q++;
Pointer Arithmetic (3/7)
One common type of pointer/array combination are the command line arguments
• These are 0 or more strings specified when a program is run
• If you run this command in a terminal:
prompt$ ./seqq 10 20
then seqq will be given 2 command-line arguments: "10", "20"
Each element of argv[] is
• a pointer to the start of a character array (char *)
➢ containing a \0-terminated string
Pointer Arithmetic (4/7)
More detail on how argv is represented:
prompt$ ./seqq 5 20
Pointer Arithmetic (5/7)
main() needs different prototype if you want to access command-line arguments:
int main(int argc, char *argv[]) { ...
• argc … stores the number of command-line arguments + 1
o argc == 1 if no command-line arguments
• argv[] … stores program name + command-line arguments
o argv[0] always contains the program name
o argv[1],argv[2],… are the command-line arguments if supplied
• atoi(char *s) converts string to int
• atof(char *s) converts string to double (can also be assigned to float variable)
Pointer Arithmetic (6/7)
Write a program that
• checks for a single command line argument
➢ if not, outputs a usage message and exits with failure
• converts this argument to a number and checks that it is positive
• applies the following Collatz’s process, until 1 is reached:
➢ If n is even, set n to n/2
➢ If n is odd, set n to 3*n+1
Pointer Arithmetic (7/7)
#include
#include
void collatz(int n) {
printf(“%d\n”, n);
while (n != 1) {
if (n % 2 == 0)
n = n / 2;
else
n = 3*n + 1;
printf(“%d\n”, n);
}
}
int main(int argc, char *argv[]) {
if (argc != 2) {
printf(“Usage: %s [number]\n”, argv[0]);
return 1;
}
int n = atoi(argv[1]);
if (n > 0)
collatz(n);
return 0;
}
Pointers and Structures (1/3)
Like any object, we can get the address of a struct via &.
typedef char Date[11];
typedef struct {
char name[60];
Date birthday;
int status;
float salary;
} WorkerT;
WorkerT w; WorkerT *wp;
wp = &w;
*wp.salary = 125000.00;
w.salary = 125000.00;
*(wp.salary) = 125000.00;
(*wp).salary = 125000.00;
// wp->salary = 125000.00;
Pointers and Structures (2/3)
Diagram of scenario from program above:
Pointers and Structures (3/3)
General principle …
If we have:
SomeStructType s, *sp = &s;
then the following are all equivalent:
s.SomeElem sp->SomeElem (*sp).SomeElem
Summary
• Introduction to ADTs
• Compilation and Makefiles
• Pointers
• Suggested reading:
➢ introduction to ADTs … Sedgewick, Ch.4.1-4.3
➢ pointers … Moffat, Ch.6.6-6.7