English edition note: These are historical study notes. The C++ standard library provided containers before C++11. The GLib/glibc comparison and the data-type table are informal summaries and need to be checked against the relevant language and library documentation.
#π What is a data structure?
A typical programming process
- Understand and analyze the problem
- Design the program variables
- Design the program logic (algorithms and flowcharts)
- Write the program
- Run and debug the program
Data structures belong to the design of program variables:
- identify data objects and their attributes;
- define and implement relationships between data and the operations on them. They provide systematic and efficient methods for doing so.
Data types used in data structures
| Data type | Set of data objects | Example operations | Internal representation |
|---|---|---|---|
| Integer | Numbers without a fractional part | +, -, *, /, %, ++, β, (and others) | Fixed-point representation |
| Real number | Numbers with a fractional part | +, -, *, /, %, ++, β, (and others) | Floating-point representation |
| Character | The character set defined by the computer system | +, -, <, >, (and others) | ASCII representation |
| Array | A collection of values of the same type | x[i] | Sequential representation of homogeneous objects |
| Structure | A collection of values of different types | x.member | Sequential representation of heterogeneous objects |
#π Classification of data structures
- Data types provided by a programming language (basic representations of data objects)
- Simple types: integer, real, character, Boolean and pointer types
- Structured types: arrays, structures, strings and others
- Structures studied in a data structures course (representations for managing sets of data objects)
- Linear list structures
- Sequential list: an ordered list implemented using sequential mapping
- Linked list: an ordered list implemented using nonsequential mapping
- Stack: a last-in, first-out (LIFO) list
- Queue: a first-in, first-out (FIFO) list
- Nonlinear structures
- Trees and binary trees: binary search trees, m-way search trees, heaps and others
- Graphs: directed graphs, undirected graphs and others
- Hash tables
- Index trees: AVL trees, B trees, B+ trees, red-black trees and others
#π Data structures in C (libraries)
C does not directly provide the data structures discussed here, so they must be implemented to use them. Third-party libraries do provide these data structures.
One is GLib.
(Take care not to confuse it with glibc.)
GLib and glibc compared
| GLib | glibc | |
|---|---|---|
| Data structures | Arrays, queues, linked lists, hash tables, trees and others | Queues, lists, trees and others |
| Object system | GObject | - |
| IO | iostream, file input/output | fopen, fwrite, fread, fclose and others |
#π Data structures in C++ (STL)
Since the C++11 standard, containers (data structures) and algorithms are provided by the standard library.
- STL means
- Standard Template Library
What is a template: C++