Ознакомление с процессом выполнения операции включения элемента в линейный односвязный список. Рассмотрение и анализ особенностей меню разрабатываемой программы. Исследование и характеристика результатов сравнения односвязного и двусвязного списков.
Аннотация к работе
C - компилируемый язык программирования общего назначения, сочетает свойства как высокоуровневых, так и низкоуровневых языков программирования. В сравнении с его предшественником - языком программирования C, - наибольшее внимание уделено поддержке объектно-ориентированного и обобщенного программирования. Название «язык программирования C » происходит от языка программирования C, в котором унарный оператор обозначает инкремент переменной.Связный список - структура, элементы которой имеют один и тот же формат и связаны друг с другом с помощью указателей, хранящихся в самих элементах. В односвязном списке каждый элемент состоит из двух различных по назначению полей: содержательного поля (поле данных) и служебного поля (поля указателя), где хранится адрес следующего элемента списка «рисунок 1». Поле указателя последнего элемента списка содержит нулевой указатель, свидетельствующий о конце списка. Линейность односвязного списка вытекает из линейной логической упорядоченности его элементов: для каждого элемента, за исключением первого и последнего, имеются единственный предыдущий и единственный последующий элементы. Односвязные списки всегда линейны, поэтому особое внимание следует уделить проблеме перестройки списка при его повреждении.Каждый элемент двусвязного списка содержит два указателя: указатель на следующий элемент, или прямой указатель, и указатель на предыдущий элемент, или обратный указатель «рисунок 5». Линейность такого списка обеспечивается тем, что каждый из двух указателей в любом элементе списка, кроме крайних, задает линейный порядок элементов, обратный по отношению к порядку, устанавливаемому другим указателем рисунок 6. Логическая структура линейного двусвязного списка: Имя списка (идентификатор), тип элементов списка, указатель начала списка, указатель конца списка, указатель текущего элемента списка. Логическая структура элемента линейного двусвязного списка: Данные или указатель на данные, указатель на следующий элемент списка, указатель на предыдущий элемент списка. Операции включения элемента в линейный двусвязный список и исключения элемента из линейного двусвязного списка реализуются аналогично соответствующим операциям над линейным односвязным списком.Разработать программу, реализующую алгоритм двусвязного, односвязного, двусвязного циклического, односвязного циклического списков (20 элементов). В качестве элемента списка выбрать структуру: Факультет I. Предусмотреть заполнение списка из файла (подготовить файл на 20 элементов). Предусмотреть многоуровневое меню: 1)Заполнение списка с начала а)с консоли (циклически) b)из файла 2)Вставка элемента (с консоли) в список а)в конец списка b)вслед за указанным элементом (по ключу)При выборе первого пункта меню вызывается функция enter, пользователю предоставляется выбор: заполнить список с консоли или считать из файла желаемое количество элементов рисунок 9. При выборе второго пункта меню вызывается функция insert1, пользователь вводит элемент с консоли и ему предоставляется выбор: добавить его в конец списка или по ключу рисунок 10. При выборе третьего пункта меню вызывается функция insert2, элемент считывается их файла и пользователю предоставляется выбор: добавить в конец списка или по ключу рисунок 11. При выборе четвертого пункта меню вызывается функция delet, пользователю предоставляется выбор: удалить элемент по ключу или из конца списка рисунок 12. При выборе пятого пункта меню вызывается функция clean, пользователю предоставляется выбор: отчистить список безвозвратно или с сохранением в файл рисунок13.Блок-схема программы смотреть рисунок 16, рисунок 17.Каждый узел ОЛС содержит 1 поле указателя на следующий узел. Каждый узел ОЦС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит адрес первого узла (корня списка). Каждый узел ДЛС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на предыдущий узел первого узла (корня списка) также содержит нулевое значение (указывает на NULL).
План
Оглавление
Реферат
Введение
1. Теоретическая часть
1.1 Односвязный и односвязный циклический списки
1.2 Двусвязный и двусвязный циклический списки
2. Практическая часть
2.1 Описание программы
2.2 Блок-схема программы
Заключение
Список литературы
Приложение
Введение
C - компилируемый язык программирования общего назначения, сочетает свойства как высокоуровневых, так и низкоуровневых языков программирования. В сравнении с его предшественником - языком программирования C, - наибольшее внимание уделено поддержке объектно-ориентированного и обобщенного программирования. Название «язык программирования C » происходит от языка программирования C, в котором унарный оператор обозначает инкремент переменной.
Не существует единственного самого лучшего способа создания программ. Для решения задач разного рода и уровня сложности требуется применять разные технологии программирования. Довольно часто можно встретить задачи, в которых количество элементов постоянно меняется, но при этом последовательность следования объектов должна оставаться неизменной. Но более жестким условием является непредсказуемость количества «объектов». В подобных случаях можно заказать массив размером, превышающий максимально возможный. Однако это неэффективно и могут возникнуть проблемы в других частях программы. Лучшим решением является организация списков. Организация односвязного, двусвязного, односвязного циклического и двусвязного циклического списков и является целью моей работы.
Вывод
В данной курсовой работе были реализованы 4 вида списков. При изучении данной темы были полученные обширные теоретические и практические знания на тему динамических структур данных.
Если сравнивать односвязный линейный и односвязный циклический списки, то: Односвязный линейный список (ОЛС). Каждый узел ОЛС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).
Односвязный циклический список (ОЦС). Каждый узел ОЦС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит адрес первого узла (корня списка).
Если сравнивать двусвязный линейный и двусвязный циклический списки, то: Двусвязный линейный список (ДЛС). Каждый узел ДЛС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит нулевое значение (указывает на NULL). Поле указателя на предыдущий узел первого узла (корня списка) также содержит нулевое значение (указывает на NULL).
Двусвязный циклический список (ДЦС). Каждый узел ДЦС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит адрес первого узла (корня списка). Поле указателя на предыдущий узел первого узла (корня списка) содержит адрес последнего узла.
Сравнивание односвязного и двусвязного списков: Линейный список представляет собой набор элементов (узлов), соединенных в цепочку. Обычно элемент представляет собой запись, которая содержит поле - указатель на следующий элемент.
Двусвязный список мало чем отличается от односвязного, но у него появляется еще одна компонента, в которой хранится адрес предыдущего элемента.
Список литературы
1. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. - М.: Наука, 2005 г.
2. Березин Б.И., Березин С.Б. Начальный курс С и C . - М.: ДИАЛОГ-МИФИ, 2007г.
4. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. - М.: Мир, 2003.
5. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 2007.
6. Гладков В. П. Задачи по информатике на вступительном экзамене в вуз и их решения: Учебное пособие. - Пермь: Перм. техн. ун-т, 2011.
7. Гладков В. П. Курс лабораторных работ по программированию: Учебное пособие для специальностей электротехнического факультета ПГТУ. Пермь: Перм. техн. ун-т, 2013.
8. Грогоно П. Программирование на языке Паскаль. -М.: Мир, 2009.
9. Дагене В.А., Григас Г. К., Аугутис К.Ф. 100 задач по программированию. - М.: Просвещение, 2002.
10. Епашников A.M., Епашников В.А. Программирование в среде Турбо Паскаль 7.0. - М.: МИФИ, 2004.
11. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Основы информатики и вычислительной техники. - М.: Просвещение, 2001.