Хранение и обработка данных с использованием линейных списков - Курсовая работа

На сегодняшний день информация и информационные ресурсы играют огромную роль в жизни человека. Существует множество выражений, которые отражают этот факт, например «Знаешь все - владеешь миром», «Проинформирован - значит вооружен» и т.п. Список - это набор записей, выстроенных в определенной последовательности.[1] В повседневной жизни списки окружают нас повсюду, являясь довольно эффективным способом хранения нужной нам информации. Примерами могут служить список продуктов, который составляют при походе в магазин, список студентов в журнале, список дел на день, различные словари и т.д. Линейные списки находят широкое применение в приложениях, где непредсказуемы требования на размер памяти, необходимой для хранения данных; большое число сложных операций над данными, особенно включений и исключений.Список представляет совокупность связанных между собой узлов. Список, каждый элемент которого содержит указатель только на следующий за ним элемент, называется однонаправленным или односвязным. Если добавить в каждый элемент вторую ссылку - на предыдущий элемент, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых операций над списком.Т.е. логично оформить в виде функций различные операции со списком (формирование, поиск, добавление, удаление элемента и т.д.), поскольку они представляют собой законченные действия. Элементы списка представим в виде структуры с именем Node, содержащей информационное поле (собственно хранимый символ) и два указателя: на предыдущий элемент и на следующий. struct Node Алгоритм работы функции добавления следующий: ввести элемент, затем обнулить указатель на следующий элемент (т.к. добавление происходит в конец списка), а в указатель на предыдущий элемент записать адрес предыдущего элемента или обнулить его (если список пуст). Следовательно, алгоритм работы функции вставки такой: ввести вставляемый элемент, ввести элемент, после которого будет произведена вставка и если такой элемент найден, произвести вставку и скорректировать указатели головы и хвоста списка. Алгоритм работы функции удаления следующий: вводится элемент, который требуется удалить, затем в зависимости от того, находится элемент в начале списка, в середине или в конце, этот элемент удаляется и соответствующим образом корректируются указатели на предыдущий и следующий элементы, а также указатели головы и хвоста списка.После разработки и выбора необходимых алгоритмов, целесообразно представить алгоритм работы программы на псевдокоде, чтобы было легче перейти к составлению программного кода. Псевдокод - формализованное текстовое описание алгоритма (текстовая нотация).[5] Т.к. работа всей программы сводится к выполнению индивидуального задания на курсовую работу, то представим псевдокод функции, отвечающей за его выполнение. Дано: целые переменные k, m и n - количество элементов первого, второго и третьего списка соответственно; указатели на начало и конец каждого из списков; i, j, z - счетчики циклов.Каждый элемент представляет собой структуру с именем Node, содержащую символьную переменную и два указателя - на предыдущий и на следующий элемент - типа Node с именами prev и next соответственно. struct Node Исходя из разработанных алгоритмов, все функции, за исключением поиска и вывода на экран, будут получать в качестве параметров ссылки на указатели начала и конца списка, чтобы после работы функции мы имели возможность работать с измененной последовательностью. Функция должна пройти по списку, начиная с головы, и проверить совпадение элемента, переданного в качестве параметра, с каждым его элементом. [6] В теле функции организуем ввод элемента, который будет удален, поиск этого элемента по списку и соответствующую кооректировку указателей, в зависимости от того, из какой части списка будет удален элемент. Если удаление происходит из начала списка, следует указателю головы присвоить адрес следующего элемента; если из середины - указатели next предстоящего элемента и prev следующего изменить так, чтобы эти элементы указывали друг на друга; если из конца списка - сместить указатель хвоста на предыдущий элемент. char key;После составления программного кода, необходимо проверить работоспособность написанной программы, т.е проивести ее отладку. Ошибки в программе разделяют на две группы: синтаксические (ошибки в тексте) и алгоритмические. Процесс отладки можно считать законченны если программа правильно работает при любом правильном наборе входных данных. Для достижения наилучшей работоспособности программы следует также провести ее тестирование, особенно если предполагается, что программой будут пользоваться другие.Тестирование следуе

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. РЕАЛИЗАЦИЯ ЛИНЕЙНЫХ СПИСКОВ

2. РАЗРАБОТКА И ВЫБОР АЛГОРИТМОВ

3. ОПИСАНИЕ РАБОТЫ ПРОГРАММЫ НА ПСЕВДОКОДЕ

4. СОСТАВЛЕНИЕ ПРОГРАММНОГО КОДА

5. ТЕСТИРОВАНИЕ И ОТЛАДКА ПРОГРАММЫ

6. РЕЗУЛЬТАТ РАБОТЫ ПРОГРАММЫ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ. ЛИСТИНГ ПРОГРАММЫ