Краткие теоретические сведения. Во многих задачах требуется использовать данные у которых конфигурация

Во многих задачах требуется использовать данные у которых конфигурация, размеры, состав могут изменяться в процессе выполнения программы. Для их представления используют динамические информационные структуры.

Наиболее простая информационная структура – это односвязный список, элементами которого служат объкты структурного типа. Например

struct имя_структурного_типа

{

элементы_структуры;

struct имя_структурного_типа *указатель;

}

В каждую структуру такого типа входит указатель на объект того же типа, что и определяемая структура.

beg

Примеры:

1. Описание структуры

struct point

{int key;

point* next;

};

Поле key содержит информационную часть структуры point, а поле next содержит адрес следующего элемента списка.

2. Функция для формирования однонаправленного списка

point* make_point( int n)

{

point *first, *p;

first=NULL;

for (int i=n;i>0;i--)

{

p=new(point);

p->key=i;

p->next=first;

first=p;

}

return first;

}

В качестве параметра в функцию передается количество элементов в списке, а результатом является указатель на первый элемент этого списка. Указатель р указывает на вновь создаваемый элемент. Для обращения к полям используется операция доступа к элементу структуры, с которой связан указатель ->. Существует вторая возможность обращения к полю динамической структуры: (*p).key или (*p).next. В информационное поле key заносится порядковый номер элемента в списке. Добавление новых элементов осуществляется в начало списка.

3. Функция для печати однонаправленного списка

point* print_point(point*first)

{

if (first==NULL)return NULL;

point*p=first;

while(p!=NULL)

{

cout<<p->key<<" ";

p=p->next;

}

return first;

}

При печати сформированного списка осуществляется проход по списку с помощью вспомогательной переменной р до тех пор, пока она не станет равна NULL.

Постановка задачи

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

Для каждого вариант разработать следующие функции:

1. Создание списка.

2. Добавление элемента в список (в соответствии со своим вариантом).

3. Удаление элемента из списка (в соответствии со своим вариантом).

4. Печать списка.

5. Запись списка в файл.

6. Уничтожение списка.

7. Восстановление списка из файла.

1. Порядок выполнения работы

1. Написать функцию для создания списка. Функция может создавать пустой список, а затем добавлять в него элементы.

2. Написать функцию для печати списка. Функция должна предусматривать вывод сообщения, если список пустой.

3. Написать функции для удаления и добавления элементов списка в соответствии со своим вариантом.

4. Выполнить изменения в списке и печать списка после каждого изменения.

5. Написать функцию для записи списка в файл.

6. Написать функцию для уничтожения списка.

7. Записать список в файл, уничтожить его и выполнить печать (при печати должно быть выдано сообщение "Список пустой").

8. Написать функцию для восстановления списка из файла.

9. Восстановить список и распечатать его.

10. Уничтожить список.

Варианты заданий

1. Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным номером, добавить элемент с заданным номером;

2. Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным ключом, добавить элемент перед элементом с заданным ключом;

3. Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него К элементов, начиная с заданного номера, добавить элемент перед элементом с заданным ключом;

4. Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным номером, добавить К элементов, начиная с заданного номера;

5. Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него К элементов, начиная с заданного номера, добавить К элементов, начиная с заданного номера;

6. Записи в линейном списке содержат ключевое поле типа int. Сформировать двунаправленный список. Удалить из него элемент с заданным номером, добавить элемент в начало списка.

7. Сформировать двунаправленный список. Удалить из него первый элемент, добавить элемент в конец списка.

8. Записи в линейном списке содержат ключевое поле типа int. Сформировать двунаправленный список. Удалить из него элемент после элемента с заданным номером, добавить К элементов в начало списка.

9. Записи в линейном списке содержат ключевое поле типа int. Сформировать двунаправленный список. Удалить из него К элементов перед элементом с заданным номером, добавить К элементов в конец списка.

10. Записи в линейном списке содержат ключевое поле типа int. Сформировать двунаправленный список. Добавить в него элемент с заданным номером, удалить К элементов из конца списка.

11. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить из него элемент с заданным ключом, добавить элемент с указанным номером.

12. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить из него Элементы, с одинаковыми ключевыми полями. Добавить элемент после элемента с заданным ключевым полем.

13. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить из него К первых элементов. Добавить элемент после элемента, начинающегося с указанного символа.

14. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить из него К элементов с указанными номерами. Добавить К элементов с указанными номерами.

15. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить К элементов из конца списка. Добавить элемент после элемента с заданным ключом.

16. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов в конец списка.

17. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным номером. Добавить К элементов в начало списка.

18. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов в начало списка.

19. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить К элементов с заданными номерами. Добавить К элементов в начало списка.

20. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить по К элементов в начало и в конец списка.

21. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элементы перед и после элемента с заданным ключом. Добавить по К элементов в начало и в конец списка.

22. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов перед элементом с заданным ключом.

23. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов после элемента с заданным ключом.

24. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным номером. Добавить по К элементов перед и после элемента с заданным ключом.

25. Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов перед элементом с заданным номером.

Содержание отчета

1. Постановка задачи.

2. Функции для работы со списком.

3. Функция main().

4. Результаты выполнения работы.