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

Федеральное агентство по связи и информации РФ 
ФГОБУ ВПО «Сибирский Государственный университет телекоммуникаций и информатики»

 

Кафедра ТС и ВС

 

 

 

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

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

 

 

 

 

 

Выполнила:

                                                                                              

Приняла:

Лебеденко Л.Ф.

 

 

 

 

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

2012г.

Содержание

1. Введение……………………………………………………………………2
2. Теоретические сведения………………………………………………….. 3
3. Создание многосвязного списка…………………………………………. 9
1. Задание…………………………………………………………….. 9
2. Разработка алгоритма……………………………………………. 10
3. Разработка программы и результаты выполнения……………...13
4. Инструкция для пользователя…………………………………... 16
4. Заключение ………………………………………………………………. 17
5. Список используемой литературы……………………………………….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 предшествующего элемента переносится в поле next нового элемента.

3) В поле next предшествующего элемента заносится адрес нового элемента. 
Приведенные алгоритмы обеспечивают вставку в  середину списка, но не могут быть применены для вставки в начало списка.  При вставке в начало списка должен модифицироваться указатель на  начало  списка.

             Удаление элемента из списка. При удалении элемента из односвязного достаточно значение из поля next удаляемого элемента перенести в поле next предыдущего элемента.

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

1) В поле next 1-го элемента  пары переносится значение из поля next 2-го элемента

2) В поле next 2-го элемента  пары заносится адрес 1-го элемента

3) В поле next элемента, предшествующего  паре, заносится адрес 2-го элемента

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

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

             Достоинства связного представления данных:

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

             Вместе с тем связное представление не лишено и недостатков, основные из которых:

• работа с указателями требует, как правило, более высокой квалификации от программиста;
• на поля связок расходуется дополнительная память;
• доступ к элементам связной структуры может быть менее эффективным по времени.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Создание многосвязного списка

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");