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

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

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

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

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

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

Тема работы

Вариант №

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

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

                                                                        группы ПДТ-73

                                                                        Кропоткин Е.А.

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

                                                                        Перцева В.А.

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

                                                                        «___» __________2007г.

                                                                                                                                                                                                    С оценкой «_______»

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

Содержание:

Задание           2

Введение           3

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

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

3. Проектный раздел                                                                   10

Приложения:

 Исходный модуль программы:                                                 11

 Результаты тестирования выполнения задания:            17

 Список литературы

Задание: 

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

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

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

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

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

          5. Выход.

          Пункт “корректировка списка” -  Удалить издания с годом меньше заданного.

          Структура содержит название книги, автора, год издания.

Введение

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

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

          Списки бывают замкнутые и разомкнутые которые могут быть односвязными и двусвязными.

          Разомкнутые списки – это такие списки, которые имеют начало и конец, т.е. есть элементы, у одного из которых нету предыдущего элемента списка а у другого нету следующего. Частный случай - если элемент один, то у него нет ни предыдущего, ни последующего элемента.

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

          Односвязные списки позволяют просматривать цепочку только в одном направлении, поэтому в зависимости от направления связи необходимо постоянно “помнить” первый или последний элемент а так же адрес текущего элемента списка. Для удаления элемента такого списка требуется просмотреть список с “головы” списка до удаляемого.

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

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

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

Исходя из задачи - разработать программу для создания и работы с двусвязным разомкнутым списком, требуется реализовать следующие операции:

- создание списка;

- добавление в конец списка новой структуры

- просмотр списка;

- корректировка списка;

          - выход

Кроме того, как промежуточные операции, потребуются:

- удаление текущего элемента;

- перемещение по списку вперёд

- перемещение по списку назад

Для начала, рассмотрим элементы списка – они содержат 3 блока данных: адрес предыдущего элемента, данные пользователя, адрес следующего элемента:

(P1, Data1, N1)

          P – адрес предыдущего элемента,

          N – адрес следующего элемента

          Data – данные пользователя

          Сразу после создания список содержит единственный элемент, поля P и N в котором содержат NULL для обозначения отсутствия предыдущего и следующего элемента.

          После добавления элемента первый элемент содержит адрес второго, а второй адрес первого:

(P1, Data1, N1)        (P2, Data2, N2)

                               NULL

Добавляя следующие элементы, получаем цепочку:

(P1, Data1, N1)        (P2, Data2, N2)        (P3, Data3, N3)       (P4, Data4, N4)

Теперь удалим элемент 2:

(P1, Data1, N1)        (P3, Data3, N3)       (P4, Data4, N4)

P1 и N4 содержат NULL

Для реализации поставленной задачи потребуются следующие операции:

- создание списка – требуется распределить память для первого элемента списка и задать всем полям начальные значения, адресам предыдущего и следующего элемента присвоить NULL;

- добавление в конец списка новой структуры – требуется пройти от текущего элемента в конец списка, признаком последнего элемента является поле N равное NULL;

- просмотр списка – перемещение на предыдущий или следующий элемент, в случае существования; также вывод всего списка на экран – переход на самый первый элемент, и вывод данных  каждого элемента списка на экран;

- корректировка списка – ввод данных в поля данных;

          - выход – завершение работы программы

- удаление текущего элемента – скорректировать адреса предыдущего и следующего элемента и освободить занятую элементом память;

- перемещение по списку вперёд – если есть следующий элемент, присвоить курсору адрес следующего элемента

- перемещение по списку назад - если есть предыдущий элемент, присвоить курсору адрес предыдущего элемента