Линейный список — это динамическая структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.
Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (next). Поле ссылки последнего элемента должно содержать пустой указатель (NULL).
Так как ссылка всего одна (только на следующий элемент), то такой список является односвязным.
Когда говорят о линейном списке, то, как правило, подразумевают именно односвязный список.
Пример. Сформировать список, содержащий целые числа 3, 5, 1, 9.
Решение. При работе с динамическими структурами данных можно рекомендовать следующий порядок действий.
а) Прежде всего необходимо определить две структуры:
структура, содержащая характеристики данных, то есть все те поля с данными, которые необходимы для решения поставленной задачи (в нашем случае имеется всего одно поле целого типа). Назовём эту структуру Data;
структура, содержащая поле типа Data и поле — адрес последующего элемента next. Вторую структуру назовём List.
Тексты этих структур необходимо расположить в начале программы (до main() и других функций). Вот возможная реализация структур:
struct Data
{
int a;
};
struct List
{
Data d;
List *next;
};
Такой подход позволит в дальнейшем изменять в широких пределах структуру с собственно данными, никак не затрагивая при этом основную структуру List.
Итак, мы описали структурный тип, с помощью которого можно создать наш односвязный список. Графически создаваемый список можно изобразить так, как это показано на рисунке ниже:
б) В программе (обычно в функции main()) определяем указатель на начало будущего списка:
List *u = NULL;
Пока список пуст, и указатель явно задан равным константе NULL.
в) Выполняем первоначальное заполнение списка.
Создадим первый элемент:
u = new List; // Выделяем память под элемент списка
u->d.a = 3; // Заполняем поля с данными
// (здесь это всего одно поле)
u->next = NULL;// Указатель на следующий элемент пуст
После включения первого элемента список можно изобразить так:
Продолжим
формирование списка, добавляя новые элементы в его конец. Для
удобства заведём вспомогательную переменную-указатель, которая будет
хранить адрес последнего элемента списка:
List *x;
x = u; // Сейчас последний элемент списка совпадает с его началом
Таким
образом, к области памяти можно обратиться через два указателя.
Выделяем место в памяти для следующего элемента списка и перенаправляем указатель x на выделенную область памяти:
x->next = new List;
x = x->next;
Затем определяем значение этого элемента списка:
x->d.a = 5;
x->next = NULL;
Получилась такая схема:
Этот
процесс продолжаем до тех пор, пока не будет сформирован весь список.
Действия со сформированным списком
Сформировав начальный список, можно выполнять с ним различные действия. Настоятельно рекомендуется каждую операцию со списком оформлять в виде отдельной функции. Такой подход заметно упрощает разработку программы и возможную её дальнейшую модификацию. Понятно, что и только что рассмотренное формирование начального списка также лучше записать в виде функции.
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;
На других операциях с двухсвязными списками останавливаться не будем, так как их можно разработать по аналогии с операциями для односвязных списков.
Кольцевой список — это список, у которого последний элемент связан с первым. Кольцевой список можно сделать как односвязным, так и двухсвязным. Рассмотрим вкратце односвязный кольцевой список.
Схема кольцевого списка представлена на рисунке ниже (используем те же данные, что и для ранее рассмотренного односвязного списка, т.е. список из чисел 3, 5, 1, 9):
Используем
те же структуры (Data
и List), что
применяли для односвязного списка. Точно так же определяем
указатель на начало будущего списка:
List *u = NULL;
и так же делаем начальное заполнение списка. Но в конце, после того, как для нашего примера мы занесли число 9 в список, требуется «замкнуть» список на начало:
x->next = u;
В итоге будет получен кольцевой список.
Операции для кольцевого списка можно выполнять те же, что и для обычного списка, но здесь будет присутствовать одна особенность: список замкнут, поэтому проверка того факта, что достигнут конец цикла, выполняется по другому. Покажем это на примере распечатки кольцевого цикла:
void printC(List *u)
{
if(u != NULL)
{
List *p = u;
cout << "Kolcevoj Spisok:" << endl;
cout << p->d.a << endl;
p = p->next;
while(p != u)
{
cout << p->d.a << endl;
p = p->next;
}
}
else
cout << "Spisok pust." << endl;
}
Возможный вызов функции:
printC(u);
Как видно из примера, после печати первого элемента, мы печатаем не до конца списка, а до нахождения начала.
Другие операции для кольцевого списка разработайте самостоятельно.
|
|
|
|
