Начало
Учебные материалыПодразделы
Другие разделы
| Введение |
| Массивы, строки и структуры |
| Операторы |
| Операции |
| Переменные и типы |
| Пояснения к курсовой работе |
| Препроцессор |
| Работа с файлами |
| Стандарты безопасного кодирования |
| Функции и модули |
| Ввод-вывод |
Дата и время
05/12/2025 21:45:09
Указатели и динамическая память
Указатели Указатели и функции, передача по ссылке в С++ Побочные эффекты и чистые функции Управление динамической памятью Списки *
Списки *
[Визуализатор операций с односвязным списком](/viz/list1.html)
Список не обеспечивает прямого доступа к элементам набора по номеру. Для перемещения по списку и получения значения используется итератор списка (указатель на текущий элемент).
```cpp
// Тип для узла списка
typedef struct Node {
int value;
struct Node *next;
} Node;
// Тип для итератора списка
typedef struct {
Node* curr=nullptr;
bool isDone() { return !curr; }
void GotoNext() { if(curr) curr=curr->next; }
int& Item() {
if(curr)
return curr->value;
else {
printf("Конец списка\n");
exit(1);
}
}
} ListIterator;
// Тип для всего списка
typedef struct {
Node* root=nullptr;
void AddFront(int v) {
Node* p=malloc(sizeof(Node));
p->value=v;
p->next=root;
root=p;
}
void DelFront() {
if(root) {
Node* p=root->next;
free(root);
root=p;
}
}
void AddAfter(ListIterator& li, int v) {
if(li.curr) {
Node* p=malloc(sizeof(Node));
p->value=v;
p->next=li.curr->next;
li.curr->next=p;
}
}
void DelAfter(ListIterator& li) {
if(li.curr && li.curr->next) {
Node* p=li.curr->next->next;
free(li.curr->next);
li.curr->next=p;
}
}
void GotoFirst(ListIteraror& li) {
li.curr=root;
}
void DelAll() {
while(root) DelFront();
}
} List;
// Примеры действий со списком
List a;
a.AddFront(1);
a.AddFront(2);
ListIterator ai;
for(a.GotoFirst(ai); !ai.isDone(); ai.GotoNext())
printf("%d\n",ai.Item());
```
Если в итераторе хранить указатели на текущий и предыдущий элементы, то не нужно будет разделять функции по удалению или добавлению значений в начало и середину списка:
[Визуализатор операций с другим итератором](/viz/list2.html)
```cpp
// Тип для узла списка
typedef struct Node {
int value;
struct Node *next;
} Node;
// Тип для итератора списка
typedef struct {
Node* curr=nullptr;
Node* prev=nullptr;
bool isDone() { return !curr; }
void GotoNext() { if(curr) {
prev=curr;
curr=curr->next; }}
int& Item() {
if(curr)
return curr->value;
else {
printf("Конец списка\n");
exit(1);
}
}
} ListIterator;
// Тип для всего списка
typedef struct {
Node* root=nullptr;
void AddFront(int v) {
Node* p=malloc(sizeof(Node));
p->value=v;
p->next=root;
root=p;
}
void InsertBefore(ListIterator& li, int v) {
if(li.curr) {
Node* p=malloc(sizeof(Node));
p->value=v;
if(li.prev) {
p->next=li.prev;
li.prev=p;
}
else {
p->next=root;
root=li.prev=p;
}
}
}
void InsertAfter(ListIterator& li, int v) {
if(li.curr) {
Node* p=malloc(sizeof(Node));
p->value=v;
p->next=li.curr->next;
li.curr->next=p;
}
}
void DelNode(ListIterator& li) {
if(li.curr) {
Node* p=li.curr->next;
free(li.curr);
li.curr=p;
if(li.prev)
li.prev->next=p;
else
root=p;
}
}
void GotoFirst(ListIteraror& li) {
li.prev=nullptr;
li.curr=root;
}
void DelAll() {
ListIterator li;
GotoFirst(li);
while(li.isDone()) DelNode(li);
}
} List;
```
Также упрощаются действия, если хранить указатель не только на следующий, но и на предыдущий элемент списка:
[Визуализатор операций с двусвязным списком](/viz/list3.html)
```cpp
// Тип для узла списка
typedef struct Node {
int value;
struct Node *next;
struct Node *prev;
} Node;
// Тип для итератора списка
typedef struct {
Node* curr=nullptr;
bool isDone() { return !curr; }
void GotoNext() { if(curr) curr=curr->next; }
void GotoPrev() { if(curr) curr=curr->prev; }
int& Item() {
if(curr)
return curr->value;
else {
printf("Конец списка\n");
exit(1);
}
}
} ListIterator;
// Тип для всего списка
typedef struct {
Node* root=nullptr;
Node* last=nullptr;
int size=0;
void AddFront(int v) {
Node* p=malloc(sizeof(Node));
p->value=v;
p->next=root;
p->prev=nullptr;
root=p;
if(!last) last=p;
++size;
}
void AddBack(int v) {
Node* p=malloc(sizeof(Node));
p->value=v;
p->prev=last;
p->next=nullptr;
last=p;
if(!root) root=p;
++size;
}
void InsertBefore(ListIterator& li, int v) {
if(li.curr) {
Node* p=malloc(sizeof(Node));
p->value=v;
if(li.curr->prev) {
p->next=li.curr->prev;
li.curr->prev=p;
}
else {
p->next=root;
root=li.curr->prev=p;
}
}
else
AddBack(v);
++size;
}
void InsertAfter(ListIterator& li, int v) {
if(li.curr) {
Node* p=malloc(sizeof(Node));
p->value=v;
p->next=li.curr->next;
p->prev=li.curr;
if(!li.curr->next) last=p;
li.curr->next=p;
++size;
}
}
void DelNode(ListIterator& li) {
if(li.curr) {
Node* n=li.curr->next;
Node* p=li.curr->prev;
free(li.curr);
li.curr=n;
if(p)
p->next=n;
else
root=p;
if(n)
n->prev=p;
else
last=p;
--size;
}
}
void GotoFirst(ListIteraror& li) {
li.curr=root;
}
void DelAll() {
ListIterator li;
GotoFirst(li);
while(li.isDone()) DelNode(li);
}
} List;
```
