Library Functions

Library Functions

CS xxxx -- CS 2123 Data Structures Do Quiz10 Do Quiz11 Ch 8 Abstract Data Types STACK Turgay Korkmaz Office: NPB 3.330 Phone: (210) 458-7346 Fax: (210) 458-4437 e-mail: [email protected] web: www.cs.utsa.edu/~korkmaz 1 Objectives To appreciate the concept and purpose of abstract data types, or ADTs To understand both the abstract behavior and the underlying implementation of the stack data type To be able to use incomplete type mechanism in ANSI C to define ADTs

To recognize that ADTs provide an attractive alternative to maintaining encapsulated state within a module. To understand the design and implementation of a scanner abstraction based on ADTs (self-study) 2 Data Structure hierarchy The atomic data typessuch as int, char, double, and enumerated typesoccupy the lowest level in the hierarchy. To represent more complex information, we combine the atomic types to form larger structures (e.g., struct A {}). These larger structures can then be assembled into even larger ones in an open-ended process using pointers. Collectively, these assemblages of atomic types records (struct {..})

data structures (stack, list, trees, graphs) 3 Abstract data Type (ADT) It is usually far more important to know how a data structure behaves rather than how it is represented or implemented A type defined in terms of its behavior rather than its representation is called an abstract data type (ADT) ADTs are defined by an interface (recall ch08a-ch03) Simplicity. Hiding the internal representation from the client means that there are fewer details for the client to understand. Flexibility. Because an ADT is defined in terms of its behavior, the lib programmer who implements one is free to change its underlying representation. As with any abstraction, it is appropriate to change the implementation as long as the interface remains the same so application programmer will not know the changes in lib implementation. 4

Security. The interface boundary acts as a wall that protects the C Stacks B A To understand the concept of ADT, we consider a specific data structure, namely stack a storage for a collection of data values (elements) values are removed from a stack in the opposite order from which they were added, so that the last item added to a stack is always the first item that gets removed. Adding a new element to a stack is called pushing Removing the most recent item from a stack is 5 called popping The Stack Metaphor A stack is a data structure in which the elements are accessible only in a last-in/first-out order.

