Введение

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

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

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

1. Теоретическая часть

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

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

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

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

Логическая структура линейного односвязного списка:

Имя списка (идентификатор), тип элементов списка, указатель начала списка, указатель текущего элемента списка.

Логическая структура элемента линейного односвязного списка:

Данные или указатель на данные, указатель на следующий элемент списка.

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

связный список циклический логический

Рис.2. Выполнение операции включения элемента в линейный односвязный список.

Рис.3. Выполнение операции исключения элемента из линейного односвязного списка.

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

Рис.4. Кольцевой односвязный список. Логическая структура.

1.2 Двусвязный и двусвязный циклический списки

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

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

Линейность такого списка обеспечивается тем, что каждый из двух указателей в любом элементе списка, кроме крайних, задает линейный порядок элементов, обратный по отношению к порядку, устанавливаемому другим указателем (рис.6).

Рис.6. Линейность двусвязного списка.

Логическая структура линейного двусвязного списка:

Имя списка (идентификатор), тип элементов списка, указатель начала списка, указатель конца списка, указатель текущего элемента списка.

Логическая структура элемента линейного двусвязного списка:

Данные или указатель на данные, указатель на следующий элемент списка, указатель на предыдущий элемент списка.

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

Для получения из линейного двусвязного списка кольцевого двусвязного списка необходимо два пустых указателя заменить указателями противоположных концов списка (рис.8).

Рис.8. Кольцевой двусвязный список. Логическая структура.

2. Практическая часть

#ifndef LIST

#define LIST

#include <iostream.h>

template <class T> class List

{

struct Element {

T data;

Element *next; // указатель на следующий элемент списка

};

private:

Element *pHead; // указатель на первый элемент списка

Element *pPrev; // указатель на последний элемент списка

int countElem; // количество элементов в списке

public:

List()

{

pHead = 0;

pPrev = 0;

countElem = 0;

}

~List()

{

delAllList();

}

void add_front(T data)

{

Element *temp = new Element;

temp->next = pHead;

pHead = temp;

if(pPrev == 0){

pPrev = pHead;

}

pHead->data = data;

countElem++;

}

void add_back(T data)

{

Element *temp = new Element;

if(pHead == 0){

pHead = temp;

}

else{

pPrev->next = temp;

}

temp->data = data;

temp->next = NULL;

pPrev = temp;

countElem++;

}

friend ostream &operator << (ostream &print,List<T> &k)

{

Element *pTemp;

pTemp=k.pHead;

print<<"(";

while(pTemp != 0)

{

print << pTemp->data <<" ";

pTemp = pTemp->next;

}

print<<")"<<endl;

}

void delAllList()

{

while(pHead != NULL)

{

Element *pTemp = pHead;

pHead = pHead->next;

delete pTemp;

}

countElem=0;

}

bool IsEmpty()

{

if(countElem == 0){

return true;

}

else{

return false;

}

}

bool erase(T val)

{

Element* ptrPrev;

int i=0;

ptrPrev=new Element;

for(Element* ptr=pHead; ptr!=0; ptr=ptr->next)

{

if(ptr->data==val){

ptrPrev->next=ptr->next;

delete ptr;

countElem--;

i++;

break;

}

ptrPrev=ptr;

}

if(i==0)

return false;

else

return true;

};

bool find(T val)

{

for(Element* ptr=pHead; ptr!=0; ptr=ptr->next)

{

if(ptr->data=val)

return true;

}

return false;

}

};

//---------------------------------------------------------------------------

template <class T> class DoubleList

