Разработка программы для создания и работы с двусвязным списком, состоящим из структур. (Структура содержит фамилию и год рождения)

Государственный комитет Российской Федерации по телекоммуникациям

Сибирский государственный университет

телекоммуникаций и информатики

КУРСОВАЯ РАБОТА

По дисциплине «Программирование на языках высокого уровня»

Двусвязные списки

Вариант №7

Работу выполнил:

студент 1 курса

группы ПДВ-02

Тюленев Николай Александрович

Работу проверил:

Работа защищена

«___» __________2010 г.

С оценкой «_______»

Новосибирск 2010

Содержание

Задание. 4

Введение. 5

1.     Постановка комплекса задач. 7

2.     Блок-схема функционирования системы.. 8

3.     Структура проекта. 10

4.     Исходный код. 18

5.     Тестирование. 33

Заключение. 35

Задание

Разработать программу для создания и работы с двусвязным списком, состоящим из структур. Для работы со списком создать меню со следующими пунктами:

1.  Создание списка.

2.  Просмотр списка.

3.  Добавление в конец списка новой структуры.

4.  Корректировка списка.

5.  Выход.

Пункт «корректировка списка» выполнить согласно своему варианту задания:

Вариант №7: структура содержит фамилию и год рождения. Добавлять новые записи так, чтобы список был упорядочен по алфавиту.

Введение

Связный список относится к одному из видов организации хранения структур данных.

Структура данных – программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

Структуры данных подразделяют на линейные и иерархические. Связный список относится к линейным структурам данных.

Связный список – структура  данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки на следующее и/или предыдущее поле. Основные виды списков: однократно или дважды связный, отсортированный или неотсортированный, кольцевой или некольцевой [3, стр. 264]. Двусвязный список разновидность связного списка, который содержит две ссылки – на следующее и предыдущее поле.

При написании программ очень важную роль играет правильный выбор структур данных для организации и хранения тех или иных данных. В формальных языках программирования (C/C++, C#, Java) именно структуры данных ставятся во главу угла архитектуры программного средства.

При выборе структуры данных, необходимо ясно представлять, какие задачи она будет решать. Так преимущество связного списка перед массивом в том, что их размер является динамическим (т.е. в отличие от массива для добавления нового элемента не нужно заново пересоздавать всю структуру данных и копировать данные по новому адресу). Особенно быстро вставка новых элементов осуществляется на концах связного списка.

Тем не менее, необходимо помнить, что осуществление доступа к элементу по индексу в связном списке гораздо медленнее, чем в массиве.

Таким образом, при выборе между массивами и списками нужно определить, какие действия в работе со структурой данных будут превалирующими. Если чаще всего будет осуществляться доступ к элементам структуры по индексу и лишь изредка (возможно) понадобиться добавление новых элементов, то выбирать нужно массив. Если же необходимо будет постоянно добавлять новые элементы, и при этом доступ по индексу не так важен (к примеру, главное – это сортировка элементов и вывод их на экран), то, безусловно, выбор – списки.

1.  Постановка комплекса задач

1.1.  Комплекса задач

На примере создания связного списка:

·  освоить и закрепить навыки синтаксиса языка C;

·  получить базовые знания о структурах данных и их проектированию;

·  получить базовые знания об алгоритмах и их программированию (на примере сортировки);

·  получить опыт проектирования и создания API;

·  получить опыт создания интерфейсов взаимодействия с пользователем.

1.2.  Метод решения

Решение поставленных задач осуществляется путем написания программы, которая должна уметь создавать связный список, выводить его содержимое на экран, добавлять в конец списка новые данные, добавлять в список данные таким образом, чтобы список был упорядочен по алфавиту.

1.3.  Входные данные

В качестве исходных входных данных, на основе которых создается список, используются данные получаемые при помощи генератора случайных чисел. Для выполнения других пунктов меню используются данные вводимые пользователем.

2.  Блок-схема функционирования системы

3.  Структура проекта

3.1.  Использование подключаемых модулей

В программе использовались только те функции, которые входят в стандартную библиотеку C:

Функция	Использование в контексте программы
asctime*	Конвертация времени в формат строки
fgets	Получение строки из потока stdin
fseek	Перемещение указателя в потоке stdin
getch*	Получение символа из потока stdin
malloc	Выделение памяти под указатель
memset	Обнуление области памяти
mktime	Конвертация времени в формат time_t
printf	Вывод форматированной строки в поток stdout
puts	Вывод строки с началом новой линии в поток stdout
rand	Получение случайного числа
scanf*	Получение данных из потока stdin
srand	Установка точки старта генерации случайного числа
strcmp	Сравнение двух строк
strcpy*	Копирование строки
strlen	Длина строки в символах
time	Получение системного времени

Примечание к таблице. Функции, обозначенные звездочкой, являются устаревшими и могут быть небезопасными. В современных системах проектирования должны быть использованы новые функции в соответствии со стандартом ISO.

3.2.  Структура программы

Программа разрабатывалась на основе шаблона функционального дизайна. Функциональный дизайн гарантирует, что каждый модуль компьютерной программы имеет только одну обязанность и исполняет ее с минимум побочных эффектов на другие части программы [1, статья «Связный список»].

Применительно к данной программе этот шаблон применялся на уровне проектирования архитектуры программы (т.е. разбиение программы на модули и организация взаимодействия между ними) и на уровне организации кода (т.е. разбиение кода каждого из модулей на функции).

Таким образом, программа разделена на два модуля:

1.  Двусвязный список – обеспечивает работу с двусвязным списком: создание списка, добавление новых элементов, сортировка, удаление списка. Предоставляет программный интерфейс для использования этой функциональности.

2.  Интерфейс взаимодействия с пользователем – обеспечивает взаимодействие программы и пользователя, выводит на экран определенные данные, обрабатывает входные данные, поступающие от пользователя. На основе этого выполняет команды по работе с двусвязным списком (посредствам предоставленного интерфейса модуля двусвязного списка).