Data Structures, Debugging | Lectures and Assignments | Introduction to C and C++ | Electrical Engineering and Computer Science | MIT OpenCourseWare Subscribe to the OCW Newsletter Help| Contact Us FIND COURSES Find courses by: Topic MIT Course Number Department Collections New Courses Most Visited Courses OCW Scholar Courses Audio/Video Lectures Online Textbooks Supplemental Resources OCW Highlights for High School MITx & Related OCW Courses MIT Open Learning Library Cross-Disciplinary Topic Lists Energy Entrepreneurship Environment Introductory Programming Life Sciences Transportation Translated Courses 繁體字 / Traditional Chinese Türkçe / Turkish (비디오)한국 / Korean For Educators Chalk Radio Podcast OCW Educator Portal Instructor Insights by Department Residential Digital Innovations OCW Highlights for High School Additional Resources Give Now Make a Donation Why Give? Our Supporters Other Ways to Contribute Become a Corporate Sponsor About About MIT OpenCourseWare Site Statistics OCW Stories Newsletter Chalk Radio Podcast Open Matters Blog Search Tips X Exclude words from your search Put - in front of a word you want to leave out. For example, jaguar speed -car Search for an exact match Put a word or phrase inside quotes. For example, "tallest building". Search for wildcards or unknown words Put a * in your word or phrase where you want to leave a placeholder. For example, "largest * in the world". Search within a range of numbers Put .. between two numbers. For example, camera $50..$100. Combine searches Put "OR" between each search query. For example, marathon OR race. Home » Courses » Electrical Engineering and Computer Science » Introduction to C and C++ » Lectures and Assignments » Data Structures, Debugging Data Structures, Debugging Course Home Syllabus and Software Lectures and Assignments Compilation Pipeline Core C C Memory Management Data Structures, Debugging C++ Introduction, Classes, and Templates C++ Inheritance Final Project Starter Kit Download Course Materials Topics: Using structs, unions, typedef, and enums, and how to debug with Valgrind and GDB. Lecture Notes Lecture 4: Data Structures, Debugging (PDF) Lab Exercises The primary goal of this lab period is to introduce debugging tools, and use of unions/structs. Exercise 1 Download and install Valgrind on your system, if it's not already. To test if you have Valgrind, run valgrind --version. It should print the version of Valgrind that is installed. #include
#include
void fn()
{
int* x = malloc(10 * sizeof(int));
printf("%d",*x);
x[10] = 0;
}
int main()
{
fn();
return 0;
} There are 3 sources of memory errors in this code. Run valgrind to determine what they are (although I suspect you can probably tell from the code anyways). Exercise 2 Use a union to print the individual bytes of an int. (Hint: Recall the size of ints and other data types.) Exercise 3 Determine how much memory is required for each of the structs below. How much of that memory is padding between the members? struct X
{
short s;
int i;
char c;
};
struct Y
{
int i;
char c;
short s;
};
struct Z
{
int i;
short s;
char c;
}; Assignment 4 Today's assignment combines the material from the past few lectures. Your job is to fill in the skeleton code we provide. I have commented the code with what each section should do. Assignment 4 files (ZIP) (This ZIP file conatins: 2 .c files and 1 .h file.) You can learn more about binary search trees and find pseudo-code on the binary search tree page on Wikipedia. Your job is to implement a binary search tree, a data structure of connected nodes with a tree shape. Each node has a node identifier (a number), data (payload), and 2 children (left and right). The children are other nodes referenced with a pointer, with the constraint that the left node's ID is less than the parent node's ID, and the right node's ID is larger than the parent node ID. No two nodes will have the same identifier. A node can have less than two children; in that case, one or more of its child pointers can be NULL. Image by MIT OpenCourseWare. user.c contains the main() function. We will replace this function with one for grading. You should use your main() function to test that your functions to insert into and search the binary tree work correctly. This is a C/C++ course, not an algorithms course, but if you want a challenge, try implementing node deletion as well! Your job is to complete the data structure and function declarations in bintree.h, then complete the implementation of your functions in bintree.c. If you want to define additional functions to simplify your program, that's fine. You cannot change the return types or argument types of the included functions, though. Even though we don't require the deletion function, make sure to free all memory you allocate! Make sure your program compiles without warning, runs, and definitely use valgrind to ensure you have no memory leaks. $ gcc -Wall -std=c99 user.c bintree.c -o bintree
$ ./bintree
Solutions Solutions are not available for this assignment. Need help getting started? Don't show me this again Don't show me this again Welcome! This is one of over 2,400 courses on OCW. Explore materials for this course in the pages linked along the left. MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum. No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates. Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW. Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.) Learn more at Get Started with MIT OpenCourseWare Find Courses Find by Topic Find by Course Number Find by Department New Courses Most Visited Courses OCW Scholar Courses Audio/Video Courses Online Textbooks Instructor Insights Supplemental Resources MITx & Related OCW Courses MIT Open Learning Library Translated Courses For Educators Chalk Radio Podcast OCW Educator Portal Instructor Insights by Department Residential Digital Innovations OCW Highlights for High School Additional Resources Give Now Make a Donation Why Give? Our Supporters Other Ways to Contribute Become a Corporate Sponsor About About OpenCourseWare Site Statistics OCW Stories Newsletter Open Matters Blog Tools Help & FAQs Contact Us Accessibility Site Map Privacy & Terms of Use RSS Feeds Our Corporate Supporters About MIT OpenCourseWare MIT OpenCourseWare is an online publication of materials from over 2,500 MIT courses, freely sharing knowledge with learners and educators around the world. Learn more » © 2001–2018 Massachusetts Institute of Technology Your use of the MIT OpenCourseWare site and materials is subject to our Creative Commons License and other terms of use.
