Связные списки

Размещено на http://www.allbest.ru/

[Введите текст]

Федеральное агентство связи

Федеральное государственное бюджетное учреждение образовательное

высшего образования

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

информатики» (СибГУТИ)

Кафедра телекоммуникационных сетей и вычислительных средств (ТС и ВС)

Курсовая работа по информатике на тему:

"Связные списки"

Выполнил: Насирахунов И. М.

Проверила: Лебеденко Л.Ф.

г. Новосибирск 2017



Содержание

Введение

Теоретические сведения

Задание

Програмная реализация

Разработка программы и результаты выполнения

Инструкция для пользователя

Заключение

Список используемой литературы



Введение

C++ -- компилируемый язык программирования общего назначения, сочетает свойства как высокоуровневых, так и низкоуровневых языков программирования. В сравнении с его предшественником -- языком программирования C, -- наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования. Название «язык программирования C++» происходит от языка программирования C, в котором унарный оператор ++ обозначает инкремент переменной.

Язык программирования C++ широко используется для разработки программного обеспечения. А именно, создание разнообразных прикладных программ, разработка операционных систем, драйверов устройств, а также видеоигр.

Не существует единственного самого лучшего способа создания программ. Для решения задач разного рода и уровня сложности требуется применять разные технологии программирования. Довольно часто можно встретить задачи, в которых количество элементов постоянно меняется, но при этом последовательность следования объектов должна оставаться неизменной. Но более жестким условием является непредсказуемость количества «объектов». В подобных случаях можно заказать массив размером, превышающий максимально возможный. Однако это неэффективно и могут возникнуть проблемы в других частях программы. Лучшим решением является организация списка. Организация многосвязного списка и является целью моей работы.



Теоретические сведения

Список представляет собой позиционно-ориентированную, линейную последовательность с доступом к элементам по номеру позиции или по значению. Элемент списка хранит значение объекта, включённого в список. Номера элементов в списке задаются в линейном порядке, начиная со значения 0 или 1. У списка есть первый и последний элементы. У всех остальных элементов есть единственный предшествующий элемент и последующий элемент. Идея связных списков состоит в представлении данных в виде объектов, связанных друг с другом указателями.

S1 и S2 являются указателями начала двух разных односвязных списков, в которые одновременно входит каждый из пяти элементов, а P1 и P2 - обозначения связок в 1 и 2 односвязных списках соответственно. S1 и S2 являются компонентами двух разных дескрипторов односвязных списков. (Рисунок 1)

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

Ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла невозможно.

Двусвязный список может и не быть линейным, если второй указатель каждого элемента списка задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому первым указателем. Каждый элемент такого двухсвязного списка содержится в двух разных односвязных списках, как показано на рисунке 1:

Рисунок 1.

Ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно передвигаться в любом направлении -- как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.

Многосвязные списки представляют собой динамические структуры данных, в основу которых положены 1- или 2-связные списка, в которых имеются дополнительные связи между звеньями. Чаще всего, такие связи проводятся между далеко отстоящими звеньями, например, обозначающими категории данных. По способу организации связей с писки могут быть: линейными.

Линейный односвязный список является самым простым видом связных списков, к которому относятся односвязные и двусвязные списки.

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

Если список не является ни линейным, ни кольцевым, то остаётся единственный вариант - ветвящийся список, фактически являющийся одной из древовидных структур данных.

Для списков характерны следующие операции:

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

Реализация операций над связными списками

Перебор элементов списка. Эта операция, возможно, чаще других выполняется над линейными списками. При ее выполнении осуществляется последовательный доступ к элементам списка - ко всем до конца списка или до нахождения искомого элемента.

1) Указатель текущего элемента устанавливается на начало списка.

2) Если указатель текущего элемента пустой - конец перебора.

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

В двухсвязном списке возможен перебор как в прямом направлении (он выглядит точно так же, как и перебор в односвязном списке), так и в обратном.

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



Задание

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

а ₁ ,а₂ ,...,а _n,0,

в которой 0 отмечает конец ввода число N не вводится, а подсчитывается при вводе последовательности), а второе используется для связи элементов списка. Если N нечетно, то один из однонаправленных списков должен оказаться короче другого. Ссылочным полям, которые никуда не ведут, должно быть присвоено значение NIL. Ссылочная переменная S используется для доступа к списочной структуре.

