Data Structures and Algorithms - Exam 1 Study Guide, Data
Structures Exam 1, Data Structures: Exam 1, Data
Structures and Algorithms Test 1
Abstract Data Types
An abstract data type (ADT) is a data type whose creation and update are constrained to specific
well-defined operations.
It's described by predefined user operations, such as "insert data at rear", without indication
how each operation is implemented.
Abstraction v. Implementation
Abstraction: In many languages, abstraction usually involves some sort of interface for a
programmer by using an API or library. When we write programs that use these interfaces, we
often do not care about how the function is actually implemented, but are just interested about
the input and output values. In a word, abstraction is about the overall idea.
Implementation: This is where we actually care about how something is done "under the hood".
We have to consider how our code's speed and efficiency is determined by the realities of the
hardware (e.g. locality is something that needs to be taken into account). There are usually
many ways to solve a problem, and implementation is all about which one is the best and how
we do it.
The implementation can contain calls to interfaces of another API intersecting abstraction and
implementation. Figure 1 shows an example of this idea using threads as our abstraction, the
pthread library as our interface, and the chain of events that occur when calling a function like
pthread_create() as our implementation. Notice how this chain switches between interface calls
and implementation details.
Data Structure
A data structure is a way of organizing, storing, and performing operations on data. Operations
performed on a data structure include accessing or updating stored data, searching for specific
data, inserting new data, and removing data. *see list of basic data structures
Break a class across two files
,Typical two files per class:
ClassName.h Contains the class definition, including data members and member function
declarations.
ClassName.cpp Contains member function definitions.
.hpp file
Header files should contain function declarations for functions defined in another file.
.cpp file
Cpp files should contain function definitions for functions declared in another file.
Why guard an .hpp file?
Header file guards are preprocessor directives, which cause the compiler to only include the
contents of the header file once.
Guards:
#ifndef FILENAME_H
#define FILENAME_H
//Header file contents
#endif
Compiling a program Modularly
As programs become larger and the number of source files increases, the time required to
recompile and link all source files can become very long - often requiring minutes to hours.
Instead of compiling an executable using a single step, a modular compilation approach can be
used that separates the compiling and linking steps within the compilation process. In this
approach, each source file is independently compiled into an object file. An object file contains
machine instructions for the compiled code along with placeholders, often referred to as
references, for calls to functions or accesses to variables or classes defined in other source files
or libraries.
For a program involving two files main.cpp and threenumsfcts.cpp, the files can be compiled
separately into two object files named main.o and threenumsfcts.o respectively. The resulting
, object files will include several placeholders for functions that are defined in other files. For
example, the main.o object file may contain placeholders for calls to any functions in
threenumsfcts.o.
After each source file has been compiled, the linker will create the final executable by linking
together the object files and libraries. For each placeholder found within an object file, the
linker searches the other object files and libraries to find the referenced function or variable.
When linking the main.o and threenumsfcts.o files, the placeholder for a call to a function in
main.o will be replaced with a jump to the first instruction of that function within the
threenumsfcts.o object file. This creates a link between the code within the main.o and
threenumsfcts.o object files. Once all placeholders have been linked together, the final
executable can be created. The following animation illustrates.
Basic Compilation Commands
g++ main.cpp threenumsfcts.cpp
Create a Makefile
Targets, Commands, Macros
When the make command is executed, if any of the prerequisites for the rule have been
modified since the target was last created, the commands for the rule will be executed to create
the target file. For example, in the above makefile, if main.cpp is modified, then make will first
execute the command g++ -Wall -c main.cpp to create the main.o object file. The -c flag is used
here to inform the compiler (e.g., g++) that the source file should only be compiled (and not
linked) to create an object file. As main.o has now been modified, make will then execute the
command g++ main.o threeintsfcts.o -o myprog.exe. The -o flag is used here to inform the linker
(e.g., g++) to link the object files into the final executable using the name specified after the -o.
In this case, the executable is named myprog.exe.
Make rules can also be used to define common operations used when managing larger
programs. One common make rule is the clean : rule that is used to execute a command for
deleting all generated files such as object files and the program executable. In the above
example, this is accomplished by running the command rm *.o myprog.exe.
By default make assumes the makefile is named makefile or Makefile. The -f flag can be used to
run make using a different filename. For example, make -f MyMakefile will run make using the
file named MyMakefile.
Structures Exam 1, Data Structures: Exam 1, Data
Structures and Algorithms Test 1
Abstract Data Types
An abstract data type (ADT) is a data type whose creation and update are constrained to specific
well-defined operations.
It's described by predefined user operations, such as "insert data at rear", without indication
how each operation is implemented.
Abstraction v. Implementation
Abstraction: In many languages, abstraction usually involves some sort of interface for a
programmer by using an API or library. When we write programs that use these interfaces, we
often do not care about how the function is actually implemented, but are just interested about
the input and output values. In a word, abstraction is about the overall idea.
Implementation: This is where we actually care about how something is done "under the hood".
We have to consider how our code's speed and efficiency is determined by the realities of the
hardware (e.g. locality is something that needs to be taken into account). There are usually
many ways to solve a problem, and implementation is all about which one is the best and how
we do it.
The implementation can contain calls to interfaces of another API intersecting abstraction and
implementation. Figure 1 shows an example of this idea using threads as our abstraction, the
pthread library as our interface, and the chain of events that occur when calling a function like
pthread_create() as our implementation. Notice how this chain switches between interface calls
and implementation details.
Data Structure
A data structure is a way of organizing, storing, and performing operations on data. Operations
performed on a data structure include accessing or updating stored data, searching for specific
data, inserting new data, and removing data. *see list of basic data structures
Break a class across two files
,Typical two files per class:
ClassName.h Contains the class definition, including data members and member function
declarations.
ClassName.cpp Contains member function definitions.
.hpp file
Header files should contain function declarations for functions defined in another file.
.cpp file
Cpp files should contain function definitions for functions declared in another file.
Why guard an .hpp file?
Header file guards are preprocessor directives, which cause the compiler to only include the
contents of the header file once.
Guards:
#ifndef FILENAME_H
#define FILENAME_H
//Header file contents
#endif
Compiling a program Modularly
As programs become larger and the number of source files increases, the time required to
recompile and link all source files can become very long - often requiring minutes to hours.
Instead of compiling an executable using a single step, a modular compilation approach can be
used that separates the compiling and linking steps within the compilation process. In this
approach, each source file is independently compiled into an object file. An object file contains
machine instructions for the compiled code along with placeholders, often referred to as
references, for calls to functions or accesses to variables or classes defined in other source files
or libraries.
For a program involving two files main.cpp and threenumsfcts.cpp, the files can be compiled
separately into two object files named main.o and threenumsfcts.o respectively. The resulting
, object files will include several placeholders for functions that are defined in other files. For
example, the main.o object file may contain placeholders for calls to any functions in
threenumsfcts.o.
After each source file has been compiled, the linker will create the final executable by linking
together the object files and libraries. For each placeholder found within an object file, the
linker searches the other object files and libraries to find the referenced function or variable.
When linking the main.o and threenumsfcts.o files, the placeholder for a call to a function in
main.o will be replaced with a jump to the first instruction of that function within the
threenumsfcts.o object file. This creates a link between the code within the main.o and
threenumsfcts.o object files. Once all placeholders have been linked together, the final
executable can be created. The following animation illustrates.
Basic Compilation Commands
g++ main.cpp threenumsfcts.cpp
Create a Makefile
Targets, Commands, Macros
When the make command is executed, if any of the prerequisites for the rule have been
modified since the target was last created, the commands for the rule will be executed to create
the target file. For example, in the above makefile, if main.cpp is modified, then make will first
execute the command g++ -Wall -c main.cpp to create the main.o object file. The -c flag is used
here to inform the compiler (e.g., g++) that the source file should only be compiled (and not
linked) to create an object file. As main.o has now been modified, make will then execute the
command g++ main.o threeintsfcts.o -o myprog.exe. The -o flag is used here to inform the linker
(e.g., g++) to link the object files into the final executable using the name specified after the -o.
In this case, the executable is named myprog.exe.
Make rules can also be used to define common operations used when managing larger
programs. One common make rule is the clean : rule that is used to execute a command for
deleting all generated files such as object files and the program executable. In the above
example, this is accomplished by running the command rm *.o myprog.exe.
By default make assumes the makefile is named makefile or Makefile. The -f flag can be used to
run make using a different filename. For example, make -f MyMakefile will run make using the
file named MyMakefile.
