Introduction to Data Structures.md

- Textbook/ Clean Code: A Handbook of Agile Software Craftsmanship Robert C. Martin - garbage collection: - passing down the stack frame. - Scope is private in a stack frame. - Stack overflow exception: - when run out of stack memory allocation. Memory management for C programming # enum -...

- Textbook/ Clean Code: A Handbook of Agile Software Craftsmanship Robert C. Martin - garbage collection: - passing down the stack frame. - Scope is private in a stack frame. - Stack overflow exception: - when run out of stack memory allocation. Memory management for C programming # enum - enum is a collection of named constants. Defined at the compile time. - Creating enumerated data using default values - `enum type_name{value1, value2,..., valueN};` - changing default values: - `enum type_name{value1=2, value2=5,..., valueN=6};` ## Building Blocks - Data Type: - A specification on the use of a particular set of bits/bytes - Built from small building blocks: integers, floats, chars - Trade-off between space for accuracy (e.g. short vs long int, float vs double) - Functions / Methods: Operations performed on the data - `GetSum()`, `ToString()`, etc. - A data type is a set of values and a collection of operations on those values - Defining your own data types is often an effective way to organize your software # Integers and Characters - ![[Integers and Characters Table.png]] - ![[Integers and Characters Table Cont'd..png]] # Pointers - 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 difficulty 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. # 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. ### 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. ![[Pointers and Memory Table.png]] # 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. ![[The & Operator.png]] ![[The & Operator 2.png]] 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. # The * Operator ![[Pasted image 20250121183638.png]] 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: # Structures ## 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. ![[structures introduction.png]] This works just fine. This is a totally acceptable approach. ## 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. ![[Structures - why do you need it picture.png]] 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. ## 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: ![[Structure for storing the date picture.png]] 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. ![[A structure for storing the date.png]] ## 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 ![[Member data.png]] Finally, to test the value of month to see if it is equal to 12, a statement such as does the trick. ![[Pasted image 20250121184525.png]] Try to determine the effect of the following statement. ![[Member Data 3.png]] # Nature of Member Data: Sample Program ![[Pasted image 20250121184720.png]] 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. # Using Structures in Expressions ![[Using Structures in Expressions.png]] # 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….