Лабораторная работа № 11
"Информационные динамические структуры"
Цель: Знакомство с динамическими информационными структурами на примере одно- и двунаправленных списков.
Краткие теоретические сведения
Во многих задачах требуется использовать данные у которых конфигурация, размеры, состав могут изменяться в процессе выполнения программы. Для их представления используют динамические информационные структуры.
Наиболее простая информационная структура – это односвязный список, элементами которого служат объкты структурного типа. Например
struct имя_структурного_типа
{
элементы_структуры;
struct имя_структурного_типа *указатель;
}
В каждую структуру такого типа входит указатель на объект того же типа, что и определяемая структура.
beg
Примеры:
Описание структуры
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<
key<<" ";
p=p->next;
}
return first;
}
При печати сформированного списка осуществляется проход по списку с помощью вспомогательной переменной р до тех пор, пока она не станет равна NULL.
2. Постановка задачи
Написать программу, в которой создаются динамические структуры и выполнить их обработку в соответствии со своим вариантом.
Для каждого вариант разработать следующие функции:
Создание списка.
Добавление элемента в список (в соответствии со своим вариантом).
Удаление элемента из списка (в соответствии со своим вариантом).
Печать списка.
Запись списка в файл.
Уничтожение списка.
Восстановление списка из файла.
Порядок выполнения работы
Написать функцию для создания списка. Функция может создавать пустой список, а затем добавлять в него элементы.
Написать функцию для печати списка. Функция должна предусматривать вывод сообщения, если список пустой.
Написать функции для удаления и добавления элементов списка в соответствии со своим вариантом.
Выполнить изменения в списке и печать списка после каждого изменения.
Написать функцию для записи списка в файл.
Написать функцию для уничтожения списка.
Записать список в файл, уничтожить его и выполнить печать (при печати должно быть выдано сообщение "Список пустой").
Написать функцию для восстановления списка из файла.
Восстановить список и распечатать его.
Уничтожить список.
4. Варианты заданий
Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным номером, добавить элемент с заданным номером;
Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным ключом, добавить элемент перед элементом с заданным ключом;
Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него К элементов, начиная с заданного номера, добавить элемент перед элементом с заданным ключом;
Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным номером, добавить К элементов, начиная с заданного номера;
Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него К элементов, начиная с заданного номера, добавить К элементов, начиная с заданного номера;
Записи в линейном списке содержат ключевое поле типа int. Сформировать двунаправленный список. Удалить из него элемент с заданным номером, добавить элемент в начало списка.
Сформировать двунаправленный список. Удалить из него первый элемент, добавить элемент в конец списка.
Записи в линейном списке содержат ключевое поле типа int. Сформировать двунаправленный список. Удалить из него элемент после элемента с заданным номером, добавить К элементов в начало списка.
Записи в линейном списке содержат ключевое поле типа int. Сформировать двунаправленный список. Удалить из него К элементов перед элементом с заданным номером, добавить К элементов в конец списка.
Записи в линейном списке содержат ключевое поле типа int. Сформировать двунаправленный список. Добавить в него элемент с заданным номером, удалить К элементов из конца списка.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить из него элемент с заданным ключом, добавить элемент с указанным номером.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить из него Элементы, с одинаковыми ключевыми полями. Добавить элемент после элемента с заданным ключевым полем.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить из него К первых элементов. Добавить элемент после элемента, начинающегося с указанного символа.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить из него К элементов с указанными номерами. Добавить К элементов с указанными номерами.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить К элементов из конца списка. Добавить элемент после элемента с заданным ключом.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов в конец списка.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным номером. Добавить К элементов в начало списка.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов в начало списка.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить К элементов с заданными номерами. Добавить К элементов в начало списка.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить по К элементов в начало и в конец списка.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элементы перед и после элемента с заданным ключом. Добавить по К элементов в начало и в конец списка.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов перед элементом с заданным ключом.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов после элемента с заданным ключом.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным номером. Добавить по К элементов перед и после элемента с заданным ключом.
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов перед элементом с заданным номером.
5.Содержание отчета
Постановка задачи.
Функции для работы со списком.
Функция main().
Результаты выполнения работы.
Библиографический список
Гладков В. П. Курс лабораторных работ по программированию : Учебное пособие для специальностей электротехнического факультета ПГТУ/ Перм. гос. техн. ун-т.-Пермь, 1998. –153с.
Подбельский В. В., Фомин С. С. Программирование на языке Си: Учеб. пособие. –М.:Финансы и статистика, 1998.–600с.
Подбельский В. В. Язык Си++: Учеб. пособие.–М.:Финансы и статистика, 1996.–560с.
Страуструп Б. Язык программирования Си++: Пер. с англ. – М.: Радио и связь, 1991.-352с.
ОГЛАВЛЕНИЕ
Лабораторная работа №1.
"Знакомство с Си++. Выполнение программы простой структуры" 2
Лабораторная работа №2.
"Использование основных операторов языка Си" 11
Лабораторная работа №3
"Вычисление функций с использованием их разложения в степенной ряд" 16
Лабораторная работа № 4
"Работа с одномерными массивами" 20
Лабораторная работа №5
"Функции и массивы" 28
Лабораторная работа № 6
"Строки" 33
Лабораторная работа № 7
7.1. "Перегрузка функций в Си++" 36
7.2. "Функции с переменным числом параметров" 39
Лабораторная работа №8
"Блоковый ввод-вывод" 43
Лабораторная работа № 9
"Строковый ввод-вывод" 51
Лабораторная работа № 10
"Динамические массивы" 55
Лабораторная работа № 11
"Информационные динамические структуры" 60
Библиографический список 64
|
