Бритуля - Богиня
Здрасте!
решение домашнего задания с предыдущей лекцииУсловие:
Перепишите программу, заданную в качестве домашнего задания на предыдущей лекции, с такими изменениями.
Структура имеет имя, фамилию, оценки и ID-номер студента. ID номер назначается автоматически при создании студента. Предположите, что количество студентов не может выходить за рамки числа, которое может быть сохранено в переменной long. Потрудитесь сделать так, чтобы ID был уникальным для каждого студента. Имя и фамилию студент получает в конструктор. (То есть: при создании переменной студент необходимо указать имя и фамилию)
Введите студентам те же оценки, которые были в прошлом задании и распечатайте имена И ID-номера тех, кто достоин поездки на олимпиаду.
Требование: все студенты должны быть созданы в куче.
Напоминаю:
Напишите программу, которая вычисляет студента, которого нужно послать на олимпиаду по физике.
Немного о вузе: в вузе есть всего 3 курса: физика, математика и английский. В Вузе - 100 бальная система оценок. Вуз заботится о своем имени и поэтому, он не посылает на такие мероприятия студентов, у которых средняя оценка по всем курсам ниже 85. На олимпиаду должны поехать студенты, у которых оценка по физике не меньше 90.
Создайте 3 студента с такими оценками:
1. физика 95, математика 90, английский 85.
2. физика 95, математика 60, английский 60.
3. физика 80, математика 90, английский 95.
Раздайте им произвольные имена.
Программа напишет на экран имена всех студентов, которые достойны поездки на олимпиаду по физике.
Примечание: Не обязательно получать данные с "внешнего источника", можно прописать их в коде. Цель задания - работа со структурами, а не с клавиатурой.
Совет: даже больше чем совет, скорее требование: разбейте код на функции, не пишите все в main, это не красиво.
решение
Код:
Результат:
Примечание:
Я пишу начальную инициализацию переменных (в конструкторе) в столбик: лишь для удобства чтения. Так тоже можно)))
лекцияВы не могли не заметить, в домашнем задании про трех студентов и олимпиаду по физике что-то, что явно бросалось в глаза: неудобная работа со структурами, которые с одной стороны нельзя создать в виде массива (потому что отсутствует пустой конструктор), а с другой - что-то типа массива там напрашивалось как необходимая вещь.
Можно, конечно, создать массив, но тут есть нюанс. Давайте остановимся на этом нюансе. Как мы уже выяснили, нельзя создать массив, если в структуре нет пустого конструктора. Но! Всегда можно создать массив указателей на эту структуру. Давайте рассмотрим такое создание. Допустим, что нужно заполнить массив в функции foo
void foo (MyStruct ** arr) {
// создаем структуры:
MyStruct st1(1);
MyStruct st2(2);
MyStruct st3(3);
// кладем в массив:
arr [ 0 ] = & st1;
arr [ 1 ] = & st2;
arr [ 2 ] = & st3;
}
В начале, хочу обратить внимание на параметр в функции foo: указатель на указатель (две звездочки). Почему? Ну, первая - мы так всегда передаем массивы. Потому, что как мы помним, что имя массива - это указатель на первый элемент. Вторая звездочка говорит, что наш массив - это массив указателей.
Видите ли вы проблему в этом коде, которую вижу я? Она уже должна бросаться в глаза: структуры st1, st2 и st3 созданы внутри функции и они будут уничтожены при выходе из функции. То есть, указатели, которые мы положили в массив, будут указывать на мусор, а попытка обратиться к ним свалит программу.
Чтобы этого не произошло, нужна динамическая аллокация, то есть, код будет работать правильно, если сделать так:
MyStruct * st1 = new MyStruct(1);
MyStruct * st2 = new MyStruct(2);
MyStruct * st3 = new MyStruct(1);
arr [ 0 ] = st1;
arr [ 1 ] = st2;
arr [ 2 ] = st3;
ИЛИ сразу вот так:
arr [ 0 ] = new MyStruct(1);
arr [ 1 ] = new MyStruct(2);
arr [ 2 ] = new MyStruct(1);
Естественно, что как только массив будет не нужен, нужно будет освободить память.
Какие минусы такого подхода? Начнем по порядку.
Во-первых - размер массива. Сейчас даже не важно, создали мы сам массив в стеке или в куче, в любом случае - у него будет фиксированный размер. Если размер нужно увеличить или уменьшить - то придется создавать другой массив с нужным размером и переписывать туда содержимое из первого.
Рассмотрим такую ситуацию: нам нужно написать программу, которая хранила бы в себе список студентов. Задание берет на себя программист, который не знает другого решения, кроме как создать массив. Он приходит к декану и спрашивает: какое максимальное число студентов может быть на курсе. Допустим, он получает ответ 60.
Программист создает массив размером в 60 ячеек и заполняет его студентами. Если студентов будет меньше, размышляет программист, то лишние ячейки будут указывать на NULL. Неплохой выход, когда не знаешь ничего более хорошего. Даже не нужно таскать за собой размер массива: допустим, нужно распечатать всех студентов, тогда цикл выполняется до тех пор, пока не достигнет 60, либо, пока не встретит первый NULL.
И вот, в середине семестра выгоняют троих. Они находятся в середине массива. Если просто освободить их места и присвоить им NULL, то у нас получатся дыры в массиве. Так как NULL в одной из ячеек означает конец списка, то дыры оставлять нельзя. Поэтому программисту нужно "двигать" студентов по массиву, и закрывать дыры.
НО! Самый печальный вариант - на этот факультет хотят записаться 90 студентов и ВУЗ решает открыть дополнительные места. Как быть? Нужно, как я уже писал выше, создавать другой массив и переписывать данные туда. Все это ОЧЕНЬ усложняет и замедляет выполнение кода. Как мы видим, массив не дает красивых решений на все случаи жизни. Однако, красивое решение есть и на этой лекции мы и поговорим о нем.
Чтобы понять, что такое "связанный список" (англ. Linked List) давайте посмотрим на структуру:
struct Student {
// привычные нам данные студента
Student * next; // указатель на такую же структуру
}
И тогда можно написать вот такой код:
Student * st1 = new Student;
// заполняем данные
Student * st2 = new Student;
// заполняем данные
а теперь, далее, мы можем просто "связать" одного студента с другим:
st1->next = st2;
То есть, указатель, который находится в структуре st1 и называется next теперь указывает на структуру st2. Таким образом, мы можем связать неограниченное количество структур, одну с другой, а в последней, мы позаботимся о том, чтобы ее next указывал на NULL и тогда, проходя по листу мы будем знать, что если next указывает на NULL, то лист закончился.
Так решается первая проблема, заявленная мною сегодня: лист (далее "связанный список" я буду называть "лист"). Так вот, лист - это удобный контейнер с той точки зрения, что его размеры могут динамически изменяться! Как только нам понадобится добавить в лист еще одного студента - мы просто "привяжем" его к последнему в листе.
Как решается проблема с удалением студента из листа? Так же элегантно и просто! Допустим, у нас есть такая последовательность:
st1->st2->st3->NULL
Мы хотим удалить st2:
st1->st3->NULL
Мы делаем простую, до безобразия вещь: указатель next, структуры st1 теперь указывает на st3, то есть на то, на что указывал st2->next, в коде это выглядит так:
st1->next = st2->next;
но так как, скорее всего, st2 был динамически аллокирован, то нужно не забыть освободить память!
Student * tmp = NULL;
tmp = st1->next;
st1->next = st1->next->next;
delete tmp;
В начале мы создадим временный указатель, которому присвоим то, на что указывает st1->next, то есть - это st2
Далее, мы говорим, что ТЕПЕРЬ st1->next будет указывать НЕ на st2, а на st2->next, но к нему мы обращаемся через st1 (я объясню далее почему именно так)
После этого, мы просто освободим то, на что указывает "временный указатель", а так как он указывает на ту ячейку памяти, на которую указывает и st2, то мы по-сути добьемся того, чего хотели - освободим st2
Мы видим, что в принципе мы решили обе проблемы, с которых и начался наш разговор. Но чтобы закрепить теорию практикой, я напишу короткую программку, которая сделает такие шаги: она создаст четырех студентов, соединит их в лист, после этого удалит третьего, а потом вставит вместо третьего - нового студента.
Я специально работаю с серединой, потому что работа с концом листа - элементарна, а в работе с началом листа (с первым элементом) есть нюансы, так как доступ ко всем членам листа осуществляется именно через первый элемент.
Код:
Результат:
Разбор полетов:
Ну, помолясь, приступим))))
Начнем с описания структуры: конструктор, деструктор, статическая переменная для раздачи уникального id (трюк из дом. задания). Потом - данные студента и, самое главное, указатель на следующий элемент.
В main ничего интересного не происходит. Построение листа - немного дебильное))) можно было бы строить новые структуры стразу привязывая их к указателю next предыдущего элемента, но я решил написать по-проще, чтобы было понятней. Плюс ко всему, я добавил распечатку листа для того, чтобы наглядно было показано, что теория работает, а так же функция распечатки показывает проход по листу, но до этого мы еще дойдем.
Далее, немного отступления: первый элемент - это "ключ" ко всему листу. Через него можно попасть в любой элемент! Часто его называют head (голова листа). Если нужно передать лист в функцию - передают первый элемент. Размер не нужен, так как конец листа - это элемент, у которого next указывает на NULL.
Итак, функция распечатки. Тут есть несколько интересных моментов. Во-первых, я создаю указатель р, который в начале указывает на голову. Я буду "двигать" р (а не head), чтобы не потерять начало. В этой функции это не критично, но если бы в ней был бы еще один проход (еще один цикл), то я бы не смог его осуществить, потому что потерял бы указатель на голову.
Цикл будет выполняться, пока р не будет указывать на NULL, а с каждым шагом цикла, р будет указывать на следующий элемент в листе. Его продвижение - последнее действие в цикле.
Теперь поговорим о самом цикле. Я выбрал while только потому, что так проще понять, что происходит.... но давайте подумаем.... вспомним, как мы ходили по массиву через while:
int i = 0; // ставим "шагающую переменную" в начало
while ( i < size ) // проверяем условие: вышли ли мы за границы массива?
{
// какое-либо действие в цикле
i++; // продвигаем переменную вперед
}
А что мы имеем тут?
Student * p = head; // ставим "шагающую переменную" в начало
while ( p != NULL ) // проверяем условие: вышли ли мы за границы листа?
{
// какое-либо действие в цикле
p = p->next; // продвигаем переменную вперед
}
Далее, мы сказали, что удобней двигаться по массиву с помощью цикла for, объединив эти действия в одну строку:
for ( int i = 0; i < size; i++)
Что нам мешает сделать такой трюк тут? Ничего!
for ( Student * p = head; p != NULL; p = p->next)
или, еще короче:
for ( Student * p = head; p; p = p->next)
Далее, вы увидите, что в большинстве случаев я использую цикл for для прохода по листу.
Теперь, функция delete_student. Я хочу остановиться тут только на одном моменте: два указателя. Зачем? Чтобы понять это, надо привести такой пример: допустим, мы хотим удалить 3-й элемент. Но мы не знаем, что элемент, который нам надо удалить - третий по счету. Нам нужно попасть в этот элемент, чтобы сравнить фамилии.
Вот мы идем по листу: 1-й элемент, сравнение - не он. Двигаем р во второй элемент. 2-й элемент, сравнение - не он. Двигаем в третий. 3-й элемент, сравнение - он! Надо удалять. А что такое удалить элемент из листа? Это значит, исключить его оттуда и освободить. НО! На него указывает 2-й элемент, а он сам - на 4-й. То есть, нужно сделать так, чтобы теперь next ВТОРОГО элемента указывал на 4-й....
НО! Мы находимся в 3-м... второй мы уже прошли.... Да, бывают листы, в котором есть указатель на next (на следующий элемент) И указатель на prev (на предыдущий элемент), такой лист называют "двусторонний", но это не наш случай))) Я специально не использовал двусторонний лист, чтобы научить пользоваться вот таким, "обычным", так как он используется довольно часто, а умея пользоваться этим - легко можно понять, как пользоваться двусторонним. То есть, в нашем случае, вернуться назад - невозможно! И это - важно понять!
Поэтому, я использую такой трюк: я двигаю 2 указателя. Второй q отстает от первого р на один шаг. Таким образом, у меня в руках есть предыдущий элемент! Далее, как только я нашел нужный элемент - я говорю, что next предыдущего (то есть второго) указывает на next этого, то есть - на четвертый. После этого я удаляю этот. Если бы мне нужно было бы удалить несколько, то я бы это делал через "временный указатель", как я объяснял в теории, а потом бы приводил в порядок указатели. Но так, как это не требуется и как только я удалю элемент, я покину цикл (break), то я не стал это делать.
Хочу заметить, что ни в этой, не в следующей функции я не могу добавить/убрать первый элемент! Почему? Потому что он - указывает на голову. Поясню:
Мы создали структуру в куче, допустим, она имеет адрес 17. После этого, мы создали указатель на нее. Указатель имеет адрес 28. Это указатель на первый элемент. Теперь по адресу 28 лежит значение "17". Мы передаем указатель в функцию. Как мы знаем, создается новая переменная из типа "указатель" и у нее есть новый адрес, допустим 33, однако, в нее скопировано значение "17".
То есть, в функции, мы работаем с указателем, имеющим адрес 33 и это наша "голова". Теперь мы хотим добавить элемент в голову, либо удалить из головы... НО! Все, что мы сделаем в этой функции - мы сделаем с указателем, который имеет адрес 33, а "настоящая" голова имеет адрес 28.... То есть, наши изменения в функции не происходят с "настоящей" головой!
Есть 2 решения:
1. вернуть "голову" из функции и присвоить ее настоящей
2. передать указатель на указатель
То есть, для того, чтобы у нас была возможность изменить первый элемент, наши обе функции (add_student, delete_student) функции должны быть описаны вот так:
add_student ( Student ** head ) // ДВЕ звезды!
А присвоение "шагающему указателю" р происходило бы так:
Student * p = (*head)->next
Почему next? Потому что перед этим, мы бы проверяли: не является ли нужный нам элемент головой? Если да, то наши действия происходили бы отдельно, а если нет - то мы бы сразу шли в следующий элемент (первый-то мы уже проверили). Но я не стал делать этого тут, чтобы не усложнить код. На самом деле, в настоящей программе, это делать необходимо.
Теперь, когда мы разобрали delete_student, в add_student мы легко поймем код, потому что там используется тот же трюк с двумя указателями. Единственное, на что хочу обратить внимание: создание нового студента происходит сразу со "связыванием" его в листе. Можно было сделать так же, как я сделал в main, но это лишние, никому не нужные телодвижения.
Функция free_list рекурсивная. Я буду удалять элементы, начиная с последнего. Потому, что если я напишу в начале delete p, то потом я не смогу продвинуться p = p->next, так как р уже не существует. Поэтому, я в начале пройду в конец листа, а потом, на выходе начну удалять элементы.
Конструктор и деструктор мы разбирать не будем, там нет ничего нового. Просто обратите внимание на то, что я даю начальные значения членам структуры в столбик, для удобства чтения кода.
Совет: для лучшего понимания того, что происходит в этих функциях, можно взять бумагу и ручку и схематически все нарисовать. Идти по алгоритму: "ага, этот указатель сейчас указывает сюда, тут я присваиваю то-то"... Желательно, хотя бы один раз все нарисовать, чтобы ГЛАЗАМИ на все посмотреть!
Когда мы узнали, что такое "связанный список" или "лист", давайте попробуем сделать работу с ним более удобной. Для того, чтобы понять, что нужно улучшать, давайте разберемся в чем проблемы?
1. Мы уже видели, что существует проблема работы с первым элементом. Он требует "особого подхода"
2. Часто нужно добавлять элемент в лист, для этого необходимо найти конец. Чтобы найти конец - нужно пройти по всему листу. Можно ли это ускорить?
3. Как узнать размер листа? Только посчитать....
Сейчас мы попробуем решить все эти проблемы, однако, есть еще ряд других проблем в листе. Например, невозможно СРАЗУ попасть в 3-й элемент, нужно начать с первого и продвигаться.... эту и еще ряд проблем мы пока не можем решить. Поэтому, если нам нужна возможность попасть сразу в определенное место в листе, то тут стоит задуматься: какой именно контейнер нам подойдет лучше? Пока мы знаем только два: массив и лист, однако, есть еще, но об этом мы поговорим в других лекциях.
А пока мы приступим к решению заявленных выше проблем, а так же поговорим о "универсальном" контейнере, способным хранить любой тип переменных. Это реально? Да, конечно. Это даже желаемо! Думаю, что не смотря на явные минусы, понятно, что лист - довольно удобный контейнер для хранения данных в программе. То есть, желательно написать это все только ОДИН раз, а далее использовать готовый, отдебаженый код во всех программах, где нужен лист. Но чтобы пользоваться этим контейнером, нужно, чтобы программа умела выполнять следующие действия:
1. Добавить данные в конец или начало листа
2. Удалить данные из листа
3. Найти данные в листе
Это обязательные возможности, но если мы уже пишем "универсальный" лист, то было бы неплохо, так же, чтобы лист умел еще:
1. Сказать какой у него размер
2. Добавить элемент в любое место в листе
3. Соединить два листа в один
4. Создать лист "клон" (точную копию себя)
5. Распечатать содержимое листа на экран
6. Стереть лист полностью (стереть все данные и сам лист)
Я покажу направление, в котором нужно двигаться, чтобы проще и с большим удобством решить эти задачи, а само решение всех поставленных задач нужно будет описать в домашнем задании))) Придется подумать головой))) не все коту масленница!
Допустим, у нас есть структура, назовем ее "узел". В этом узле мы будем держать данные. Как можно сделать контейнер, который способен хранить ЛЮБОЙ тип переменной? Тут на помощь придет "неопределенный указатель", то есть void *. Итак, наш "узел" выглядит так:
struct Node {
void * data; // указатель, который будет содержать данные
Node * next; // указатель на следующий элемент в листе
};
Тут вроде ничего нового нет (кроме фокуса с void*) и это не решает проблему. НО! Мы можем ввести еще одну структуру, которая будет "заведующей" листом. Мы так и назовем ее "Лист":
struct List {
unsigned long size; // хранит количество элементов в листе
Node * head; // хранит указатель на голову
Node * tail; // хранит указатель на последний элемент (хвост)
};
Теперь, таким образом мы решили из "обязательных":
1. Добавить данные в конец или начало листа
Из "дополнительных":
1. Сказать какой у него размер
2. Добавить элемент в любое место в листе
3. Соединить два листа в один
При этом, у нас есть проблемы с этим:
"Обязательные":
2. Удалить данные из листа
3. Найти данные в листе
"Дополнительные":
4. Создать лист "клон" (точную копию себя)
5. Распечатать содержимое листа на экран
6. Очистить лист полностью (стереть все данные)
В чем же проблемы?
1. Для того, чтобы найти данные в листе, необходимо уметь сравнить данные))) (КЭП?) А как сравнить данные, если мы не знаем, ЧТО там лежит? Числовые переменные нужно сравнивать через оператор ==. Стринги мы сравниваем через функцию strcmp, а студентов? Студентов наверное надо сравнивать по id или по фамилии.....
2. Для того, чтобы удалить содержимое ПРАВИЛЬНО, нужно освободить память... а как? ЛИБО delete, либо delete [ ] (в листе, в качестве данных вполне может лежать массив В КАЖДОМ узле - свой....). А если предположить, что память освобождать не нужно? Кто-то еще пользуется этими данными.... нужно просто исключить его из листа.... как быть?
3. Для того, чтобы распечатать содержимое листа, нужна функция распечатки.... а у нас там void*, который может быть обычным стрингом, а может быть структурой "Студент", у которого есть имя, фамилия, id, оценки.... да мало ли?
4. Чтобы создать клон, нужно знать, как создавать то, что лежит в КАЖДОМ узле...
Как же решить эти проблемы? И вот тут на помощь нам придут указатели на функцию))). И вот мы медленно, но верно, поняв все, стоящие перед нами задачи, подошли к домашнему заданию. Оно не будет простым. Потребуется немного вспомнить материал, МНОГО думать головой и отлично понимать материал этой лекции. Думаю, что мы подошли к моменту, когда каждый точно поймет: насколько он понял все то, что я рассказываю? Если с пониманием проблем не было, то и в домашнем задании их не будет. А если есть "белые пятна", то я советую ВСЕ РАВНО пытаться решить эту задачу, так как попробовав, всегда понимаешь лучше решение другого человека. Ну, а это другое решение мы увидим уже на следующей лекции))))
Создайте две структуры Node и List так, как я описал это выше. Желательно подумать о конструкторах и деструкторах: стоит ли их создавать и если да, то какие?
Вместе с этим, имплементируйте такие функции:
List * create_list (void) - создает новый, пустой лист
void destroy_list ( List * list, void (*destroy_func) (void*) ) - уничтожает лист, с возможностью освободить память.
подробнее:
List * list - лист, который нужно уничтожить
void (*destroy_func) (void*) - указатель на функцию освобождения памяти. Функция умеет освобождать ОДИН элемент в листе, то есть, нужно вызвать ее для каждого элемента (функция принимает void* и ничего не возвращает)
при условии, что память освобождать не нужно, вместо функции будет передан NULL
void append_to_list ( List * list, void * item ) - добавить элемент item в конец листа
void prepend_to_list ( List * list, void * item ) - добавить элемент item в начало листа
bool insert_to_list ( List * list, void * item, unsigned long index ) - добавить элемент item в место номер index листа (вернет false при провале)
void remove_from_list ( List * list, void * item, short (*compare_func) (void*, void*), void (*destroy_func) (void*) ) - удалит элемент, равный item из листа
указатель на функцию void (*destroy_func) (void*) - работает так же как и в destroy_list
указатель на функцию short (*compare_func) (void*, void*) принимает для сравнения 2 элемента и возвращает:
-1 если первый меньше второго
0 если первый равен второму
1 если первый больше второго
* примечание: чуть позже, когда выучим сортировки, такая же точно функция поможет отсортировать лист
void * find_in_list( List * list, void * item, short (*compare_func) (void*, void*) ) - находит элемент item в листе
указатель short (*compare_func) (void*, void*) работает так же, как и в remove_from_list
void concat_list ( List * list1, List * list2) - соединяет два листа в один (к концу list1 привязывает list2)
void print_list ( List * list, void (*print_func) (void *) ) - распечатывает лист на экран
указатель void (*print_func) (void *) умеет указывает на функцию, которая умеет распечатать один элемент на экран
List * copy_list ( List * src, void * (*copy_item) (void * item) ) - создаст точно такой же лист, как и src
указатель void * (*copy_item) (void * item) умеет создать копию item. При копировании листа функция вызывается для каждого элемента
Можно создавать дополнительные функции, помогающие в работе этих.
Удачи! Она вам пригодится))))
решение домашнего задания с предыдущей лекцииУсловие:
Перепишите программу, заданную в качестве домашнего задания на предыдущей лекции, с такими изменениями.
Структура имеет имя, фамилию, оценки и ID-номер студента. ID номер назначается автоматически при создании студента. Предположите, что количество студентов не может выходить за рамки числа, которое может быть сохранено в переменной long. Потрудитесь сделать так, чтобы ID был уникальным для каждого студента. Имя и фамилию студент получает в конструктор. (То есть: при создании переменной студент необходимо указать имя и фамилию)
Введите студентам те же оценки, которые были в прошлом задании и распечатайте имена И ID-номера тех, кто достоин поездки на олимпиаду.
Требование: все студенты должны быть созданы в куче.
Напоминаю:
Напишите программу, которая вычисляет студента, которого нужно послать на олимпиаду по физике.
Немного о вузе: в вузе есть всего 3 курса: физика, математика и английский. В Вузе - 100 бальная система оценок. Вуз заботится о своем имени и поэтому, он не посылает на такие мероприятия студентов, у которых средняя оценка по всем курсам ниже 85. На олимпиаду должны поехать студенты, у которых оценка по физике не меньше 90.
Создайте 3 студента с такими оценками:
1. физика 95, математика 90, английский 85.
2. физика 95, математика 60, английский 60.
3. физика 80, математика 90, английский 95.
Раздайте им произвольные имена.
Программа напишет на экран имена всех студентов, которые достойны поездки на олимпиаду по физике.
Примечание: Не обязательно получать данные с "внешнего источника", можно прописать их в коде. Цель задания - работа со структурами, а не с клавиатурой.
Совет: даже больше чем совет, скорее требование: разбейте код на функции, не пишите все в main, это не красиво.
решение
Код:
Результат:
Примечание:
Я пишу начальную инициализацию переменных (в конструкторе) в столбик: лишь для удобства чтения. Так тоже можно)))
лекцияВы не могли не заметить, в домашнем задании про трех студентов и олимпиаду по физике что-то, что явно бросалось в глаза: неудобная работа со структурами, которые с одной стороны нельзя создать в виде массива (потому что отсутствует пустой конструктор), а с другой - что-то типа массива там напрашивалось как необходимая вещь.
Можно, конечно, создать массив, но тут есть нюанс. Давайте остановимся на этом нюансе. Как мы уже выяснили, нельзя создать массив, если в структуре нет пустого конструктора. Но! Всегда можно создать массив указателей на эту структуру. Давайте рассмотрим такое создание. Допустим, что нужно заполнить массив в функции foo
void foo (MyStruct ** arr) {
// создаем структуры:
MyStruct st1(1);
MyStruct st2(2);
MyStruct st3(3);
// кладем в массив:
arr [ 0 ] = & st1;
arr [ 1 ] = & st2;
arr [ 2 ] = & st3;
}
В начале, хочу обратить внимание на параметр в функции foo: указатель на указатель (две звездочки). Почему? Ну, первая - мы так всегда передаем массивы. Потому, что как мы помним, что имя массива - это указатель на первый элемент. Вторая звездочка говорит, что наш массив - это массив указателей.
Видите ли вы проблему в этом коде, которую вижу я? Она уже должна бросаться в глаза: структуры st1, st2 и st3 созданы внутри функции и они будут уничтожены при выходе из функции. То есть, указатели, которые мы положили в массив, будут указывать на мусор, а попытка обратиться к ним свалит программу.
Чтобы этого не произошло, нужна динамическая аллокация, то есть, код будет работать правильно, если сделать так:
MyStruct * st1 = new MyStruct(1);
MyStruct * st2 = new MyStruct(2);
MyStruct * st3 = new MyStruct(1);
arr [ 0 ] = st1;
arr [ 1 ] = st2;
arr [ 2 ] = st3;
ИЛИ сразу вот так:
arr [ 0 ] = new MyStruct(1);
arr [ 1 ] = new MyStruct(2);
arr [ 2 ] = new MyStruct(1);
Естественно, что как только массив будет не нужен, нужно будет освободить память.
Какие минусы такого подхода? Начнем по порядку.
Во-первых - размер массива. Сейчас даже не важно, создали мы сам массив в стеке или в куче, в любом случае - у него будет фиксированный размер. Если размер нужно увеличить или уменьшить - то придется создавать другой массив с нужным размером и переписывать туда содержимое из первого.
Рассмотрим такую ситуацию: нам нужно написать программу, которая хранила бы в себе список студентов. Задание берет на себя программист, который не знает другого решения, кроме как создать массив. Он приходит к декану и спрашивает: какое максимальное число студентов может быть на курсе. Допустим, он получает ответ 60.
Программист создает массив размером в 60 ячеек и заполняет его студентами. Если студентов будет меньше, размышляет программист, то лишние ячейки будут указывать на NULL. Неплохой выход, когда не знаешь ничего более хорошего. Даже не нужно таскать за собой размер массива: допустим, нужно распечатать всех студентов, тогда цикл выполняется до тех пор, пока не достигнет 60, либо, пока не встретит первый NULL.
И вот, в середине семестра выгоняют троих. Они находятся в середине массива. Если просто освободить их места и присвоить им NULL, то у нас получатся дыры в массиве. Так как NULL в одной из ячеек означает конец списка, то дыры оставлять нельзя. Поэтому программисту нужно "двигать" студентов по массиву, и закрывать дыры.
НО! Самый печальный вариант - на этот факультет хотят записаться 90 студентов и ВУЗ решает открыть дополнительные места. Как быть? Нужно, как я уже писал выше, создавать другой массив и переписывать данные туда. Все это ОЧЕНЬ усложняет и замедляет выполнение кода. Как мы видим, массив не дает красивых решений на все случаи жизни. Однако, красивое решение есть и на этой лекции мы и поговорим о нем.
Связанные списки
Чтобы понять, что такое "связанный список" (англ. Linked List) давайте посмотрим на структуру:
struct Student {
// привычные нам данные студента
Student * next; // указатель на такую же структуру
}
И тогда можно написать вот такой код:
Student * st1 = new Student;
// заполняем данные
Student * st2 = new Student;
// заполняем данные
а теперь, далее, мы можем просто "связать" одного студента с другим:
st1->next = st2;
То есть, указатель, который находится в структуре st1 и называется next теперь указывает на структуру st2. Таким образом, мы можем связать неограниченное количество структур, одну с другой, а в последней, мы позаботимся о том, чтобы ее next указывал на NULL и тогда, проходя по листу мы будем знать, что если next указывает на NULL, то лист закончился.
Так решается первая проблема, заявленная мною сегодня: лист (далее "связанный список" я буду называть "лист"). Так вот, лист - это удобный контейнер с той точки зрения, что его размеры могут динамически изменяться! Как только нам понадобится добавить в лист еще одного студента - мы просто "привяжем" его к последнему в листе.
Как решается проблема с удалением студента из листа? Так же элегантно и просто! Допустим, у нас есть такая последовательность:
st1->st2->st3->NULL
Мы хотим удалить st2:
st1->st3->NULL
Мы делаем простую, до безобразия вещь: указатель next, структуры st1 теперь указывает на st3, то есть на то, на что указывал st2->next, в коде это выглядит так:
st1->next = st2->next;
но так как, скорее всего, st2 был динамически аллокирован, то нужно не забыть освободить память!
Student * tmp = NULL;
tmp = st1->next;
st1->next = st1->next->next;
delete tmp;
В начале мы создадим временный указатель, которому присвоим то, на что указывает st1->next, то есть - это st2
Далее, мы говорим, что ТЕПЕРЬ st1->next будет указывать НЕ на st2, а на st2->next, но к нему мы обращаемся через st1 (я объясню далее почему именно так)
После этого, мы просто освободим то, на что указывает "временный указатель", а так как он указывает на ту ячейку памяти, на которую указывает и st2, то мы по-сути добьемся того, чего хотели - освободим st2
Мы видим, что в принципе мы решили обе проблемы, с которых и начался наш разговор. Но чтобы закрепить теорию практикой, я напишу короткую программку, которая сделает такие шаги: она создаст четырех студентов, соединит их в лист, после этого удалит третьего, а потом вставит вместо третьего - нового студента.
Я специально работаю с серединой, потому что работа с концом листа - элементарна, а в работе с началом листа (с первым элементом) есть нюансы, так как доступ ко всем членам листа осуществляется именно через первый элемент.
Код:
Результат:
Разбор полетов:
Ну, помолясь, приступим))))
Начнем с описания структуры: конструктор, деструктор, статическая переменная для раздачи уникального id (трюк из дом. задания). Потом - данные студента и, самое главное, указатель на следующий элемент.
В main ничего интересного не происходит. Построение листа - немного дебильное))) можно было бы строить новые структуры стразу привязывая их к указателю next предыдущего элемента, но я решил написать по-проще, чтобы было понятней. Плюс ко всему, я добавил распечатку листа для того, чтобы наглядно было показано, что теория работает, а так же функция распечатки показывает проход по листу, но до этого мы еще дойдем.
Далее, немного отступления: первый элемент - это "ключ" ко всему листу. Через него можно попасть в любой элемент! Часто его называют head (голова листа). Если нужно передать лист в функцию - передают первый элемент. Размер не нужен, так как конец листа - это элемент, у которого next указывает на NULL.
Итак, функция распечатки. Тут есть несколько интересных моментов. Во-первых, я создаю указатель р, который в начале указывает на голову. Я буду "двигать" р (а не head), чтобы не потерять начало. В этой функции это не критично, но если бы в ней был бы еще один проход (еще один цикл), то я бы не смог его осуществить, потому что потерял бы указатель на голову.
Цикл будет выполняться, пока р не будет указывать на NULL, а с каждым шагом цикла, р будет указывать на следующий элемент в листе. Его продвижение - последнее действие в цикле.
Теперь поговорим о самом цикле. Я выбрал while только потому, что так проще понять, что происходит.... но давайте подумаем.... вспомним, как мы ходили по массиву через while:
int i = 0; // ставим "шагающую переменную" в начало
while ( i < size ) // проверяем условие: вышли ли мы за границы массива?
{
// какое-либо действие в цикле
i++; // продвигаем переменную вперед
}
А что мы имеем тут?
Student * p = head; // ставим "шагающую переменную" в начало
while ( p != NULL ) // проверяем условие: вышли ли мы за границы листа?
{
// какое-либо действие в цикле
p = p->next; // продвигаем переменную вперед
}
Далее, мы сказали, что удобней двигаться по массиву с помощью цикла for, объединив эти действия в одну строку:
for ( int i = 0; i < size; i++)
Что нам мешает сделать такой трюк тут? Ничего!
for ( Student * p = head; p != NULL; p = p->next)
или, еще короче:
for ( Student * p = head; p; p = p->next)
Далее, вы увидите, что в большинстве случаев я использую цикл for для прохода по листу.
Теперь, функция delete_student. Я хочу остановиться тут только на одном моменте: два указателя. Зачем? Чтобы понять это, надо привести такой пример: допустим, мы хотим удалить 3-й элемент. Но мы не знаем, что элемент, который нам надо удалить - третий по счету. Нам нужно попасть в этот элемент, чтобы сравнить фамилии.
Вот мы идем по листу: 1-й элемент, сравнение - не он. Двигаем р во второй элемент. 2-й элемент, сравнение - не он. Двигаем в третий. 3-й элемент, сравнение - он! Надо удалять. А что такое удалить элемент из листа? Это значит, исключить его оттуда и освободить. НО! На него указывает 2-й элемент, а он сам - на 4-й. То есть, нужно сделать так, чтобы теперь next ВТОРОГО элемента указывал на 4-й....
НО! Мы находимся в 3-м... второй мы уже прошли.... Да, бывают листы, в котором есть указатель на next (на следующий элемент) И указатель на prev (на предыдущий элемент), такой лист называют "двусторонний", но это не наш случай))) Я специально не использовал двусторонний лист, чтобы научить пользоваться вот таким, "обычным", так как он используется довольно часто, а умея пользоваться этим - легко можно понять, как пользоваться двусторонним. То есть, в нашем случае, вернуться назад - невозможно! И это - важно понять!
Поэтому, я использую такой трюк: я двигаю 2 указателя. Второй q отстает от первого р на один шаг. Таким образом, у меня в руках есть предыдущий элемент! Далее, как только я нашел нужный элемент - я говорю, что next предыдущего (то есть второго) указывает на next этого, то есть - на четвертый. После этого я удаляю этот. Если бы мне нужно было бы удалить несколько, то я бы это делал через "временный указатель", как я объяснял в теории, а потом бы приводил в порядок указатели. Но так, как это не требуется и как только я удалю элемент, я покину цикл (break), то я не стал это делать.
Хочу заметить, что ни в этой, не в следующей функции я не могу добавить/убрать первый элемент! Почему? Потому что он - указывает на голову. Поясню:
Мы создали структуру в куче, допустим, она имеет адрес 17. После этого, мы создали указатель на нее. Указатель имеет адрес 28. Это указатель на первый элемент. Теперь по адресу 28 лежит значение "17". Мы передаем указатель в функцию. Как мы знаем, создается новая переменная из типа "указатель" и у нее есть новый адрес, допустим 33, однако, в нее скопировано значение "17".
То есть, в функции, мы работаем с указателем, имеющим адрес 33 и это наша "голова". Теперь мы хотим добавить элемент в голову, либо удалить из головы... НО! Все, что мы сделаем в этой функции - мы сделаем с указателем, который имеет адрес 33, а "настоящая" голова имеет адрес 28.... То есть, наши изменения в функции не происходят с "настоящей" головой!
Есть 2 решения:
1. вернуть "голову" из функции и присвоить ее настоящей
2. передать указатель на указатель
То есть, для того, чтобы у нас была возможность изменить первый элемент, наши обе функции (add_student, delete_student) функции должны быть описаны вот так:
add_student ( Student ** head ) // ДВЕ звезды!
А присвоение "шагающему указателю" р происходило бы так:
Student * p = (*head)->next
Почему next? Потому что перед этим, мы бы проверяли: не является ли нужный нам элемент головой? Если да, то наши действия происходили бы отдельно, а если нет - то мы бы сразу шли в следующий элемент (первый-то мы уже проверили). Но я не стал делать этого тут, чтобы не усложнить код. На самом деле, в настоящей программе, это делать необходимо.
Теперь, когда мы разобрали delete_student, в add_student мы легко поймем код, потому что там используется тот же трюк с двумя указателями. Единственное, на что хочу обратить внимание: создание нового студента происходит сразу со "связыванием" его в листе. Можно было сделать так же, как я сделал в main, но это лишние, никому не нужные телодвижения.
Функция free_list рекурсивная. Я буду удалять элементы, начиная с последнего. Потому, что если я напишу в начале delete p, то потом я не смогу продвинуться p = p->next, так как р уже не существует. Поэтому, я в начале пройду в конец листа, а потом, на выходе начну удалять элементы.
Конструктор и деструктор мы разбирать не будем, там нет ничего нового. Просто обратите внимание на то, что я даю начальные значения членам структуры в столбик, для удобства чтения кода.
Совет: для лучшего понимания того, что происходит в этих функциях, можно взять бумагу и ручку и схематически все нарисовать. Идти по алгоритму: "ага, этот указатель сейчас указывает сюда, тут я присваиваю то-то"... Желательно, хотя бы один раз все нарисовать, чтобы ГЛАЗАМИ на все посмотреть!
Список как объект
Когда мы узнали, что такое "связанный список" или "лист", давайте попробуем сделать работу с ним более удобной. Для того, чтобы понять, что нужно улучшать, давайте разберемся в чем проблемы?
1. Мы уже видели, что существует проблема работы с первым элементом. Он требует "особого подхода"
2. Часто нужно добавлять элемент в лист, для этого необходимо найти конец. Чтобы найти конец - нужно пройти по всему листу. Можно ли это ускорить?
3. Как узнать размер листа? Только посчитать....
Сейчас мы попробуем решить все эти проблемы, однако, есть еще ряд других проблем в листе. Например, невозможно СРАЗУ попасть в 3-й элемент, нужно начать с первого и продвигаться.... эту и еще ряд проблем мы пока не можем решить. Поэтому, если нам нужна возможность попасть сразу в определенное место в листе, то тут стоит задуматься: какой именно контейнер нам подойдет лучше? Пока мы знаем только два: массив и лист, однако, есть еще, но об этом мы поговорим в других лекциях.
А пока мы приступим к решению заявленных выше проблем, а так же поговорим о "универсальном" контейнере, способным хранить любой тип переменных. Это реально? Да, конечно. Это даже желаемо! Думаю, что не смотря на явные минусы, понятно, что лист - довольно удобный контейнер для хранения данных в программе. То есть, желательно написать это все только ОДИН раз, а далее использовать готовый, отдебаженый код во всех программах, где нужен лист. Но чтобы пользоваться этим контейнером, нужно, чтобы программа умела выполнять следующие действия:
1. Добавить данные в конец или начало листа
2. Удалить данные из листа
3. Найти данные в листе
Это обязательные возможности, но если мы уже пишем "универсальный" лист, то было бы неплохо, так же, чтобы лист умел еще:
1. Сказать какой у него размер
2. Добавить элемент в любое место в листе
3. Соединить два листа в один
4. Создать лист "клон" (точную копию себя)
5. Распечатать содержимое листа на экран
6. Стереть лист полностью (стереть все данные и сам лист)
Я покажу направление, в котором нужно двигаться, чтобы проще и с большим удобством решить эти задачи, а само решение всех поставленных задач нужно будет описать в домашнем задании))) Придется подумать головой))) не все коту масленница!
Допустим, у нас есть структура, назовем ее "узел". В этом узле мы будем держать данные. Как можно сделать контейнер, который способен хранить ЛЮБОЙ тип переменной? Тут на помощь придет "неопределенный указатель", то есть void *. Итак, наш "узел" выглядит так:
struct Node {
void * data; // указатель, который будет содержать данные
Node * next; // указатель на следующий элемент в листе
};
Тут вроде ничего нового нет (кроме фокуса с void*) и это не решает проблему. НО! Мы можем ввести еще одну структуру, которая будет "заведующей" листом. Мы так и назовем ее "Лист":
struct List {
unsigned long size; // хранит количество элементов в листе
Node * head; // хранит указатель на голову
Node * tail; // хранит указатель на последний элемент (хвост)
};
Теперь, таким образом мы решили из "обязательных":
1. Добавить данные в конец или начало листа
Из "дополнительных":
1. Сказать какой у него размер
2. Добавить элемент в любое место в листе
3. Соединить два листа в один
При этом, у нас есть проблемы с этим:
"Обязательные":
2. Удалить данные из листа
3. Найти данные в листе
"Дополнительные":
4. Создать лист "клон" (точную копию себя)
5. Распечатать содержимое листа на экран
6. Очистить лист полностью (стереть все данные)
В чем же проблемы?
1. Для того, чтобы найти данные в листе, необходимо уметь сравнить данные))) (КЭП?) А как сравнить данные, если мы не знаем, ЧТО там лежит? Числовые переменные нужно сравнивать через оператор ==. Стринги мы сравниваем через функцию strcmp, а студентов? Студентов наверное надо сравнивать по id или по фамилии.....
2. Для того, чтобы удалить содержимое ПРАВИЛЬНО, нужно освободить память... а как? ЛИБО delete, либо delete [ ] (в листе, в качестве данных вполне может лежать массив В КАЖДОМ узле - свой....). А если предположить, что память освобождать не нужно? Кто-то еще пользуется этими данными.... нужно просто исключить его из листа.... как быть?
3. Для того, чтобы распечатать содержимое листа, нужна функция распечатки.... а у нас там void*, который может быть обычным стрингом, а может быть структурой "Студент", у которого есть имя, фамилия, id, оценки.... да мало ли?
4. Чтобы создать клон, нужно знать, как создавать то, что лежит в КАЖДОМ узле...
Как же решить эти проблемы? И вот тут на помощь нам придут указатели на функцию))). И вот мы медленно, но верно, поняв все, стоящие перед нами задачи, подошли к домашнему заданию. Оно не будет простым. Потребуется немного вспомнить материал, МНОГО думать головой и отлично понимать материал этой лекции. Думаю, что мы подошли к моменту, когда каждый точно поймет: насколько он понял все то, что я рассказываю? Если с пониманием проблем не было, то и в домашнем задании их не будет. А если есть "белые пятна", то я советую ВСЕ РАВНО пытаться решить эту задачу, так как попробовав, всегда понимаешь лучше решение другого человека. Ну, а это другое решение мы увидим уже на следующей лекции))))
Домашнее задание
Создайте две структуры Node и List так, как я описал это выше. Желательно подумать о конструкторах и деструкторах: стоит ли их создавать и если да, то какие?
Вместе с этим, имплементируйте такие функции:
List * create_list (void) - создает новый, пустой лист
void destroy_list ( List * list, void (*destroy_func) (void*) ) - уничтожает лист, с возможностью освободить память.
подробнее:
List * list - лист, который нужно уничтожить
void (*destroy_func) (void*) - указатель на функцию освобождения памяти. Функция умеет освобождать ОДИН элемент в листе, то есть, нужно вызвать ее для каждого элемента (функция принимает void* и ничего не возвращает)
при условии, что память освобождать не нужно, вместо функции будет передан NULL
void append_to_list ( List * list, void * item ) - добавить элемент item в конец листа
void prepend_to_list ( List * list, void * item ) - добавить элемент item в начало листа
bool insert_to_list ( List * list, void * item, unsigned long index ) - добавить элемент item в место номер index листа (вернет false при провале)
void remove_from_list ( List * list, void * item, short (*compare_func) (void*, void*), void (*destroy_func) (void*) ) - удалит элемент, равный item из листа
указатель на функцию void (*destroy_func) (void*) - работает так же как и в destroy_list
указатель на функцию short (*compare_func) (void*, void*) принимает для сравнения 2 элемента и возвращает:
-1 если первый меньше второго
0 если первый равен второму
1 если первый больше второго
* примечание: чуть позже, когда выучим сортировки, такая же точно функция поможет отсортировать лист
void * find_in_list( List * list, void * item, short (*compare_func) (void*, void*) ) - находит элемент item в листе
указатель short (*compare_func) (void*, void*) работает так же, как и в remove_from_list
void concat_list ( List * list1, List * list2) - соединяет два листа в один (к концу list1 привязывает list2)
void print_list ( List * list, void (*print_func) (void *) ) - распечатывает лист на экран
указатель void (*print_func) (void *) умеет указывает на функцию, которая умеет распечатать один элемент на экран
List * copy_list ( List * src, void * (*copy_item) (void * item) ) - создаст точно такой же лист, как и src
указатель void * (*copy_item) (void * item) умеет создать копию item. При копировании листа функция вызывается для каждого элемента
Можно создавать дополнительные функции, помогающие в работе этих.
Удачи! Она вам пригодится))))
@темы: C++