А.А. Вылиток, Т.К. Матвеева - Динамические структуры данных. Задание практикума. Язык Паскаль (1113471), страница 6
Текст из файла (страница 6)
Описать процедуру in_order(L,x), которая в список Lупорядоченных по неубыванию целых чисел вставляет элемент x, сохраняяупорядоченность.Решениеprocedure in_order(var L:list; x:elemtype);{вставляет x в список L упорядоченных по неубыванию целыхчисел, сохраняя упорядоченность(elemtype=integer)}var p,q:link;begin{создать звено для хранения элемента}new(p);if L = nil then {вставка в пустой список}begin p↑.elem:= x;p↑.next:= nil;L:= pend- 32 -elsebegin q:=L; {поиск подходящего места для вставки}while (q↑.next< > nil) and (q↑.elem <= x)doq:=q↑.next;if q↑.elem <= x then {вставка в конец списка}beginp↑.elem:= x;p↑.next:= nil;q↑.next:= pendelse {вставка x перед q↑.elem}beginp↑.next:= q↑.next;q↑.next:= p;p↑.elem:= q↑.elem;q↑.elem:= xendendend;Задача 7.
Описать рекурсивную процедуру count(L,e),подсчитывает число вхождений элемента e в список L.котораяРешениеЕсли список пуст, то число вхождений элемента e в список L равнонулю. Для непустого списка нужно подсчитать, сколько вхождений имеется в«хвосте» списка, и прибавить единицу или ноль в зависимости от того,совпадает ли «голова» с элементом e.function count(L:list;e:elemtype):integer;{подсчитывает число вхождений элемента e в список L}beginif L = nil then count:=0else count:=count(L↑.next,e)+ord(L↑.elem=e)end;Задача 8. Описать рекурсивную функцию copy(L), которая строит копиюсписка L, возвращая ссылку на первое звено построенного списка или nil, еслиL пуст.Решениеfunction copy(L:list):list;{возвращает ссылку на копию списка L}var head:link;begin- 33 -if L = nil then copy:= nilelsebegin {создаем копию «головы» списка}new(head);head↑.elem:= L↑.elem;{к созданной «голове» присоединяемкопию «хвоста»}head↑.next:= copy(L↑.next)endend;Задача 9.
Используя стек (тип данных и операции над стеком считать ужеописанными), описать процедуру pairs(f) для решения следующей задачи. Втекстовом файле f находится последовательность символов, сбалансированнаяпо круглым скобкам. Требуется для каждой пары соответствующихоткрывающей и закрывающей скобок вывести на экран номера их позиций впоследовательности, упорядочив пары номеров в порядке возрастания номеровпозиций закрывающих скобок. Например, для текста A+(45-F(X)*(B-C))надо вывести: 8 10; 12 16; 3 17 .РешениеОпишем в процедуре переменную sym для хранения очередногосчитанного из файла f символа; переменную pos для хранения номера позициитекущего символа sym, и переменную S, представляющую стек, в которыйбудут помещаться номера позиций открывающих скобок.Алгоритм обработки последовательности таков.
Сначала счётчикпозиций pos устанавливаем в ноль, создаём пустой стек (с помощьюinit_stack(S)) и открываем файл f для чтения. Пока не конец файла,повторяем следующие действия:1) считываем в sym очередной символ и увеличиваем pos на единицу;2) еcли текущий символ – открывающая скобка, то номер его позициипомещаем в стек (c помощью push(S, pos));3) если текущий символ – закрывающая скобка, то это значит, что впеременной pos – номер позиции этой скобки, а на вершине стека –номер позиции соответствующей открывающей скобки; поэтомуберём элемент из стека, помещая его во вспомогательнуюпеременную i (с помощью pop(S,i)), и печатаем пару (i, pos).В нашем алгоритме нет проверки стека на переполнение.
Всбалансированном по скобкам тексте количество открывающих скобок неможет превосходить половину длины текста. Поэтому размер стека долженбыть не меньше, чем половина длины обрабатываемого текста, или входнойтекст должен иметь длину не более чем в два раза превосходящую размерстека.11Если стек представлен не массивом, а динамической цепочкой (см. задачу 10), то его размерзаранее не ограничен. Стек может расти, пока у Паскаль-машины хватает ресурсов для созданиянового динамического объекта – очередного звена стека.- 34 -В алгоритме также нет проверки стека на пустоту перед тем, как взятьэлемент из стека. Эта проверка не нужна, так как в сбалансированнойпоследовательности каждая открывающая скобка предшествует парной ейзакрывающей скобке. Следовательно, номер любой открывающей скобкиокажется в стеке раньше, чем произойдёт операция его извлечения на шаге (3).По достижении конца файла стек станет пустым, поскольку открывающих изакрывающих скобок в правильном входном тексте поровну.Изобразим на рисунке последовательность состояний переменных f,output, pos, sym, S при обработке текста A+(45-F(X)*(B-C)).
Файловыепеременные будем изображать в виде ленты, разделённой на ячейки. В однойячейке располагается одна компонента файла. Если файл открыт для чтения, тострелка, указывающая снизу на ячейку, отмечает компоненту, которая будетсчитана при очередном обращении к процедуре read. Если стрелка указываетна место за последней ячейкой, то чтение очередной компоненты невозможно,так как достигнут конец файла (функция eof в этой ситуации возвращаетзначение «истина»). Стек представим в виде горизонтальной трубки, открытой справого конца (вершина стека справа). Левый конец («дно» стека) отметимломаной линией, символизирующей «пружину» для выталкивания элементов изстека.Перед чтением первого символа из f значение переменной sym неопределено, pos=0, стек S и файл output пусты.1234567891011121314151617f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’↑symoutput0posS1234567891011121314151617f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’↑’A’1sympos1234567891011121314151617f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’↑sym- 35 -’+’pos21234567891011121314151617f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’↑S33pos’(’sym…1234567891011121314151617f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’↑S3123’(’sym84567891011128pos1314151617f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’↑S3123’X’sym84567891011129pos1314151617f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’↑S’)’sym310posoutput ’8’ ’9’ ’1’ ’0’ ’;’ ’9’1234567891011121314151617f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’↑- 36 -S3’(’sym1212pos…1234567891011121314151617f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’↑S’)’sym316posoutput ’8’ ’9’ ’1’ ’0’ ’;’ ’9’ ’1’ ’2’ ’9’ ’1’ ’6’ ’;’ ’9’1234567891011121314151617f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’↑Ssym’)’pos17output’8’ ’9’ ’1’ ’0’ ’;’ ’9’ ’1’ ’2’ ’9’ ’1’ ’6’ ’;’ ’9’ ’3’ ’9’ ’1’ ’7’ ’;’ ’9’После того, как входная последовательность обработана (т.е.
достигнут конецфайла f) стек S пуст, в файле output результат – номера позиций парныхскобок.Заметим, что текст может быть разбит на строки, т.е. кроме обычныхсимволов (типа char) может встречаться специальный символ – маркер концастроки. При чтении этого маркера значение переменной pos изменять ненужно, так он как не является «видимым» символом и не занимает отдельнуюпозицию в исходной последовательности. Пропустить маркер конца строки иперейти к следующей строке можно с помощью оператора readln(f).procedure pairs(f:text);{ печатает пары номеров позиций открывающих и закрывающихскобок из текста f в порядке возрастания номеров длязакрывающих скобок}var sym: char;pos,i: integer;S: stack;- 37 -begin reset(f);init_stack(S); pos:=0;if not eof(f) thenrepeatif eoln(f) then readln(f)elsebegin read(f,sym); pos:=pos+1;if sym = '(' then push(S, pos){номер позиции открывающей скобки в стек}else if sym = ')' then{номер позиции открывающей скобки,соответствующей данной закрывающей, взять изстека и напечатать пару номеров}begin pop(S,i);write(i,'9',pos,';9')end;end;until eof(f);writeln;end {pairs};Задача 10.
Программа на языке Турбо Паскаль. Программа запрашивает упользователя имя текстового файла, в котором находится последовательностьсимволов, сбалансированная по круглым скобкам, и выводит на экран номерапарных скобок как в задаче 9.РешениеОпишем в программе переменную name типа string и присвоим ейвведённое пользователем имя внешнего файла, в котором хранится исходныйтекст.
Опишем также переменную g типа text; c помощью процедуры assignсвяжем файловую переменную g с внешним файлом name. Чтобы напечататьпоследовательность номеров парных скобок, воспользуемся процедурой pairsиз задачи 9. Поскольку в pairs используется стек, мы должны реализовать внашей программе соответствующие структуру данных и операции, т.е. описатьтип stack и процедуры, необходимые для работы со стеком. Реализуем стек спомощью списка без заглавного звена.
Процедура init_stack(S)делаетсписок S пустым; push(S,e)вставляет в начало списка S элемент e – этооперация «положить элемент в стек»; pop(S,e) удаляет из списка S первыйэлемент и присваивает его переменной e – это операция «вытолкнуть (взять)элемент из стека». После того, как работа с файлом закончена, его следуетзакрыть обращением к процедуре close.program parantheses(input, output);type elemtype=integer;link=↑node;node=recordelem:elemtype;next:link- 38 -end;stack=link;procedurebeginS:=nilend;init_stack(var S:stack);procedure push(var S:stack; e:elemtype);var p:link;beginnew(p);p↑.elem:=e;p↑.next:=S;S:=pend;procedure pop(var S:stack; var e:elemtype);var p:link;beginp:=S;S:=S↑.next;e:=p↑.elem;dispose(p)end;procedure pairs(var f:text);var sym :char;pos,i:integer;S:stack;beginreset(f); pos:=0; init_stack(S);if not eof(f) thenrepeatif eoln(f) then readln(f)elsebegin read(f,sym); pos:=pos+1;ifsym='(' then push(S,pos)else if sym=')' thenbegin pop(S,i);write(i,'9 ',pos,';9');endenduntil eof(f);writelnend;- 39 -var name:string;g:text;beginwrite('Введите имя файла:9');readln(name);assign(g,name);pairs(g);close(g);end.Сделаем два замечания к данной программе.
Во-первых, в ней использованысредства языка Турбо Паскаль, которых нет в стандартном Паскале: assign,close, string. Во-вторых, программа будет корректно работать только сфайлами, сбалансированными по скобкам. Если баланса скобок нет, во времявыполнения может произойти ошибка, связанная с попыткой взять элемент изпустого стека. Примером файла, подходящего для обработки даннойпрограммой, является файл, содержащий её исходный текст.Задание практикума на ЭВМВ этом разделе приводятся варианты задания практикума на ЭВМ потеме «Динамические структуры данных».Постановка задачиДан текст, состоящий из непустой последовательности слов из латинскихбукв, разделённых запятыми, за последним словом – точка; каждое словосостоит не более, чем из 10 символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
