Создание программы "Телефонный справочник": загрузка телефонной книги; разработка алгоритмов добавления, редактирования, удаления записи; поиск по различным параметрам, вывод данных на печать. Интерфейс пользователя, системные требования и ограничения.
Техническое задание 2.1 Структура для хранения справочника 2.2 Структура для хранения номеров телефонов 2.
Список литературы
Приложение. Текст программы
Техническое задание
В данной курсовой работе требуется создать программу телефонный справочник, содержащую следующие сведения: ФИО, адрес, электронная почта, телефон (мобильный, домашний).
Выполним постановку задачи и приведем условия, которым должна удовлетворять программа, а также требования к необходимому результату: 1. Ввод исходных данных и формирование телефонной книги, возможность загрузки ранее созданного справочника и подгрузки данных в уже существующий справочник.
2. Корректировка данных: добавление данных, причем на одного абонента может приходиться несколько номеров телефона как мобильных, так и домашних; редактирование данных абонента; удаление абонента из справочника.
3. Сортировка телефонной книги должна быть в алфавитном порядке. Алгоритм реализации сортировки должен давать результат за максимально короткий промежуток времени.
4. В справочнике реализуется динамический поиск. Поиск должен проходить по нескольким параметрам: фамилии, номеру телефону, оператору.
5. Вывод данных об абоненте на печать.
Введение
Решение данной задачи можно разбить на несколько подзадач таких, как загрузить телефонную книгу, создать справочник, добавить, редактировать, удалить запись, поиск по различным параметрам, вывод данных на печать. Наиболее важными алгоритмами для поставленной задачи являются алгоритмы поиска и сортировки. Выбор подходящих алгоритмов поиска и сортировки основаны на простоте реализации и эффективности работы в рамках данной программы.
1. Теоретический материал
В данной работе реализованы различные алгоритмы, но наиболее важными из них являются алгоритм сортировки и поиска.
Сортировка один из наиболее распространенных процессов обработки данных. Сортировка к тому же еще достаточно хороший пример задачи, которую можно решать с помощью многих различных алгоритмов. Каждый из них имеет и свои достоинства, и свои недостатки, и выбирать алгоритмы нужно, исходя из конкретной постановки задачи. Рассмотрим несколько примеров сортировок и сравним их с алгоритмом, выбранным для реализации телефонной книги [1].
Сортировка с помощью прямого выбора. Суть этой сортировки заключается в том, что выбирается элемент с наименьшим значением, меняется местами с первым элементом, затем этот процесс повторяется с оставшимися элементами до тех пор пока список будет отсортирован.
Рис.1.1 Схема алгоритма прямого выбора
Сортировка с помощью прямого включения. В сортировке включениями элементы разделяются на уже упорядоченную и неупорядоченную последовательности. В начале упорядоченная часть содержит только один элемент. Очередной элемент из начала неупорядоченной части вставляется на подходящее место в упорядоченную часть. При этом упорядоченная часть удлиняется на один элемент, а неупорядоченная - укорачивается. Сортировка заканчивается при исчезновении неупорядоченной части [4].
Рис 1.2 Схема алгоритма прямых включений
Сортировка прямого обмена. Алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы. Повторяются проходы по списку, сдвигая каждый раз наибольший (или наименьший) элемент оставшейся последовательности к левому концу списка. Такой метод широко известен под именем пузырьковая сортировка. Очевидный способ улучшения этого алгоритма - были или не были перестановки в процессе некоторого прохода. Если в последнем проходе перестановок не было, то алгоритм можно заканчивать.
Рис 1.3 Схема алгоритма прямого обмена
Для решения поставленной задачи был выбран алгоритм прямого обмена, так как эта сортировка более проста в реализации и эффективна для данной задачи. Другие алгоритмы сортировки сложны в реализации, поэтому от них решили отказаться.
Важным алгоритмом для данной курсовой работы является алгоритм поиска подстроки в строке. Рассмотрим некоторые алгоритмы.
Алгоритм основанный на методе последовательного поиска. Обозначим S - слово, в котором ищется образец X. Пусть m и n - длины слов S и X соответственно. Можно сравнить со словом X все подслова S, которые начинаются с позиций 1,2,...,m-n 1 в слове S; в случае равенства выводится соответствующая позиция. Алгоритм прост в реализации. Количество сравнений будет равно O ((m-n 1)*n 1) [3].
Алгоритм Рабина. В слове A, длина которого равна m, мы ищем образец X длины n. Вырежем "окошечко" размером n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в "окошечке" с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую числовую функцию на словах длины n, тогда задача сведется к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в "окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам. Общее время работы есть O(n m). Данный метод накладывает некоторые ограничения на текст и искомую строку [2].
В курсовой работе использовали алгоритм последовательно поиска, так как данный алгоритм является простейшим алгоритмом поиска, не накладывает никаких ограничений на текс или искомую строку и имеет простейшую реализацию.
2. Описание использованных структур данных
2.1 Структура для хранения справочника
На практике (в зависимости от требуемой задачи) используются различные способы представления данных в памяти компьютера: 1) список 2) массив 3) битовые поля 4) деревья и т.д.
Для хранения данных телефонной книги использовали двухсвязный список. Каждый элемент списка состоит из двух полей: информационного, где хранятся данные абонента (ФИО, адрес, электронная почта, номера телефонов) и поля связок, где содержится указатель на следующего и предыдущего абонента телефонной книги.
Графически структура списка выглядит следующим образом:
Рис. 2.1 Структура двусвязного списка
В программе список реализован в следующем виде: LINKABONENT = ^Abonent; //ссылка на запись абонент
BACKABONENT: LINKABONENT; //предыдущий index:Integer; //порядковыйномеротображаемогоабонента show:Integer; //отображается или нет абонент end;
Достоинство этой структуры данных, помимо возможности изменять размер, - это простота реализации. Также, благодаря наличию ссылок, каждый элемент в списке, в отличие от массива, может занимать разный объем памяти. Адрес первого элемента в линейном списке однозначно определяется адресом самого списка.Легкость добавления и удаления элементов так же является одним из достоинств данной структуры.
2.2 Структура для хранения номеров телефонов
Для хранения номеров телефона использовали так же список, но в данном случае односвязный. Каждый элемент представляется в виде двух полей: информационного (номера телефонов) и поля связок (указатель на следующий элемент списка).
Графическое представление данной структуры:
Рис. 2.2 Структура односвязного списка
Структура хранения номеров телефона в программе представлена в следующем виде: Telephone = record // телефон telephone: ANSISTRING; // номертелефона
TYPETEL: TYPETELEPHONE; //тип телефона (мобильный или домашний )
NEXTTELEPHONE: LINKTEL; // указатель на следующий номер телефона end;
Односвязный список оказался наиболее подходящей структурой для хранения номеров телефона. Эта структура легка в применении и эффективна для данной задачи.
2.3 Структура файла телефонной книги
Файл телефонного справочника с пользовательским расширением tlb, вкотором хранится данные о абонентах: ФИО, адрес, почта, номера телефонов. Данный файл можно открывать в таких приложения как блокнот.
3. Описание процедур и функций
Данная программа состоит из большого числа процедур и функций. Опишем их.
New Abonent (SURNAME, Name, SECONDNAME, Adress, Mail: ANSISTRING; Tel: LINKTEL) - процедура добавления нового абонента в телефонный справочник.
Входные данные: фамилия, имя, отчество, адрес, почта и номера телефона. В этой процедуре вызывается процедура Add Abonent.
NEXTSTEP (cur, new: ANSISTRING): Step - функция определяющая направление движения при сортировки абонентов в справочнике. Входные данные: текущий и новый элемент. Возвращает положение элемента при сортировки.
Add Abonent (Abonent: Link Abonent) - процедура добавления абонента и сортировки списка абонентов. Входные данные: абонент телефонного справочника. Из этой процедуры идет вызов функции NEXTSTEP.
Add Telephone (TELLIST: LINKTEL; Telephone: ANSISTRING; TYPETEL: TYPETELEPHONE) - процедура добавления номера телефона. Входные данные: список телефонов текущего абонента, новый номер телефона, тип нового номера.
SHOWABONENT (abonent: LINKABONENT; SG1,SG2: TSTRINGGRID) - процедура отображения информации об абоненте .Входные данные: абонент. Из данной процедуры вызывается процедура SHOWALLTEL.
LIVESEARCH (FINDSTR: ANSISTRING; TYPES:TYPESEARCH) - процедура, реализующая живой поиск в телефонном справочнике. Входные данные: искомая подстрока, тип искомого элемента.
Create Telephone Book(): Integer - процедура создание новой телефонной книги. Функция возвращает единицу, если создан телефонный справочник.
Иерархия вызова функций имеет следующий вид (рис.3.1):
Рис.3.1 Иерархия вызовов функций
4. Описание структуры приложения и интерфейсапользователя
Программа имеет простой интерфейс для пользователя. Рассмотрим возможные операции данной программы.
Рис. 4.1 Главное окно программы
Рис. 4.2 Главное окно программы
1. Файл. Позволяет создать новую телефонную книгу, сохранить справочник, открыть или закрыть телефонный справочник.
2. В данном окне выводится абоненты занесенные в телефонную книгу.
3. Поисковая строка. В зависимости от того какой поиск реализуется, в поисковую строку будут вводиться соответствующие данные.
4. Параметры, по которым возможен поиск в рамках данной программы. Поиск можно производить по фамилии, телефону и оператору.
5. Кнопки позволяющие добавлять новый абонент, редактировать данные и удалять контакт из телефонного справочника.
6. Отображает данные абонента: фамилию, имя, отчество, адрес, электронную почту, номера телефонов и тип соответствующего телефона.
7. Выводит данные о каком-либо абоненты на печать.
Для открытия телефонной книге щелкните левой кнопкой мыши на поле «файл», выберите необходимое действие «открыть», появится новое окно, предлагающее выбрать телефонный справочник из ранее сохраненных (рис.7).
Рис. 7 Открытие телефонной книги
Рис. 8. Выводимые данные на печать
Печать данных происходить следующим образом. Сначала выбираем абонента, информацию о котором необходимо распечатать, щелкнем по кнопки печать и программа выдаст нам окно, содержащее данные абонента (рис.3), далее нажимаем снова печать и выбираем необходимый принтер (рис.4).
Рис. 9. Выбор принтера
Приложение имеет модульную структуру. В ее состав входит один модуль, который состоит из всех процедур и функций программы.
5. Системные требования и имеющиеся ограничения
Для работы программы требуются персональные компьютеры со следующими характеристиками: 1. Операционная система: Windows 98/NT/XP/VISTA/7 с установленным. Память: 108 Кбайт свободного места на жестком диске. Клавиатура, мышь.
2. Программа не имеет ограничений по количеству записей в телефонную книгу. Ограничения по объему записей будет только оперативной памяти.
3. Программа работает с файлами формата *.tlb, созданный данной программой. Она не предохранена от некорректного ввода данных из файла, поэтому если файл поврежден, поведение программы при открытии такого файла является непредвиденным. Программа не требует защиты и может свободно распространяться.
6. Результаты тестирования приложения
При помощи специально написанной процедуры был произведен тест производительности алгоритма на разных объемах входных данных. Тест выдавал информацию о количественных характеристиках работы алгоритма, таких как количество перестановок при сортировке, количество перестановок при поиске. Наиболее значимым параметром является количество выполненных перестановок, так как они отражают эффективность.
Тест производился следующим образом: загружаем определенное количество записей в телефонный справочник и проверяем, сколько для него было сделано перестановок при сортировке и при поиске. Проверим работу программу на десяти различных объемах данных.
Результаты теста показаны ниже:
Рис. 6.1 Колво перестановок сортировки при 1000 записей
Рис. 6.2 Колво перестановок поиска при 1000 записей
Рис. 6.3 Колво перестановок сортировки при 5000 записей
Рис. 6.4 Колво перестановок сортировки при 5000 записей
7.Анализ временных характеристик и выводы
Результаты тестирования для десяти различных объемов данных представлены ниже в таблице и на графиках: Таблица 1
Зависимость перестановок при сортировке и поиске от объема
Количество перестановок при сортировке 1309 3031 3088 3971 4726 6543 8159 10447 11085 12705
Количество перестановок при поиске 2000 4000 6044 8020 10086 12091 14110 16109 18130 19901
Рис. 7.1 Зависимость перестановок при сортировки от объема записей
Рис. 7.2 Зависимость перестановок при поиске от объема записей
Взглянув на графики, можно убедиться, что как и ожидалось из теории количество перестановок при сортировки и при поиске линейно растет от общего количества записей в телефонной книге. При увеличения объема записей возрастает количество перестановок.
Из графика видно, время работы справочника линейно зависит от объема загружаемых данных.
Рис. 7.3 Зависимость времени работы справочника от объема входных данных
Тем не менее, практическое сопоставление временной сложности с теоретической оценкой весьма затруднительно, поскольку для этого требуются специально подбирать вводимые данные, чтобы явно показать зависимость сложности перестановок и объема данных.
Заключение
В соответствии с заданием была разработана программа, имеющая удобный интерфейс, и предоставляющая возможность создания и редактирования телефонного справочника и поиск по различным параметрам. В ходе работы были рассмотрены алгоритм живого поиска, поиска подстроки в строке и сортировка, и проведен анализ их временной сложности. Задача была реализована в интегрированной среде разработки Borland Delphi 7.0.
Список литературы
1. Гагарина Л.Г. Алгоритмы и структуры данных: учеб. пособие/Л.Г. Гагарина, В.Д. Колдаев. - М.: , 2009. - 304 с.
2. Ахо А. Структуры данных и алгоритмы: учеб. пособие/ А. Ахо, Хопкрофт Д.Э., Ульман Д.Д.- М.:,2003. - 384с.
