CS计算机代考程序代写 data structure chain compiler Java algorithm COMP9024: Data Structures and Algorithms

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 defines useful functions to convert strings:

• 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