- •Конспект лекций Часть 2 Оглавление
- •Часть 2 1
- •8. Указатели
- •8.1. Указатели Понятие указателя
- •Работа с указателями
- •Арифметика указателей
- •Ошибки при работе с указателями
- •If (p1) // Если указатель не равен 0, то все в порядке
- •8.2. Указатели и массивы
- •9. Функции и структура программы
- •9.1. Создание и использование функций Процедурный подход к разработке программ
- •Int Максимум_строки (int Строка)
- •Int Минимум_строки (int Строка)
- •Int Максимум_столбца (int Столбец)
- •Int Минимум_столбца (int Столбец)
- •Определение функций в программе
- •Завершение работы функции (инструкция return)
- •If ( Ошибка )
- •Список параметров функций
- •Обращение к функциям в программе
- •Передача данных по значению
- •Передача данных с помощью указателей
- •Передача данных по ссылке
- •Перегружаемые функции
- •Параметры по умолчанию
- •Функции с переменным числом параметров
- •Рекурсивное использование функций
- •Передача функций в качестве параметров
- •Встраиваемые функции (inline - функции)
- •Прототипы функций
- •9.2. Структура программы. Глобальные и локальные данные (области видимости и время жизни) Структура программы
- •Глобальные и локальные данные
- •Классы памяти
- •Многофайловые проекты
- •10. Структуры, объединения, перечисления
- •10.1. Структуры Определение структур
- •Доступ к полям структур
- •Указатели на структуры
- •Структурные параметры функций
- •Битовые поля структур
- •10.2. Объединения Обычные объединения
- •Анонимные объединения
- •10.3. Перечисления
- •Void WriteColor (тип_Спектр c )
- •11. Организация работы с файлами
- •11.1. Потоки для работы с файлами Общие сведения
- •Пример работы с файлом
- •11.2. Работа с файлами Создание потока, открытие и закрытие файла
- •Запись и чтение данных в текстовых файлах
- •Запись и чтение данных в двоичном режиме
- •If ( !File ) // Проверили удалось ли открыть файл
- •Как обнаружить конец файла?
- •Прямой доступ при работе с файлами
- •If ( !File ) // Проверили удалось ли открыть файл
- •Статус потоков ввода-вывода
- •Некоторые другие функции управления потоками ввода-вывода
- •Примеры по работе с файлами
- •12. Работа с динамической памятью Распределение памяти при работе программы
- •Динамическое выделение и освобождение памяти в стиле c
- •Возможные ошибки при работе с динамической памятью
- •Динамические массивы
- •Одномерные однонаправленные списки
- •Одномерные двунаправленные списки
- •Многомерные списки
Одномерные однонаправленные списки
Одномерный однонаправленный список представляет собой совокупность отдельных элементов, каждый из которых содержит две части – информационную (Inf) и адресную (Adr). Информационная часть предназначена для хранения “полезных” данных и может иметь практически любой тип. Адресная часть каждого элемента содержит адрес следующего элемента списка. Схематическое изображение такого списка представлено на следующем рисунке.
Список может содержать произвольное количество элементов. Адресная часть последнего элемента списка содержит нулевой адрес, свидетельствующий об окончании списка.
Для работы со списком достаточно знать только адрес первого элемента списка (Beg). Зная адрес первого элемента списка можно последовательно получить доступ к любому другому его элементу.
Достоинством подобных структур являются простота добавления, удаления и перестановки элементов списка, которые осуществляются путем манипуляций с адресными частями без перезаписи всего списка.
Типовыми операциями при работе со списками являются:
создание списка;
освобождение памяти от списка (удаление списка);
доступ к заданному элементу списка для манипуляций с его информационной частью;
добавление нового элемента к списку;
удаление элемента из списка;
перестановка элемента списка на новую позицию внутри списка.
Рассмотрим эти операции на примере списка, в котором информационные части представляют собой, например, вещественные числа типа double. Все эти операции оформим в виде отдельных функций.
Прежде всего, определим необходимые типы данных для работы со списком.
Поскольку каждый элемент списка должен иметь две части, логичнее всего представить его в виде следующей структуры:
struct t_Item
{
double Inf;
t_Item * Adr;
};
Для того чтобы хранить в списке другие данные (не double), достаточно заменить типdouble поляInfна другой необходимый тип данных.
Тип адресного поля этой структуры определен как указатель на тип данных элемента списка (t_Item * Adr).
Создание списка
Представленная ниже функция CreateList обеспечивает создание динамического однонаправленного списка наLength элементов и возвращает адрес первого элемента созданного списка.
t_Item *CreateList ( unsigned Length )
{
t_Item *Curr = 0, // Адрес очередного элемента списка
*Next = 0; // Адрес следующего за очередным элемента списка
// Начинаем создавать список с последнего элемента
for ( unsigned i = 1; i <= Length; ++ i )
{
// Создаем очередной элемент списка
Curr = new t_Item;
// В адресную часть записываем адрес следующего
// за очередным элемента списка
Curr->Adr = Next;
// Запоминаем адрес очередного элемента в качестве
// следующего элемента для следующего шага цикла
Next = Curr;
}
// Возвращаем адрес последнего созданного элемента,
// как адрес первого элемента списка
return Curr;
}
Для создания списка используется цикл на Lengthитераций. На каждом шаге этого цикла в динамической области памяти создается очередной элемент списка с адресомCurr и в его адресную частьCurr->Adr записывается адрес следующего за ним элементаNext. Наиболее простой алгоритм работы этой функции получается в том случае, когда список начинает создаваться не с первого элемента, а с последнего.
Использовать эту функцию для создания списка можно, например, так:
t_Item *List = CreateList ( 5 );
Переменная List будет содержать адрес первого элемента динамического списка, содержащего5элементов. Информационные части элементов этого списка в функцииCreateList не инициализируются и будут иметь после выхода из функции непредсказуемые значения.
Заполнить информационные части элементов этого списка конкретными данными, например, с клавиатуры можно так:
// Чтобы не потерять адрес начала списка (он нам понадобится для дальнейшей
// работы со списком) вводим дополнительную переменную-указатель Curr– адрес
// очередного элемента списка и делаем его равным адресу первого элемента списка
t_Item * Curr = List;
// Выполняем цикл пока адрес очередного элемента списка не равен 0
while ( Curr )
{
// Вводим данные в информационную часть очередного элемента с клавиатуры
cin >> Curr->Inf;
// Делаем очередным следующий элемент списка. Для этого переменной
// Currприсваиваем адрес следующего элемента списка. Последний элемент
// списка содержит в адресной части 0, поэтому кода мы обработаем последний
// элемент списка, переменная Currстанет равна 0, и цикл закончится
Curr = Curr->Adr;
}
Вывод значений информационных частей элементов списка на экран делается аналогично:
Curr = List;
while ( Curr )
{
// Выводим информационную часть очередного элемента на экран
cout << Curr->Inf << “ “;
Curr = Curr->Adr;
}
cout << endl;
Удаление списка
После окончания работы со списком необходимо освободить от него динамическую память. Для этого можно использовать следующую функцию, имеющую единственный параметр-ссылку Beg– адрес начала списка:
void DeleteList ( t_Item * &Beg )
{
t_Item *Next; // Указатель на следующий элемент списка
// Начинаем с начала списка
while ( Beg )
{
// Запоминаем адрес следующего элемента списка. Если этого не сделать,
// то после удаления элемента по адресу Begнегде будет взять адрес
// следующего элемента списка
Next = Beg->Adr;
// Удаляем первый элемент списка
delete Beg;
// Делаем адрес первого элемента списка равным адресу
// следующего после удаленного (мы его запомнили чуть выше)
Beg = Next;
}
}
После окончания работы эта функция возвращает через свой параметр-ссылку Begадрес0– список отсутствует (он перестал существовать).
Использование этой функции:
DeleteList ( List );
Если проверить значение указателя List после вызова этой функции, то оно действительно будет равно0, что будет свидетельствовать о том, что список не существует.
Доступ к заданному элементу списка
Функция ListItem возвращает адрес элемента списка с индексомIndex (индексация элементов в списке начинается с0). Если элемент с заданным индексом в списке отсутствует, функция возвращает нулевой адрес. ПараметрBeg задает адрес первого элемента списка (адрес начала списка). Третий параметр функцииErrMsg определяет надо ли выводить сообщение об ошибке при неправильно заданном индексе.
t_Item *ListItem( t_Item *Beg, unsigned Index, bool ErrMsg = true )
{
// Цикл заканчивается, когда
while ( Beg && ( Index -- ) )
Beg = Beg->Adr;
if ( ErrMsg && !Beg )
cout << "Элемент списка отсутствует \n";
return Beg;
}
Добавление нового элемента к списку
t_Item *InsItem( t_Item * &Beg, unsigned Index )
{
t_Item * Item = new t_Item;
if ( !Index || !Beg)
{
Item->Adr = Beg;
Beg = Item;
return Item;
}
t_Item * PredItem = Beg;
-- Index;
while ( PredItem->Adr && ( Index -- ) )
PredItem = PredItem->Adr;
Item->Adr = PredItem->Adr;
PredItem->Adr = Item;
return Item;
}
Определение количества элементов в списке
unsigned LengthList ( t_Item * Beg )
{
unsigned Length = 0; // Счетчик элементов списка
// Начинаем с начала списка
while ( Beg )
{
// Увеличиваем счетчик элементов списка на единицу
++ Length;
// Перемещаемся на следующий элемент списка
Beg = Beg->Adr;
}
return Length;
}
Удаление элемента из списка
void DelItem( t_Item * &Beg, unsigned Index )
{
if ( Index >= LengthList ( Beg ) )
return;
t_Item * Item;
if ( !Index )
{
Item = Beg->Adr;
delete Beg;
Beg = Item;
return;
}
Item = ListItem ( Beg, Index - 1, 0 );
t_Item * DItem = Item->Adr;
Item->Adr = DItem->Adr;
delete DItem;
}