Разработка программы на языке С++, реализующей создание и выведение на экран связных списков

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

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

ФГОБУ ВПО СибГУТИ

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

Курсовая работа

по курсу «Информатика»

Выполнил: Томилов Сергей

Группа: АС-25

Проверила: Парначева Тамара Ивановна

Новосибирск 2013 год

Введение

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

С++ как приемник языка С широко используется в системном программировании. На нем можно писать высокоэффективные программы, в том числе операционные системы, драйверы и т.п.

Обработка сложных структур данных - текста, бизнес информации, Internet-страниц и т.п. - одна из наиболее распространенных возможностей применения языка. И в настоящее время С++ является одним из самых распространенных языков программирования в мире.

Цель моей курсовой работы - написать программу на С++ реализующую создание и выведение на экран связных списков.

ЗАДАНИЕ

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

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



Рисунок 1. Пример связного списка

У последней записи на рисунке отсутствует ссылка, но она есть и указывает на NULL. На основе списков можно реализовать структуры данных, такие как стеки, очереди и ассоциативные массивы.

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

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

Связные списки стали применяться и при разработке операционных систем, например, для реализации файловых систем. Так, для операционной системы TSS/360 компания IBM разработала двойные связные списки и утилиту на их основе для исправления ошибок в файловой системе. Если при сканировании каталога обнаруживался поврежденный элемент, то происходил откат с заменой поврежденного элемента на его предыдущую версию. Основные правила реализации связных списков.

Список состоит из элементов, называемых узлами (node). Первый узел списка называется «головным» (head), а последний - «хвостовым» (tail). На рисунке 2 изображен двойной связный список.

Рисунок 2. Двойной связный список

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

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

Еще один негативный момент при использовании связных списков связан с нерациональным использованием памяти. Если в узле хранится небольшая порция данных, например, булевское значение, то список становится неэффективными из-за того, что объем памяти, выделяемой под хранение связей, превышает объем памяти, выделяемой под хранение «полезной нагрузки». Для решения этой проблемы существуют развернутые связные списки - unrolled linked list, каждый элемент которого включает целый массив данных. Пример такого списка приведен в листинге 1.

Листинг 1. Развернутый связный список

record node

{

node next;

int numElements;

array elements;

}

Связный список - это рекурсивная структура, так как узел всегда содержит указатель на следующий узел. Это позволяет использовать простой рекурсивный алгоритм для таких операций, как объединение двух списков или изменение порядка элементов на обратный. У односвязных списков есть важное преимущество: если к вершине такого списка добавляется новый элемент, то старый список будет по прежнему доступен по ссылке на только что добавленный узел. Этот прием называется persistent data structure (постоянное хранение данных). У двусвязных списков есть свои преимущества, так как они позволяют выполнять итерацию в обоих направлениях, в отличие от односвязных списков.

Если последний элемент будет указывать на первый элемент списка, то такая структура называется циклическим замкнутым (или кольцевым (circular)) списком. Кольцевые списки можно использовать для списка процессов, в которых применяется «карусельный» (round-robin) алгоритм. Для такого списка достаточно иметь один указатель, который одновременно указывает и на конец, и на начало очереди. Кольцевой список можно разбить на два кольцевых списка или, наоборот, объединить.



Рисунок 3. Кольцевой связный список

Блок-схема реализуемого алгоритма

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

язык программирование связный список

Содержание файла stdafx.h

#pragma once

#include "targetver.h"

#include <stdio.h>

#include <tchar.h>

#include <iostream>

#include <conio.h>

Содержание файла code.cpp

// code.cpp : Defines the entry point for the console application.

//ВАРИАНТ 16

#include "stdafx.h"

using namespace std;

struct sp {

int key;

sp* next;

};

struct sp1 {

sp1* next;

sp* unten;

sp1* links;

};

int _tmain(int argc, _TCHAR* argv[])

{

int n,i;

int *mass = new int[] ;

n=1;

i=0;

cout<<"Geben Sie die Informationen ein und klicken Enter"<<endl;

while (n!=0)

{

cin>>n;

mass[i]=n;

i++;

}

i--;

sp1 *s; //Указатель на начало списка

sp *p;

sp1 *w;

p=new sp;

p->key=mass[0];

p->next=NULL;

s=new sp1; //Указатель на начало списка

s->links=NULL;

s->next=NULL;

s->unten=p;

w=s;

int j;sp *q; sp1 *w1;

for (j=1;j<i;j++)

{

q=new sp;

q->next=NULL;

q->key=mass[j];

w1=new sp1;

p->next=q;

p=p->next;

w1->next=NULL;

w1->unten=p;

w1->links=w;

w->next=w1;

w=w->next;

}

cout<<endl;

w=s;

cout<<" Verwenden Sie die Tasten, um nach links, rechts und unten "<<endl;

int f=0;

while ((f!=1)&&(w!=NULL)){

getch();

n=getch();

switch(n){

case 80:{q=w->unten;f=1;cout<<" unten ";break;}// Вниз

case 77:{w=w->next;cout<<" -> ";break;} // Вправо

case 75:{w=w->links;cout<<" <- ";break;}} // Влево

}

if(w!=NULL){

while (q!=NULL)

{cout<<q->key<<" ";

getch();

n=getch();

switch(n){

case 77:{q=q->next;cout<<" -> ";break;} // Вправо

}

}}

system("PAUSE");

return 0;

}

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

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

После запуска программы, в появившемся окне, следует ввести последовательность положительных целых чисел заканчивающихся нулем ( например «1 2 4…12 0» ).

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

Вывод

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

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

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

2. Герберт Шилдт самоучитель «С++ для начинающих» ППП «типография«Наука» 121099, Москва, Шубинский пер., 6, 2011.

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

...