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

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

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

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. Написать функцию для создания списка. Функция может создавать пустой список, а затем добавлять в него элементы.

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. Результаты выполнения работы.

Библиографический список

1. Подбельский В. В., Фомин С. С. Программирование на языке Си: Учеб. пособие. –М.:Финансы и статистика, 1998.–600с.

2. Подбельский В. В. Язык Си++: Учеб. пособие.–М.:Финансы и статистика, 1996.–560с.

3. Страуструп Б. Язык программирования Си++: Пер. с англ. – М.: Радио и связь, 1991.-352с.