Лабораторная работа №13. Контейнер List. Выполнение операций над списками

Контрольные вопросы:

1. 
   Понятие списка.
   
2. 
   Как реализуются списки в языках программирования?
   
3. 
   Какие операции производят над списками?
   
4. 
   Понятие очереди.
   
5. 
   Понятие Линейного списка
   
6. 
   Последовательное представление линейных списков
   
7. 
   Связное представление линейных списков
   
8. 
   Понятие Циклического списка
   
9. 
   Списки с двумя связями
   
10. 
    Примеры применения связных списков
    

Лабораторная работа № 14. Связной список. Работа с односвязным списком.


Цель работы: Понять назначение динамических структур данных. Научиться использовать в программах односвязные списки.


Теоретическая часть:


Односвязный линейный список

Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).

Узел ОЛС можно представить в виде структуры
struct list
{
int field; // поле данных
struct list *ptr; // указатель на следующий элемент
};
Основные действия, производимые над элементами ОЛС:

• 
  Инициализация списка
  
• 
  Добавление узла в список
  
• 
  Удаление узла из списка
  
• 
  Удаление корня списка
  
• 
  Вывод элементов списка
  
• 
  Взаимообмен двух узлов списка
  

Инициализация ОЛС
Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит нулевое значение.

struct list * init(int a) // а- значение первого узла
{
struct list *lst;
// выделение памяти под корень списка
lst = (struct list*)malloc(sizeof(struct list));
lst->field = a;
lst->ptr = NULL; // это последний узел списка
return(lst);
}