Tutorial 02/25

ADTs in C

• C just uses files for ADTS, not modules/namespaces.

• Our example ADT is the sequence Operations— creates an empty sequence

• Insert(s,i,e) - inserts e at index i in sequence S

  • Pre: 0<= i<= Size(S)

    • It's Size(S), to allow for unbounded growth

A precondition, is a condition that has to be true, for the rest of the function to be valid.

• Size(S) - # Elements in S

• remove(s,i) - removes item at index i from S.

  • Pre: 0<= i<= Size(S) - 1

• index(s,i) - return the i-th element of S

  • Pre: 0<= i<=Size(s)-1

• Want our sequence to grow as necessary. What Data Structure ?

Implementation options:

1. Linked List:

   1. Easy to grow

   2. Slow to Index

2. Array:

   1. Constant-time Indexing

   2. Harder to grow !

Approach: Partially-filled Heap Array

Partially-Filled Heap Array

struct Sequence {
int * array;
int size; // how many elements are in the sequence
int cap; // how many slots the array has.
}

First File

sequence.h

struct Sequence emptySeq();
int size(Sequence S);
void add(Sequence S, int e);
void remove(Sequence s);
int index(Sequence s);

sequence.c

##include sequence.h
struct Sequence emptySeq();
struct Sequence res;
res.size=0;
res.array = malloc(10*sizeof(int));
res.cap = 10;
return res;
}

int seqSize(struct Sequence s) {
return s.size();
}
void add(struct Sequence *s, int i, int e){
//insert element at anywhere do sequence
//what if in the middle of sequence?
//have to shift everything.
for(int n=s->size; n>i;--n){
(s->array)[n] = (s->array)[n-1];
}
//its in this order so moves all elts one to the right w/out overwriting other data.
}
void remove -> exercise

int index(struct sequence *s, int i){

return (s->array)[i];
}
int free -> exercise,
//hint check malloc.

// main.c
##include "sequence.c"
int main(){
struct S = emptySeq();
add(&S,0,0);
add(&s, )
// why address of s?
}

There is a chance that this Abstract ADT can be used improperly. How can we make this data-structure bullet-proof.

What happens when the array is full?

//realloc may return Null, if it doesn't have enough space.
//good exercise, is how to handle w/out leaks.
void (add struct Sequence *S, int i, int l){
if (s->size == s->cap){
//full
//use realloc, takes a peice of memory and expands the range a bit.
s->array = realloc(s->array,___);
//if realloc removes some space, what happens??
}

}

realloc will get a larger chunk of memory.

• Good case: S->array can be simply be exapnded into neighbouring memory.

  • The memory is not used.

• Worse case: An entirely new chunk of memory must be allocated, and the old array has to be copied over at O(n) cost.

Leading Questions:

How big should we make the array??