1 INTRODUCTION
Introduction
Definition: A data structure is a way to store and organize data in order to facilitate access and modifications.
- It is important to choose an appropriate data structure for a problem, because each data structure has its own advantages and disadvantages.
Definition: An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.
- The crucial question is: which algorithms are efficient in the chosen data structure?
1.1 C++ Data Type
Data Type
Definition: Data type T = \langle V, O \rangle
- V is a set of values
- O is a set of operations or methods
Example: Consider short int T
- V =
{-32768, ..., 32767} - O =
{+, -, *, /}
C++ Primitive Data Types
| Data Type | Size | Operations |
|---|---|---|
bool |
1 | … |
char, unsigned char |
1 | … |
short, unsigned short |
2 | … |
int, unsigned int |
4 | … |
long, unsigned long |
4 | … |
long long, unsigned long long |
8 | … |
float |
4 | … |
double |
8 | … |
C++ Structured Data Types
stringstructclass- array
1.2 Abstract Data Type
Abstract Data Type (ADT)
Definition:
- An abstract data type (ADT) is a specification for a group of values and the operations on those values.
- A data structure is an implementation of an ADT within a programming language.
Example: A Stack is an iterable collection of items that is based on the last-in-first-out (LIFO) policy.
| Method | Description |
|---|---|
push |
add an item to the stack |
pop |
remove the most recently added item |