Разработка алгоритма

Блок-схема алгоритма формирование двух списков:



Программная реализация

Создана структура для элемента однонаправленного списка List1, которая содержит следующие поля:

· Информационное поле

· Указатель на правый элемент

Создана структура для элемента трехнаправленного списка List3, которая содержит следующие поля:

· Указатель на верхний элемент

· Указатель на нижний элемент

· Указатель на правый элемент

Работа программы происходит по следующим этапам:

· Объявляем указатель s на начало списка. Сначала его обнуляем.

· Вызываем функцию InputList, которая создает списки и возвращает количество введенных элементов. Эта функция размещает элементы списка в динамической памяти, вводит числа (информационные поля элементов списка) с клавиатуры и настраивает связи между элементами списков.

· Вызываем функцию ViewList, которая позволяет просматривать списки. Эта функция при нажатии клавиши `2' позволяет из трехнаправленного списка перемещаться в нижний список, при нажатии клавиши `8' позволяет из трехнаправленного списка перемещаться в верхний список, а при нажатии клавиши `6' позволяет перемещаться вправо по трехнаправленному списку.

При всех перемещениях на экран выводится информация о текущем элементе списка.

Нажатие клавиши `0' - окончание просмотра.



Разработка программы и результаты выполнения

#include <iostream>

#include <stdio.h>

#include <conio.h>

using namespace std;

FILE *f; // Файл для вывода результатов

// Структура для однонаправленного списка

struct List1

{

int info; // Информационное поле

List1 *right; // Указатель на правый элемент

};

// Структура для трехнаправленного списка

struct List3

{

List1 *up; // Указатель на верхний элемент

List1 *down; // Указатель на нижний элемент

List3 *right; // Указатель на правый элемент

};

// Вводит список. Возвращает число n

int InputList(List3 **s)

{

List1 *t1 = 0; // Указатель на текущий элемент верхнего или нижнего списка

List3 *t3 = 0; // Указатель на текущий элемент трехнаправленного списка

List1 *p2 = 0; // Указатель на последний введенный элемент верхнего списка

List3 *p0 = 0; // Указатель на последний элемент трехнаправленного списка

List1 *p1 = 0; // Указатель на последний введенный элемент нижнего списка

int n = 0; // Количество элементов

int a; // Вводимое число

scanf("%d", &a);

fprintf(f, "%d ", a);

while (a != 0) {

n++;

t1 = (List1 *) malloc(sizeof(List1)); // Создаем новый элемент

t1->info = a;

t1->right = 0;

if (n % 2 == 1) { // Если вводим элемент нижнего списка

t3 = (List3 *) malloc(sizeof(List3)); // Создаем новый элемент

t3->up = 0;

t3->down = t1;

t3->right = 0;

}

if (n == 1) // Если вводим первый элемент

*s = t3;

if (n % 2 == 1) { // Если вводим элемент нижнего списка

if (n != 1) { // Если вводим не первый элемент

p1->right = t1;

p0->right = t3;

}

p1 = t1;

p0 = t3;

}

else { // Если вводим элемент верхнего списка

if (n != 2) // Если вводим не второй элемент

p2->right = t1;

p2 = t1;

p0->up = t1;

}

scanf("%d", &a);

fprintf(f, "%d ", a);

}

fprintf(f, "\n");

return n;

}

// Просматривает список

void ViewList(List3 *s)

{

List1 *t1 = 0; // Указатель на текущий элемент верхнего или нижнего списка

List3 *t3 = 0; // Указатель на текущий элемент трехнаправленного списка

char y = 'y';

char c;

while (y == 'y') {

printf("\nПросмотр списка ");

printf("(8 - Переход вверх, 2 - Переход вниз, 6 - Переход вправо, 0 - Конец просмотра):\n");

fprintf(f, "\nПросмотр списка ");

fprintf(f, "(8 - Переход вверх, 2 - Переход вниз, 6 - Переход вправо, 0 - Конец просмотра):\n");

t3 = s;

c = '?';

while (c != '8' && c != '2' && c != '0') {

if (c == '6') { // Если идем вправо

if (t3->right != 0) {

printf("Вправо ");

fprintf(f, "Вправо ");

t3 = t3->right;

}

else {

printf("Пусто справа ");

fprintf(f, "Пусто справа ");

}

}

c = getch(); // Ждем нажатия клавиши

while (c == '8' && t3->up == 0) {

printf("Пусто вверху ");

fprintf(f, "Пусто вверху ");

c = getch(); // Ждем нажатия клавиши

}

}

if (c == '8' || c == '2') { // Если идем вверх или вниз

if (c == '8') { // Если идем вверх

t1 = t3->up;

printf("\nВверх\n");

fprintf(f, "\nВверх\n");

}

else { // Если идем вниз

t1 = t3->down;

printf("\nВниз\n");

fprintf(f, "\nВниз\n");

}

printf("6 - Переход вправо, 0 - Конец просмотра):\n");

fprintf(f, "6 - Переход вправо, 0 - Конец просмотра):\n");

c = getch(); // Ждем нажатия клавиши

while (c != '0') {

if (c == '6') { // Если идем вправо

if (t1->right != 0) {

printf("%d Вправо ", t1->info);

fprintf(f, "%d Вправо ", t1->info);

t1 = t1->right;

}

else {

printf("%d Пусто справа ", t1->info);

fprintf(f, "%d Пусто справа ", t1->info);

}

}

c = getch(); // Ждем нажатия клавиши

}

}

printf("\nНовый просмотр? (y/n) ");

fprintf(f, "\nНовый просмотр? (y/n) ");

y = getch(); // Ждем нажатия клавиши

}

}

void main()

{

setlocale(LC_ALL, "russian"); // Русский шрифт

List3 *s = 0; // Указатель на первый элемент списка

f = fopen("results.txt", "w"); // Открываем файл results.txt для записи результатов

puts("Введите последовательность целых чисел, в которой 0 отмечает конец ввода:");

fprintf(f, "Последовательность целых чисел:\n");

int n = InputList(&s);

if (n < 1) {

puts("В последовательности должно быть хотя бы одно число. Нажмите любую клавишу для выхода");

fprintf(f, "В последовательности должно быть хотя бы одно число\n");

fclose(f); // Закрываем файл

getch(); // Ждем нажатия любой клавиши

return;

}

ViewList(s);

fclose(f); // Закрываем файл

}

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

Таким образом, видим, что информационные поля и связи внутри списков и между списками настроены правильно.

Программа отлажена в Microsoft Visual Studio 2008.



Инструкция пользователя

В начале выполнения программы надо ввести целочисленные элементы списка, завершая их вводом нуля. В списке должно быть не менее одного элемента.

Далее программа предлагает выполнить просмотр созданных списков. Для этого можно нажимать следующие клавиши:

· нажатие клавиши `2' позволяет из трехнаправленного списка перемещаться в нижний список.

