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 typesType conversionWorking around the limitations of types•Function pointersSorting an array of integers, or of stringsSorting an array of any type–Void pointers and casting–Pointers to functions•Abstract Data TypesMaking “array” an ADT3Data Types•Ultimately, all data is represented as bitsUsually manipulated at the level of bytes or wordsCan be interpreted by machine code instructions•A type is attribute of a piece of dataTells the computer something about the dataConstraints on the data–What values it can take–What operations may be performed•Ultimately determines what machine code is runCompiler generates machine code appropriate to the type, to interpret the bits (or bytes) as intended4Type Conversion•Changing an entity of one data type to anotherFor 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 partTo enable operations not otherwise possible–E.g., square root of an integer input•Implicit vs. explicit conversionCoercion: 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 explicitDocumentation: 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 wayLimiting the generality of a function we writeSo that it can only run for data of a single type•Void pointers as a way outStore and manipulate data indirectly, using pointersManipulating the addresses where data are stored… rather than the data directly•But, sometimes type-specific operations are neededE.g., comparison operator (“>” for int, strcmp() for strings)•Function pointers are a way outRather than putting type-specific code in the functionPass a pointer to another function for type-specific actions… and simply call the function where needed7Sorting an Array of Integers•Example problemInput: array v of n integersOutput: array in sorted order, from smallest to largest•Many ways to sort, but three common aspectsComparison between any two elementsExchange to reverse the order of two elementsAlgorithm making comparisons and exchanges till done•Simple approachGo one by one through the n array elementsBy 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 differentArray elements are char* Swap variable is char*•Comparison operator is differentThe greater-than (“>”) sign does not workNeed 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 wayWe 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 arraysWe 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 operatorsGreater-than sign (“>”) is only good for numerical typesstrcmp() is only good for stringsWe need to be able to tell sort() what comparison function to use13Generalizing: Void Pointers•Generic pointers are the same as any other pointerExcept they point to a variable with no specific typeExample: void *datap = “CS217”;•Difference:Regular pointers: compilers“know” what they point tovoid 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 parametersInput: array of pointers to some unknown type•Local swap variablePointer 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