Двунаправленные и кольцевые списки. Операции над ними.

Чтобы в списках был удобный способ доступа к предыдущим элементам, добавим в каждый элемент списка еще один указатель, значением которого будет адрес предыдущего звена списка:

struct elem{

ETYPE data;

elem * next;

elem * pred;

elem (ETYPE c, elem * n, elem * p){ data = c; next = n; pred = p; } };

С помощью элементов такого типа (рис. 6.) можно сформировать так называемый двунаправленный список (с заглавным элементом):

Рис. 6. Двунаправленный список

Здесь в поле pred заглавного звена содержится пустой указатель NULL, означающий, что у заглавного элемента нет предыдущего. Часто двунаправленные списки обобщают следующим образом (рис. 7, 8): в качестве значения next последнего звена принимают указатель на заглавное (или первое) звено, а в качестве значения поля pred заглавного (соответственно первого) звена - указатель на последнее звено:

Рис. 7. Первый вариант двунаправленного кольцевого списка

Рис. 8. Второй вариант двунаправленного кольцевого списка

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

В первом варианте (рис. 7) очень просто реализуется вставка нового звена как в начало списка (после заглавного звена, так и в его конец, т.к. вставка звена в конец списка эквивалентна его вставке перед заглавным элементом. Однако здесь при циклической обработке элементов придётся каждый раз проверять, не является ли очередное звено заглавным. Этого недостатка лишён второй вариант списка (рис. 8), но в этом случае труднее реализуется добавление в конец списка.
Операции.

Вставка элемента

 

Пусть h, p, q - переменные типа elem*, а k - переменная типа int, значение которой должно содержаться в информационной части элемента, который должен быть вставлен после звена, на которое указывает указатель p.

 

Эту вставку можно осуществить так:

 

q = new elem (k, p->next, p);

p->next->pred=q; p->next=q; // В таком порядке!

 

Для вставки нового элемента в начало списка достаточно, чтобы указатель p принял значение адреса заглавного элемента списка: p=h;

 

Удаление элемента

 

Возможность двигаться по указателям в любом направлении позволяет задавать исключаемое звено указателем p непосредственно на само это звено:

 

p->next->pred = p->pred;

p->pred->next = p->next;

delete p;

 

Поиск элемента

 

Пусть h - указатель на заглавный элемент списка, r - указатель, ко-торый будет указывать на найденное звено, содержащее k. Пусть также p, q - переменные типа elem*, b - типа int. Поиск элемента, содержащего число k, осуществляется так:

 

b=1; h->data = k+1; // В информационную часть заглавного звена

// заведомо занесём число, отличное от k.

p=h->next; // Сначала p указывает на первое звено.

r=NULL;

q=p; // q указывает на первое звено.

do {

if (p->data= =k){

b=0;

r=p;

}

p=p->next;

}while ((p!=q) && b);

 

Заметим, что если в списке вообще нет звена, содержащего k, то после поиска значение b останется равным единице, указатель r будет равен NULL, а p примет значение q, т.е. снова будет указывать на первое звено (после заглавного).

Стеки. Их реализация.

В программировании часто используется структура данных, которая называется очередью. Над очередью определены две операции - занесение элемента в очередь и выбор элемента из очереди. При этом выбранный элемент исключается из очереди. В очереди доступны две позиции - ее начало (из этой позиции выбирается элемент из очереди) и конец (в эту позицию помещается заносимый в очередь элемент). Различают два основных вида очередей, отличающихся по дисциплине обслуживания. При первой из дисциплин элемент, поступивший в очередь первым, выбирается первым и удаляется из очереди. Эту дисциплину обслуживания очереди принято называть FIFO (First In - First Out -> первый в очередь - первый из очереди).

 

Остановимся более подробно на очереди с такой дисциплиной обслуживания, при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним. Эту дисциплину обслуживания принято называть LIFO (Last In - Fist Out -> последний в очередь - первый из очереди). Очередь такого вида в программировании называют стеком или магазином. В стеке доступна единственная его позиция, называемая вершиной стека. Это позиция, в которой находится последний по времени поступления элемент. Отобразим стек на подходящую структуру данных языка С++.

 

Реализация стека через массив

 

// Файл stack0.cpp

typedef char ETYPE;

class stack {

enum {EMPTY = -1};

char *s;

int max_len;

int top;

public:

stack () {s = new ETYPE [100];

max_len = 100;

top = EMPLY; // Стек пуст.

}

stack (int size) {s = new ETYPE [size]; max_len = size;

top = EMPTY; }

stack (const ETYPE a [ ], int len){ // Инициализация массивом.

max_len = len;

s = new ETYPE [max_len];

for (int i = 0; i < max_len; i ++) s[i] = a[i];

top = max_len - 1;

}

stack (const stack & a) { // Инициализация стеком.

s = new ETYPE [a.max_len];

max_len = a.max_len; top = a.top;

for (int i = 0; i < max_len; i ++) s[i] = a.s[i];

}

~ stack () { delete s;}

void reset (){ top = EMPTY; } // Сброс стека в состояние ПУСТ.

void push (ETYPE c) { s [ ++ top ] = c; } // Занесение в стек.

ETYPE pop () { return (s [ top - - ]); } // Извлечение из стека.

ETYPE top_show () const { return (s [top]); }

/* Возвращает элемент из стека, фактически не извлекая его. Модификатор const гарантирует, что эта функция не будет менять данные-члены объектов типа stack */

int empty () const { return (top = = EMPTY); }

// Проверяет, пуст ли стек. Возвращает

// 1, если стек пуст, 0 - если не пуст.

int full () const { return (top = = max_len - 1); }

// Проверяет, есть ли в стеке еще место.

};

// Конец файла stack0.cpp

 

Теперь в программе могут появиться такие операторы:

 

stack data (1000); // Создание стека длиной 1000.

stack d[5] // Конструктор по умолчанию создает массив

// из 5 стеков по 100 элементов каждый.

stack w ("ABCD", 4); // w.s[0] = 'A'... s[3] = 'D'.

stack cop (w); // cop - копия стека w.

 

В качестве примера рассмотрим задачу вывода строки в обратном порядке.

 

# include

# include "stack.cpp"

 

void main (){

char str [ ] = "Дядя Вася!";

stack s;

int i = 0;

cout << str <<'\n';

while (str [ i ])

if (!s.full ()) s.push (str [ i++]);

else {cout << "Стек заполнен!" <<'\n'; break;}

while (!s.emply ())cout<< s.pop(); // Печать в обратном порядке.

cout <<'\n';

Дядя Вася! !ясаВ ядяД

}

 

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

 

Можно решить эту задачу и так:

 

char str [ ] = "Дядя Вася!"; int len = (sizeof str)/sizeof (ETYPE);

stack s (str, len); stack s (st, 10);

while (!s.emply ()) cout <<.pop; cout <<'\n';