Связные списки
Федеральное агентство по
связи и информации РФ
ФГОБУ ВПО «Сибирский Государственный
университет телекоммуникаций и информатики»
Кафедра ТС и ВС
Курсовая работа по информатике на тему:
"Связные списки"
Выполнила:
Приняла:
Лебеденко Л.Ф.
г. Новосибирск
2012г.
Содержание
- Введение…………………………………………………………
…………2 - Теоретические сведения………………………………………………….. 3
- Создание многосвязного списка…………………………………………. 9
- Задание……………………………………………………………
.. 9 - Разработка алгоритма……………………………………………. 10
- Разработка программы и результаты выполнения……………...13
- Инструкция для пользователя…………………………………... 16
- Заключение ………………………………………………………………. 17
- Список используемой литературы……………………………………….18
1. Введение
C++ — компилируемый язык программирования общего назначения, сочетает свойства как высокоуровневых, так и низкоуровневых языков программирования. В сравнении с его предшественником — языком программирования C, — наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования. Название «язык программирования C++» происходит от языка программирования C, в котором унарный оператор ++ обозначает инкремент переменной.
Язык программирования C++ широко используется для разработки программного обеспечения. А именно, создание разнообразных прикладных программ, разработка операционных систем, драйверов устройств, а также видеоигр.
Не существует единственного самого лучшего способа создания программ. Для решения задач разного рода и уровня сложности требуется применять разные технологии программирования. Довольно часто можно встретить задачи, в которых количество элементов постоянно меняется, но при этом последовательность следования объектов должна оставаться неизменной. Но более жестким условием является непредсказуемость количества «объектов». В подобных случаях можно заказать массив размером, превышающий максимально возможный. Однако это неэффективно и могут возникнуть проблемы в других частях программы. Лучшим решением является организация списка. Организация многосвязного списка и является целью моей работы.
2. Теоретические сведения
Список представляет собой позиционно–ориентированную, линейную последовательность с доступом к элементам по номеру позиции или по значению. Элемент списка хранит значение объекта, включённого в список. Номера элементов в списке задаются в линейном порядке, начиная со значения 0 или 1. У списка есть первый и последний элементы. У всех остальных элементов есть единственный предшествующий элемент и последующий элемент. Идея связных списков состоит в представлении данных в виде объектов, связанных друг с другом указателями.
Здесь *prev и *next – указатели на предыдущий и следующий объекты соответственно; *head и *tail – указатели на первый и последний объекты; *current – указатель на текущий объект, с которым идет работа. Если предыдущего или последующего объекта не существует, то указатели *prev и *next принимают значение NULL. Указатели *head и *tail являются вспомогательными и служат для быстрого перемещения к первому и последнему объекту соответственно.
По числу связей и одновременно направлению списки бывают:
- односвязные (однонаправленные)
Ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла невозможно.
- двусвязные (двунаправленные)
Ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
- многосвязные
Многосвязные списки представляют собой динамические структуры данных, в основу которых положены 1- или 2-связные списки, в которых имеются дополнительные связи между звеньями. Чаще всего, такие связи проводятся между далеко отстоящими звеньями, например, обозначающими категории данных.
По способу организации связей списки могут быть:
- линейными
Линейный односвязный список является самым простым видом связных списков, к которому относятся односвязные и двусвязные списки.
- кольцевыми (циклическими).
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний. Реализация такой структуры происходит на базе линейного списка. В каждом кольцевом списке есть указатель на первый элемент. В этом списке константы NULL не существует.
Если список не является ни линейным, ни кольцевым, то остаётся единственный вариант – ветвящийся список, фактически являющийся одной из древовидных структур данных.
Для списков характерны следующие операции:
- добавление нового звена списка (вставка звена);
- удаление звена;
- просмотр (или прохождение) списка;
- поиск данных в списке;
- создание ведущего (заглавного) звена (при необходимости);
- сортировка списка;
- обращение (реверсирование) списка, т.е. перестановка всех его звеньев в обратном порядке.
Реализация операций над связными списками
Перебор элементов списка. Эта операция, возможно, чаще других выполняется над линейными списками. При ее выполнении осуществляется последовательный доступ к элементам списка - ко всем до конца списка или до нахождения искомого элемента.
1) Указатель текущего
элемента устанавливается на
начало списка.
2) Если указатель текущего элемента пустой
– конец перебора.
2) Обрабатывается информационная
часть текущего элемента, на который из
текущего элементата выбирается указатель
на следующий элемент, следующий элемент
становится текущим.
4) Повторяются децствия с п.2.
В двухсвязном списке возможен перебор как в прямом направлении (он выглядит точно так же, как и перебор в односвязном списке), так и в обратном.
В кольцевом списке окончание перебора должно происходить не по признаку последнего элемента - такой признак отсутствует, а по достижению элемента, с которого начался перебор.
Вставка элемента в список. Вставка элемента в середину односвязного списка реализуется следующим алгоритмом.
1) Выделяется память для нового элемента и записывается его информационная часть.
2) Значение указателя
next предшествующего элемента
3) В поле next предшествующего
элемента заносится адрес нового элемента.
Приведенные алгоритмы обеспечивают вставку
в середину списка, но не могут быть применены
для вставки в начало списка. При вставке
в начало списка должен модифицироваться
указатель на начало списка.
Удаление элемента из списка. При удалении элемента из односвязного достаточно значение из поля next удаляемого элемента перенести в поле next предыдущего элемента.
Перестановка элементов списка. Изменчивость динамических структур данных предполагает не только изменения размера структуры, но и изменения связей между элементами. Для связных структур изменение связей не требует пересылки данных в памяти, а только изменения указателей в элементах связной структуры. В качестве примера приведена перестановка двух соседних элементов списка. В алгоритме перестановки в односвязном списке исходили из того, что известен адрес элемента, предшествующего паре, в которой производится перестановка. В приведенном алгоритме также не учитывается случай перестановки первого и второго элементов.
1) В поле next 1-го элемента пары переносится значение из поля next 2-го элемента
2) В поле next 2-го элемента пары заносится адрес 1-го элемента
3) В поле next элемента, предшествующего паре, заносится адрес 2-го элемента
Копирование части списка. При копировании старый список сохраняется в памяти и создается новый список. Информационные поля элементов нового списка содержат те же данные, что и в элементах старого списка, но поля связок в новом списке совершенно другие, поскольку элементы нового списка расположены по другим адресам в памяти. Операция копирования предполагает дублирование данных в памяти.
Слияние двух списков. Операция слияния заключается в формировании из двух списков одного - она аналогична операции сцепления строк. В случае односвязного списка последний элемент первого списка содержит пустой указатель на следующий элемент, этот указатель служит признаком конца списка. Вместо этого пустого указатель в последний элемент первого списка заносится указатель на начало второго списка. Таким образом, второй список становится продолжением первого.
Достоинства связного представления данных:
- возможность обеспечения значительной изменчивости структур;
- размер структуры ограничивается только доступным объемом машинной памяти;
- при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей.
Вместе с тем связное представление не лишено и недостатков, основные из которых:
- работа с указателями требует, как правило, более высокой квалификации от программиста;
- на поля связок расходуется дополнительная память;
- доступ к элементам связной структуры может быть менее эффективным по времени.
- Создание многосвязного списка
3.1. Задание
3.1. Разработка алгоритма
Блок-схема алгоритма составления списка:
Блок-схема алгоритма составления интерфейса:
3.3. Разработка программы и результаты выполнения
#include "stdafx.h"
#include <conio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define st struct st
#define list struct list
//односвязный список
list
{ int info;
list*next;
};
//двусвязный список
st
{ st*left;
list*down;
st*right;
};
list*t1,*p1; //указатели на односвязный список
st *s,*t,*p; //указатели на двусвязный список
int _tmain(int argc, _TCHAR* argv[])
{setlocale(0,"Rus");
int a,n; //объявление переменных
char y,c; //объявление переменных
printf("Курсовая работа студентки группы А-14 Михайловой Кристины \n");
printf("->");
scanf("%d",&a); //считывание переменной а
n=1;
if(a==0) //если список пуст
printf("spisok pust:/n");
else //если список не пуст
{
while(a!=0)
{
//создание и заполнение двусвязного списка
t=new st;
t->left=0;
t->down=0;
t->right=0;
//создание и заполнение односвязного списка
t1=new list;
t1->info=a; //заполнение информационного поля
t1->next=NULL;
t->down=t1;
if(s==0)
s=t;
else
{
p->right=t;
t->left=p;
p1->next=t1;
}
scanf("%d",&a);n++;
p=t; p1=t1;
}
t->right=s; s->left=t; //связка
printf("перход направо клавишей 6\n");
printf("перход налево клавишей 4\n");
printf("перход вниз 2\n");
printf("по окончанию списка нажмите 1 \n");
printf("если вы хотите закончить нажмите любую клавишу\n");
//создание интерфейса
y='y';
while(y=='y')
{
printf("\n Vvod upravlenia:\n");
n=0; p=s; p1=0;
c=getch();
while(c!='1')
{
if(c=='2')//down(вниз)
{
if(n==0)
{
if(p->down!=0)
{
printf("Vniz:\n");
p1=p->down;
n=1;
printf ("| %d |",p1->info);
}
else
printf("Pusto down\n");
}
}
if(c=='6')//right(вправо)
{
if(n==0)
{
if(p->right!=0)
{
printf("Vpravo:\n");
p=p->right;
}
else
printf("Pusto right\n");
}
if (n==1)
{
if (p1->next!=NULL)
{
p1=p1->next;
printf ("| %d |",p1->info);
}
else
printf("Pusto right\n");
}
}
if(c=='4')//left(влево)
{
if(n==0)
{
if(p->left!=0)
{
printf("Vlevo:\n");
p=p->left;
}
else
printf("Pusto left\n");
}
}
c=getch();
}
printf(" Продолжать? (y/n)");
y=getch();
}
}
return 0;
}
Результат выполнения:
Программа отлажена в Microsoft Visual Studio 2008.
3.4. Инструкция пользователя
Запустите программу. Появится командная строка, в которую следует ввести любое количество чисел, в любой последовательности. Обязательное условие – ввод чисел должен заканчиваться нулем. После ввода нажать «Enter». Управление программой осуществляется при помощи кнопок на клавиатуре:
- Переход вправо – клавиша «6»
- Переход влево – клавиша «4»
- Переход вниз – клавиша «2»
Когда весь список будет пройден, на экран будет выведено сообщение «Pusto right». По окончанию списка нажмите на клавишу «1». Далее появится вопрос: «Продолжить?», в ответ на который для выхода из программы используйте клавишу «n», для продолжения – «у». Язык – английский.
4. Заключение
Сильная сторона списков заключается в том, что с их помощью можно без проблем добавлять и удалять элементы, что гораздо труднее делать с помощью массивов. Также можно без проблем изменить размер списков, добавив/удалив новые узлы.
У списков есть, конечно же, и слабые стороны. Получить доступ к какому-либо элементу не так просто. Необходимо пройти до этого элемента от начала списка, в то время как в массивах доступ к любому элементу можно получить с помощью индекса. Доступ к элементам списков происходит медленнее, чем к элементам массива, так как узлы списков хранятся в разных участках памяти. Кроме того, для хранения списков требуется больше памяти. В списках удобно хранить объекты больших сложных классов. Если имеется множество мелких объектов, будет эффективнее сохранить их в массиве.
В ходе выполнения курсовой работы были получены основы разработки многосвязных списков. Была изучена среда разработки Microsoft Visual Studio 2008. В результате работы была написана программа, которая строит списочную структуру, состоящую из кольцевого двунаправленного и однонаправленного списков, связанных между собой.
5. Список литературы
- Карпов Б., Баранов Т. «С++: специальный справочник» - СПб.: Питер, 2001. — 480 с.:ил.
- Культин Н. «С/С++ в задачах и примерах» - СПб.:БХВ-Петербург, 2002. — 288 с.
- Павловская Т.А. “С/с++. Программирование на языке высокого уровня. - СПб.: Лидер, 2010. — 461 с.:ил.
http://life-prog.ru/view_
http://saod.narod.ru/saod3/
http://shatalov.su/ru/
http://www.sernam.ru/c_44.php
http://ru.wikipedia.org/wiki/%