WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 11 | 12 || 14 | 15 |   ...   | 17 |

delete r;} elem iter::operator ++ ( ){ /* Возвращает указатель на текущий элемент списка. Осуществляет продвижение по списку. Запоминает новый текущий элемент списка.

*/ if ( current ) { elem * tmp = current;

current = current->next;

return tmp; } return NULL;

} void list::release ( ) { iter t ( *this );

elem *p;

while (( p = ++t )!= NULL ) {h = h->next; delete p;}} void list::print ( ) { iter t ( *this );

elem *p;

while (( p = ++t )!= NULL ) cout << p->data << “ “;

cout << ’\n’;

} // Конец файла list.cpp Здесь реализован односвязный список. Это одна из простых моделей структур управления данным. Класс list, реализующий эту модель, – представитель так называемых содержательных или контейнерных типов. Класс iter создан специально для перебора элементов произвольного списка типа list. Объекты, предназначенные для перебора элементов внутри некоторого набора данных, обычно называют итераторами.

Приведем пример использования односвязного списка.

В файле int.txt расположена непустая последовательность целых чисел A1, A2,,..., An. Определить количество этих чисел n и вывести их в порядке возрастания.

Для решения этой задачи будем строить список, элементы которого упорядочены по возрастанию содержащихся в них целых чисел. Построение выполняется за n шагов. Первый шаг – это создание списка, состоящего из одного элемента, который содержит А1. Очевидно, этот список упорядочен. На i-м шаге ( i = 2, 3, …, n ) переходим от упорядоченного списка, элементы которого содержат числа А1,..., Ai-1, к упорядоченному списку, элементы которого содержат A1,…, Ai-1, Ai. Для выполнения такого перехода достаточно включить в список новый элемент, содержащий Аi. Его надо вставить непосредственно за последним по порядку элементом, содержащим число, меньшее, чем Аi.

Если же все элементы исходного списка содержат числа, не меньшие, чем Ai, то новый элемент нужно вставить в начало списка.

#include “list.cpp“ #include < fstream.h > void main ( ) { ifstream file ( “int.txt” );

list lst; int i, n;

file >> i; n = 1;

lst.create ( i );

while ( file.peek ( )!= EOF ) { file >> i; n ++;

iter tmp ( lst ); // Создаем объект-итератор для перебора // элементов списка lst.

elem *p, *q;

while (( p = ++tmp)!= NULL ) if ( p->data < i ) q = p;

else break;

if ( p = = lst.first ( )) lst.create ( i );

else lst.insert ( q, i );} cout <<” В файле чисел: ” << n << “\n”;

cout <<” Упорядоченный список:\n”;

lst.print ( );

} В последнем операторе if – else делается проверка p = = lst.first ().

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

Его информационная часть обычно не используется.

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

struct elem{ ETYPE data;

elem * next;

elem * pred;

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

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

list h data data data NULL next...

NULL pred...

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

list h data data data...

...

Заглавный эл.

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

...

З. эл.

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

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

Рассмотрим основные операции с кольцевыми двунаправленными списками в первом варианте (рис. 7).

24.3. Операции над кольцевыми списками Вставка элемента Пусть h, p, q – переменные типа elem*, а k – переменная типа int.

Значение k нужно занести в информационную часть элемента, который должен быть вставлен после звена, на которое указывает указатель 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, т.е. снова будет указывать на первое звено (после заглавного).

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

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

25.1. Реализация стека через массив // Файл 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 = EMPTY; // Стек пуст.

} 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.empty ())cout<

cout <<’\n’;

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

Дядя Вася! !ясаВ ядяД Можно решить эту задачу и так:

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

stack s (str, 10);

while (!s.empty ()) cout <

25.2. Реализация стека через динамическую цепочку звеньев Пусть значением указателя, представляющего стек в целом, является адрес вершины стека. Как и в случае односвязного списка, каждое звено будет содержать указатель на следующей элемент, причем «дно» стека (т.е. элемент, занесенный в стек раньше всех) содержит указатель NULL.

// Файл stack.cpp typedef char ETYPE;

struct elem { ETYPE data;

elem* next;

elem (ETYPE d, elem* n){ data = d; next = n; } };

