Файл list 1. h //определение списка и его операций
#ifndef _LIST1_Н //предотвращение многократного
#define _LIST1_Н //включения заголовочного файла
#include <iostream>
using std::endl;
using std::cout;
// Элемент списка
struct Elem {
int x; //данные – целое значение
Elem* next; //указатель на следующий элемент списка
};
//Операции со списком:
//Добавление элемента в конец списка
void add_end(Elem **start, const int& a)
{
Elem *tmp, //адрес нового, добавляемого элемента
*cur; //текущий указатель для прохода по списку
tmp = new Elem; //выделение памяти для нового элемента
if (!tmp) { //если память не выделена, тогда возврат
cout<<"память для элемента не выделена"<<endl;
return;
}
tmp->x = a; //занесение данных в новый элемент
tmp->next = NULL; //новый элемент – последний в списке
if (!*start) //если список пуст,
*start = tmp; //формирование нового списка
else{
//продвижение по списку до последнего элемента
cur = *start;
while (cur->next) // пока cur->next не равно 0
cur = cur->next; //перемещение указателя на следующий элемент
cur->next = tmp; //ссылка последнего элемента на новый,
//добавляемый в конец списка
}
return;
}
Обратите внимание на прототип функции добавления элемента в конец списка:
void add_end(Elem **start, const int& a)
Указатель на начало списка должен быть описан как двойной указатель. Значением start является указатель, который передается в функцию по адресу. Таким образом, в функции add _ end формальный параметр start (указатель на начало списка) является указателем на указатель на структуру данных Elem.
//Удаление последнего элемента списка
void del _ end (Elem * start)
{
Elem *prev, //указатель на предпоследний элемент списка
*end; //указатель на последний элемент списка
if (!start){ //если список пуст,
cout<<"Список пуст"<<endl;//тогда возврат
return;
}
if (!start->next){ //если в списке один элемент,
delete start; start=NULL; // удаление списка
return;
}
//продвижение по списку до последнего элемента
end = start;
while (end->next){ // пока end->next не равно 0
prev = end; //запоминание адреса предыдущего элемента
end = end->next; //перемещение указателя на следующий элемент
}
delete end; //удаление последнего элемента списка
prev->next = NULL; //предпоследний элемент становится последним
return;
}
//Вывод значений данных элементов списка
void print_list(const Elem *start)
{
Elem *tmp; //указатель на текущий элемент списка
if (!start){ //если список пуст,
cout<<"Список пуст"<<endl; //тогда возврат
return;
}
//продвижение по списку до последнего элемента
tmp = const_cast<Elem *>(start);
while (tmp){ //пока в списке есть элементы – tmp не равно 0
cout<<tmp->x<<" "; //вывод данных текущего элемента списка
tmp = tmp->next; //перемещение указателя на следующий элемент
}
cout<<endl;
return;
}
// Удаление списка
void del_list(Elem *start)
{
Elem *tmp,
*prev; //вспомогательные указатели
if (!start){ //если список пуст,
cout<<"Список пуст"<<endl; //тогда возврат
return;
}
//продвижение по списку и удаление элементов
tmp = start;
while (tmp){ //пока в списке есть элементы
prev = tmp; //запоминание адреса текущего элемента
tmp = tmp->next; //перемещение указателя на следующий элемент
delete prev; //удаление текущего элемента
}
start = NULL; // список пуст
return;
}
# endif _ LIST 1_Н
Файл List 1. cpp //использование списка
# include " list 1. h " //включение описания массива
// и файла <iostream>
Int main()
{
Elem * start = NULL; //сначала список пуст
for (int i =0; i <5;++ i) //формирование списка из 5 элементов
add_end(&start, i+1);// данные списка: 1, 2, 3, 4, 5
print _ list (start); //вывод значений данных элементов списка
del _ end (s tart); //удаление последнего элемента списка
del_end (start); //удаление последнего элемента списка
print_list(start); //вывод значений данных элементов списка
system("pause");
del_list (start); // удаление списка
return 0;
}
Формируемая в примере структура списка показана на рисунке 3.5.
Рисунок 3.5 – Структура списка в окне отладки MS Visual Studio
Результат работы программы:
Задания для самостоятельной работы
