Сформировав начальный список, можно выполнять с ним различные действия. Настоятельно рекомендуется каждую операцию со списком оформлять в виде отдельной функции. Такой подход заметно упрощает разработку программы и возможную её дальнейшую модификацию. Понятно, что и только что рассмотренное формирование начального списка также лучше записать в виде функции.
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;
На других операциях с двухсвязными списками останавливаться не будем, так как их можно разработать по аналогии с операциями для односвязных списков.
Индивидуальные варианты заданий
| Вариант 1
| 1
| Описать структуру с именем STUDENT, содержащую следующие поля:
• фамилия и инициалы;
• номер группы;
• успеваемость (массив из пяти элементов).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из десяти структур типа STUDENT (записи должны быть упорядочены по возрастанию номера группы);
• вывод на экран фамилий и номеров групп для всех студентов, включенных, в массив, если средний балл студента больше 4,0 (если таких студентов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список целых чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 2
| 1
| Описать структуру с именем STUDENT, содержащую следующие поля:
• фамилия и инициалы;
• номер группы;
• успеваемость (массив из пяти элементов).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий йз десяти структур типа STUDENT (записи должны быть упорядочены по возрастанию среднего балла);
• вывод на экран фамилий и номеров групп для всех студентов, имеющих оценки 4 и 5 (если таких студентов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список дробных чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 3
| 1
| Описать структуру с именем STUDENT, содержащую следующие поля:
• фамилия и инициалы;
• номер группы;
• успеваемость (массив из пяти элементов).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из десяти структур типа STUDENT (записи должны быть упорядочены по алфавиту);
• вывод на экран фамилий и номеров групп для всех студентов, имеющих хотя бы одну оценку 2 (если таких студентов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список символов. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 4
| 1
| Описать структуру с именем AERОFLОT, содержащую следующие поля:
• название пункта назначения рейса;
• номер рейса;
• тип самолета.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из семи элементов типа AER0FL0T (записи должны быть упорядочены по возрастанию номера рейса);
• вывод на экран номеров рейсов и типов самолетов, вылетающих в пункт назначения, название которого совпало с названием, введенным с клавиатуры
(если таких рейсов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список целых чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 5
| 1
| Описать структуру с именем AER0FL0T, содержащую следующие поля:
• название пункта назначения рейса;
• номер рейса;
• тип самолета.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из семи элементов типа AER0FL0T (записи должны быть размещены в алфавитном порядке по названиям пунктов назначения);
• вывод на экран пунктов назначения и номеров рейсов, обслуживаемых самолетом, тип которого введен с клавиатуры (если таких рейсов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список дробных чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 6
| 1
| Описать структуру с именем WORKER, содержащую следующие поля:
• фамилия и инициалы работника;
• название занимаемой должности;
• год поступления на работу.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из десяти структур типа WORKER (записи должны быть упорядочены по алфавиту);
• вывод на экран фамилий работников, стаж работы которых превышает значение, введенное с клавиатуры (если таких работников нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список символов. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 7
| 1
| Описать структуру с именем TRAIN, содержащую следующие поля:
• название пункта назначения;
• номер поезда;
• время отправления.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа TRAIN (записи должны быть размещены в алфавитном порядке по названиям пунктов назначения);
• вывод на экран информации о поездах, отправляющихся после введенного с клавиатуры времени (если таких поездов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список дробных чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 8
| 1
| Описать структуру с именем TRAIN, содержащую следующие поля:
• название пункта назначения;
• номер поезда;
• время отправления.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из шести элементов типа TRAIN (записи должны быть упорядочены по времени отправления поезда);
• вывод на экран информации о поездах, направляющихся в пункт, название которого введено с клавиатуры (если таких поездов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список целых чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 9
| 1
| Описать структуру с именем TRAIN, содержащую следующие поля:
• название пункта назначения;
• номер поезда;
• время отправления.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа TRAIN (записи должны быть упорядочены по номерам поездов);
• вывод на экран информации о поезде, номер которого введен с клавиатуры (если таких поездов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список символов. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 10
| 1
| Описать структуру с именем MARSH, содержащую следующие поля:
• название начального пункта маршрута;
• название конечного пункта маршрута;
• номер маршрута.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа MARSH (записи должны быть упорядочены по номерам маршрутов);
• вывод на экран информации о маршруте, номер которого введен с клавиатуры (если таких маршрутов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список дробных чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 11
| 1
| Описать структуру с именем MARSH, содержащую следующие поля:
• название начального пункта маршрута;
• название конечного пункта маршрута;
• номер маршрута.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа MARSH (записи должны быть упорядочены по номерам маршрутов);
• вывод на экран информации о маршрутах, которые начинаются или оканчиваются в пункте, название которого введено с клавиатуры (если таких маршрутов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список дробных чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 12
| 1
| Описать структуру с именем NOTE, содержащую следующие поля:
• фамилия, имя;
• номер телефона;
• дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа NOTE (записи должны быть упорядочены по дате рождения);
• вывод на экран информации о человеке, номер телефона которого введен с клавиатуры (если такого нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список символов. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 13
| 1
| Описать структуру с именем NOTE, содержащую следующие поля:
• фамилия, имя;
• номер телефона;
• дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа NOTE (записи должны быть размещены по алфавиту);
• вывод на экран информации о людях, чьи дни рождения приходятся на месяц, значение которого введено с клавиатуры (если таких нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список целых чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 14
| 1
| Описать структуру с именем NOTE, содержащую следующие поля:
• фамилия, имя;
• номер телефона;
• дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа NOTE (записи должны быть упорядочены по трем первым цифрам номера телефона);
• вывод на экран информации о человеке, чья фамилия введена с клавиатуры (если такого нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список дробных чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 15
| 1
| Описать структуру с именем ZNAK, содержащую следующие поля:
• фамилия, имя;
• знак Зодиака;
• дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа ZNAK (записи должны быть упорядочены по дате рождения);
• вывод на экран информации о человеке, чья фамилия введена с клавиатуры (если такого нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список символов. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 16
| 1
| Описать структуру с именем ZNAK, содержащую следующие поля:
• фамилия, имя;
• знак Зодиака;
• дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа ZNAK (записи должны быть упорядочены по дате рождения);
• вывод на экран информации о людях, родившихся под знаком, название которого введено с клавиатуры (если таких нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список дробных чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 17
| 1
| Описать структуру с именем ZNAK, содержащую следующие поля:
• фамилия, имя;
• знак Зодиака;
• дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа ZNAK (записи должны быть упорядочены по знакам Зодиака);
• вывод на экран информации о людях, родившихся в месяц, значение которого введено с клавиатуры (если таких нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список символов. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 18
| 1
| Описать структуру с именем PRICE, содержащую следующие поля:
• название товара;
• название магазина, в котором продается товар;
• стоимость товара в рублях.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа PRICE (записи должны быть упорядочены в алфавитном порядке по названиям товаров);
• вывод на экран информации о товаре, название которого введено с клавиатуры
(если таких товаров нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список целых чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 19
| 1
| Описать структуру с именем PRICE, содержащую следующие поля:
• название товара;
• название магазина, в котором продается товар;
• стоимость товара в рублях.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа PRICE (записи должны быть упорядочены в алфавитном порядке по названиям магазинов);
• вывод на экран информации о товарах, продающихся в магазине, название которого введено с клавиатуры (если такого магазина нет, вывести соответствующее
сообщение).
|
| 2
| Реализовать линейный список дробных чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 20
| 1
| Описать структуру с именем ORDER, содержащую следующие поля:
• расчетный счет плательщика;
• расчетный счет получателя;
• перечисляемая сумма в рублях.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа ORDER (записи должны быть размещены в алфавитном порядке по расчетным счетам плательщиков);
• вывод на экран информации о сумме, снятой с расчетного счета плательщика, введенного с клавиатуры (если такого расчетного счета нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список дробных чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 21
| 1
| Описать структуру с именем NOTE, содержащую следующие поля:
• фамилия, имя;
• номер телефона;
• дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа NOTE (записи должны быть размещены по алфавиту);
• вывод на экран информации о людях, чьи дни рождения приходятся на месяц, значение которого введено с клавиатуры (если таких нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список символов. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 22
| 1
| Описать структуру с именем TRAIN, содержащую следующие поля:
• название пункта назначения;
• номер поезда;
• время отправления.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа TRAIN (записи должны быть упорядочены по номерам поездов);
• вывод на экран информации о поезде, номер которого введен с клавиатуры (если таких поездов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список дробных чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 23
| 1
| Описать структуру с именем AER0FL0T, содержащую следующие поля:
• название пункта назначения рейса;
• номер рейса;
• тип самолета.
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из семи элементов типа AER0FL0T (записи должны быть размещены в алфавитном порядке по названиям пунктов назначения);
• вывод на экран пунктов назначения и номеров рейсов, обслуживаемых самолетом, тип которого введен с клавиатуры (если таких рейсов нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список целых чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 24
| 1
| Описать структуру с именем NOTE, содержащую следующие поля:
• фамилия, имя;
• номер телефона;
• дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из восьми элементов типа NOTE (записи должны быть упорядочены по дате рождения);
• вывод на экран информации о человеке, номер телефона которого введен с клавиатуры (если такого нет, вывести соответствующее сообщение).
|
| 2
| Реализовать линейный список целых чисел. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
| Вариант 25
| 1
| Описать структуру с именем ZNAK, содержащую следующие поля:
• фамилия, имя;
• знак Зодиака;
• дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
• ввод с клавиатуры данных в массив, состоящий из семи элементов типа ZNAK (записи должны быть упорядочены по знакам Зодиака);
• вывод на экран информации о людях заданного с клавиатуры знака зодиака.
|
| 2
| Реализовать линейный список символов. Добавить возможность добавления и удаления элементов, вывода списка на экран.
|
Контрольные вопросы
1. Что такое структура?
2. Как объявляется структура в С++?
3. Как создать указатель на структуру?
4. Как можно инициализировать структуру?
5. Что такое линейный список?
6. Как реализуется линейный список в С++?
7. Что такое двусвязный список?
8. Как реализуется двусвязный список?
Содержание отчета
1. Титульный лист
2. Цели, задачи работы
3. Индивидуальное задание
5. Листинг программы(для каждой задачи)
6. Результат выполнения программы – скриншот (для каждой задачи)
7. Ответы на контрольные вопросы
Археология
Биология
Генетика
География
Информатика
История
Логика
Маркетинг
Математика
Менеджмент
Механика
Педагогика
Религия
Социология
Технологии
Физика
Философия
Финансы
Химия
Экология
