DOC PREVIEW
Princeton COS 217 - Function Pointers and Abstract Data Types

This preview shows page 1-2-3-24-25-26 out of 26 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Function Pointers and Abstract Data TypesGoals of Today’s LectureData TypesType ConversionCasting: Explicit ConversionsWriting Software for Various TypesSorting an Array of IntegersInteger Sorting ExampleInteger Sorting FunctionSorting an Array of StringsString Sorting FunctionCreating a Generic FunctionGeneralizing: Void PointersVoid Pointers in SortGeneric Sort FunctionUsing Generic Sort With StringUsing Generic Sort With IntegersMaking “Array” an ADTArray ADT: InterfaceClient Using Array ADT: StringsClient Using Array ADT: IntegersArray ADT ImplementationArray ADT Implementation (Cont)Array ADT Implementation (Cont.)Slide 25Summary1Function Pointers and Abstract Data TypesProfessor Jennifer RexfordCOS 2172Goals of Today’s Lecture•Data typesType conversionWorking around the limitations of types•Function pointersSorting an array of integers, or of stringsSorting an array of any type–Void pointers and casting–Pointers to functions•Abstract Data TypesMaking “array” an ADT3Data Types•Ultimately, all data is represented as bitsUsually manipulated at the level of bytes or wordsCan be interpreted by machine code instructions•A type is attribute of a piece of dataTells the computer something about the dataConstraints on the data–What values it can take–What operations may be performed•Ultimately determines what machine code is runCompiler generates machine code appropriate to the type, to interpret the bits (or bytes) as intended4Type Conversion•Changing an entity of one data type to anotherFor more efficient storage (values from more limited set)–E.g., int from getchar() stored later as a char–E.g., double as an int when no fractional partTo enable operations not otherwise possible–E.g., square root of an integer input•Implicit vs. explicit conversionCoercion: implicit conversion by the compiler–E.g., sqrt(2) implicitly sqrt((double) 2)Casting: explicit conversion specified by programmer–E.g, (int) f to extract integer portion of f5Casting: Explicit Conversions•Sometimes useful to make conversion explicitDocumentation: making implicit type conversions explicit–E.g., getting the integer part of a floating-point number–Done by int_part = (int) float_number;Control: overrule compiler by forcing conversions –E.g., getting fractional part of a floating-point number–Done by frac_part = f – (int) f;6Writing Software for Various Types•But, sometimes types get in our wayLimiting the generality of a function we writeSo that it can only run for data of a single type•Void pointers as a way outStore and manipulate data indirectly, using pointersManipulating the addresses where data are stored… rather than the data directly•But, sometimes type-specific operations are neededE.g., comparison operator (“>” for int, strcmp() for strings)•Function pointers are a way outRather than putting type-specific code in the functionPass a pointer to another function for type-specific actions… and simply call the function where needed7Sorting an Array of Integers•Example problemInput: array v of n integersOutput: array in sorted order, from smallest to largest•Many ways to sort, but three common aspectsComparison between any two elementsExchange to reverse the order of two elementsAlgorithm making comparisons and exchanges till done•Simple approachGo one by one through the n array elementsBy the end of step i, get ith smallest value in element i–Compare element i with all elements after it–Swap values if the ith element is larger8Integer Sorting Example7 2 9 69 62 7v[0] > v[1]?Yes, swap9 62 7v[0] > v[2]?9 62 7v[0] > v[3]?9 62 7v[1] > v[2]?9 62 7v[1] > v[3]?Yes, swap9 72 6…9Integer Sorting Functionvoid sort(int *v, int n){ int i, j; for (i = 0; i < n; i++) { for (j = i+1; j < n; j++) { if (v[i] > v[j]) { int swap = v[i]; v[i] = v[j]; v[j] = swap; } } }}comparisonswap10Sorting an Array of Strings•Data types are differentArray elements are char* Swap variable is char*•Comparison operator is differentThe greater-than (“>”) sign does not workNeed to use strcmp() function instead“the”0123“quick”“brown”“fox”“the”0123“quick”“brown”“fox”11String Sorting Functionvoid sort(char *v[], int n){ int i, j; for (i = 0; i < n; i++) { for (j = i+1; j < n; j++) { if (strcmp(v[i], v[j]) > 0) { char* swap = v[i]; v[i] = v[j]; v[j] = swap; } } }}12Creating a Generic Function•Generic function A single sort() function that works for all data types•C’s notion of data types is getting in our wayWe need to accept parameters in any type–sort(int *v, int n) is only good for integer arrays–sort(char *v[], int n) is only good for string arraysWe need to have local variables of any type–int swap is only good for swapping integers–char* swap is only good for swapping strings•Different types need different comparison operatorsGreater-than sign (“>”) is only good for numerical typesstrcmp() is only good for stringsWe need to be able to tell sort() what comparison function to use13Generalizing: Void Pointers•Generic pointers are the same as any other pointerExcept they point to a variable with no specific typeExample: void *datap = “CS217”;•Difference:Regular pointers: compilers“know” what they point tovoid pointers: compilers “don’t know” what they point to•Common uses:Abstract data typessupporting polymorphism*Pass pointer to function thatcould be any of several typesMemory0x000000000x100053840x100053840xFFFFFFFF`C` `S` `2` `1``7` `\0`datap* Allowing the same definitions to be used with different types of data14Void Pointers in Sort•Function parametersInput: array of pointers to some unknown type•Local swap variablePointer to some unknown type•But, what about the comparison step?Need to be able to pass a function to sortvoid *swap = v[i];v[i] = v[j];v[j] = swap;void sort(void *v[], int n)15Generic Sort Functionvoid sort(void *v[], int n, int (*compare)(void *datap1, void *datap2)){ int i, j; for (i = 0; i < n; i++) { for (j = i+1; j < n; j++) { if ((*compare)(v[i], v[j]) > 0) { void *swap = v[i]; v[i] = v[j];


View Full Document

Princeton COS 217 - Function Pointers and Abstract Data Types

Documents in this Course
Summary

Summary

4 pages

Lecture

Lecture

4 pages

Generics

Generics

14 pages

Generics

Generics

16 pages

Lecture

Lecture

20 pages

Debugging

Debugging

35 pages

Types

Types

7 pages

Lecture

Lecture

21 pages

Assembler

Assembler

16 pages

Lecture

Lecture

20 pages

Lecture

Lecture

39 pages

Testing

Testing

44 pages

Pipeline

Pipeline

19 pages

Lecture

Lecture

6 pages

Signals

Signals

67 pages

Building

Building

17 pages

Lecture

Lecture

7 pages

Modules

Modules

12 pages

Generics

Generics

16 pages

Testing

Testing

22 pages

Signals

Signals

34 pages

Lecture

Lecture

19 pages

Load more
Download Function Pointers and Abstract Data Types
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Function Pointers and Abstract Data Types and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Function Pointers and Abstract Data Types 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?