Abstract Data Types (ADTs)Preparing for the Midterm ExamAbstract Data Type (ADT)ADT Example: Rational NumbersSeveral Ways to Represent RationalAnother Example ADT: SetsSeveral Ways to Represent SetsAnother ADT Example: StacksGoals for the StackSlide 10Notes on stack.hStack Implementation: ArrayCareful Checking With AssertStack Implementation: Array (Cont.)Problems With Array ImplementationLinked List Would be Better…Popping and PushingStack Implementation: Linked ListSlide 19stack.c, continuedClient Program: Uses InterfaceProblem: Multiple Kinds of Stacks?Slide 23Stack Implementation (with void*)stack.c (with void*) continuedSlide 26Client Program (With Void)Structural Equality TestingAlmost, But Not Quite...Item ADT Provides Equal TestFunction PointersPassing a Function PointerConclusions1Abstract Data Types (ADTs)Professor Jennifer RexfordCOS 2172Preparing for the Midterm Exam•Exam logisticsDate/time: Wednesday March 12 in lectureOpen books, open notes, open mind, but not open laptop/PDACovering material from lecture, precept, and reading, but not tools•Preparing for the midtermLecture and precept materials available onlineCourse textbooks, plus optional books on reserveOffice hours and the course listserv•Old exams from previous semestersMidterms: http://www.cs.princeton.edu/courses/archive/spring08/cos217/exam1old/Finals: http://www.cs.princeton.edu/courses/archive/spring08/cos217/exam2old/3Abstract Data Type (ADT)•An ADT module provides:Data typeFunctions that operate on the type•Client does not manipulate the data representation directlyThe client should just call functions•“Abstract” because the observable results (obtained by client) are independent of the data representationSeparation of interface and implementation•Programming language support for ADTEnsure that client cannot possibly access representation directlyC++, Java, other object-oriented languages have private fieldsC has opaque pointers4ADT Example: Rational Numbers•Rational numbersCan be written as a/b where a and b are int and b != 0Precision may be lost in representing as a single number•Interface functionsMakeRationalAddRationalMultiplyRationalEqualRationalPrintRationalReduceRational5Several Ways to Represent Rationaltypedef struct { int numerator; int denominator;} Rational; typedef struct { int ar[2];} Rational;6Another Example ADT: Sets•SetsA collection of elements•Interface functionsMakeNullSetIsMemberInsertDeleteUnionIntersection7Several Ways to Represent Setstypedef struct { Etype elem[MAX]; int size;} Set; Or, as a linked list…8Another ADT Example: Stacks•LIFO: Last-In, First-Out•Like the stack of trays at the cafeteria“Push” a tray onto the stack“Pop” a tray off the stack•Useful in many contexts9Goals for the Stack•Hide implementation details from the clientPut only the interface in stack.h, and implementation in stack.cOnly allow the client to have a pointer to a Stack•Allow multiple instances of stacks in the same programDefine a type of Stack, rather than a global variable in stack.c•Allow different stacks to have different kinds of elementsAllow another abstract data type to define the type of ItemOnly allow the Stack to refer to a pointer to an Item•Allow different stacks with different element types in the same programUsing void pointers10Stack Interface (stack.h)#ifndef STACK_INCLUDED#define STACK_INCLUDEDtypedef struct Item *Item_T;typedef struct Stack *Stack_T;Stack_T Stack_new(void);int Stack_empty(Stack_T stk); void Stack_push(Stack_T stk, Item_T item);Item_T Stack_pop(Stack_T stk); #endifWhat’s this for?11Notes on stack.h•Type Stack_T is an opaque pointerClients can pass Stack_T around but can’t look insideDefinition of Stack can change without recompiling the client code•Type Item_T is also an opaque pointer… but defined in some other ADTSo, Stack implementation doesn’t need to know about itAnd, Stack implementation can be used for many kinds of items•Stack_ is a disambiguating prefixA convention that helps avoid name collisions12Stack Implementation: Arraystack.c#include <assert.h>#include <stdlib.h>#include “stack.h”enum {CAPACITY = 1000};struct Stack { int count; Item_T data[CAPACITY];};Stack_T Stack_new(void) { Stack_T stk = malloc(sizeof(*stk)); assert(stk != NULL); stk->count = 0; return stk; }13Careful Checking With Assertstack.c#include <assert.h>#include <stdlib.h>#include “stack.h”enum {CAPACITY = 1000};struct Stack { int count; Item_T data[CAPACITY]; };Stack_T Stack_new(void) { Stack_T stk = malloc(sizeof(*stk)); assert(stk != NULL); stk->count = 0; return stk; }Make sure stk!=NULL, or halt the program!14Stack Implementation: Array (Cont.)int Stack_empty(Stack_T stk) { assert(stk != NULL); return (stk->count == 0); }void Stack_push(Stack_T stk, Item_T item) { assert(stk != NULL); assert(stk->count < CAPACITY); stack->data[stack->count] = item; stack->count++;}Item_T Stack_pop(Stack_T stk) { assert(stk != NULL); assert(stk->count > 0); stk->count--; return stk->data[stk->count];}012345count is 3CAPACITY is 615Problems With Array ImplementationCAPACITY too large: waste memoryCAPACITY too small: assertion failure (if you were careful) buffer overrun (if you were careless)wasted spacedatadata16Linked List Would be Better…nextvalheadhead3 2 1empty stackpush(1); push(2); push(3);struct List {int val; struct List *next;} *head;17Popping and Pushingpop( );head3 2 1head3 2 1head2 14push(4);18Stack Implementation: Linked Liststack.c#include <assert.h>#include <stdlib.h>#include “stack.h”struct Stack {struct List *head;};struct List {Item_T val; struct List *next;};Stack_T Stack_new(void) { Stack_T stk = malloc(sizeof(*stk)); assert(stk != NULL); stk->head = NULL; return stk; }19Stack Implementation: Linked Listint Stack_empty(Stack_T stk) { assert(stk != NULL); return (stk->head == NULL); }void Stack_push(Stack_T stk, Item_T item) { struct List *t = malloc(sizeof(*t)); assert(t != NULL); assert(stk != NULL); t->val = item; t->next = stk->head; stk->head = t; }head3 2 14t20stack.c, continuedItem_T Stack_pop(Stack_T stk) { Item_T x; struct List *p; assert(stk != NULL); assert(stk->head != NULL); x = stk->head->val; p = stk->head; stk->head = stk->head->next; free(p); return x;}head3 2 121Client Program: Uses
View Full Document
Unlocking...