Programming Studio #11 ECE 190Programming Studio #11 • Topics this week: • Data Structures in C • Dynamic Memory Allocation • Linked Lists • MP5 overviewAnnouncements • Exam 2 Programming re-grade requests due by 5pm – “Time spent” is not a valid grading metric • Final Exam Times – AE1: Monday 5/9, 7pm-10pm – AE2: Wednesday 5/11, 1:30pm-4:30pm – AE3: Friday 5/13, 1:30pm-4:30pm • Conflict Exam Deadline: Monday 5/2 5pmCheating • Reminder: We do not tolerate any form of cheating! – Looking at somebody’s code and taking notes is cheating – Sharing code is cheating – Sharing code and renaming variables is still cheating – Sharing code and adding/removing spaces/tabs is still cheatingData Types • Basic data types in C – int (integer), float/double (real number), char (text) • What about data in the real world? – For most parts, real-world data can be represented using integer, real numbers or characters – Data is often aggregated into groups • Vectors: direction, magnitude • Complex numbers: real part, complex part • Student record: last name, first name, UIN, GPA, standing…Data aggregation with structures • Student Record Example First Name (char[]) Last Name (char[]) netID (char[]) UIN (unsigned int) GPA (float) Student Record Structure John Doe doe1 123456789 3.99 Student 1 Sarah Smith Smith1 987654321 4.00 Student 2struct construct • Define a customized data type (structure) • Use it to declare variables struct student_record { char first_name[12]; char last_name[12]; char netid[8]; unsigned int uin; float gpa; }; struct student_record student_1; student_1.first_name = “John”; student_1.last_name = “Doe”; student_1.uin = 123456789; First Name (char[]) Last Name (char[]) netID (char[]) UIN (unsigned int) GPA (float) Student Record StructureMemory allocation for structures • Memory is allocated the same way as for any variable – Locals are allocated on the run-time stack and globals are allocated in the global data section – Variables of type struct occupy contiguous regions of memory blocks. Each block occupies as much memory as the sum of sizes of all of the member elements • How much space does each student entry take up? • Arrays of structures: struct student_record students[100]; student[0].first_name = “John”; student[0].last_name = “Doe”; student[0].uin = 123456789;Structures and Pointers • Since structures are handled the same way as normal data types in C, pointers to structures can be created • Pointers can be dereferenced • Another way to access structure members using a pointer to a structure is to use the -> operator struct student_record students[100]; struct student_record *st_ptr; st_ptr = &students[3]; (*st_ptr).gpa = 3.25; st_ptr->gpa = 3.25;Enumerations • What if your data types should contain only certain values? – Storing multiple choice answers (A,B,C,D) – Opcodes in an assembly language • You could just use an integer value to represent each of these things, but it is not always convenient: – Which opcode is this? If (op == 2) • Solution: create a list where each number is assigned a human readable representation – This is much easier: if (op == LD) • Enumerated list: enum opcode {BR, ADD, LD}; enum opcode op; op = 1; if(op == LD) Is this statement true? which opcode does op hold?Dynamic Memory Allocation • So far we know how to allocate memory using arrays – Limitation: we can only allocate a constant amount of elements – This amount must be known at compile time (specified in the source code) • It could be either waste of memory, or danger of not allocating enough space to store all data • What if we want to allocate during run-time instead of compile time?Dynamic Memory Allocation • Use function malloc(size) to allocate memory at runtime – size is a parameter that tells malloc how many bytes to allocate – Memory is allocated in the heap • Dynamic memory must be freed manually using free function – Without freeing memory, no other programs may use this memory block (we can run out of memory)Dynamic Memory Allocation int main() { struct student_record *students; int number; printf("How many students?"); scanf("%d", &number); students = (student_record*) malloc(number * sizeof(student_record)); /* students is now a pointer to the 0th element of the 'students' block */ students[0].first_name = "John"; students->last_name = "Doe"; /* do stuff */ free(students); }Sample Exercise • Complex number adder – Create a structure for a complex number (float real_part, float complex_part); – Ask the user how many complex numbers will be entered – Dynamically allocate enough space to hold all the complex numbers – Ask the user to enter each number (first ask for the real part, then ask for the complex part) – Add all the complex numbers together: • The real_part of the sum is just the sum of the real parts of all the numbers • The complex_part of the sum is just the sum of the complex parts of all the numbers – Print out the answer in the format: “Sum = <real_part> + j <complex_part>” – Remember to free the memory after you’re done.Linked Lists • A fundamental data structure widely used in computing • Like arrays, linked lists are used to store data as a list of elements • Unlike arrays, each element in the linked list need not be directly adjacent in memory to the next elements in the list A[0] A[1] A[2] array L0 L1 L2 linked list NULLAdding/removing nodes • Add • Remove L0 L1 L2 NULL new node L0 L1 L2 NULL head node tail nodeExample • Car data structure typedef struct carType Car; struct carType { int vehicleID; char make[20]; char model[20]; int year; int mileage; double cost; Car * next; /* ptr to next car in list */ }Scanning the list Car * ScanList(Car * head, int searchID) { Car * previous, * current; previous = head; current = head->next; /* Traverse until ID >= searchID */ while ((current!=NULL) && (current->vehicleID < searchID)) { previous = current; current = current->next; } return previous;