· нажатие клавиши `8' позволяет из трехнаправленного списка перемещаться в верхний список.

· нажатие клавиши `6' позволяет перемещаться вправо по любому из трех списков.

· нажатие клавиши `0' - окончание просмотра.

При всех перемещениях по однонаправленным спискам на экран выводится информация о текущем элементе списка.



Заключение

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

У списков есть, конечно же, и слабые стороны. Получить доступ к какому-либо элементу не так просто. Необходимо пройти до этого элемента от начала списка, в то время как в массивах доступ к любому элементу можно получить с помощью индекса. Доступ к элементам списков происходит медленнее, чем к элементам массива, так как узлы списков хранятся в разных участках памяти. Кроме того, для хранения списков требуется больше памяти. В списках удобно хранить объекты больших сложных классов. Если имеется множество мелких объектов, будет эффективнее сохранить их в массиве.

В ходе выполнения курсовой работы были получены основы разработки многосвязных списков. Была изучена среда разработки Microsoft Visual Studio 2008. В результате работы была написана программа, которая строит списочную структуру, состоящую из кольцевого двунаправленного и однонаправленного списков, связанных между собой.



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

Карпов Б., Баранов Т. «С++: специальный справочник» - СПб.: Питер, 2001. -- 480 с.:ил.

Культин Н. «С/С++ в задачах и примерах» - СПб.:БХВ-Петербург, 2002. -- 288 с.

Павловская Т.А. “С/с++. Программирование на языке высокого уровня. - СПб.: Лидер, 2010. -- 461 с.:ил.

Размещено на Allbest.ru

...