Overview University of Washington Computer Programming I Data types of C Nested Data Structures structs within structs Arrays of structs structs containing arrays Sorting an array of structs 2000 UW CSE U 1 Data Types of C U 2 Composite Data Simple data types int double char Atomic chunks of data cannot be pulled apart into components Composite data Arrays Structs 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 For many problems an array or a struct still not sufficient including an array or struct U 3 Nested structs Example Nested struct Layout typedef struct r double x y point width typedef struct size height double width height dimension typedef struct x lower left dimension size y point lower left int line color fill color rectangle line color 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 4 fill color U 5 variable declaration rectangle r U 6 U 1 QUIZ Calculating Types 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 size width height lower left x y rectangle R rectangle rp typedef struct double x y point r typedef struct double width height dimension typedef struct line color fill color U 7 dimension size point lower left int line color fill color rectangle R size R lower left R fill color R lower left x R lower left y rp size rp lower left rp line color R size rp size widthU 8 Components in struct Arrays Structures and Arrays pentagon an array of points A struct represents a single record x y Typically computer applications have to deal with collections of such records Examples student records employee records customer records parts records x y pentagon 1 a point structure x y pentagon 4 x a double x y In each case we will have multiple instances of one record struct type x y point pentagon 5 Arrays of structs are the natural way to do this U 9 Arrays in structs U 10 Component Access 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 grade Given a data structure If it s an array use subscripts to access an element If it s a struct use to access a field If the result is itself an array or struct use or to access components as appropriate student record cse 142 MAX STUDENTS What is student 0 s hw int hw exam student record U 11 answer cse 142 0 hw U 12 U 2 Using Arrays of structs Type Quiz student record class MAX STUDENTS read student hw and exams and calculate grade for i 0 i nstudents i i 1 scanf d d class i hw class i exam class i grade double class i hw class i exam 50 0 U 13 StudentRecord a MAX STUDENTS 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 a score 0 StudentRecord 1 U 14 Review structs as Parameters Type Quiz typedef struct char name MAX NAME 1 int id double score StudentRecord typedef struct char name MAX NAME 1 int id double score StudentRecord What is the type of each a a 0 a 5 name a 4 id a 6 score a 2 name 1 a score 0 StudentRecord 1 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 15 Passing Arrays of structs Sorting 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 16 U 17 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 18 U 3 Helper for Selection Sort Review 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 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 b k b m Interchange values void swap int x int y U 19 Modifying for Array of StudentRecord 1 Decide which field to sort by the sort key Let s sort by score 2 Change array types to StudentRecord 3 Change comparison to pull out sort key from the structs 4 Write a swap for StudentRecord U 20 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 b k b m U 21 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 Interchange values U 23 void swap StudentRecord x StudentRecord y U 22 Alphabetical Order Phil 920914 2 8 David 920915 2 9 Harry 910607 3 6 Susan 901028 4 0 Harry Phil 910607 920914 3 6 2 8 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 Need a function to compare two strings U 24 U 4 Modified …
View Full Document
Unlocking...