Действия со сформированным списком
Сформировав начальный список, можно выполнять с ним различные действия. Настоятельно рекомендуется каждую операцию со списком оформлять в виде отдельной функции. Такой подход заметно упрощает разработку программы и возможную её дальнейшую модификацию. Понятно, что и только что рассмотренное формирование начального списка также лучше записать в виде функции.
1. Просмотр списка — осуществляется последовательно, начиная с его начала. Указатель последовательно ссылается на первый, второй, и т.д. элементы списка до тех пор, пока весь список не будет пройден. Приведём пример реализации просмотра, например, для вывода списка на экран монитора:
void Print(List *u)
{
List *p = u;
cout << "Spisok:" << endl;
While(p)
{
cout << p->d.a << endl;
p = p->next;
}
}
Обратиться к функции можно так:
Print(u);
Здесь и далее в примерах u — это указатель на начало списка.
2. Поиск первого вхождения в список элемента, соответствующего заданным требованиям:
List * Find(List *u, Data &x)
{
List *p = u;
While(p)
{
if(p->d.a == x.a) // условие для поиска
return p;
p = p->next;
}
return 0;
}
Возможный вызов функции:
List * v = Find(u, x);
где x — объект типа Data.
3. Добавление нового элемента в начало списка:
void Add_Beg(List **u, Data &x)
{
List *t = new List;
t->d.a = x.a;
t->next = *u;
*u = t;
}
Возможный вызов функции:
Add_Beg(&u, x);
где x — объект типа Data.
4. Вставка нового элемента в произвольное место списка по какому-нибудь принципу, например, вставка в отсортированный по возрастанию список:
|
|
|
void Insert(List **u, Data &x)
{
Вставка в список одного элемента перед элементом,
Меньшим или равным данному x
List *p = new List;
p->d.a = x.a;
if(*u == 0) // исходный список пуст - вставка в начало
{
p->next = 0;
*u = p;
return;
}
List *t = *u;
if(t->d.a >= p->d.a) // исходный список не пуст -
Вставка в начало
{
p->next = t;
*u = p;
return;
}
List *t1 = t->next;
While(t1)
{
if(t->d.a < p->d.a && p->d.a <= t1->d.a)
{ // вставка в середину
t->next = p;
p->next = t1;
return;
}
t = t1;
t1 = t1->next;
}
t->next = p; // добавляем в конец списка
p->next = 0;
}
Возможный вызов функции:
Insert(&u, x)
где x — объект типа Data.
Эта функция позволяет сразу формировать упорядоченный список.
5. Удаление элемента из линейного списка:
void Delete(List **u, Data &x)
{
if(*u == 0) // исходный список пуст - удалять нечего!
{
return;
}
List *t = *u;
if(t->d.a == x.a) // исходный список не пуст -
Удаляется начало
{
*u = t->next;
delete t;
return;
}
List *t1 = t->next;
While(t1)
{
if(t1->d.a == x.a)
Исходный список не пуст -
Удаляется не первый элемент
{
t->next = t1->next;
delete t1;
return;
}
t = t1;
t1 = t1->next;
}
}
Возможный вызов функции:
Delete(&u, x);
где x — объект типа Data.
6. Удаление (очистка) всего списка
Когда данные, хранящиеся в списке, становятся ненужными, можно очистить весь список, т.е. освободить память, которую занимали все элементы списка. Выполнять эту операцию желательно сразу после того, как список стал не нужен. Реализация этой операции может быть такой:
|
|
|
void Clear(List **u)
{
Удаление (очистка) всего списка
if(*u == 0) return;
List *p = *u;
List *t;
While(p)
{
t = p;
p = p->next;
delete t;
}
*u = 0;
}
Возможный вызов функции:
Clear(&u);
Мы рассмотрели наиболее важные действия со списками. По аналогии с ними можно реализовать и другие действия, которые могут потребоваться для решения практических задач.
Двухсвязные линейные списки
Как мы уже говорили, линейные списки могут быть односвязными и двухсвязными.
Каждый элемент односвязного списка кроме собственно данных содержит поле с адресом следующего элемента. Работу с такими списками мы только что рассмотрели.
В двухсвязном списке каждый элемент имеет поля с данными и два указателя: один указатель хранит адрес предшествующего элемента списка, второй — адрес последующего элемента. Вполне естественно для работы с двухсвязным списком использовать два указателя, хранящие адреса начала и конца такого списка. На рисунке ниже даётся графическое представление двухсвязного списка.
|
|
|
Рассмотрим особенности работы с двухсвязным списком.
1. Как и в случае с односвязным списком, создадим две структуры. Тексты этих структур расположим в начале программы (до main() и других функций). Вот возможная реализация структур:
Struct Data
{
Int a; // данные
};
Struct List2
{
Data d;
List2 *prev; // указатель на предшествующий элемент
List2 *next; // указатель на последующий элемент
};
2. Затем создаём два указателя:
List2 *Begin = NULL; // Начало списка
List2 *End = NULL; // Конец списка
3. Теперь можно формировать какой-то начальный список. Делаем это по аналогии с тем, как делали при работе с односвязными списками. Начнём формировать список из трёх чисел 3, 5 и 1:
// Создаём первый элемент
List2 *t = new List2;
t->d.a = 3;
t->prev = NULL;
t->next = NULL;
// Настроим на него оба указателя
Begin = t;
End = t;
// Создаём второй элемент
t->next = new List2;
List2 *p = t;
t = t->next;
t->prev = p;
t->d.a = 5;
t->next = NULL;
End = t;
// Создаём третий элемент
t->next = new List2;
p = t;
t = t->next;
t->prev = p;
t->d.a = 1;
t->next = NULL;
End = t;
Всё, список из трёх чисел создан. Приведём хотя бы некоторые действия с этим списком.
1.Обход списка в прямом направлении и его вывод на экран монитора:
void print_forward(List2 *Begin)
|
|
|
{
List2 *p = Begin;
cout << "Spisok (forward):" << endl;
While(p)
{
cout << p->d.a << endl;
p = p->next;
}
}
Возможный вызов функции:
print_forward(Begin);
Как видим, полученная реализация по сути является копией функции print() для печати односвязного списка.
2.Обход списка в обратном направлении и его вывод на экран монитора:
void print_back(List2 *End)
{
List2 *p = End;
cout << "Spisok (back):" << endl;
While(p)
{
cout << p->d.a << endl;
p = p->prev;
}
}
Возможный вызов функции:
print_back(End);
И здесь сходство большое. Важно обратить внимание на оператор, за счет которого выполняется движение назад:
p = p->prev;
На других операциях с двухсвязными списками останавливаться не будем, так как их можно разработать по аналогии с операциями для односвязных списков.
Дата добавления: 2020-04-25; просмотров: 194; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!