Материал: 7
//Создаемузелснулевымиссылкаминасебяслед.узел
public Node() { this(null, null); } //Создаетузелсзаданнымэлемеиссылкойследатом.узел.
public Node(E e, Node<E> n) { element = e; next = n; } // Методы геттеры:
public E getElement() { return element; } public Node<E> getNext() { return next; }
// Методы сеттеры:
public void setElement(E newElem) { element = newElem; } public void setNext(Node<E> newNext) { next = newNext; }
}
public class NodeStack<E> implements Stack<E> { protected Node<E> top; ссылканазаглавное// звено protected int size; количество//элементовстеке
//конструируемпустекой
public NodeStack() { top = null; size = 0;
}
public int size() { return size; } public boolean isEmpty() {
if (top == null) return true; return false; }
public void push(E elem) {
// создаем и привязывем новый узел
Node<E> v = new Node<E>(elem, top); top = v;
size++; }
public E top() throws EmptyStackException {
if (isEmpty()) throw new EmptyStackException("Stack is
empty.");
return top.getElement(); } public E pop() throws EmptyStackException {
if (isEmpty()) throw new EmptyStackException("Stack is
empty.");
E temp = top.getElement();
top = top.getNext(); // отделяем бывший верхним узел size--;
return temp; }
}
Каждый из методов интерфейса Stack требует постоянного времени. Сложность O (n), где n число элементов в стеке.
Нет проблемы с переполнением, как в массиве на основе стека.
Каждая открывающая скобка “(”, “{”, или “[” должна иметь закрывающую пару, в соответствии с ее типом “)”, “}”, или “[”
•правильно: ( )(( )){([( )])}
•правильно: (( )( )){([( )])}
•неправильно: )(( )){([( )])}
•неправильно: ({[ ])}
•неправильно: (
Алгоритм сопоставления скобок
Algorithm ParenMatch(X,n): |
|
n то,кеноваждыйизкоторых |
||||
{ |
Ввод: |
Какойлибомассив |
X из |
|||
являетсяибо |
симвскогруппирующим(лбоксимволом), |
|
|
|
||
переменная,арифметическийоператор,илисло |
|
|
|
|
||
Вывод: |
true- тогдаитолькотогда,когдавсегруппысимволов |
|
|
X |
||
соответствуют |
|
|
|
|
||
|
Let S be an empty stack; |
|
|
|
||
|
for ( i=0; i < n; i++) |
вающимгруппирующимсимволом) |
||||
|
if ( X[i]являетсяоткры |
|||||
|
|
S.push(X[i]); |
|
|
|
|
|
else if ( X[i]являетсязакрывающимгруппирующим |
|
||||
символом) |
|
{ |
|
|
|
|
|
|
|
|
|
|
|
|
|
if ( S.isEmpty() ) |
// ничнесоответствуетго |
|||
|
|
return false; |
|
|||
|
|
if ( S.pop()несоответствует |
X[i] ) |
|||
|
|
return false; |
|
// неправильный тип |
||
|
|
|
} |
|
|
|
|
if ( S.isEmpty() ) |
|
|
|
||
|
return true; |
// каждыйсимвсоответствуетл |
|
|||
|
else |
|
// некоторыесимволы |
соответствуют} |
||
|
return false; |
|||||
Пример: Сопоставление HTML тэгов
Для полностью корректного HTML, каждому тегу <name> должен соответствовать тег </name>.
<body>
<center>
<h1> The Little Boat </h1> </center>
<p> The storm tossed the little boat like a cheap sneaker in an old washing machine. The three drunken fishermen were used to such treatment, of course, but not the tree salesman, who even as a stowaway now felt that he
had overpaid for the voyage. </p> <ol>
<li> Will the salesman die? </li> <li> What color is the boat? </li>
<li> And what about Naomi? </li> </ol>
</body>
import java.io.*; |
|
|
import java.util.Scanner; |
|
|
import net.datastructures.*; |
- |
|
/**УпрощеннаяпроверкасоответстпарныхтегоHTMLвия |
|
|
документе. */ |
|
|
public class HTML { |
|
*/ |
/**выдпеиляемрвыйпоследнийсимволытег<>строке. |
||
public static String stripEnds(String t) { |
|
|
if (t.length() <= 2) return null; |
|
|
//это вырожденный тег |
|
|
return t.substring(1,t.length()-1); |
|
|
} |
аключеннаявтегистрокапустойили |
|
/**проверка,являетсяи |
|
|
этооткрывающийтег. |
*/ |
|
public static boolean isOpeningTag(String tag){ |
|
|
return (tag.length() == 0) || (tag.charAt(0) != '/'); |
|
|
} |
tag1соотвезакрывающийтствуетег |
tag2 |
/**проверка,еслитегу |
||
(первыйсимволунег |
о '/'). */ |
|
public static boolean areMatchingTags(String tag1, String tag2) {// проверка имени после'/'
return tag1.equals(tag2.substring(1));
} |
|
/**проверканато,чтокаждыйоткрывающийтегимеет |
*/ |
соответстзакрытег. ваующий |
public static boolean isHTMLMatched(String[] tag) { Stack<String> S = new NodeStack<String>();
// стек для соответствия тегов
for (int i = 0; (i < tag.length) && (tag[i] != null); i++) { //открывающийтег;то push егов стек
if (isOpeningTag(tag[i])) S.push(tag[i]); else { if (S.isEmpty()) return false;
//ничнесоответствуетго
if (!areMatchingTags(S.pop(), tag[i])) return false; //неправильноесоответствие
}
}
if (S.isEmpty()) return true;мыв//сравнилие
//унасетегить,которыенигднесовпали return false;
}
public final static int CAPACITY = 1000;
//размермассиватегов |
HTML документвмассив |
html тегов*/ |
/*Распарсим |
||
public static String[] parseHTML(Scanner s) { |
||
//нашмассивтеговизначально( |
null) |
|
String[] tag = new String[CAPACITY]; |
|
|
int count = 0; // счетчик тегов
String token; // токен, возвращаемый scanners
while (s.hasNextLine()) { //находим следующийтег
while ((token = s.findInLine("<[^>]*>")) != null) //выделимокончаниекаждоготега
tag[count++] = stripEnds(token); s.nextLine();перехок//слестрокедующейим
} |
массиввыя( )теговленных |
return tag;наш// |
}
public static void main(String[] args) throws IOException { //
тестер
if (isHTMLMatched(parseHTML(new Scanner(System.in)))) System.out.println("The input file is a matched HTML
document.");
else System.out.println("The input file is not a matched HTML document.");
}
}
Очереди
АТД Очередь (Queue) хранит произвольные объекты
Вставки и удаления происходят после по очереди вслед за первым, по схеме FIFO ( First inFirst out)
Элементы вставляются в конец очереди, а удаляются сначала Основные операции над очередью:
•enqueue(object): вставка элемента в конец очереди
•object dequeue(): удаляем и возвращаем элемент в передней части очереди, т. е,. с ее начала
Применение очередей
Непосредственное применение
•Листы ожидания, бюрократические процедуры
•Доступ к разделяемым ресурсам (например, принтер)
•Мультипрограммирование
Косвенное применение
•Вспомогательная структура данных для алгоритмов
•Как компонент других структур данных
Очередь на основе массива
Используем массив размера N по кругу
Две переменные отслеживают начало и конец очереди
•f индекс начала
•r индекс последнего элемента Далее индекса r массив пустой нормальная конфигурация
Развернутая конфигурация
Операции над очередью
Мы используем оператор деления по модулю (остаток от целочисленного деления).
Algorithm size()
{ return (N - f + r) mod N;} Algorithm isEmpty()
{ return (f = r); }
Операция включения в очередь генерирут исключение, если очередь заполнена, то есть массив полон. Это исключение зависит от конкретной реализации.
Algorithm enqueue(o)
{ if ( size() = N - 1)
throw FullQueueException;
else
{ Q[r] = o;
r = (r + 1) mod N ;
}
}