Сортировка двусвязного динамического списка, структура которого содержит фамилию, год рождения

Страницы работы

Содержание работы

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

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

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

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

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

Тема работы

Сортировка двусвязного динамического списка

Вариант № 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. Блок-схема функционирования системы

Блок-схема: узел: 1Блок-схема: альтернативный процесс:  Начало
  6

 


Блок-схема: узел: 1Рис 6.1. Блок – схема работы "меню"


Рис 6.2. Блок – схема работы процедуры "Создание списка"

Рис 6.4. Блок – схема работы процедуры " Добавление в конец списка новой структуры "

 


Блок-схема: альтернативный процесс: Конец
     

Рис 6.3. Блок – схема работы процедуры "Просмотр списка"


Блок-схема: узел: 1                                                   Рис 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().

Похожие материалы

Информация о работе