Создание и обработка динамического списка на языке c++

1Постановка задачи Необходимо создать однонаправленный динамический список,, содержащий информацию о реках. Список должен состоять из 4 полей: 1 поле – название реки, 2 поле - длина реки, 3 поле – площадь реки, 4 поле количество притоков. Необходимо реализовать следующие действия со списком
§ Ввод динамического списка § Вывод списка § Обмен элементов (задаются номера элементов, которые нужно поменять местами) § Удаление последнего элемента в списке Программу построить по процедурному принципу. Пользовательский интерфейс реализовать в виде меню. 2 Разработка метода решения задачи и её формализация Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера. Работа с динамическими величинами связана с использованием ссылочного типа данных. Величины, имеющие ссылочный тип, называют указателями. Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти. Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом. Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. Из определения следует, что каждый элемент списка содержит поле данных (Inf ) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (Null) Рисунок 1 Здесь Inf — информационная часть звена списка (величина любого простого или структурированного типа, кроме файлового), Next — указатель на следующее звено списка; First — указатель на заглавное звено списка. Согласно определению, список располагается в динамически распределяемой памяти, в статической памяти хранится лишь указатель на заглавное звено. Структура, в отличие от массива, является действительно динамической: звенья создаются и удаляются по мере необходимости, в процессе выполнения программы. Однонаправленный список – это список, в котором указатель ссылается только на следующее звено списка (как показано на рисунке). 3 Разработка состава и структуры данных и результатов Поля исходных данных, программы, разрабатываемой в данной курсовой, будут иметь следующий вид: Таблица 1 Название Длина Площадь Притоки Название – название реки Длина – длина реки Площадь – площадь бассейна реки Притоки – количество притоков В таблице приведены используемые данные: Таблица 2 Обозначение Тип Назначение a Char (символьный) Название b Int целый тип Длина c Int целый тип Площадь d Int целый тип Притоки list_head Ссылочный тип Ссылка на начало списка Sheet Struct Структура Sheet new_sheet Struct Создание структуры Sheet first Ссылочный тип Меняемый элемент second Ссылочный тип Меняемый элемент cur Ссылочный тип Указатель s Тип Sheet Переменная menuc Char (символьный) Меню code Char (символьный) Переменная p1 Int целый тип Первая позиция p2 Int целый тип Вторая позиция Результатом выполнения программы является вывод на экран пунктов меню: · Запись – Ввод данных с клавиатуры. · Вывод– Вывод данных на экран в виде таблицы. · Обмен – Обмен элементов с заданными номерами.
· Удаление – Удаление последнего элемента в списке. · Выход – Выход. При выборе пункта меню выполняется соответствующее действие. 4Разработка алгоритма Алгоритм решения поставленной задачи мы будем разрабатывать по процедурному принципу. С реализацией меню. Он будет состоять из 4 функций, и главной программы объединяющей все функции.
§ Запись § Вывод § Обмен § Удаление § Выход § Главная часть Перемещение по меню будет реализовано с помощью клавиш (влево, вправо) Выбор каждого пункта меню производиться с помощью клавиши Enter 1) Запись В данной функции будет производиться ввод списка, а также последующее его добавление. При этом начнётся цикл создания динамического однонаправленного списка, создание первого элемента и последующих элементов в цикле. При создании каждого элемента, будет предложено заполнить привёдённые ниже поля данных: 1 Введите имя реки – название реки 2 Введите длину – длина реки 3 Введите площадь бассейна – площадь бассейна реки 4 Введите количество притоков – количество притоков После заполнения всех полей списка, программа выходит в меню предлагая пользователю выбор. 2) Вывод В данной функции реализуется вывод списка в виде таблицы. Выводиться шапка выходной таблицы. Затем с помощью цикла начинают просматриваться и выводиться элементы данного списка на экран. Все элементы начиная с первого помещая их в таблицу с разделами: Название, Длина, Площадь, Притоков. После вывода, программа просит нажатия « , для выхода в меню. 3) Обмен Здесь задаются элементы, которые нужно поменять местами друг с другом. Задаются элементы, которые нужно обменять. С помощью 1 цикла находим первый элемент и запоминаем его. С помощью второго цикла находим 2 элемент и запоминаем. Проверяем, что они не пустые, если они не пустые, то производим обмен, если пустые не обмениваем и выходим. 4) Удаление Функция реализует удаление последнего элемента в списке. Устанавливаем указатель на начало списка. Проверяем пустой ли список. Если он пустой, то пишем сообщение, что он пустой и выходим из функции. Если список не пустой, просматриваем весь список и находим предпоследний элемент, запоминаем. Если последний элемент не пустой, то мы его удаляем, и ставим указатель на 0. 5) Выход Выход. При выборе этого пункта меню происходит выход в систему, при этом все введенные данные будут потеряны. 6) Главная часть Реализует меню и «собирает все функции воедино». Создается меню с бесконечным циклом, которое позволяет выбирать функции для выполнения. Блок схема алгоритма приведена в Приложении 1. 5Выбор языка программирования Для реализации программы был выбран язык C++. Язык C++ - это универсальный язык программирования, для которого характерны экономичность выражения, современный поток управления и структуры данных, богатый набор операторов. Язык “C” не является ни языком “очень высокого уровня”, ни “большим” языком, и не предназначается для некоторой специальной области применения, но отсутствие ограничений и общность языка делают его более удобным и эффективным для многих задач, чем языки, предположительно более мощные. Ключевым понятием С++ является класс. Класс - это тип, определяемый пользователем. Классы обеспечивают сокрытие дан­ных, гарантированную инициализацию данных, неявное преобразо­вание типов для типов, определенных пользователем, динамичес­кое задание типа, контролируемое пользователем управление памятью и механизмы перегрузки операций. С++ предоставляет гораздо лучшие, чем в C, средства выражения модульности прог­раммы и проверки типов. В языке есть также усовершенствова­ния, не связанные непосредственно с классами, включающие в себя символические константы, inline-подстановку функций, па­раметры функции по умолчанию, перегруженные имена функций, операции управления свободной памятью и ссылочный тип. В С++ сохранены возможности языка C по работе с основными объектами аппаратного обеспечения (биты, байты, слова, адреса и т.п.). Это позволяет весьма эффективно реализовывать типы, определя­емые пользователем. С++ и его стандартные библиотеки спроектированы так, чтобы обеспечивать переносимость. Имеющаяся на текущий момент реализация языка будет идти в большинстве систем, поддержива­ющих C. Из С++ программ можно использовать C библиотеки, и с С++ можно использовать большую часть инструментальных средств, поддерживающих программирование на C. Также в С++ есть средство для работы с динамическими данными, что позволяет решить поставленную выше задачу. 6 Разработка программы Построение программы будем производить по процедурному принципу. Программа состоит из следующих процедур: 1) Главная часть – эта часть программы, которая выводит на экран все пункты меню, то есть организует пользовательский интерфейс, также она объединяет все процедуры используемые в программе. Она состоит из бесконечного цикла, который позволяет создать «вечное меню». При выборе пункта Выход, происходит выход и этого вечного цикла, и выход в систему. Результатом работы данной части программы является вывод на экран следующих пунктов меню: § Запись § Вывод § Обмен § Удаление § Выход Перемещение по меню реализуется с помощью клавиш (право, влево), а выбор производиться с помощью клавиши Enter. 2) Ввод – это процедура создания однонаправленного динамического списка, она требует заполнения четырёх полей списка. Заполнение происходит следующим образом: Вводиться сначала последовательно четыре поля, затем происходит выделение памяти для новых элементов и перемещение их в начало с помощью функции push_front. Причём при последующем вводе происходит добавление элементов в начало списка. 3) Вывод – эта процедура вывода созданного динамического списка. Вывод начинается с первого элемента и заканчивается последним элементом. Таблица заполняется данными введёнными после заполнения динамического списка, а также после его обработки. 4)Обмен – эта процедура меняет заданные элементы местами. Т.е. сначала задаётся первый номер элемента, затем второй номер. С помощью 1 цикла происходит поиск номера первого элемента, с помощью второго цикла происходит поиск 2 элемента. Затем происходит проверки на 0 элементов second и first и если они равны 0, обмена не происходит, иначе они обмениваются. После выполнения действия программа возвращается в меню. 5) Удаление – эта процедура удаляет последний элемент в динамическом списке. Сначала происходит установка указателя на начало. Затем проверяем пустой ли список. Если он пустой, то пишем сообщение, что список пуст и выходим из функции в меню. Если список не пустой, то начинаем просматривать весь список и находим предпоследний элемент, производим запоминание найдённого элемента. Если последний элемент не пустой, то мы его удаляем, и ставим указатель на 0. После завершения работы с функцией, программа производит выход в меню. 7 Отладка и тестирование
Отладка и тестирование проводились встроенными средствами интегрированной среды программирования, языка Borland C++ 5.02. После создания программы возникла необходимость исправить синтаксические и лексические ошибки. Нахождение ошибок осуществлялось попыткой запустить программу, при этом система показывала номер строки ошибки и выводила код данной ошибки. Исправление синтаксических и лексических ошибок осуществлялось при помощи пункта меню Debug, а также с помощью литературы, приведённой в разделе пояснительной записки 8. Список литературы. После исправления синтаксических ошибок, средствами Отладки, языка Borland C++ 5.02 .Производилась проверка всех путей алгоритма, посредством ввода разнообразных, тестирующих данных. После устранения всех ошибок и недочётов, программа стала отвечать требованиям задания курсового проекта. Дальнейшая отладка и тестирование программы на этом прекратилось.
Список Литературы 1) Язык Си++: Учеб. пособие.-5-е изд.- М.: Финансы и статистика, 2001.-560 с.: ил. 2) www.chelp.ru