Abstract Data Types (ADTs), After More on the HeapPreparing for the Midterm ExamA Little More About the Heap…Example: Read a Line (or URL)Problem: Need Storage for String Problem: Input Longer Than ArrayProblem: How Much Storage?Really Solving the ProblemAbstract Data Types (ADTs) Abstract Data Type (ADT)An ADT Example: StacksNotes on stack.hStack Implementation: ArrayCareful Checking With AssertStack Implementation: Array (Cont.)Problems With Array ImplementationLinked List Would be Better…Popping and PushingStack Implementation: Linked ListStack Implementation: Linked Liststack.c, continuedClient Program: Uses InterfaceProblem: Multiple Kinds of Stacks?ConclusionsBackup Slides on Void Opaque PointersStack Implementation (with void*)stack.c (with void*) continuedstack.c (with void*) continuedClient Program (With Void)Structural Equality TestingAlmost, But Not Quite...Item ADT Provides Equal TestFunction PointersPassing a Function Pointer1Abstract Data Types (ADTs),After More on the HeapProf. David AugustCOS 2172Preparing for the Midterm Exam• Exam logisticso Date/time: Thursday October 26 in lectureo Open books, open notes, open mind, but not open laptop/PDAo Covering material from lecture, precept, and reading, but not tools• Preparing for the midtermo Lecture and precept materials available onlineo Course textbooks, plus optional books on reserveo Office hours and the course listservo Old midterm exams on the course Web site3A Little More About the Heap…• Memory layout of a C programo Text: code, constant datao Data: initialized global & static variableso BSS: uninitialized global & static variableso Heap: dynamic memoryo Stack: local variables• Purpose of the heapo Memory allocated explicitly by the programmero Using the functions malloc and free• But, why would you ever do this???o Glutton for punishment???00xffffffffTextDataBSSHeapStack4Example: Read a Line (or URL)• Write a function that reads a word from stdino Read from stdin until encountering a space, tab, ‘\n’, or EOFo Output a pointer to the sequence of characters, ending with ‘\0’• Example code (very, very buggy)#include <stdio.h>int main(void) {char* buf;scanf(“%s”, buf);printf(“Hello %s\n”, buf);return 0;}5Problem: Need Storage for String • Improving the codeo Allocate storage space for the stringo Example: define an array• Example (still somewhat buggy)#include <stdio.h>int main(void) {char buf[64];scanf(“%s”, buf);printf(“Hello %s\n”, buf);return 0;}6Problem: Input Longer Than Array• Improving the codeo Don’t allow input that exceeds the array size• Example (better, but not perfect)#include <stdio.h>int main(void) {char buf[64];if (scanf(“%63s”, buf) == 1)printf(“Hello %s\n”, buf);elsefprintf(stderr, Input error\n”);return 0;}7Problem: How Much Storage?• Improving the codeo Finding out how much space you need from the usero Allocate exactly that much space, to avoid wasting• Beginning of the example (is this really better?)int main(void) {int n;char* buf;printf(“Max size of word: “);scanf(“%d”, &n);buf = malloc((n+1) * sizeof(char));scanf(“%s”, buf);printf(“Hello %s\n”, buf);return 0;}8Really Solving the Problem• Remaining problemso User can’t input long words o Storage wasted on short words• But, how do we proceed?o Too little storage, and we’ll run pass the end or have to truncateo Yet, we don’t know how big the word might be• The gist of a solution o Pick a storage size (“line_size”) and read up to that lengtho If we stay within the limit, we’re doneo If the user input exceeds the space, we can – Allocate space for another line, and keep on reading – At the end, allocate one big buffer and copy all the lines into it9Abstract Data Types (ADTs)10Abstract Data Type (ADT)• An ADT module provides:o Data typeo Functions that operate on the type• Client does not manipulate the data representation directlyo The client should just call functions• “Abstract” because the observable results (obtained by client) are independent of the data representation• Programming language support for ADTo Ensure that client cannot possibly access representation directlyo C++, Java, other object-oriented languages have privatefieldso C has opaquepointers11An ADT Example: Stacks• LIFO: Last-In, First-Out• Like the stack of trays at the cafeteriao “Push” a tray onto the stacko “Pop” a tray off the stack• Useful in many contexts12Stack Interface (stack.h)#ifndef STACK_INCLUDED#define STACK_INCLUDEDtypedef struct Item *Item_T;typedef struct Stack *Stack_T;extern Stack_T Stack_new(void);extern int Stack_empty(Stack_T stk); extern void Stack_push(Stack_T stk, Item_T item);extern Item_T Stack_pop(Stack_T stk); #endifWhat’s this for?13Notes on stack.h•Type Stack_T is an opaque pointero Clients can pass Stack_T around but can’t look inside•Type Item_T is also an opaque pointero … but defined in some other ADT•Stack_ is a disambiguating prefixo A convention that helps avoid name collisions14Stack 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; }15Careful 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!16Stack 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];}17Problems With Array ImplementationCAPACITY too large: waste memoryCAPACITY too small: assertion failure (if you were careful)buffer overrun (if you were careless)wasted spacedatadata18Linked List Would be Better…nextvalheadhead3 2 1empty stackpush(1); push(2); push(3);struct Stack {int val; struct Stack *next;} *head;19Popping and Pushingpop( );head3 2 1head3 2 1head3 2 14 push(4);20Stack Implementation: Linked Liststack.c#include <assert.h>#include
View Full Document
Unlocking...