Файл: Обзор языков программирования высокого уровня (Современные языки программирования).pdf
Добавлен: 31.03.2023
Просмотров: 81
Скачиваний: 2
Архитектурно правильным решением будет выделение внутренних (приватных) и внешних (публичных) методов доступа к данным. Первые будут представлять низкоуровневую часть, непосредственно работать с элементами. Вторые будут являться так называемой оберткой к низкоуровневым методам и предоставлять интерфейс для работы со списком. Это позволит разграничить доступ, повысив надежность программы. Разумно будет возложить на внешние методы осуществление различных проверок, такие как выход за границы списка, удаление несуществующего элемента. Также они могут являться удобной комбинацией внутренних методов, например, pop – удаление последнего элемента и возврат его значения реализуется через последовательное выполнение внутренних методов get (получение значения) и remove (удаление значения).
Рассмотрим внутренние методы.
int insertNode(int index, int val) – этот метод вставляет элемент val в указанное место index. И, согласно принятой практике, возвращает 0 в случае успешного выполнения и код ошибки в противном случае. Как уже говорилось, проверка выхода за границы списка производится во внешних методах, поэтому здесь мы уверены, что index допустимый. Во время выделения памяти для нового элемента может произойти ошибка, поэтому соответствующее исключение ловится, и функция возвращает -1.
Следует выделять три разных ситуации: добавление в начало списка, середину и конец. В первом случае поле next нового элемента должно указывать на бывший первый элемент, а указатель начала head списка следует перенаправить на новый элемент.
new_node->next = head;
head = new_node;
Вставку в середину и конец списка можно объединить. Для этих случаев нужно начать с головы списка и продвигаться по нему до тех пор, пока не будет найден узел, после которого нужно вставить новый элемент.
node = head;
for (int i=0; i<index-1; i++)
node = node->next;
На выходе цикла node будет указывать на элемент, после которого будет производиться вставка. Для самой вставки полю next нового элемента присваивается указатель следующего элемента, на который указывает предыдущий элемент, а потом и полю next предыдущего элемента следует присвоить адрес нового элемента.
new_node->next = node->next;
node->next = new_node;
Также не стоит забывать и о том, что в случае вставки в конец списка поле next нового элемента должно иметь значение NULL, но этот шаг опускается, так как он уже был сделан при инициализации структуры нового элемента. В конце функции увеличивается счетчик количества элементов.
Метод int getNodeValue(int index) предназначен для поиска элемента по его индексу. Здесь поиск аналогичен описанному выше, только итерация идет не до index-1 (предыдущий элемент), а до index. Сам метод возвращает значение найденного элемента.
Метод void updateNodeValue(int index, int val) обновляет существующий элемент новым значением. Для этого нужно найти этот элемент по индексу и обновить ему поле val.
Метод int findValue(int value) ищет элемент по его значению.
Node *node = head;
// если элемент найден, возвращаем его индекс
for (int i=0; node; node=node->next, i++)
if (node->val == value)
return i;
// элемент не найден
return -1;
В данном случае цикл выполняется до тех пор, пока не будет найден элемент с нужным значением, или пока не будет достигнут конец списка. В этом цикле признаком конца списка является достижение элемента с нулевым полем next. Также в качестве признака конца списка можно использовать известное количество элементов в списке (node_counter). Если элемент находится, возвращается значение счетчика цикла – он будет равен индексу искомого узла. Если же элемент не найден (выход из цикла), то будет возращено значение -1, которое не может служить индексом узла, и поэтому является признаком отсутствия искомого элемента.
Метод void deleteNode(int index) предназначен для удаления элемента по его индексу. Как и в случае добавления элемента стоит выделить 3 ситуации: удаление с начала списка, с середины и с конца. В первом случае мы перенаправляем указатель головы списка на следующий элемент и удаляем первый узел:
node = head;
head = head->next;
delete node;
Для удаления с середины и конца списка нам также нужно найти предыдущий узел. Далее по его полю next находим удаляемый элемент, и полю next предыдущего элемента присваиваем указатель next удаляемого узла. После этого можно освобождать память удаляемого элемента.
node = head;
for (int i=0; i<index-1; i++)
node = node->next;
del_node = node->next;
node->next = del_node->next;
delete del_node;
Удаление с середины и конца списка также легко объединяется. При удалении последнего элемента указатель next предыдущего элемента должен быть обнулен, но это является частным случаем операции node->next = del_node->next, так как del_node->next уже равнялся NULL. В конце функции нужно уменьшить счетчик node_counter.
Метод void deleteAllNodes() удаляет все имеющиеся элементы. Для этого понадобится два указателя, ведь для удаления нужно знать адрес удаляемого элемента, а также адрес следующего элемента, который мы не узнаем, сначала удалив узел.
Node *node = head;
while (node) {
head = head->next;
delete node;
node = head;
}
Указанные приватные методы являются базой для работы со списком. На их основе можно создавать удобные интерфейсы, что и будет показано в публичных методах.
Рассмотрим внешний интерфейс, который предоставляет класс LinkedList. В интерфейсе используется термин позиция – это порядковый номер элемента в списке. Людям привычнее начинать счет с единицы, а не с нуля, поэтому позиция автоматически преобразуется в индекс вычитанием единицы.
Методы void append(int value), voide prepend(int value) добавляют узел соответственно в конец и начало списка. Они являются частными случаями метода void insert(int pos, int value), который вставляет элемент на указанную позицию, и служат для удобства работы с классом. Все три метода вызывают приватный метод insertNode, только с разными параметрами. Количество элементов в списке нам известно благодаря счетчику, поэтому вычислить индекс при добавлении элемента в конец списка не составляет труда. Помимо этого метод insert сначала проверяет границы списка, и лишь потом вызывает insertNode. Стоит заметить, что эти три публичных метода намеренно никак не реагируют на ошибку выделения памяти для нового элемента (сообщение о проблеме выведет приватный метод), и программа продолжает работу. Можно завершить программу, но тогда данные в списке будут потеряны.
Метод void insert(int pos, int value) вставляет элемент в указанную позицию, void remove(int pos) удаляет элемент, void get(int pos) выводит значение элемента, а void update(int pos, int value) обновляет элемент по указанной позиции. Все они проверяют значение позиции, чтобы она была не меньше 1 (нумерация начинает с 1) и не выходила за края списка.
if (pos < 1 || pos > node_counter)
cout << "неверная позиция" << endl;
else
…
Метод void pop() является удобной комбинацией получения значения элемента и его последующим удалением:
void pop() {
if (!node_counter) {
cout << "список пуст" << endl;
} else {
cout << getNodeValue(node_counter-1) << endl;
deleteNode(node_counter-1);
}
}
Метод void length() выводит количество элементов в списке. Благодаря хранению счетчика узлов, достаточно вывести его значения, а не проходить весь список.
Метод void find(int val) ищет элемент с заданным значением val, используя для этого приватный метод int findValue(int value).
Метод void print() выводит поочередно все элемента списка.
Node* node;
if (!head) {
cout << "список пуст" << endl;
} else {
// проход по списку без использования знаний о количестве
// элементов (node_counter)
cout << "Список (" << node_counter << " элемент(а,ов)): ";
for (node=head; node; node=node->next)
cout << node->val << " ";
cout << endl;
}
Здесь отдельно обрабатывается ситуация, когда список пуст – в этом случае указатель на голову списка равен NULL. Следуя ранее заданной концепции, когда публичный метод обращается к приватному для доступа к элементу, стоило написать цикл, чтобы в нем вызывался getNodeValue от 0 до node_counter-1. Но решено был продемонстрировать проход по циклу без использования node_counter. В этом случае цикл выполняется, пока node не равен NULL, что укорочено можно записать как просто node.
Сама программа имеет консольный интерфейс. В нем за публичными методами закреплен свой номер. Эти значения имеются в меню, которое выводится в бесконечном цикле. Пользователь может самостоятельно работать со списком, выбирая необходимые операции по их номеру. У выхода из программы есть свой номер операции, также можно стандартно завершить программу по Ctrl+C.
Меню программы имеет следующий вид:
Операции:
1. Create list (создать список)
2. Append (добавить элемент в конец)
3. Prepend (добавить элемент в начало)
4. Insert (вставить элемент на указанную позицию)
5. Update (обновить элемент на указанной позиции)
6. Find (найти элемент по указанному значению)
7. Get (вывести элемент на указанной позиции)
8. Print (вывести все элементы)
9. Remove (удалить элемент на указанной позиции)
10. Pop (удалить последний элемент и вывести его значение)
11. Delete list (удалить список)
12. Exit (выход из программы)
Выберите номер операции:
Программа проверяет корректность введенных значений и в случае ошибки предлагает попробовать снова. Благодаря оператору switch удалось сгруппировать проверки по операциям и повысить читаемость кода.
Полный текст программы находится в Приложении.
Как видно, практическая часть организации данных в списковые структуры имеет свои тонкости, которые не всегда освещаются в теории. К сожалению, их нельзя освоить, просто прочитав необходимую литературу. Помимо этого необходим самостоятельный опыт работы, использование изученных методов на реальных примерах. Как говорил Александр Суворов, «Теория без практики — мертва, практика без теории — слепа».
Заключение
В данной работе были рассмотрены различные группы языков программирования. Как было показано, классификация не всегда носит строгий характер, но этого и не требовалось. Основная задача проведения классификации заключалась в выявлении характерных черт, присущих той или иной группе. А обладая этими знаниями, можно судить не только о знакомых языках, но и составить общее представление о возможностях неизвестных, возможно новых языках по их описанию. Также были рассмотрены самые популярные языки программирования на сегодняшний день, их сильные и слабые стороны.
Сравнивая языки между собой, было показано, что не существует лучшего языка программирования, каждый хорош в своей области, где важны определенные критерии, а при использовании в другой области с отличными критериями язык может оказаться в аутсайдерах. Даже у самых мощных языков имеются недостатки, заключающиеся как минимум в сложности программирования на них, что является весомым фактором не только для новичков, выбирающих свой первый язык для изучения, но и для корпораций, которые задумываются о поиске квалифицированного персонала, времени и затратах на разработку и дальнейшую поддержку своих продуктов.
Внутреннее устройство динамических структур в языках программирования имеет большое значение, ведь скорость работы алгоритмы и программы в целом сильно зависит от них. Сценарные языки часто скрывают их внутреннее представление, называя списки массивами. Это далеко не всегда является преимуществом. При повышенных требованиях к быстродействию и потребляемым ресурсам нередко приходится переходить на другой, не всегда такой же удобный язык, но позволяющий явно задавать необходимое внутреннее устройство динамических структур.
При рассмотрении динамических структур данных были определены принципы их построения, основные операции для работы с ними. Не смотря на имеющиеся недостатки, динамические структуры являются необходимой составляющей в программах, размер данных в которых заранее неизвестен. Благодаря своим особенностям они показывают отличные результаты в операциях, где необходимо интенсивное перемещение данных, например, в сортировке. Ведь для этого не требуют перемещение самих данных, как массивах, достаточно поменять указатели.
Особое внимание было уделено спискам, так как они являются основой для остальных динамических структур. Были рассмотрены широко используемые не только в компьютерной области, но и в повседневной жизни такие структуры, как очередь, стек и дек, особенности их построения на основе списков. Также затрагивались и более сложные нелинейные структуры на примере их характерного представителя – дерева, его частный случай бинарное дерево, которое позволяет добиться высокой эффективности не только в сортировке, но и в поиске.
В практической части была написана программа на языке программирования C++ для работы с линейным списком и описаны тонкости, на которые стоит обратить внимание при организации данных в списковые структуры. Благодаря выбору подходящего инструмента (C++) удалось не только продемонстрировать внутреннее устройство динамических данных и основных операций для работы с ними, но и изолировать эту внутреннюю реализацию, предоставив в качестве публичных методов удобные (хотя и избыточные) интерфейсы для работы со списком, что повышает надежность программы и безопасность данных.