Chapter 19Chapter 19Dynamic Data Structures2Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyData StructuresData Structures A data structure is a particular organization of data in memory.– We want to group related items together.– We want to organize these data bundles in a way that is convenient to program and efficient to execute. An array is one kind of data structure. In this chapter, we look at two more:– struct – directly supported by C– linked list – built from struct and dynamic allocation3Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyStructures in CStructures in C A struct is a mechanism for grouping together related data items of different types.– Recall that an array groups items of a single type. Example: Data for an aircraft in flight– We first need to define a new type for the compiler and define our memory needs for it.struct flightType {char flightNum[7]; /* max 6 characters */int altitude; /* in meters */int longitude; /* in tenths of degrees */int latitude; /* in tenths of degrees */int heading; /* in tenths of degrees */double airSpeed; /* in km/hr */}; This tells the compiler how big our struct is and how the different data items (“members”) are laid out in memory.– But it does not allocate any memory.4Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyDeclaring and Using a StructDeclaring and Using a Struct To allocate memory for a struct, we declare a variable using our new data type.struct flightType plane; Memory is allocated, and we can accessindividual members of this variable:plane.airSpeed = 800.0;plane.altitude = 10000; A struct’s members are laid out in the order specified by the definition.plane.flightNum[0]plane.flightNum[6]plane.altitudeplane.longitudeplane.latitudeplane.headingplane.airspeed5Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyDefining, Declaring, and typdefsDefining, Declaring, and typdefs You can both define and declare a struct at the same time.struct flightType {char flightNum[7]; /* max 6 characters */int altitude; /* in meters */int longitude; /* in tenths of degrees */int latitude; /* in tenths of degrees */int heading; /* in tenths of degrees */double airSpeed; /* in km/hr */} toChicago; And you can use the flightType name to declare other structs.struct flightType fromChicago; C provides a way to define a data type by giving a new name to a predefined type.typedef <type> <name>;6Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyGenerating Code for StructsGenerating Code for Structs Suppose our program starts out like this:int x;Flight plane;int y;plane.altitude = 0;... LC-3 code for this assignment:AND R1, R1, #0ADD R0, R5, #-13 ; R0=planeSTR R1, R0, #7 ; 8th wordyplane.flightNum[0]plane.flightNum[6]plane.altitudeplane.longitudeplane.latitudeplane.headingplane.airspeedxR57Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyArray of StructsArray of Structs Can declare an array of structs: Flight planes[100]; Each array element is a struct (7 words, in this case). To access member of a particular element: planes[34].altitude = 10000; Because the [] and . operators are at the same precedence,and both associate left-to-right, this is the same as: (planes[34]).altitude = 10000;8Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyPointer to StructPointer to Struct We can declare and create a pointer to a struct:Flight *planePtr;planePtr = &planes[34]; To access a member of the struct addressed by dayPtr:(*planePtr).altitude = 10000; Because the . operator has higher precedence than *, this is NOT the same as:*planePtr.altitude = 10000; C provides special syntax for accessing a struct memberthrough a pointer:planePtr->altitude = 10000;9Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyPassing Structs as ArgumentsPassing Structs as Arguments Unlike an array, a struct is always passed by value into a function.– This means the struct members are copied to the function’s activation record, and changes inside the function are not reflected in the calling routine’s copy. Most of the time, you’ll want to pass a pointer to a struct.– Why?int Collide(Flight *planeA, Flight *planeB){if (planeA->altitude == planeB->altitude) {...}elsereturn 0;}10Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & AssemblyDynamic AllocationDynamic Allocation Suppose we want our weather program to handle a variable number of planes – as many as the user wants to enter.– We can’t allocate an array, because we don’t know the maximum number of planes that might be required.– Even if we do know the maximum number, it might be wasteful to allocate that much memory because most of the time only a few planes’ worth of data is needed. Solution:Allocate storage for data dynamically, as needed.11Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG 320/520Comp. Org. & Assemblymalloc()malloc() The Standard C Library provides a function for allocating memory at run-time: malloc.void *malloc(int numBytes); It returns a generic pointer (void*) to a contiguous region of memory of the requested size (in bytes). The bytes are allocated from a region in memory called the heap. – The run-time system keeps track of chunks of memory from the heap that have been allocated. To use malloc, we need to know how many bytes to allocate. The sizeof operator asks the compiler to calculate the size of a particular type.planes = malloc(n * sizeof(Flight)); We also need to change the type of the return value to the proper kind of pointer – this is called “casting.”planes = Flight*) malloc(n* sizeof(Flight));12Wright State University, College of EngineeringDr. T. Doom, Computer Science & EngineeringCEG