Пример 3_8_3. Односвязный список

 

Файл 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

Результат работы программы:

 

 

Задания для самостоятельной работы