The fundamental operations on a stack are push, which adds a new value to the top of the stack, and pop, which removes and returns the top value. One of the most common metaphors for the stack concept is a spring-loaded storage tray for dishes. Adding a new dish to the stack pushes any previous dishes downward. Taking the top dish away allows the dishes to pop back up. C B A Stacks turn out to be particularly useful in a variety of programming applications. APPLICATIONS OF STACKS 7 Applications of Stacks The primary reason that stacks are important in programming is that nested function calls behave in a stack-oriented fashion, recall Fact(n) example Compiler example: check if bracketing operators (parentheses, brackets, and curly braces) in a string are properly matched. {

[()]} Pocket calculator example from the textbook. 8 Exercise: check bracketing operators Write a C program that checks whether the bracketing operators (parentheses, brackets, and curly braces) in a string are properly matched. As an example of proper matching, consider the string { s = 2 * (a[2] + 3); x = (1 + (2)); } If you go through the string carefully, you discover that all the bracketing operators are correctly nested, with each open parenthesis matched by a close parenthesis, each open bracket matched by a close bracket, and so on. OperatorMatching Enter string: { s = 2 * (a[2] + 3); x = (1 + (2)); } Brackets are properly nested Enter string: (a[2] + b[3) Brackets are incorrect Enter string: If we have a Stack ADT, it will be easy to solve this problem HOW? We will give actual imp

later. Exercise: Stacks and pocket calculators Suppose you want to compute 50.0 * 1.5 + 3.8 / 2.0 In a (reverse Polish notation, or RPN) calculator, you will do this as follows: ENTER: PUSH the previous value on a stack Arithmetic operator (+ - * / ): if the user has just entered a value push it on the stack We will give Apply the operator actual imp POP the top two values from stack Apply the arithmetic OP later. 10 stack.h defines the behavior of Stack ADT

(interface) Export data types Export prototypes for public functions (new_stack, push, pop, etc.) stack.c implements the public and private functions stack lib DEVELOPING A STACK ADT 11 Defining stack.h Interface #ifndef _stack_h textbook */ #define _stack_h /* for comments see actual stack.h in the //#include "genlib.h // #define New(ptr_t) ((ptr_t) malloc(sizeof *((ptr_t) NULL))) #typedef int bool; typedef double stackElementT; // double char, void *, etc typedef struct stackCDT *stackADT; stackADT

NewStack(void); void FreeStack(stackADT stack); void Push(stackADT stack, stackElementT element); stackElementT Pop(stackADT stack); bool StackIsEmpty(stackADT stack); bool StackIsFull(stackADT stack); int StackDepth(stackADT stack); stackElementT GetStackElement(stackADT stack, int index); #endif 12 Data Types in Stack ADT When implementing stack ADT, we need to consider two important types:

The type of the element stored in the stack The type of the stack data structure itself We must decide whether each type is part of the library implementation or part of the clients domain/application 13 First think about stack element type For example: double in calculator and char in bracket matching Stack element type belongs to the clients domain/application Stack library implementation should not worry about the type of elements. All it needs to store and return an element with any type So if C had any type, we would simply use any for data elements (some languages have this called polymorphism)

But, C has no such type and requires specific types when the exported functions declare their parameters The closest thing C provides is the type void * which is compatible with any pointer type SO, ONE SOLUTION TO DECIDING THE TYPE OF STACK ELEMENT Define stack element type as void * Let client application allocate memory for any element and give its pointer to stack ATD Our Stack ADT will push/pop pointers to/from stack (GREAT FLEXIBILITY) but 14 For some applications dealing with pointers might be to complicated and stack element type (second solution) If you allow client to access the source code of stack library or package, you can increase the flexibility and efficiency by using typedef In stack.h define typedef double StackElementT; If client wants to use stack ADT with char type, all he/she needs to do is to change the above definition with typedef char StackElementT;

- Client will edit stack.h (violates principle of abstraction) - Client should have the source code to compile There is no optimal design strategy. The best you can 15 The type of the stack itself Stack type definitely belongs to the library implementation of stack ADT Your implementation should be able to push values of StackElementT onto a stack retrieve them in a LIFO order when popped To perform these operations, you need to choose a representation for stack Client should not see the

16 Opaque type In stack.h, we can define an opaque type such that its underlying representation is hidden from client (it is later implemented in stack.c) typedef struct nameCDT *nameADT; For Stack ADT: Concret Abstract Data e Type We will have the following incomplete type in stack.h typedef struct stackCDT *stackADT; We then define the concrete type in implementation stack.c struct stackCDT { 17 Defining stack.h Interface #ifndef _stack_h textbook */ #define _stack_h

/* for comments see actual stack.h in the As library // #include "genlib.h developer // #define New(ptr_t) ((ptr_t) malloc(sizeof *((ptr_t) NULL))) we need to #typedef int bool; also implement typedef double stackElementT; // char, void *, etc stack.c typedef struct stackCDT *stackADT; For the stackADT NewStack(void); time being, suppose void FreeStack(stackADT stack); void Push(stackADT stack, stackElementT element); we implement stackElementT Pop(stackADT stack); ed stack.c bool StackIsEmpty(stackADT stack); So stack lib bool StackIsFull(stackADT stack); is ready to int StackDepth(stackADT stack); be used by stackElementT GetStackElement(stackADT stack, int index);application 18 s.

#endif #ifndef _stack_h textbook */ #define _stack_h /* for comments see actual stack.h in the // #include "genlib.h // #define New(ptr_t) ((ptr_t) malloc(sizeof *((ptr_t) NULL))) #typedef int bool; typedef double stackElementT; // char, void *, etc typedef struct stackCDT *stackADT; stackADT NewStack(void); void FreeStack(stackADT stack); void Push(stackADT stack, stackElementT element); stackElementT Pop(stackADT stack); bool StackIsEmpty(stackADT stack); bool StackIsFull(stackADT stack); int StackDepth(stackADT stack); stackElementT GetStackElement(stackADT stack, int index); #endif APPLICATIONS OF STACK ADT 19 stack.h: bracket.c #include "stack.h" /* other libraries */ main()

{ stackADT stack1; char *line; char ch; int i; stack1 = NewStack(); printf("> "); line = GetLine(); /* suppose we have */ typedef char stackElementT; for(i=0; i < strlen(line); i++){ if( line[i]=={ || line[i]==[ || line[i]==( ) push(stack1, line[i]); if (line[i]==} && pop(stack1) != {) break; if (line[i]==] && pop(stack1) != [) break; if (line[i]==) && pop(stack1) != () break; } if (StackIsEmpty(stack1)) printf(Brackets are properly nested\n); else printf(Brackets are not properly nested\n); Is this FreeStack(stack1); library! } working? GetLine(); // is from the textbooks You can implement it too, as we provided in Assing 2 How

It dynamically allocates memory and gets the whole input line as about a [ } String. Instead, you can also use fgets() but you have to allocate space in > gcc bracket.c stack.c o advance bracket For example: > bracket 20 stack.h: rpncalc.c #include "stack.h" /* other libraries */ /* suppose we have */ main() typedef double stackElementT; { stackADT operandStack; char *line; char ch; operandStack = NewStack(); while ( 1 ) { printf("> "); line = GetLine(); ch = toupper(line[0]); switch (ch) { case 'Q': exit(0); case 'H': HelpCommand(); break; case 'C': ClearStack(operandStack); break; case 'S': DisplayStack(operandStack);

break; default: if (isdigit(ch)) { Push(operandStack, StringToReal(line)); } else { ApplyOperator(ch, operandStack); } break; void ApplyOperator(char op, stackADT operandStack) { double lhs, rhs, result; rhs = Pop(operandStack); lhs = Pop(operandStack); switch (op) { case '+': result = lhs + rhs; break; case '-': result = lhs - rhs; break; case '*': result = lhs * rhs; break; case '/': result = lhs / rhs; break; default: Error("Illegal operator %c", op); } printf("%g\n", result); Push(operandStack, result); } static void ClearStack(stackADT stack) { while (!StackIsEmpty(stack)) { (void) Pop(stack); } } static void DisplayStack(stackADT stack)

{ int i, depth; printf("Stack: "); depth = StackDepth(stack); } static void HelpCommand(void) 21 EXERCISES 22 Exercise: Reimplementation of Proper matching of { ( [ ] ) } Write a C program that checks whether the bracketing operators (parentheses, brackets, and curly braces) in a string are properly matched. #ifndef _stack_h #define _stack_h For example, // #include "genlib.h //#define New(ptr_t) ((ptr_t) malloc(sizeof *((ptr_t) NULL))) #typedef int bool; typedef

{ s = 2 * (a[2] + 3); x = (1 + (2)); } is a proper matching, Suppose you cannot change stack.h and it exports typedef void *stackElementT; Home void *stackElementT; typedef struct stackCDT *stackADT; stackADT NewStack(void); void FreeStack(stackADT stack); void Push(stackADT stack, stackElementT element); stackElementT Pop(stackADT stack); bool StackIsEmpty(stackADT stack); bool StackIsFull(stackADT stack); int StackDepth(stackADT stack); stackElementT GetStackElement(stackADT stack,23 int index); M th od is ify stack.h: bracket.c #include "stack.h" /* other libraries */ main() { stackADT stack1;

char *line; char ch; int i; stack1 = NewStack(); printf("> "); line = GetLine(); /* suppose we have */ typedef void *stackElementT; for(i=0; i < strlen(line); i++){ if( line[i]=={ || line[i]==[ || line[i]==( ) push(stack1, line[i]); if (line[i]==} && pop(stack1) != {) break; if (line[i]==] && pop(stack1) != [) break; if (line[i]==) && pop(stack1) != () break; } if (StackIsEmpty(stack1)) printf(Brackets are properly nested\n); else printf(Brackets are not properly nested\n); FreeStack(stack1); } > gcc bracket.c stack.c > bracket 24 of RPN calculator and Proper matching

#ifndef _stack_h #define _stack_h Suppose you cannot change stack.h and instead of chartypedef void *stackElementT; or double, it currently exports typedef void *stackElementT; Given this version of stack.h, implement RPN calc and proper matching What will be the main difference? #include "genlib.h // #define New(ptr_t) ((ptr_t) malloc(sizeof *((ptr_t) NULL))) #typedef int bool; typedef struct stackCDT *stackADT; stackADT NewStack(void); void FreeStack(stackADT stack); void Push(stackADT stack, stackElementT element); stackElementT Pop(stackADT stack); bool StackIsEmpty(stackADT stack); bool StackIsFull(stackADT stack); int StackDepth(stackADT stack); stackElementT GetStackElement(stackADT stack, int index);

#endif Ho xe me rc is e Dynamically allocate memory for each 25 M th od is ify stack.h: rpncalc.c #include "stack.h" /* other libraries */ main() { stackADT operandStack; string line; char ch; operandStack = NewStack(); while (TRUE) { printf("> "); line = GetLine(); ch = toupper(line[0]); switch (ch) { case 'Q': exit(0);

case 'H': HelpCommand(); break; case 'C': ClearStack(operandStack); break; case 'S': DisplayStack(operandStack); break; default: if (isdigit(ch)) { Push(operandStack, StringToReal(line)); } else { ApplyOperator(ch, operandStack); } break; void ApplyOperator(char op, stackADT operandStack) { double lhs, rhs, result; rhs = Pop(operandStack); lhs = Pop(operandStack); switch (op) { case '+': result = lhs + rhs; break; case '-': result = lhs - rhs; break; case '*': result = lhs * rhs; break; case '/': result = lhs / rhs; break; default: Error("Illegal operator %c", op); } printf("%g\n", result); Push(operandStack, result); } static void ClearStack(stackADT stack) { while (!StackIsEmpty(stack)) { (void) Pop(stack);

} } static void DisplayStack(stackADT stack) { int i, depth; printf("Stack: "); depth = StackDepth(stack); } static void HelpCommand(void) 26 // app.c #include stack.h void main() { stackADT s1; char ch; s1 = NewStack(); #ifndef _stack_h textbook */ #define _stack_h /* for comments see actual stack.h in the #include "genlib.h // #define New(ptr_t) ((ptr_t) malloc(sizeof *((ptr_t) NULL))) #typedef int bool; typedef char stackElementT; // double, char, void *, etc

typedef struct stackCDT *stackADT; Push(s1, A); Push(s1, B); Push(s1, C); ch = Pop(s1); stackADT NewStack(void); void FreeStack(stackADT stack); void Push(stackADT stack, stackElementT element); stackElementT Pop(stackADT stack); bool StackIsEmpty(stackADT stack); bool StackIsFull(stackADT stack); } int StackDepth(stackADT stack); stackElementT GetStackElement(stackADT stack, int index); // gcc app.c stack.c o app #endif IMPLEMENTATION OF STACK.C 27 typedef struct stackCDT *stackADT; Concrete Data Type (CDT) First provide a concrete representation for abstract type stackADT in stack.c

Suppose we decided to use ARRAY to hold elements on the stack #define MaxStackSize 100 struct stackCDT { stackElementT elements[MaxStackSize]; int count; }; We then implement the exported (public) and private functions based on 28 stack.c #include stack.h /* other libraries */ #define MaxStackSize 100 struct stackCDT { stackElementT elements[MaxStackSize]; int count; }; #include stack.h void main() { stackADT s1; char ch; s1 = NewStack(); FreeStack(s1); } stackADT NewStack(void)

{ stackADT stack; // stack = New(stackADT); // stack=(struct stackCDT *) malloc(sizeof(struct stackCDT)); // stack=(stackADT) malloc(sizeof(struct stackCDT)); stack=(stackADT) malloc(sizeof *stack); if(!stack) return NULL; stack->count = 0; return (stack); } void FreeStack(stackADT stack) 29 stack.c 0 1 2 3 99 elements count = 0 }

#include stack.h void main() { stackADT s1; char ch; s1 = NewStack(); Push(s1, A); ch = Pop(s1); } void Push(stackADT stack, stackElementT element) { stack->elements[stack->count] = element; stack->count++; stackElementT Pop(stackADT stack) { stack->count--; return(stack->elements[stack>count]); } bool StackIsEmpty(stackADT stack) { return (stack->count == 0); } bool StackIsFull(stackADT stack) { return (stack->count == MaxStackSize ); 30 } 0 1

2 3 99 elements count = 0 #include stack.h void main() { Push(s1, A); ch = Pop(s1); } stack->elements[stack->count] = element; stack->count++; stack->count--; return(stack->elements[stack>count]); stack.c Check possible errors. void Push(stackADT stack, stackElementT element) { if (StackIsFull(stack) Error(Stack Size exceeds); stack->elements[stack->count++] =

element; } stackElementT Pop(stackADT stack) { if (StackIsEmpty(stack)) Error("Pop of an empty stack"); } return (stack->elements[--stack->count]); 31 stack.c (contd) int StackDepth(stackADT stack) { return (stack->count); } count elements index F 0 E 1 D 2

C 3 B 4 A 5 [6] [5] stackElementT GetStackElement(stackADT stack, [4] int index) [3] { [2] if (index < 0 || index >= stack->count) { [1] Error("Non-existent stack element"); } [0] return (stack->elements[stack->count - index - 1]); } 32 #ifndef _stack_h textbook */ #define _stack_h /* for comments see actual stack.h in the

#include "genlib.h // #define New(ptr_t) ((ptr_t) malloc(sizeof *((ptr_t) NULL))) #typedef int bool; typedef double stackElementT; // char, void *, etc typedef struct stackCDT *stackADT; Do Quiz 10 magic ADT stackADT NewStack(void); void FreeStack(stackADT stack); void Push(stackADT stack, stackElementT element); stackElementT Pop(stackADT stack); bool StackIsEmpty(stackADT stack); bool StackIsFull(stackADT stack); int StackDepth(stackADT stack); stackElementT GetStackElement(stackADT stack, int index); #endif ANOTHER IMPLEMENTATION OF STACK.C 33 Improving stack.c implementation using dynamic array while keeping stack.h as is #include stack.h /* and other libraries */ #define InitialStackSize 100// instead of #define MaxStackSize 100 struct stackCDT { stackElementT *elements;struct stackCDT {

stackElementT int count; elements[MaxStackSize]; int size; int count; }; /* Prototype for Private functions, NOT }; exported in stack.h */ static void ExpandStack(stackADT stack); stackADT NewStack(void) { stackADT stack; // stack = (stackADT) malloc(sizeof(struct stackCDT)); stack = (stackADT) malloc(sizeof *stack); if(!stack) return NULL; stack->elements = malloc(InitialStackSize * sizeof(stackElementT)); // if NULL stack->count = 0; stack->size = InitialStackSize; return (stack); 34 void Push(stackADT stack, stackElementT element) { if (stack->count == stack->size) ExpandStack(stack); stack->elements[stack->count++] = element; } stackElementT Pop(stackADT stack) { if (StackIsEmpty(stack)) Error("Pop of an empty stack"); return (stack->elements[--stack->count]); 0 1 2 3 } bool StackIsEmpty(stackADT stack)

{ return (stack->count == 0); } bool StackIsFull(stackADT stack) { return (FALSE); } void FreeStack(stackADT stack) { free(stack->elements); free(stack); } 99 elements = count = 0 size=100 35 int StackDepth(stackADT stack) { return (stack->count); } stackElementT GetStackElement(stackADT stack, int index) { if (index < 0 || index >= stack->count) { Error("Non-existent stack element"); } 0 -1 return (stack->elements[stack->count - index

1]); 2 } /* Private functions, NOT exported in stack.h */ static void ExpandStack(stackADT stack) elements = { count = 0 stackElementT *array; size=100 int i, newSize; 3 newSize stack->size * 2;* sizeof(stackElementT)); // if array = = malloc(newSize NULL = NewArray(newSize, stackElementT); array for (i = 0; i < stack->count; i++) { array[i] = stack->elements[i]; } free(stack->elements); // FreeBlock(stack->elements); stack->elements = array; stack->size = newSize; 99 36 Do Quiz 11 Exercise

Suppose we want to implement an opposite function to ExpandStack that we call Shrink(stack). It will be called when the number of elements in stack is less than the quarter of the current size of the array and the current size of the array is larger than 200. 37 /**** stack.h is the same ****/ typedef double stackElementT; typedef struct stackCDT *stackADT; /* . exported functions .. */ ---------------------------------------------/**** improved stack.c ****/ #define InitialStackSize100 struct stackCDT{ stackElementT *elements; int count; int size; }; stackElementT Pop(stackADT stack) { if (StackIsEmpty(stack)) Error("Pop of an empty stack"); if(stack->count < stack->size / 4 && stack->size > 200) Shrink(stack); return (stack->elements[--stack->count]); } static void Shrink(stackADT stack) { }

38 struct stackCDT { struct stackCDT { stackElementT elements[MaxStackSize]; stackElementT elements[MaxStackSize]; } int count; static int count; }; Danger of Encapsulated State You can declare a global variable in a module to maintain state between functions (e.g., randword.c, scanadt.h in previous book) static will make it private (encapsulated state) The module that uses it can have only one copy of the state information, OP T

So we cannot use that module in different parts of the program In case of layered abstractions, client may not know anything about the underlying modules and use them in different places, resulting in error ADT provide a safe alternative to 39

Recently Viewed Presentations

  • Science 90

    Science 90

    WHMIS / GHS Workplace Hazardous Materials Information System Globally Harmonized System (WHMIS 2.0) WHMIS / GHS is a system of warning symbols and information sheets which detail the danger, safe handling and disposal of a variety of chemical substances in...
  • NABL Preparation

    NABL Preparation

    Haematologyand Immunohaematology. Microbiology and Serelogy. Histopathology . Cytopathology. Genetics Nuclear Medicine (in-vitro . tests only) Application. The scope of accreditation which includes. materials or items tested. specific tests or types of tests performed .
  • ADVANCED STRATEGIES LAB Welcome to SBCEs Advanced Strategies

    ADVANCED STRATEGIES LAB Welcome to SBCEs Advanced Strategies

    - The LEGO® name is made from the first two letters of the Danish words LEG GODT, meaning "play well". - The LEGO Group patented the LEGO brick with the familiar tubes inside and studs on top on 28 January...
  • 233S16 FINAL REVIEW - Purdue University

    233S16 FINAL REVIEW - Purdue University

    blood-letting by gods to feed earth. Descent into Mictlan. Quetzalcoatl and spirit-double (nahualli) Xolotl retrieve bones. Mountain of Sustenance. contains maize. Quetzalcoatl fails to retrieve it. Nanahuatzin(Lame Pimply God) splits mountain with lightning. servants of Tlaloc (Rain God) steal maize
  • weather_test_online_rya - skysailtraining

    weather_test_online_rya - skysailtraining

    b) Sea heaps up, spray, breaking waves, foam blows in streaks. Force 5 17-21 knots Force 7 28-33 knots Occluded Front Buys Ballot's Law in the Northern Hemisphere, if you stand with your back to the wind, the area of...
  • Energy for Schools - Birmingham Diocesan Education Service

    Energy for Schools - Birmingham Diocesan Education Service

    Energy for Schools. Replicate success of parishes energy buying group (20 dioceses buying together). OJEU compliant contract. Partnered with IFM. Invitation to Birmingham- join NOTT, WES, NOR
  • Healthcare Information Technology Standards Panel 2006, 2007 and

    Healthcare Information Technology Standards Panel 2006, 2007 and

    We use a HITSP developed comment tracking database to track all submitted comments. This helps us ensure all comments are addressed. Before we send any Interoperability Specifications to the HITSP Panel for approval, we ensure the Technical Committees or Work...
  • Product Updates: Surveys on Labour, Household Spending ...

    Product Updates: Surveys on Labour, Household Spending ...

    Product Updates: Surveys on Labour, Household Spending, Justice, and Post-Census . DLI Ontario Training. December 7, 2016. Jane Fry and Kristi Thompson