{

struct Elem{

T data;

Elem * next, * prev;

};

Elem* Head; // Голова

Elem* Tail; // Хвост

int Count;

public:

DoubleList()

{

Head = Tail = NULL;

Count = 0;

}

~DoubleList()

{

DelAll();

}

int GetCount()

{

return Count;

}

void DelAll()// Удалить весь список

{

while(Count != 0)

{

Del(1);

}

}

void Del(int pos) // Удаление элемента

{

int i = 1;

Elem * Del = Head;

while(i < pos)

{

Del = Del->next; // Доходим до элемента, который удаляется

i++;

}

Elem * PrevDel = Del->prev; // Доходим до элемента, который // предшествует удаляемому

Elem * AfterDel = Del->next; // Доходим до элемента, который // следует за удаляемым

if(PrevDel != 0 && Count != 1){ // Если удаляем не голову

PrevDel->next = AfterDel;

}

if(AfterDel != 0 && Count != 1){ // Если удаляем не хвост

AfterDel->prev = PrevDel;

}

if(pos == 1){ // Удаляются крайние?

Head = AfterDel;

}

if(pos == Count){

Tail = PrevDel;

delete Del; // Удаление элемента

Count--;

}

void Insert(int pos, T inf) // Вставка элемента,

{

if(pos == Count + 1) // Если вставка в конец списка

{

AddTail(inf);

}

else if(pos == 1){

AddHead(inf);

}

int i = 1;

Elem * Ins = Head; // Отсчитываем от головы n - 1 элементов

while(i < pos)

{

Ins = Ins->next; // Доходим до элемента, перед

// которым вставляемся

i++;

}

Elem * PrevIns = Ins->prev; // Доходим до элемента,

// который предшествует

Elem * temp = new Elem;

temp->data=inf;

if(PrevIns != 0 && Count != 1){// настройка связей

PrevIns->next = temp;

temp->next = Ins;

temp->prev = PrevIns;

Ins->prev = temp;

Count++;

}

void AddTail(T n) // Добавление в конец списка

{

Elem * temp = new Elem;

temp->next = 0; // Следующего нет

temp->data = n;

temp->prev = Tail; // Предыдущий - бывший хвост

if(Tail != 0){ // Если элементы есть

Tail->next = temp;

}

if(Count == 0){ // Если элемент первый, то

// он одновременно и голова и хвост

Head = Tail = temp;

}

else{

Tail = temp; // иначе новый элемент - хвостовой

}

Count++;

}

void AddHead(T n) // Добавление в начало списка

{

Elem * temp = new Elem;

temp->prev = 0; // Предыдущего нет

temp->data = n;

temp->next = Head; // Следующий - бывшая голова

if(Head != 0){ // Если элементы есть

Head->prev = temp;

}

if(Count == 0){ // Если элемент первый, то он одновременно

// и голова и хвост

Head = Tail = temp;

}

else{

Head = temp; // иначе новый элемент - головной

}

Count++;

}

friend ostream &operator << (ostream &print,DoubleList<T> &k)

{

Elem * temp;

temp=k.Head;

print << "( ";

while(temp->next != 0)

{

print << temp->data << ", ";

temp = temp->next;

}

print << temp->data << " )\n";

}

};

//---------------------------------------------------------------------------

template <class T> class CycleDoubleList

{

struct Element

{

T data;

Element *next;

Element *prev;

};

private:

Element *Head;

Element *Curr;

int length;

public:

CycleDoubleList()

{

Head =NULL;

Curr=NULL;

length=0;

}

~CycleDoubleList()

{

clear();

}

void init()// приведения списка к состоянию текущий

{ // элемент - первый не удаленный

Curr=Head; // устанавливаем текущий элемент на первый не удаленный

}

void push(T data) // добавляем новый элемент в список

{

Element *inserted;

inserted= new Element;

inserted->data=data;

if (!isNoEmpty()) // если список пуст

{

Head=inserted;

Curr=inserted;

Curr->next=inserted;

Curr->prev=inserted;

}

else // если список не пуст

{

inserted->next=Curr->next;

inserted->next->prev=inserted;

Curr->next=inserted

inserted->prev=Curr

}

length++;

Curr=inserted; // устанавливаем текущий указатель на добавленный

}

T pop()// извлекаем текущий элемент

{

T tag; // переменная под возвращаемое значение

if (!isNoEmpty()) return 0; // если список пуст вернуть "ложь"

Element *temp=Curr; // сохраняем указатель на текущий элемент

tag=temp->data;

if (length==1){ // если элемент единственный в списке

Head=NULL; // обнулить значение первого элемента

Curr=NULL; // обнулить значение текущего элемента

}

else{

Curr->next->prev=Curr->prev;

Curr->prev->next=Curr->next;

Curr=Curr->next;

}

if(temp==Head){ // если удаляемый элемент - первый добавленный

Head=Head->next; // перенаправить первый на следующий

}

length--;

delete temp;

return tag;

}

void delFromData(T adr) // находим и удаляем элемент

{ // содержащий переданные данные

if(isNoEmpty())

{

Element *tmp=Curr;

for(int i=0;i<length;i)

{

if(Curr->data==adr)

{

if(Curr==tmp){

tmp=tmp->next

pop(); // извлечь значение

}

next(); // перейти к следующему элементу

}

Curr=tmp;

}

}

}

friend ostream &operator << (ostream &print,CycleDoubleList<T> &k)

{

Element *tempCar;

tempCar=k.Head;

print<<"(";

for (int i=0;i<k.length;i++)

{

print <<tempCar->data <<" ";

tempCar=tempCar->next ;

}

print << ")"<<endl;

}

void clear()// очистить весь список

{

for(int i=0;i<length;){

pop(); // извлекаем текущий элемент

}

}

void next() // перейти к следующему элементу

{

if(isNoEmpty()){

Curr=Curr->next;

}

}

void prev() // перейти к предыдущему элементу

{

if(isNoEmpty()){

Curr=Curr->prev;

}

}

bool isNoEmpty()// проверка состояния списка (если список не пуст)

{

if (Curr==NULL ){

return 0;

}

else{

return 1;

}

}

};

//---------------------------------------------------------------------------

template <class T> class CycleList

{

struct nodes{

T data;

nodes* next;

};

private:

nodes* head; //начало списка.

nodes* position; //активная (текущая) запись.

int count;

public:

CycleList()

{

head = NULL;

count = 0;

go_first();

}

~CycleList()

{

free();

}

void insert(T data) //Вставляет запись за текущей.

{

nodes* new_node = new nodes;

new_node->data = data;

if(position != NULL){

new_node->next = position->next;

position->next = new_node;

}

else{

new_node->next = new_node;

position = head = new_node;

}

count++;

}

void del_next()//Удаляет запись за текущей.

{

if (position != NULL){

nodes* tmp = position->next;

position->next = position->next->next;

if(tmp == head) head = tmp->next;

delete tmp;

}

count--;

}

void go_next()//Переходит к следующей записи.

{

if (position != NULL)

position = position->next;

}

void go_first()//Переходит к первой записи.

{

position = head;

}

int size()//Возвращает количество элементов в списке.

{

return count;

}

void free()//удаляет все элементы, освобождает память

{

go_first();

while(head->next != head) del_next();

del_next();

}

bool isNoEmpty()

{

if (count==0)

return false;

else

return true;

}

friend ostream &operator << (ostream &print,CycleList<T> &k)

{

nodes *temp;

temp=k.head->next;

print<<"(";

for (int i=0;i<k.count;i++)

{

print <<temp->data <<" ";

temp=temp->next ;

}

print << ")"<<endl;

}

};

#endif

2.2 Листинг файла «List.cpp»

List <int> list;

int i;

const int n = 10;

int a[n] = {0,1,2,3,4,5,6,7,8,9};

printf("Class List: \n" );

for(i = 0; i < n; i++){

if(i % 2 == 0)

list.add_front(a[i]);

else

list.add_back(a[i]);

}

cout << list;

list.erase(5);

cout << list;

list.find(7);

printf("\n \n");

//---------------------------------------------------------------------------

DoubleList<int> L;

for(i = 0; i < n; i++){// Добавляем элементы, стоящие на четных индексах,

//в голову, на нечетных - в хвост

if(i % 2 == 0)

L.AddHead(a[i]);

else

L.AddTail(a[i]);

}

printf("Class DoubleList: \n \n");

cout << L;

L.Insert(5,3);

cout << L;

printf("\n \n");

//---------------------------------------------------------------------------

CycleDoubleList<int> M;

for(i = 0; i < n; i++)

M.push(a[i]);

printf("Class CycleDoubleList: \n");

cout<<M;

M.pop();

cout<<M;

printf("\n");

//---------------------------------------------------------------------------

CycleList<int> Cl;

for(i = 0; i < n; i++)

Cl.insert(a[i]);

printf("Class CycleList: \n \n");

cout<<Cl;

Cl.go_first();

Cl.del_next();

cout<<Cl;

getchar(); getchar();

return 0;

}

//---------------------------------------------------------------------------

Заключение

В данной курсовой работе были реализованы 4 вида списков. При изучении данной темы были полученные обширные теоретические и практические знания на тему динамических структур данных.

Список использованных источников и литературы

1. [Электронный ресурс] URL: http://algmet.narod.ru/theory_a4m/spiski/ (дата обращения 12.05.2013).

2. C/C++. Программирование на языке высокого уровня. Т.Ф. Павловская. -СПб.: Питер, 2003.- 114-119стр.

Приложение

Пример работы программы:

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