Week 1 - Introduction to Data Structures PDF

SENG1050: Data Structures Introduction to Data Structures Week 1 1 This class Why do we need Data Structures? Data Types in Software Programming Pointers Structures o Member Data o Methods to manipulate Structures...

SENG1050: Data Structures Introduction to Data Structures Week 1 1 This class Why do we need Data Structures? Data Types in Software Programming Pointers Structures o Member Data o Methods to manipulate Structures 2 WHY DO WE NEED DATA STRUCTURES? 3 Let’s talk about data. Data is a broad term that refers to all types of information, down to the most basic numbers and strings. In the simple but classic “Hello World!” program, the string "Hello World!" is a piece of data. In fact, even the most complex pieces of data usually break down into a bunch of numbers and strings. Data structures refer to how data is organized. Let us learn about this Data Organization by looking at a couple of examples. 4 Example 1: Boots and Shoes For example, let’s say we have some footwear, as depicted in the below figure. We have two boots and two shoes arranged alternately. We can think of each side of the shoe as a unit of data. If we needed a way to maintain this data arrangement, we would need a mechanism to provide some ordering and identification of these shoes; this is what we may call a data structure. 5 Example 1: Boots and Shoes Contd., Now let us reorganize / reorder our inventory to help us with easy identification of data. Now the first two in the collection are shoes and the next two are boots. This helps us with some sort of easy identification technique. 6 Example 1: Boots and Shoes Contd., A data structure may also be able to take each item and, regardless of whether it’s a shoe or boot, assign an identifier, for example So, if I wanted the “second shoe,” instead of wondering if this means from the left or from the right, I can simply tell the data structure, “Give me the shoe at index 2,” and I will get exactly what I wanted. 7 Example 2: Simple Code Let’s look at the following code: This simple program deals with three pieces of data, outputting three strings to make one coherent message. If we were to describe how the data is organized in this program, we’d say that we have three independent strings, each contained within a single variable. 8 Example 2: Simple Code Contd., However, this same data can also be stored in an array: This piece of code also takes three strings and append them together as in the previous example. The only difference here is that the data in the first example i.e., three string variable is now reorganized to be a collection (array) of three strings together. 9 In this course we are going to learn that the organization of data doesn’t just matter for organization’s sake but can significantly impact how fast your code runs. Depending on how you choose to organize your data, your program may run faster or slower by orders of magnitude. If you’re building a program that needs to deal with lots of data, or a web app used by thousands of people simultaneously, the data structures you select may affect whether your software runs at all, or simply conks out because it can’t handle the load. 10 DATA TYPES IN SOFTWARE PROGRAMMING 11 Building Blocks Data type: A specification on the use of a particular set of bits / bytes o Built from small building blocks: integers, floats, and chars o Trade-off between space for accuracy (e.g., short vs. long int, float vs. double) Functions / Methods: Operations performed on the data o GetSum(), ToString(), etc. 12 Building Blocks – Contd., A data type is a set of values and a collection of operations on those values C Data Types Defining your own data types is often an effective way to organize your software Primary Secondary Float Array Integers Union Double Pointer Characters Enum Void Structure 13 Integers and Characters 14 Integers and Characters – Contd., 15 enum Creating enumerated data using default values enum type_name{value1, value2,..., valueN}; Default: value1=0, value2=1, … Changing default values enum type_name{value1=2, value2=5,..., valueN=6}; 16 POINTERS 17 Pointers in C The basic concept of a pointer is simple: It is a variable that stores the address of a memory location of another variable. The key to comprehending pointers is understanding how memory is managed in a C program. After all, pointers contain addresses in memory. If we don’t understand how memory is organized and managed, it is difficult to understand how pointers work. A pointer is normally declared to be of a specific type depending on what it points to, such as a pointer to a char. The object may be any C data type such as integer, character, string, or structure. However, nothing inherent in a pointer indicates what type of data the pointer is referencing. A pointer only contains an address. 18 Pointers and Memory When a C program is compiled, it works with three types of memory: Static / Global: Statically declared variables are allocated to this type of memory. Global variables also use this region of memory. They are allocated when the program starts and remain in existence until the program terminates. While all functions have access to global variables, the scope of static variables is restricted to their defining function. 19 Pointers and Memory – Contd., Automatic: These variables are declared within a function and are created when a function is called. Their scope is restricted to the function, and their lifetime is limited to the time the function is executing. Dynamic: Memory is allocated from the heap and can be released, as necessary. A pointer references the allocated memory. The scope is limited to the pointer or pointers that reference the memory. It exists until it is released. 20 The & Operator: When a variable x is declared in a program, a storage location in the main memory is made available by the compiler. It may be observed that x is the name associated by the compiler to a location in the memory of the computer. Let us assume that, at the time of execution, the physical address of this memory location (called x) is 2712. Now, a point worth noting is that this memory location is viewed by the programmer as variable x and by the operating system as an address 2712. The address of variable x can be obtained by ‘&’ an address of operator. This operator when applied to a variable gives the physical memory address of the variable. Thus, &x will provide the address 2712. 21 The & Operator – Contd.,: It may be noted here that the value of address of x (i.e., 2712) is assumed and the actual value is dependent on ‘machine and execution’ time. 22 The * operator: The ‘*’ is an indirection operator or ‘value at address operator’. In simple words, we can say that if address of a variable is known, then the ‘*’ operator provides the contents of the variable. Consider the following program segment: 23 STRUCTURES 24 Structures - Introduction Suppose you want to store a date—for example 9/25/15—inside a program, perhaps to be used for the heading of some program output, or even for computational purposes. A natural method for storing the date is to simply assign the month to an integer variable called month, the day to an integer variable called day, and the year to an integer variable called year. This works just fine. This is a totally acceptable approach. 25 Structures – Why do you need it? But suppose your program also needs to store the date of purchase of a particular item, for example. You can go about the same procedure of defining three more variables such as purchaseMonth, purchaseDay, and purchaseYear. Whenever you need to use the purchase date, these three variables could then be explicitly accessed. 26 Structures – Why do you need it? Contd., Using this method, you must keep track of three separate variables for each date that you use in the program—variables that are logically related. It would be much better if you could somehow group these sets of three variables together. This is precisely what the structure in C allows you to do. 27 A Structure for Storing the Date You can define a structure called date in the C language that consists of three components that represent the month, day, and year. The syntax for such a definition is rather straightforward, as follows: The date structure just defined contains three integer members called month, day, and year. The definition of date in a sense defines a new type in the language in that variables can subsequently be declared to be of type struct date. 28 A Structure for Storing the Date As discussed, you can create variables of type struct date.3 You can also declare a variable purchaseDate to be of the same type by a separate declaration, such as Or, you can simply include the two declarations on the same line, as in 29 Member Data Unlike variables of type int, float, or char, a special syntax is needed when dealing with structure variables. A member of a structure i.e., day, year, month from the above example, is accessed by specifying the variable name, followed by a period, and then the member's name. For example, to set the value of the day in the variable today to 25 and value of year in the variable today to 2015, you write 30 Member Data – Contd., Finally, to test the value of month to see if it is equal to 12, a statement such as does the trick. Try to determine the effect of the following statement. 31 Nature of Member Data: Sample Program The first statement inside main() defines the structure called date to consist of three integer members called month, day, and year. In the second statement, the variable today is declared to be of type struct date. The first statement simply defines what a date structure looks like to the C compiler and causes no storage to be reserved inside the computer. The second statement declares a variable to be of type struct date and, therefore, does cause memory to be reserved for storing the three integer values of the variable today. Be certain you understand the difference between defining a structure and declaring variables of the structure type. 32 Using Structures in Expressions When it comes to the evaluation of expressions, structure members follow the same rules as ordinary variables do in the C language. So, division of an integer structure member by another integer is performed as an integer division, as in 33 Methods to Manipulate Structures To understand how to manipulate the member data of structures within the program, let us try to solve the below problem. Suppose you want to write a simple program that accepts today’s date as input and displays tomorrow’s date to the user. This should properly handle the below 2 use cases: If user entered date falls at the end of a month. If use entered date falls at the end of a year (that is, if today’s date is December 31). Let us switch over to a demonstration…. 34 Next class Algorithm Efficiency o Using Big O notation to classify algorithms according to their growth rate. o Analyze Algorithm Efficiency. o Evaluate algorithms according to efficiency. 35 References Programming in C, Fourth Edition by Stephen G.Kochan A Common-Sense Guide to Data Structures and Algorithms, Second Edition by Jay Wengrow Data Structures and Algorithms in Java, 2nd Edition by Robert Lafore Codeless Data Structures and Algorithms by Armstrong Subero Introduction to Data Structures in C by Ahok Kamthane 36