University of Washington Computer Programming I Lecture 20 Nested Data Structures 2000 UW CSE U 1 Overview Data representation in C Arrays of structs structs containing arrays Sorting an array of structs U 2 Data Representation in C Simple data types int double char Atomic chunks of data cannot be pulled apart into components Composite data Arrays Structs U 3 Composite Data Arrays Sequence of variables all of the same type structs Collection of fields of possibly different types Key point variables of any type can be a component of an array or struct including an array or struct U 4 Nested structs Example typedef struct a single point double x y point typedef struct a size double width height dimension typedef struct description of rectangle dimension size point lower left int line color fill color rectangle U 5 Nested struct Layout typedef struct double x y point typedef struct double width height dimension typedef struct dimension size point lower left int line color fill color rectangle variable declaration rectangle r r width size height lower left x y line color fill color U 6 Field Selection Use the operator to select a field If the field it itself a struct use again to select its components r r lower left r lower left x r size width height lower left x y line color fill color U 7 Structures and Arrays A struct represents a single record Typically computer applications have to deal with collections of such records Examples student records employee records customer records parts records In each case we will have multiple instances of one record struct type Arrays of structs are the natural way to do this U 9 Components in struct Arrays pentagon an array of points x y x y pentagon 1 a point structure x y pentagon 4 x a double x y x y point pentagon 5 U 10 Arrays in structs The fields in a struct can themselves be an array Common example strings arrays of char define MAX NAME 40 typedef struct char name MAX NAME 1 int id double score student record U 11 Review structs as Parameters A single struct is passed by value all of its components are copied from the argument actual parameter to initialize the formal parameter even if they are arrays unless you use pointers explicitly point midpoint point a point b int main void point p1 p2 m declare 3 points m midpoint p1 p2 U 14 Passing Arrays of structs An array of structs is an array When any array is an argument actual parameter it is passed by reference not copied The parameter is an alias of the actual array argument int avg student rec class db MAX N int main void student rec cse 142 MAX N int average average avg cse 142 by reference U 15 Sorting Arrays of structs Bill 920915 2 9 Will Gill 901028 900317 4 0 3 9 Phil Jill 920914 910607 2 8 3 6 Phil 920914 2 8 Jill Bill 920915 910607 3 6 2 9 Will Gill 900317 901028 4 0 3 9 typedef struct char name MAX NAME 1 int id double score StudentRecord U 16 Review Selection Sort Sort b 0 n 1 in non decreasing order rearrange elements in b so that b 0 b 1 b n 1 void sel sort int b int n int k m for k 0 k n 1 k k 1 m min loc b k n swap a k b m U 17 Helper for Selection Sort Find location of smallest element in b k n 1 Returns index of smallest does not return the smallest value itself int min loc int b int k int n int j pos b pos is smallest element pos k found so far for j k 1 j n j j 1 if b j b pos pos j return pos Interchange values void swap int x int y U 18 Modifying for Array of StudentRecord Decide which field to sort by the sort key Let s sort by score Change array types to StudentRecord Change comparison to pull out sort key from the structs Write a swap for StudentRecord U 19 Selection Sort Helper Modified Sort b 0 n 1 in non decreasing order rearrange elements in b so that b 0 b 1 b n 1 void sel sort StudentRecord b int n int k m for k 0 k n 1 k k 1 m min loc b k n swap a k b m U 20 Selection Sort Modified Find location of smallest element in b k n 1 Returns index of smallest does not return the smallest value itself int min loc StudentRecord b int k int n int j pos b pos is smallest element pos k found so far for j k 1 j n j j 1 if b j score b pos score pos j return pos U 21 Interchange values void swap StudentRecord x StudentRecord y Alphabetical Order Phil 920914 2 8 David 920915 2 9 Harry 910607 3 6 Susan 901028 4 0 Harry Phil 910607 920914 2 8 3 6 David Sarah 920915 900317 2 9 3 9 Sarah Susan 900317 901028 3 9 4 0 typedef struct char name MAX NAME 1 int id double score student record U 22 Need a function to compare two strings Review String Comparison Alice is less than Bob Dave is less than David Rob is less than Robert include string h int strcmp char str1 char str2 returns negative integer if str1 is less than str2 0 if str1 equals str2 positive integer if str1 is greater than str2U 23 Modified to Sort by Name The only change from sorting by score is in the function min loc int min loc StudentRecord b int k int n int j pos b pos is smallest element pos k found so far for j k 1 j n j j 1 if 0 strcmp b j name b pos name pos j return pos U 24 Type Quiz typedef struct char name MAX NAME 1 int id double score StudentRecord StudentRecord a MAX STUDENTS What is the type of each a a 0 a 5 name a 4 id a 6 score a 2 name 1 U 25 a score 0 StudentRecord 1 Data Structures What If you wanted to keep information about one song on the computer What pieces of data would you want How would you organize them How would it look in C And then What if you wanted information about an entire CD of songs And then how about a whole collection of CD s U 26 Summary Arrays and structs can be combined and nested to any level The separate rules for arrays and structs are followed even when the two ideas are combined 2 D arrays and strings can be used where appropriate too An infinite number of data structures can be created each one appropriate to a particularU 27 programming problem
View Full Document
Unlocking...