РАЗДЕЛ 7.
СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
1
ПРОСТЫЕ ТИПЫ ДАННЫХ
Представление целых чисел
100001010
0
100000000 00001010
0
100000000 00000000 00000000 00001010
0
100000000 00000000 00000000 00000000
0 00000000 00000000 00000000 00001010 3
Представление отрицательных чисел
-10 |
Прямой код |
10001010 |
-10 |
Обратный код |
11110101 |
-10 |
Дополнительный |
11110110 |
|
код |
|
4
Представление вещественных чисел
СВЯЗНЫЕ СПИСКИ
Связные списки
•Связный список — это набор элементов, содержащихся в узлах (node), каждый из которых также содержит ссылку (link) на некоторый узел
•По количеству ссылок различают:
•Однонаправленные (односвязные) списки – каждый узел содержит ссылку только на следующий узел
•Двунаправленные (двусвязные) списки – каждый узел содержит ссылку на следующий и предыдущий узел
•Если последний узел ссылается на первый, то список называется циклическим, в противном случае линейным
7
Соглашения о первом элементе
•Список определяется как указатель на первый узел:
•Первый узел содержит первый элемент списка
•Первый узел является фиктивным (dummy node), его ссылка указывает на узел, содержащий первый элемент списка
8
Соглашения о ссылке последнего узла
•Ссылка последнего узла:
•Пустая ссылка (null), не указывающая на какой либо узел
•Ссылка указывает на фиктивный узел (dummy node), который не содержит элементов
9
Линейный односвязный список
С начальным и конечным фиктивными узлами
Head
dummy *
1 
*
2 *
dummy *
С начальным фиктивным узлом
Head
dummy *
1 
*
2 null
10