This repository has been archived by the owner on Feb 10, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
dl_list_readme.txt
119 lines (90 loc) · 3.89 KB
/
dl_list_readme.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
Это инструкция по использованию двусвязного списка.
Внутренние файлы списка: dl_list.c, dl_cells.c, dl_cell_test, dl_list_test
Заголовочный файл: dl_list.h
Список состоит из ячеек:
Объявление ячейки: struct cell <name>
Внутреннее строение (работа напрямую не предусмотрена):
struct cell {
struct cell* prev;
struct cell* next;
long long int data;
struct cache_t* cache_ptr;
};
Доступные функции:
Создание одной ячейки:
struct cell* make_cell()
Создает ячейку, возвращает указатель на нее. Имя по умолчанию 0, указатель на страницу отсутствует.
Не забудьте почистить память после использования.
struct cell* make_cell_n(long long int name)
Создает ячейку с заданным именем
struct cell* make_cell_p(long long int name, struct cache_t* cache_ptr)
Создает ячейку с заданным указателем.
struct cell* make_cell_np(long long int name, struct cache_t* cache_ptr)
Создает ячейку с заданным именем и указателем.
Извлечение ячейки:
struct cell* extract_cell(struct cell* c);
Извлекает ячейку из списка, стирает все ее связи. Дыры в списке затягиваются.
Уничтожение ячейки:
void destroy_cell(struct cell* c)
Уничтожает одну ячейку по введенному указателю, очищая память.
Затягивает "дыры", которые могли остаться на ее месте.
void destroy_all_cells(struct cell* c)
Уничтожает указанную ячейку и все, которые с ней связаны.
Предусмотрена работа на зацикленных списках.
Перемещение ячейки:
struct cell* place_cell_before(struct cell* c, struct cell* place)
struct cell* place_cell_after(struct cell* c, struct cell* place)
Перемещает ячеку *с на позицию до или после *place. Затягивает "дыры", которые могли остаться на старом месте.
Вставление между двумя подряд идущими ячейками предусмотрено.
Получение имени ячейки:
long long int cell_name(struct cell* c)
Возвращает имя ячейки по указателю.
Переход к предыдущей/следующей ячейке:
struct cell* next_cell(struct cell* c)
struct cell* prev_cell(struct cell* c)
Получает указатель на текущую ячейку, возвращает указатель на следующую/предыдущую.
Работа с указателем ячейки:
struct cell* set_page(struct cell* c, struct cache_t* cache_ptr)
Записывает в ячейку значение введенного указателя, старый при наличии безвозвратно затирается.
Возращает указатель на ячейку.
struct cache_t* cell_page(struct cell* c)
Возвращает записанный в ячейку указатель. При отстутствии возращает NULL.
Поиск ячейки:
struct cell* find_cell(struct list_t* l, long long int name)
Ищет ячейку с заданным именем, возвращает указатель на нее. l - указатель на список.
При наличии нескольких ячеек с одинаковым именем возвращает любую.
Нахождение длины списка:
unsigned long long list_len(struct cell* c)
Возвращает длину списка по любой его ячейке. Предусмотрена работа с зацикленными списками.
Сам список представлен открытой для внешнего использования структурой
struct list_t {
struct cell* head;
unsigned long long length;
struct cell* last_found_elem;
struct cell* end;
};
Функции для работы со списком:
Создание списка без ячеек
struct list_t* make_list()
Возвращает указатель на список. Все указатели NULL, длина 0.
Удаление списка (вместе с ячейками)
void destroy_list(struct list_t* l)
Поиск элемента списка по названию.
struct cell* find_list_elem(struct list_t* l, long long int name)
Найденный элемент возвращается функцией.
Вставка элемента в начало списка
struct cell* insert_to_head(struct list_t* l, struct cell* c)
Перестановка элемента
struct cell* replace_lf_to_head(struct list_t* cur, struct list_t* next, struct cell* c)
Cur и next могут быть как разными, так и одним и тем же списком.
Проверяется наличие c в cur
Удаляет последний элемент списка.
void delete_last_elem(struct list_t* l)
Тесты находятся под условной компиляцией:
Тестирование работоспособности ячеек списка:
void dl_cell_test()
Для включения: определить CELL_TEST
Тестирование работоспособности списка:
void dl_list_test()
Сделано при помощи реализации сортировки вставками.
Для включения: определить LIST_TEST