Unformatted text preview:

University of Texas at Austin CS310H - Computer Organization Spring 2010 Don FussellC Dynamic Data StructuresUniversity of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 2Data StructuresA data structure is a particular organizationof data in memory.We want to group related items together.We want to organize these data bundles in a way that isconvenient 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 Clinked list – built from struct and dynamic allocationUniversity of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 3Structures in CA struct is a mechanism for grouping togetherrelated data items of different types.Recall that an array groups items of a single type.Example: We want to represent an airborne aircraft:char flightNum[7];int altitude;int longitude;int latitude;int heading;double airSpeed;We can use a struct to group these data together for each plane.University of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 4Defining a StructWe first need to define a new type for the compilerand tell it what our struct looks like.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 andhow the different data items (“members”) are laid out in memory.But it does not allocate any memory.University of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 5Declaring and Using a StructTo 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 thisvariable:plane.airSpeed = 800.0;plane.altitude = 10000;A struct’s members are laid outin the order specified by the definition.plane.flightNum[0]plane.flightNum[6]plane.altitudeplane.longitudeplane.latitudeplane.headingplane.airspeedUniversity of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 6Defining and Declaring at OnceYou 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 */} maverick;And you can use the flightType nameto declare other structs.struct flightType iceMan;University of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 7typedefC provides a way to define a data typeby giving a new name to a predefined type.Syntax: typedef <type> <name>;Examples: typedef int Color; typedef struct flightType WeatherData; typedef struct ab_type { int a; double b; } ABGroup;University of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 8Using typedefThis gives us a way to make code more readableby giving application-specific names to types. Color pixels[500]; Flight plane1, plane2;Typical practice:Put typedef’s into a header file, and use type names inmain program. If the definition of Color/Flightchanges, you might not need to change the code in yourmain program file.University of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 9Generating Code for StructsSuppose 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.airspeedxR5University of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 10Array of StructsCan 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;University of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 11Pointer to StructWe 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;University of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 12Passing Structs as ArgumentsUnlike an array, a struct is always passed by valueinto a function.This means the struct members are copied tothe function’s activation record, and changes inside the functionare not reflected in the calling routine’s copy.Most of the time, you’ll want to pass a pointer to a struct.int Collide(Flight *planeA, Flight *planeB){ if (planeA->altitude == planeB->altitude) { ... } else return 0;}University of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 13Dynamic AllocationSuppose we want our weather program to handlea variable number of planes – as many as the user wantsto enter.We can’t allocate an array, because we don’t know themaximum number of planes that might be required.Even if we do know the maximum number,it might be wasteful to allocate that much memorybecause most of the time only a few planes’ worth of data isneeded.Solution:Allocate storage for data dynamically, as needed.University of Texas at Austin CS310H - Computer Organization Spring 2010 Don Fussell 14mallocThe Standard C Library provides a function forallocating memory at run-time: malloc. void *malloc(int numBytes);It returns a generic pointer (void*) to a contiguousregion of memory of the requested size (in bytes).The bytes are allocated from a region in memorycalled the heap.The run-time system keeps track of chunks of memory from theheap that have been allocated.University of


View Full Document

UT CS 310 - Data Structures

Download Data Structures
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 Data Structures 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 Data Structures 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?