DOC PREVIEW
UW CSE 142 - Study Notes

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 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 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

U-1U-1University of WashingtonComputer Programming INested Data Structures© 2000 UW CSEU-2OverviewData types of Cstructs within structsArrays of structsstructs containing arraysSorting an array of structsU-3Data Types of CSimple data typesint, double, charAtomic chunks of data - cannot be pulled apart into componentsComposite dataArraysStructsFor many problems, an array or a structstill not sufficientU-4Composite DataArraysSequence of variables all of the same typestructs Collection of fields of possibly differenttypesKey point: variables of any type can be a component of an array or struct…including an array or struct!U-5Nested structs -Exampletypedef 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-6Nested struct Layouttypedef 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;widthheightxyline_colorfill_colorlower_leftsizerU-2U-7Field SelectionUse the . operator to select a field.If the field it itself a struct, use. again to select its componentswidthheightxyline_colorfill_colorlower_leftsizerr r.lower_left r.lower_left.x U-8QUIZ: Calculating Typesrectangle R;rectangle * rp;R.sizeR.lower_leftR.fill_color R.lower_left.x &R.lower_left.yrp -> size &rp -> lower_left *rp.line_color R -> sizerp -> size -> widthtypedef struct {double x, y ;} point ;typedef struct { double width, height ;} dimension ;typedef struct {dimension size ;point lower_left ;int line_color, fill_color ;} rectangle ;U-9Structures and ArraysA struct represents a single recordTypically, computer applications have to deal with collectionsof such records Examples: student records, employee records, customer records, parts records In each case we will have multiple instances of one record (struct) typeArrays of structs are the natural way to do thisU-10Components in struct Arrayspoint pentagon[5];pentagon -- an array of pointsxyxyxyxyxypentagon[1] -- a point structurexypentagon[4].x -- a doubleU-11Arrays in structsThe fields in a struct can themselves be an arrayCommon example: strings (arrays of char)#define MAX_NAME 40typedef struct { char name [MAX_NAME+1] ;int id ;double grade ;int hw, exam;} student_record ;U-12Component AccessGiven a data structure,If it’s an array, use subscripts ([ ]) to access an elementIf it’s a struct, use . to access a fieldIf the result is itself an array or struct, use .. or [ ] to access components, as appropriatestudent_record cse_142[MAX_STUDENTS];What is student 0's hw?answer: cse_142[0].hwU-3U-13Using Arrays of structsstudent_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-14Type QuizStudentRecord a [MAX_STUDENTS];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] U-15Type QuizStudentRecord a [MAX_STUDENTS];typedef struct {char name [MAX_NAME+1];int id ;double score ;} StudentRecord ;/*What is the type of each?*/aa[0]a[5].name a[4].id&a[6].score a[2].name[1]a.score[0]StudentRecord[1]U-16Review: structs as ParametersA single struct is passed by valueall 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-17Passing Arrays of structsAn 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 argumentint 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-18Sorting Arrays of structsJill9106073.6Gill9003173.9Phil9209142.8Will9010284.0Bill9209152.9Bill9209152.9Jill9106073.6Gill9003173.9Phil9209142.8Will9010284.0typedef struct {char name [MAX_NAME + 1] ;int id ;double score ;} StudentRecord ;U-4U-19Review: 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(&b[k], &b[m]);}}U-20Helper 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-21Modifying for Array of StudentRecord1. Decide which field to sort by: the “sort key”Let’s sort by score2. Change array types to StudentRecord3. Change comparison to pull out sort key from the structs4. Write a “swap” for StudentRecordU-22Selection 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-23Selection 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 */void swap (StudentRecord * x, StudentRecord * y);U-24Alphabetical OrderHarry9106073.6Sarah9003173.9Phil9209142.8Susan9010284.0David9209152.9typedef struct {char name[MAX_NAME + 1];int id;double score;} student_record;Need a function to compare two


View Full Document

UW CSE 142 - Study Notes

Download Study Notes
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 Study Notes 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 Study Notes 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?