INB371 Week 2 Lecture

8 Pages

Course Code
Malcolm Corney

This preview shows pages 1,2 and half of page 3. Sign up to view the full 8 pages of the document.
Lecture 2 – INB371 Data Structures and Algorithms Lecture Overview − enumeration types − data and memory − pointers − arrays − pointers and arrays − records − dynamic allocation More Data Types By nesting different types together, you can build 'algorithmical complexity', you can also build complexity with data types. You can create complex data types with primitive data types such as integers, characters, floats, booleans, etc. Pointer The internal machine address of a value in the computers C#, pointers exist but you can't 'play' with them. In C++, you can access the lowest levels of memory, and are able to manipulate memory as required. Arrays Ordered collection of data values of the same type. Record A collection of data values that represent a logical entity, e.g. a 'student' record where you collect multiple types of information, similar to a 'row' in a database table, where each column has a different type of data stored in it. Components of a record identified by a field name, and can be different types. Enumeration Types Enumeration types are a type with a set of values which we create. We can define the domain of values for an enumeration type. The Syntax is 'enum name { element-list };' with element-list being a list of identifiers (enumeration constants) and 'name' is the new type name. Example: 'enum Direction {NORTH, EAST, SOUTH, WEST}' when numeration type is defined, variables of that type can be declared. Example: 'Direction heading; heading = SOUTH;' Internal Representation Values of enumeration types are stored as integers, and during compilation the compiler assigns consecutive integers to the enumeration constants, e.g. 'NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3'. Encoding of these values can be controlled by specifying all the values, or by specifying the first value. Example: 'enum DollarNotes { FIVE = 5; TEN = 10; etc' Note that the type is given an upper case initial, followed by camelcase. Constants are defined by all capitals. This is a convention for programming standards, not required by the compiler. Instead of doing 'const int JANAURY = 1; const int FEBRUARY = 2;' etc, you can simply make an enum like so: 'enum Month { JANUARY = 1; FEBRUARY; MARCH; }' etc. and it will have the same effect. If you don't wish to assign the values specifically, you don't have to. Having separate meaningful typenames makes the program easier to read. Knowing that a variable is of “Month” type lets you easily know what it is without knowing the code. Compare 'Month varname = JANUARY' to 'varname = JANUARY', it's much easier to know what the first one is. The compiler does type checking on enumerated types, int cant be assigned to an enum variable without a typecast, which helps with range checking. The enumeration constants can also be available to the debugger, letting the debugger see the constant name instead of the value. CODE EXAMPLE enum TrafficLightColour {RED, YELLOW, GREEN}; enum Gender {MALE, FEMALE}; TrafficLightColour x; int I; x = YELLOW; // good, assigns value 2 to x I = x // legal, but bad style, assigns 2 to I, which would be female/ I = (int) x // Legal, explicit cast is better style x = (TrafficLightColour)2; // Legal, but no type check done to ensure value is legal. x = FEMALE; // BAD, compiler will give error, because female is of type Gender, so it doesn't know what it is. x = 5 // BAD, compiler will give error, because it's outside the range of TrafficLightColour. Scalar Types Enumeration types, characters, integers, belong to a general class – Scalar types. Scalar types have an underlying integer representation to represent the value. e.g. A = 65. This means that you would be able to check to see if it's still in the domain of an enumerator CODE EXAMPLE – turns right, by adding 1 to the current direction Direction RightFrom(Direction dir) { return Direction((dir + 1) % 4); } Data And Memory Instructions for program set into memory, area set aside in memory for constants, area for the stack frame, area called 'heap'. All data must be stored at bit level, e.g. 0's and 1's. Not done often, but can be done. Normally people use bytes. One byte is 8 bits. One byte is sufficient space to store a single character. 8 bits gives 256 different values for a data type (ascended ascii). Bytes are assembled into larger structures called 'words'. Words are defined to be the size required to hold an int. 2 byte word = 16 bits, 4 byte word = 32 bits. Every byte in memory has a numeric address, just like street addresses. First byte is numbered 0. If 4 megabytes of memory are available, there are 4x2^20 or 4,194,304 bytes. Each byte's address is actually stored as hexidecimal value, as opposed to decimal value. If a program declares 'ch = 'A';', then the compiler reserves one byte of storage for that statement to run. If address 1000 was reserved, then '65', the integer representation of A would be stored in address 1000. Values that have types larger than a single character are stored in consecutive bytes of memory. If a word has 4 bytes, then it would be stored in 4 consecutive bytes, e.g. location 1000 to location 1003. the sizeof() operator takes a single operand (a type name in parentheses) or the result of an expression, and returns the number of bytes to store an int. example: 'double x = 1000L; sizeof x;' returns the number of bytes to store the variable. One of the design principles for C++ was that programmers should have as much access as possible to the features provided by the hardware. This allows you to directly address hardware, such as drivers etc. Most drivers would be written in C++, allowing you to access the hardware memory locations. A data item whose value is an address in memory is called a pointer. High level languages (java, c#) hide pointers, but C and C++ give access to them. They allow you to refer to large data structures in a compact way. This makes it possible to reserve new memory during program execution. Pointers can also be used to record relationships among data items, linking multiple items in a conceptual sequence. Pointers must be declared before use. You must give a type name and a variable name, but important part is the asterisk, which declares it as a pointer. 'int *p' declares variable 'p' to be a pointer to int. 'char *ch' declares variable ch to be of type pointer-to-char. To be able to use data values at the address in the pointer, the compiler must know how to interpret the value being pointed at. This is why you declare the 'base type' of the pointer, e.g. pointer-to-int having a 'int' base type. & operator – Address-of * operator – value pointed to the & operator takes an lvalue (appears on left hand side of assignment statement. e.g. simple variables.) and returns the memory address in which the lvalue is stored. In the code 'X = 4;', x is the lvalue. Everything on the left side has an address in memory, which you can get using the & operator. Constant integers aren't lvalue's though. Constant's are never lvalues, because they are constants, they are unable to be changed, therefore you can't address them. Example: int x, y; int *p1, *p2; (Theoretical view of memory allocation) 1000 [] x 1004 [] y 1008 [] p1 1012 [] p2 (Integers are 4 bytes each, each block indicates 4 bytes) Executing this code: 'x = -42; y = 163;' 1000 [-42] x
More Less
Unlock Document

Only pages 1,2 and half of page 3 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.