Государственный комитет Российской Федерации по телекоммуникациям
Сибирский государственный университет
телекоммуникаций и информатики
КУРСОВАЯ РАБОТА
По дисциплине " Программирование на языках высокого уровня"
Тема работы
Сортировка двусвязного динамического списка
Вариант № 7
Работу выполнил
студент 1 курса
группы ПДТ - 73
Трофимов М. И.
Работу проверил
Перцева В. А.
Работа защищена
«___» __________2007г.
С оценкой «_______»
Новосибирск 2007
2. Задание
Разработать программу для создания и работы с двусвязным списком, состоящим из структур. Для работы со списком создать меню со следующими пунктами:
1. Создание списка.
2. Просмотр списка.
3. Добавление в конец списка новой структуры.
4. Корректировка списка
5. Выход.
Пункт "Корректировка списка" выполнить согласно своему варианту задания.
Вариант задания: Структура содержит фамилию, год рождения. Добавлять новые записи так, чтобы список был упорядочен по алфавиту.
3. Содержание
1 Титульный лист 1
2 Задание 2
3 Содержание 3
4 Введение 4
5 Постановка комплекса задач 5
6 Блок-схема функционирования системы 6
7 Проектный раздел 10
8 Исходный модуль программы 14
9 Результаты тестирования выполнения программы 19
10 Список используемой литературы 22
4. Введение
Язык программирования Си создан в 1972 г. Деннисом Ритчи при разработке операционной системы UNIX. Язык проектировался как инструмент для системного программирования с ориентацией на разработку хорошо структурированных программ. Первоначально он появился в операционной системе UNIX, и развивался как основной язык систем, совместимых с ОС UNIX. Сам язык, однако, не связан с какой-либо одной операционной системой или машиной; и хотя его называют языком системного программирования, так как он удобен для написания операционных систем, он может использоваться для написания любых больших вычислительных программ, программ для обработки текстов и баз данных. Компиляторы языка Си работают почти на всех типах современных ЭВМ в операционных системах UNIX, MS-DOS, OS/2, Windows, Windows NT и т.д.
5. Постановка комплекса задач
Необходимо создать двусвязный динамический список, состоящий из структур содержащих информацию о людях. Структура должна состоять из 2 полей:
1 поле – фамилия, 2 поле – год рождения.
Необходимо реализовать следующие действия со списком
§ Ввод динамического списка
§ Вывод списка
§ Добавление новых стрктур
§ Сортировка списка по алфавиту
В состав программы входят следующие модули:
5.1. Меню – состоящее из следующих пунктов:
1. Создание списка
2. Просмотр списка.
3. Добавление в конец списка новой структуры.
4. Корректировка списка.
5. Выход.
5.2. Блок "Создание списка" – выполняет задачу по созданию новых структур двусвязного списка, каждая структура содержит данные о фамилии и годе рождения абстрактного человека.
5.3. Блок "Просмотр списка" – выводит на экран в виде таблицы содержимое двусвязного списка, начиная с первой структуры.
5.4. Блок "Добавление в конец списка новой структуры" – позволяет добавлять
в конец списка новые структуры.
5.5. Блок "Корректировка списка" выполняет добавление новых записей содержащих фамилию и год рождения, сортирует список в алфавитном порядке и выводит отсортированный список на экран.
5.6. Выход – позволяет пользователю закончить выполнение программы.
6. Блок-схема функционирования системы
6
 |
Рис 6.1. Блок – схема работы
"меню"
 |
Рис 6.2. Блок – схема работы процедуры "Создание списка"
 |
 |
||||
|
|||||
Рис 6.3. Блок – схема работы процедуры "Просмотр списка"
 |
|||
 |
|||
Рис
6.5. Блок – схема работы процедуры
"Корректировка списка"
7. Проектный раздел
Список – это последовательность структур, каждая из которых содержит ссылку связывающую ее с другой структурой.
Динамический список, в котором каждый элемент кроме первого и последнего связан с предыдущим и следующим за ним элементами называется двусвязным. Каждый элемент такого списка имеет два поля с указателями: одно поле содержит ссылку на следующий элемент, другое поле – ссылку на предыдущий элемент и третье поле - информационное.
 |
 |
NULL NULL
HEAD TAIL
Рис 7.1. Двусвязный динамический список.
7.1.В данной работе использовались:
1. Заголовочные файлы: stdio.h, conio.h, string.h, alloc.h содержат средства для организации ввода вывода информации, работы с терминалом, обработки строк, динамического выделения памяти.
2. Глобальные переменные:
family – массив из 20 элементов типа char. Содержит информацию о фамилии.
year - массив из 4 элементов типа char. Содержит информацию о годе рождения.
*prev, *next, – указатели на предыдущую и следующую структуры.
*head, *tall – указатели на начало и конец списка.
Эти переменны являются элементами структуры spis:
struct spis
{ char family[20]; char year[5];
struct spis *prev; // на предыдущую структуру
struct spis *next; // на следующую
};
struct spis *head, *tail; // указатели на начало и конец списка.
3. Локальные переменные для :
Процедуры создания списка: *p, *pr – указатели на новую и предыдущую структуры.
Процедуры просмотра списка: *p- указатель на текущую структуру.
Процедуры сортировки: *p, *pn, *temp, - указатели на текущую, следующую, временную структуры. Указатель *temp содержит адрес наменьшей из двух сравниваемых по фамилии структур. Переменная "fl" типа int принимает значение -1- если в цикле найдена структура с фамилией меньшей чем текущая, если такая структура не найдена "fl" равен -0-.
Процедуры добавления новой структуры в конец списка: *p, *pn – указатели на текущую и новую структуры.
Процедуры меню: переменная "х" типа int возвращае значение введенное с клавиатуры для выбора пункта меню.
7.2. Описание процедур:
1) Создание списка - void build().
Очистка экрана - clrscr().
Вывод сообщения " *********** Создание списка ***********" – printf().
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.