Динамический стек

Do

Else

Else

head = p.next;

}

Если последний элемент линейного списка связать с первым посредством указателя Next, то получится кольцевойодносвязный список, как показано на рис. 8.11.

Рис. 8.11. Односвязный кольцевой список

Для создания двусвязного кольцевогосписка необходимо связать последний элемент с первым как по указателю Next, так и по указателю Pred. Двусвязный кольцевой список показан на рис. 8.12.

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

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

В качестве примера использования двусвязного кольцевого списка решим следующую задачу. Дети стали в круг, взявшись за руки. Начав отсчет от первого, каждый i-тый выходит из круга, а круг смыкается. Кто останется?

Первая часть задачи — создание списка. Процедура Insert2 вставляет элемент в двусвязный список.

Листинг 8.20. Процедура Insert2 вставляет элемент в двусвязный список

public void Insert2(MyNode2 p, int e)

// вставка элемента в двусвязный список

{ // список пуст, создание первого элемента

if (head == null)

{

head = new MyNode2(e, null, null);

head.next = head;

head.pred = head; // ссылки замыкаем на себя

}

{

MyNode2 t = new MyNode2(e, head.next, head);

head.next.pred = t; head.next = t;

}

}

Вызвав эту процедуру K раз, получим список, содержащий K элементов. Указатель списка стоит на первом включенном в список элементе.

Вторая часть задачи – удаление i-того элемента, считая от первого. Алгоритм прост: отсчитывается заданное количество элементов, требуемый элемент удаляется, указатель на список переносится на следующий за удаленным элемент. Когда в списке останется только один элемент, его поля Pred и Next будут указывать на него самого. Метод CountDel реализует этот алгоритм.

Листинг 8.21. Удаление элемента

public MyNode2 CountDel(MyNode2 p, int step)

{

MyNode2 r = p;

{

for (int i=1; i <= step; i++)

r = r.next;

MyNode2 t = r.pred; // этот элемент будем удалять

t.pred.next = r; r.pred = t.pred; // замыкаем круг

}

while (r == r.next);

return r;

}

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

Стек реализован в виде класса, поля и методы которого представлены в листинге 8.22.

Листинг 8.22. Класс стека, реализованный динамически

class MyStack

{

Node top;

public void Push(object data) // положить в стек

public object Pop() // взять из стека

public bool IsEmpty() // проверка на пустоту

class Node // узел

}

Развернутый вариант кода класса:

Листинг 8.23. Класс стека, реализованный динамически

namespace SpaceStack

{

class MyStack

{

Node top;

public void Push(object data)

//положить в стек

{

top = new Node(top, data);

}

public object Pop() // взять из стека

{

if (top == null) throw new

InvalidOperationException();

object result = top.data;

top = top.next;

return result;

}

public bool isEmpty() // проверка на пустоту

{

return top == null;

}

class Node // узел

{

public Node next;

public object data;

// конструктор

public Node(Node next, object data)

{

this.next = next;

this.data = data;

}

}

}

}

Следует обратить внимание на то, что метод Pop() — извлечения элемента из стека — внутри себя не делает проверки на пустоту стека. Дело в том, что эта метод должна вызываться только в том случае, когда заранее известно, что стек не пуст. В том случае, когда проверкой (метод IsEmpty) установлено, что стек пуст, решение о дальнейших действиях должно приниматься в вызывающем контексте.

В примере объявляется класс MyStack, принадлежащий пространству имен SpaceStack. Полное имя этого класса — SpaceStack.Stack. Этот класс содержит несколько членов: поле top, два метода Push и Pop, а также вложенный класс Node. Класс Node в свою очередь содержит три члена: поля next и data, а также конструктор. Если исходный код примера хранится в файле MyStack.cs, команда

csc /t:library MyStack.cs

компилирует текст в виде библиотеки, если код не имеет метода Main() и создает сборку с именем MyStack.dll.

В программе C# возможность обращения к открытым типам и членам, содержащимся в конкретной сборке, реализуется посредством ссылки на эту сборку во время компиляции программы. Если в программе используется класс SpaceStack.MyStack, содержащийся в сборке MyStack.dll , то можно решить следующую задачу.

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

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

Примечание. Не составит труда, изменив тип информационного поля на string, добавить еще несколько видов скобок, например, операторные скобки begin и end.

Ошибки, которые могут встретиться при расстановке скобок:

· несоответствие открывающей и закрывающей скобок, например: {a×[b+c)};

· непарные скобки, то есть открывающих скобок больше, чем закрывающих (или наоборот).

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

Метод BracketTest, приведенная в листинге 8.24, реализует этот алгоритм и возвращает значения:

· –1, если скобки расставлены правильно;

· 0, если не хватает закрывающих скобок;

· номер позиции в строке, на которой стоит "неправильная" скобка.

Листинг 8.24. Проверка скобок в арифметическом выражении

static int BracketTest(string a)

{

char[] begBracket = { '(', '[', '{' };

char[] endBracket = { ')', ']', '}' };

MyStack myStack = new MyStack();

int lenA = a.Length;

bool error = false;

int result = -1;

int i = -1;

Дата добавления: 2014-03-11; просмотров: 492; Нарушение авторских прав

Мы поможем в написании ваших работ!