英格兰萨里大学：《C语言》课程教学资源（讲义）Lecture 15 - Data Structures

Lecture 15Data Structuresntatat.OneuseoffunctionsisthatofproceduralabstractionPage81of notesn- Breaking a complicated program into smaller manageablepiecesan-This is knows as structured programming:Programsconsistofbothalgorithmsanddataandstructuresnte:Cprovidesawayofstructuring complicateddata intoneat units too-thedata structureCasestidcloterynuntergmeaData StructuresData Structuresstruct epix(·Asimpleexampleisacomplexnumberdouble real;double Imag::ComplexnumbersconsistofJ:-a real partThis createsanewstructureddatatype· an imaginary partcalledstruct cplxwhichwecanusein.We could represent this using an array of size 2a similar wayto otherdatatypes(int,-doublearray/2)char etc).Or we can declare a data structureatruet eplx(e.g.we can declare andinitialise variableskeyworddoublereal;structure membersof this type:double Smag;*Cagstruet eplx a, b-(1.0, -5.3). c;Data StructuresStructureMembers·Actually thetag"is optional (but useful)so if.Thestructurememberscanbeamixtureofwewanttodeclareasinglestructureddifferentdatatypes,includingsimpletypes(int,long,double,etc)arrays,pointers,variablewecanomitit.stringsandotherstructs.Wecan also combinethis withthe.Wecanthenrefertomembersusingadotinitialisationstruct (notatione.g.doublereal;no7agp.thing=17;q.other=p.other/3.2;double imag:(anint)1 p-(57,9.2). 9:(afloat)(afloat).However,wenow cantusethis structuretodefine further variables ofthe same type

1 1. Introduction 2. Binary Representation 3. Hardware and Software 4. High Level Languages 5. Standard input and output 6. Operators, expression and statements 7. Making Decisions 8. Looping 9. Arrays 10. Basics of pointers 11. Strings 12. Basics of functions 13. More about functions 14. Files 15. Data Structures 16. Case study: lottery number generator Lecture 15 Lecture 15 Page 81 of notes Data Structures • One use of functions is that of procedural abstraction – Breaking a complicated program into smaller manageable pieces – This is knows as structured programming • Programs consist of both algorithms and data and structures • C provides a way of structuring complicated data into neat units too - the data structure Data Structures • A simple example is a complex number • Complex numbers consist of – a real part – an imaginary part • We could represent this using an array of size 2 – double array[2] • Or we can declare a data structure struct cplx{ double real; double imag; }; keyword “tag” structure members Data Structures struct cplx{ double real; double imag; }; • This creates a new structured data type called struct cplx which we can use in a similar way to other data types (int, char etc) • e.g. we can declare and initialise variables of this type: struct cplx a, b={1.0, -5.3}, c; Data Structures • Actually the “tag” is optional (but useful) so if we want to declare a single structured variable we can omit it. • We can also combine this with the initialisation struct { double real; double imag; } p={57,9.2}, q; • However, we now cant use this structure to define further variables of the same type. no “tag” Structure Members • The structure members can be a mixture of different data types, including simple types (int, long, double, etc) arrays, pointers, strings and other structs • We can then refer to members using a dot notation e.g. p.thing=17; q.other=p.other/3.2; (an int) (a float) (a float)

OperationsonStructuresStructureMembersTheonly legal operations onastructureareaccessing its members (see last slide) copying or assigning to it taking its addresscomplex1.cIn the previous examplewe could havewritten q=p; then gpg 81is an individual copy ofpwe don't have to copy the members of the structure individually thecompiler will do this for us-(2.5, 5.0).y- (3.2, -1.7), -lxRememberthat+-/datagipury parta-/calling a function by value includes copying its argumentsretuming a value also includes a copy processStructures aretherefore a very convenient way of passing=5.70+3.30jinformation into and out offunctionsScopeofStructurescomplex2.ceallpayprtpg82·Thescoperulesforstructaresimilartoepig blr/- ts protetype -/thosefor variables-1.3),2.Astructdeclaredwithinablock(includingfunction body)is visible onlywithin that blockAstructdeclaredatthestartofaprogram,outsideanyblock is visiblethroughout theprogram i.e. it is globalwarahiee-This isusefulwhereastruct istobepassedtofunctions2-5.70+3.30Pointersto StructuresPointerstoStructures(*px).real-33.5;:Apointertoa struct can be created and·NotethattheparenthesesOarenecessaryinitialisedwiththe&(addressofoperator)justaswithanyothertype.This is sucha common operation thatthere isa special notation for it.e.g.usingthestruct cplxpreviouslydeclared(*px).realpx->realstruct cplx x-[1.0, -2.1], y;:whichmeanstakethethingpxpointstoandstruct eplx* px;access itsmemberpx-x;·Pointers allow us to use call-by-referencey-*px;(*px).real-33.5;- useful because it can avoid a lot of copying ifstructures are large,this can slow down yourprogram2

2 Structure Members /* Example: using structures to represent complex numbers */ #include void main(void) { struct cplx { double real; /* real part */ double imag; /* imaginary part */ }; struct cplx x = {2.5, 5.0}, y = {3.2, -1.7}, z; z.real = x.real + y.real; /* add real parts */ z.imag = x.imag + y.imag; /* add imaginary parts */ printf("z = %4.2f + %4.2f j\n", z.real, z.imag); return; } /* Example: using structures to represent complex numbers */ #include void main(void) { struct cplx { double real; /* real part */ double imag; /* imaginary part */ }; struct cplx x = {2.5, 5.0}, y = {3.2, -1.7}, z; z.real = x.real + y.real; /* add real parts */ z.imag = x.imag + y.imag; /* add imaginary parts */ printf("z = %4.2f + %4.2f j\n", z.real, z.imag); return; } z = 5.70 + 3.30 j z = 5.70 + 3.30 j complex1.c pg 81 complex1.c pg 81 Operations on Structures • The only legal operations on a structure are – accessing its members (see last slide) – copying or assigning to it – taking its address • In the previous example we could have written q=p; then q is an individual copy of p – we don’t have to copy the members of the structure individually the compiler will do this for us • Remember that – calling a function by value includes copying its arguments – returning a value also includes a copy process • Structures are therefore a very convenient way of passing information into and out of functions /* Example: structures as function arguments and return values */ #include struct cplx { double real; /* real part */ double imag; /* imaginary part */ }; struct cplx add(struct cplx a, struct cplx b); /* function prototype */ void main(void) { struct cplx x = {2.5, 5.0}, y = {3.2, -1.7}, z; z = add(x, y); printf("z = %4.2f + %4.2f j\n", z.real, z.imag); return; } struct cplx add(struct cplx a, struct cplx b) { struct cplx c = a; /* can initialise an auto struct variable */ c.real += b.real; c.imag += b.imag; return c; /* can return a struct value */ } /* Example: structures as function arguments and return values */ #include struct cplx { double real; /* real part */ double imag; /* imaginary part */ }; struct cplx add(struct cplx a, struct cplx b); /* function prototype */ void main(void) { struct cplx x = {2.5, 5.0}, y = {3.2, -1.7}, z; z = add(x, y); printf("z = %4.2f + %4.2f j\n", z.real, z.imag); return; } struct cplx add(struct cplx a, struct cplx b) { struct cplx c = a; /* can initialise an auto struct variable */ c.real += b.real; c.imag += b.imag; return c; /* can return a struct value */ } complex2.c pg 82 complex2.c pg 82 z = 5.70 + 3.30 j z = 5.70 + 3.30 j Scope of Structures • The scope rules for struct are similar to those for variables • A struct declared within a block (including function body) is visible only within that block • A struct declared at the start of a program, outside any block is visible throughout the program i.e. it is global – This is useful where a struct is to be passed to functions Pointers to Structures • A pointer to a struct can be created and initialised with the & (address of operator) just as with any other type • e.g. using the struct cplx previously declared struct cplx x={1.0, -2.1}, y; struct cplx* px; px=&x; y=*px; (*px).real=33.5; Pointers to Structures (*px).real=33.5; • Note that the parentheses () are necessary • This is such a common operation that there is a special notation for it (*px).real = px->real • which means take the thing px points to and access its member • Pointers allow us to use call-by-reference – useful because it can avoid a lot of copying if structures are large, this can slow down your program

complex3.cpg82ArraysofStructures.Aswithotherdatatypeswecanhavearrays which are very useful-.7e.g.struct cplx arr[35];(e):g :pana1Mo As Us mnaRs s StructurescontainingStructures:>There is no reason why one structure cant1. wuniprue o kam 1.wT.eow..-.emsonam containanother.This allowsustobuildupcomplicated real-/tuqauworlddatarecordsstepbystepIf structure1contains structure2whichhasaMmemberxwecanaccess itusingo leaeteidegio urWFTs aRBnstructurei.structure2.x nsine peiJ onne2.Defininga StructuralData Type0R.队国a 国dke ad:oThe typedef keyword allows us to use a.nameasa synonymforanothertype19nbutypeder 1ohg, urg.oniginal typee.g.1urn u, v-1234567;newtype福This is mostuseful when a structured datatype is tobe used widely e.g.forthe complexO+ 9] enumberprogram1mtmb1estypedef struct (eeomneF- TWdouble real;-double imag;: Cp1x;3

3 /* Example: pointers to structures */ #include struct cplx { double real; /* real part */ double imag; /* imaginary part */ }; void add(struct cplx *pa, struct cplx *pb, struct cplx *pc); void main(void) { struct cplx x = {2.5, 5.0}, y = {3.2, -1.7}, z; add(&x, &y, &z); /* call by reference: pointers are passed */ printf("z = %4.2f + %4.2f j\n", z.real, z.imag); return; } void add(struct cplx *pa, struct cplx *pb, struct cplx *pc) { (*pc).real = (*pa).real + (*pb).real; /* add real parts */ (*pc).imag = (*pa).imag + (*pb).imag; /* add imaginary parts */ /* Or we could write pc->real = pa->real + pb->real; pc->imag = pa->imag + pb->imag; which is a shorthand notation meaning exactly the same thing. */ return; } /* Example: pointers to structures */ #include struct cplx { double real; /* real part */ double imag; /* imaginary part */ }; void add(struct cplx *pa, struct cplx *pb, struct cplx *pc); void main(void) { struct cplx x = {2.5, 5.0}, y = {3.2, -1.7}, z; add(&x, &y, &z); /* call by reference: pointers are passed */ printf("z = %4.2f + %4.2f j\n", z.real, z.imag); return; } void add(struct cplx *pa, struct cplx *pb, struct cplx *pc) { (*pc).real = (*pa).real + (*pb).real; /* add real parts */ (*pc).imag = (*pa).imag + (*pb).imag; /* add imaginary parts */ /* Or we could write pc->real = pa->real + pb->real; pc->imag = pa->imag + pb->imag; which is a shorthand notation meaning exactly the same thing. */ return; } complex3.c pg 82 complex3.c pg 82 Arrays of Structures • As with other data types we can have arrays which are very useful e.g. struct cplx arr[35]; /* Example: array of structures - stores items */ #include #include void main(void) { struct { char part_no[7]; /* stores part number */ char desc[40]; /* description */ float price; /* price each */ int qty; /* quantity in stock */ } part[20]; /* array of structures */ int total_stock; float total_value; /* assign values to structure members (in practice this would probably be done by reading the data from a file): */ strcpy(part[0].part_no, "4Y4759"); strcpy(part[0].desc, "741 OP AMP IC"); part[0].price = 0.25; part[0].qty = 1738; strcpy(part[1].part_no, "2X6641"); strcpy(part[1].desc, "10K OHM 5% 0.24W RESISTOR"); part[1].price = 0.05; part[1].qty = 23438; /* access structure members: */ total_stock = part[0].qty + part[1].qty; total_value = part[0].qty * part[0].price + part[1].qty * part[1].price; printf("Total stock level = %i items\n", total_stock); printf("Total stock value = %4.2f\n", total_value); return; } /* Example: array of structures - stores items */ #include #include void main(void) { struct { char part_no[7]; /* stores part number */ char desc[40]; /* description */ float price; /* price each */ int qty; /* quantity in stock */ } part[20]; /* array of structures */ int total_stock; float total_value; /* assign values to structure members (in practice this would probably be done by reading the data from a file): */ strcpy(part[0].part_no, "4Y4759"); strcpy(part[0].desc, "741 OP AMP IC"); part[0].price = 0.25; part[0].qty = 1738; strcpy(part[1].part_no, "2X6641"); strcpy(part[1].desc, "10K OHM 5% 0.24W RESISTOR"); part[1].price = 0.05; part[1].qty = 23438; /* access structure members: */ total_stock = part[0].qty + part[1].qty; total_value = part[0].qty * part[0].price + part[1].qty * part[1].price; printf("Total stock level = %i items\n", total_stock); printf("Total stock value = %4.2f\n", total_value); return; } stores.c stores.c pg 83 pg 83 Structures containing Structures • There is no reason why one structure cant contain another • This allows us to build up complicated real￾world data records step by step • If structure1 contains structure2 which has a member x we can access it using structure1.structure2.x /* Example: building a complicated data structure, step by step */ #include /* declare structures: */ struct date { int d; /* day of month, 1 to 31 */ int m; /* month, 1 to 12 */ int y; /* year, e.g. 1996 - avoids millenium bug! */ }; struct module { unsigned int pc; /* percentage mark, 0 to 100 */ char gr; /* letter grade, S to F */ unsigned int cr; /* credits awarded */ }; struct student { long urn; /* University Reg. No. */ char surname[20]; /* surname */ char forenames[30]; /* forenames */ struct date born; /* date of birth */ struct date enrol; /* date of enrolment */ struct module L1U10; /* programming module */ }; void print_results(struct student s); /* function prototype */ void main(void) { /* declare and initialise structured variables: */ struct student him = {1234567, "JOHNSON", "Jeremiah Methuselah", {27, 3, 1974}, {3, 9, 1995}, {0, '\0', 0,} }; struct student her = {5342096, "ROBINSON", "Anne Louise", {5, 11, 1978}, {1, 9, 1996}, {0, '\0', 0,} }; /* assign values to structure members: */ him.L1U10.pc = 23; him.L1U10.gr = 'F'; him.L1U10.cr = 0; her.L1U10.pc = 89; her.L1U10.gr = 'S'; her.L1U10.cr = 10; /* call a function, passing structure as argument: */ print_results(him); print_results(her); return; } void print_results(struct student s) { printf("URN: %li - ", s.urn); printf("%s %s\n", s.forenames, s.surname); printf(" Born: %i/%i/%i\n", s.born.d, s.born.m, s.born.y); printf(" Enrolled: %i/%i/%i\n", s.enrol.d, s.enrol.m, s.enrol.y); printf(" Module L1U10: %i%%, ", s.L1U10.pc); printf("grade %c, ", s.L1U10.gr); printf("%i credits\n\n", s.L1U10.cr); return; } /* Example: building a complicated data structure, step by step */ #include /* declare structures: */ struct date { int d; /* day of month, 1 to 31 */ int m; /* month, 1 to 12 */ int y; /* year, e.g. 1996 - avoids millenium bug! */ }; struct module { unsigned int pc; /* percentage mark, 0 to 100 */ char gr; /* letter grade, S to F */ unsigned int cr; /* credits awarded */ }; struct student { long urn; /* University Reg. No. */ char surname[20]; /* surname */ char forenames[30]; /* forenames */ struct date born; /* date of birth */ struct date enrol; /* date of enrolment */ struct module L1U10; /* programming module */ }; void print_results(struct student s); /* function prototype */ void main(void) { /* declare and initialise structured variables: */ struct student him = {1234567, "JOHNSON", "Jeremiah Methuselah", {27, 3, 1974}, {3, 9, 1995}, {0, '\0', 0,} }; struct student her = {5342096, "ROBINSON", "Anne Louise", {5, 11, 1978}, {1, 9, 1996}, {0, '\0', 0,} }; /* assign values to structure members: */ him.L1U10.pc = 23; him.L1U10.gr = 'F'; him.L1U10.cr = 0; her.L1U10.pc = 89; her.L1U10.gr = 'S'; her.L1U10.cr = 10; /* call a function, passing structure as argument: */ print_results(him); print_results(her); return; } void print_results(struct student s) { printf("URN: %li - ", s.urn); printf("%s %s\n", s.forenames, s.surname); printf(" Born: %i/%i/%i\n", s.born.d, s.born.m, s.born.y); printf(" Enrolled: %i/%i/%i\n", s.enrol.d, s.enrol.m, s.enrol.y); printf(" Module L1U10: %i%%, ", s.L1U10.pc); printf("grade %c, ", s.L1U10.gr); printf("%i credits\n\n", s.L1U10.cr); return; } students.c pg 84 students.c pg 84 Defining a Structural Data Type • The typedef keyword allows us to use a name as a synonym for another type e.g. typedef long, urn; urn u, v=1234567; • This is most useful when a structured data type is to be used widely e.g. for the complex number program typedef struct { double real; double imag; } Cplx; original type new type

tyPe:Whatarethe advantages ofSexatdio.bstypedef.ctypedet atructhis approach?dais eg, /. tmg ensy Plee +pg 85cplx;.Hides the complexityof thedata structure.Ouruserdefinedtypecanbeusedalmostoexactlythesamewayasanyotherdatatype- simpler to write1.7- makes the program easier to understand.at02.13ag we can write more complex functions whichperform higher level operations on structured datarather than just simple variablesWhat are the advantages of this approach ?.Ifyouthinkofthesestructuresasobjectsthenc.you arewell on the way ofmovingto ObjectOrientatedProgrammingandC++Lectures12and13lookedathowtousefunctions.to structureyourprogramsTheFILEdatatype.Todaywe looked athowtoalso structureyourdata This was the last piece of the equation for programming C.RememberlastlecturewelookedatYouarenowprogrammers!!!.files/streams andtheuse oftheFILEdata type-Well not really but you nowknow enough C tobecome:Well FILE isactuallyatypedefinprogrammersS0.h>*/nyphcdThe rest is up to you and it involves practiceSetinaNext Lecturewewill coversomeoftherevision.topicsyouhaverequested,namelypg 86 Arays? PointersPan·FunctionsFIL·Is there anything else you would like to cover againteSeinatdoot(104

4 /* Example: using typedef to define a structure type */ /* This program is based closely on complex2.c; compare them */ #include typedef struct { double real; /* real part */ double imag; /* imaginary part */ } Cplx; /* "Cplx" can now be used as a synonym for this struct. This neatens things up somewhat. */ Cplx add(Cplx a, Cplx b); /* function prototype */ void main(void) { Cplx x = {2.5, 5.0}, y = {3.2, -1.7}, z; z = add(x, y); printf("z = %4.2f + %4.2f j\n", z.real, z.imag); return; } Cplx add(Cplx a, Cplx b) { Cplx c = a; c.real += b.real; c.imag += b.imag; return c; } /* Example: using typedef to define a structure type */ /* This program is based closely on complex2.c; compare them */ #include typedef struct { double real; /* real part */ double imag; /* imaginary part */ } Cplx; /* "Cplx" can now be used as a synonym for this struct. This neatens things up somewhat. */ Cplx add(Cplx a, Cplx b); /* function prototype */ void main(void) { Cplx x = {2.5, 5.0}, y = {3.2, -1.7}, z; z = add(x, y); printf("z = %4.2f + %4.2f j\n", z.real, z.imag); return; } Cplx add(Cplx a, Cplx b) { Cplx c = a; c.real += b.real; c.imag += b.imag; return c; } typedef.c pg 85 typedef.c pg 85 What are the advantages of this approach ? What are the advantages of this approach? • Hides the complexity of the data structure • Our user defined type can be used almost exactly the same way as any other data type – simpler to write – makes the program easier to understand – we can write more complex functions which perform higher level operations on structured data rather than just simple variables • If you think of these structures as objects then you are well on the way of moving to Object Orientated Programming and C++ The FILE data type • Remember last lecture we looked at files/streams and the use of the FILE data type • Well FILE is actually a typedef in /* Typical definition of type FILE in */ #define OPEN_MAX 32 typedef struct _iobuf { int cnt; /* characters left */ char *ptr; /* next character */ char *base; /* start of buffer */ int bufsize; /* size of buffer */ int flag; /* file access mode */ int fd; /* file “handle” */ } FILE; FILE _iob[OPEN_MAX]; /* global array of FILE structs */ #define stdin (&_iob[0]) /* standard input stream */ #define stdout (&_iob[1]) /* standard output stream */ #define stderr (&_iob[2]) /* standard error stream */ pg 86 pg 86 • Lectures 12 and 13 looked at how to use functions to structure your programs • Today we looked at how to also structure your data – This was the last piece of the equation for programming C • You are now programmers!!! – Well not really but you now know enough C to become programmers – The rest is up to you and it involves practice • Next Lecture we will cover some of the revision topics you have requested, namely • Arrays • Pointers • Functions • Is there anything else you would like to cover again