В линейном двусвязном списке продвижение возможно в любом из двух направлений по цепочке элементов. Каждый элемент двусвязного списка содержит два указателя: указатель на следующий элемент, или прямой указатель, и указатель на предыдущий элемент, или обратный указатель (рис.5). У первого элемента двусвязного списка обратный указатель пустой, а у последнего элемента двусвязного списка – прямой указатель.
Рис.5. Линейный двусвязный список. Логическая структура.
Линейность такого списка обеспечивается тем, что каждый из двух указателей в любом элементе списка, кроме крайних, задает линейный порядок элементов, обратный по отношению к порядку, устанавливаемому другим указателем (рис.6).
Рис.6. Линейность двусвязного списка.
Логическая структура линейного двусвязного списка:
Имя списка (идентификатор), тип элементов списка, указатель начала списка, указатель конца списка, указатель текущего элемента списка.
Логическая структура элемента линейного двусвязного списка:
Данные или указатель на данные, указатель на следующий элемент списка, указатель на предыдущий элемент списка.
Продвижение в линейном двусвязном списке возможно в любом направлении. Операции включения элемента в линейный двусвязный список и исключения элемента из линейного двусвязного списка реализуются аналогично соответствующим операциям над линейным односвязным списком. Результат выполнения операций включения элемента в линейный двусвязный список и исключения элемента из линейного двусвязного списка – линейный двусвязный список.
Для получения из линейного двусвязного списка кольцевого двусвязного списка необходимо два пустых указателя заменить указателями противоположных концов списка (рис.8).
Рис.8. Кольцевой двусвязный список. Логическая структура.
Практическая часть
2.1 Листинг заголовочного файла “List.h”
#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”
//---------------------------------------------------------------------------
#pragma hdrstop
#include "List.h"
#include <stdio.h>
//---------------------------------------------------------------------------
#pragma argsused
int main(int argc, char* argv[])
{
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 вида списков. При изучении данной темы были полученные обширные теоретические и практические знания на тему динамических структур данных.