class stack { elem*h; // Адрес вершины стека.

public:

stack () {h = NULL;} // Создание пустого стека.

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





h = NULL;

for (int i = 0; i< len; i++) h = new elem (a[i], h);

} stack (stack & a){ // Инициализация стека другим стеком.

elem *p,*q;

p = a.h; q = NULL;

while (p) { q = new elem (p->data, q);

if (q->next = = NULL) h = q;

else q->next->next = q;

p = p->next;

} q->next = NULL;

} ~stack () {reset ();} void push (ETYPE c) { h = new elem (c, h); } // Поместить в стек.

ETYPE pop () { elem *q = h; ETYPE a = h->data; // Извлечь из стека.

h = h->next; delete q;

return a;

} ETYPE pop_show () {return h->data;} // Показать вершину.

void reset () { while (h ){ elem *q = h; h = h->next; delete q; } } int empty () { return h 0:1;} };

// Конец файла stack.cpp Приведем задачу, в решении которой удобно использовать стек.

В файле задана строка литер. Требуется проверить баланс скобок в этой строке.

Баланс соблюдается, если выполнено каждое из следующих условий:

1) Для каждой открывающей скобки справа от нее есть соответствующая закрывающая скобка. Наоборот, для каждой закрывающей скобки слева от нее есть соответствующая открывающая скобка.

2) Соответствующие пары скобок разных типов правильно вложены друг в друга.

Так в строке {[(a*b)+(n-4)]/[7-sin(x)]+exp(d)}*s баланс скобок соблюдается, а в строке [{a+b[i]((x-sin(x))]d)) – нет.

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

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

Обозначим через s – стек, sym – обрабатываемый символ, а через b – целую переменную, фиксирующую факт соответствия закрывающей скобки из строки с открывающей скобкой из вершины стека. Для проверки на соответствие закрывающей скобки, являющейся значением переменной sym, и открывающей скобки в вершине стека, опишем специальную функцию accord(), которая возвращает целое значение и удаляет открывающую скобку из стека.

# include # include # include “stack.cpp“ int accord (stack & s, char sym){ char r = s.pop ( );

switch (sym) { case ‘)’ : return r = = ‘(‘;

case ‘]’ : return r = = ‘[‘;

case ‘}’ : return r = = ‘{‘;

default : break;

} } void main ( ) { ifstream file ( “a.txt“ );

if ( !file ){ cout << “Ошибка при открытии файла a.txt!\n“; exit(1); } stack s;

char sym; int i, n, b = 1;

while ( file.peek () != EOF && b){ file >> sym; cout <

switch (sym){ case ‘(’ : case ‘[’ : case ‘{’ : s.push(sym); break;

case ‘)’ : case ‘]’ : case ‘}’ :

if ( s.empty () || !accord (s, sym)) b = 0; break;

} } if (!b || !s.empty ()) cout <<”\nБаланса скобок нет!\n”;

else cout <<”\nСкобки сбалансированы\n”;} 26. Двоичные деревья 26.1. Определение и построение Связанный граф, в котором нет циклов, называется деревом. Дерево называется ориентированным, если на каждом его ребре указано направление.

Двоичное дерево – это такое ориентированное дерево, в котором:

1) Имеется ровно одна вершина, в которую не входит ни одного ребра. Эта вершина называется корнем двоичного дерева.

2) В каждую вершину, кроме корня, входит одно ребро.

3) Из каждой вершины исходит не более двух ребер.

Будем изображать двоичные деревья так, чтобы корень располагался выше других вершин.

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

При решении некоторых задач бывает удобно представить наборы объектов в виде двоичных деревьев.

Рассмотрим задачу кодирования непустой последовательности целых чисел.

Пусть дана последовательность целых чисел а1, …, аn и функция целочисленного аргумента F(x), принимающая целые значения. Значение F(x) будем называть кодом числа x. Пусть требуется закодировать данные числа, т.е. вычислить значения F(a1),..., F(an), и пусть в последовательности a1,..., an имеются частые повторения значений элементов.

Чтобы избежать повторных вычислений одного и того же значения, следует по ходу кодирования строить таблицу уже найденных кодов. Организация этой таблицы должна быть такой, чтобы, во-первых, в ней довольно быстро можно было находить элементы с данным значением (или устанавливать факт отсутствия его в таблице), и, во-вторых, без особых затрат добавлять в таблицу новые элементы.

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

Pages:     | 1 |   ...   | 11 | 12 || 14 | 15 |   ...   | 17 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.