В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 58
Текст из файла (страница 58)
Найти значение серединного элемента.2.1. Присвоить компонентам массива типа real в качестве значений последовательные элементы исходного файла с именем Вещфайл.2.2. Отпечатать элементы вещественного массива, начиная с последнегои кончая элементом, индекс которого равен значению, найденному в п. 1,3.При внимательном анализе выделенных подзадач можно заметить, чтовводимые в употребление массивы носят вспомогательный и временныйхарактер. Действительно, после нахождения серединного элемента массивцелого типа уже не нужен, поэтому естественно ввести его динамически,249только на время поиска серединного элемента. После того, как этот элемент будет найден, от этого динамического объекта можно отказаться,освободив ту часть памяти, которая ему была выделена.
Вещественныймассив тоже можно ввести динамически — в тот момент, когда в нем действительно возникает необходимость, причем для этого динамическогообъекта, возможно, будет выделен тот же участок памяти (или использована часть этого участка памяти), который был высвобожден на первомэтапе (после нахождения серединного элемента).
Таким образом, динамически вводя в употребление вспомогательные объекты, можно, с однойстороны, упростить алгоритм решения задачи, а с другой — эффективноиспользовать память ЭВМ.После проведенной детализации и замечаний об использовании динамичес к и х объектов уже довольно просто выписать полный текст паскаль-программы, предназначенной для решения поставленной задачи.{Пример 13.2.Большакова Е.И.
ф-т ВМиК МГУ 17.2.07г.Печать в обратном порядке элементов вещественногоФайла до элемента, номер которого равен значениюсерединного элемента другого, целочисленногоФайла. Количество элементов в каждом Файле непревышает 10000>{Использование динамических объектов и ссылочныхпеременных с целью экономии памяти}programпечатьэлементов(Целфайл,Вещфайл,output);c o n s t N=10000;typeцелмас=аггау C1..N3 o-f i n t e g e r ;вещмас-аггау C1..N3 o f r e a l ;vari , j , k: i nteger;p: *целмас;q: +вещмас;Целфайл: f i l e of 1... 100;Вещфайл: f i l e o f r e a l ;begin{Порождение динамическогообъекта типа целмас}new(р);{Перепись элементов Файла Целфайл в массив}reset<ЦелФайл);i:=0;w h i l e n o t eof(Целфайл)dob e g i n i:=i+l; ptCi]:=Целфайл•;250get(Целфайл)end;{Нахождение серединного элемента}i:=р+[<i div 2) +13;{Удаление динамического объекта типа целмас}di spose <р);{Порождение динамического объектатипа вещмас}new(q);{Перепись элементов Файла Вещфайл в массив}reset(Вещфайл>;j:=0;while not eo-f (ВецФайл) dobegin j:=j+l; qtСj3:=Вещфайлt; get(Вещфайл)end;{Печать элементов массива в обратном порядке доэлемента с индексом равным i включительно}for k:=j downto i do write(qf[k3 , ' _ ' ) ;wr i telnend.Отметим тот факт, что синтаксически буферная переменная файла ипеременная с указателем выглядят одинаково (например, в оператореpt [i] : = Ц е л ф а й л ! ) : справа от имени файла или переменной ссылочноготипа указывается стрелка t.
Но смысл этих конструкций различен: буферная переменная принимает значение компоненты файла, на которое указывает окно, а переменная с указателем дает возможность манипулироватьс значением того динамического объекта, на который указывает значениесоответствующей ссылочной переменной. Путаницы между этими конструкциями языка не происходит в силу однозначности их трактовки по одисанию соответствующих переменных и типов.13.3. Динамические структуры данных (строки)Мы уже говорили о том, что для обеспечения простоты и надежности разрабатываемого алгоритма решения той или иной задачи важное значениеимеет выбор наиболее подходящих структур тех данных, которые используются в процессе решения этой задачи.К настоящему времени мы познакомились со всеми типами значений,предусмотренными в языке паскаль.
Как видно, этот набор типов достаточно богат, а каждый тип значений паскаля на самом деле определяети некоторую структуру данных. Важно при этом подчеркнуть, что этот набор типов настолько универсален и гибок, что на его базе можно вводитьв употребление и использовать самые различные структуры данных, которые в явном виде в языке и не фигурируют. Особенно большие возможности в этом отношении дает ссылочный тип в сочетании с регулярным икомбинированным типами значений. Цель настоящего раздела к а к рази состоит в том, чтобы проиллюстрировать эти потенциальные возможности паскаля хотя бы на примере одной из таких структур данных, которыешироко используются в программистской практике, но которые в явномвиде в паскале не фигурируют,В качестве такой структуры данных мы возьмем с т р о к и .
Под строкой принято понимать упорядоченную последовательность литер из некоторого алфавита (в теории алгоритмов вместо термина строка обычно используется термин слово).Эта структура данных используется в программировании,пожалуй,наиболее часто — практически во всех задачах, связанных с обработкой символьной информации: трансляция программ с одного языкана другой, перевод текста с одного естественного языка на другой(например, с английского на русский), алгебраические преобразованияформул, аналитическое дифференцирование и интегрирование, информационно-поисковые системы и т.д. и т.п.И вообще строка является самой универсальной структурой данных —известно, например, что любой алгоритм может быть представлен как алгоритм преобразования слов (строк).
Так что наш выбор для иллюстрацииименно этой структуры данных вовсе не случаен.Над строкой определены следующие основные операции, с помощьюкоторых можно осуществить любое преобразование строк:— поиск вхождения заданной литеры в строку;— вставка заданной литеры в указанное место строки;— исключение литеры из указанного места строки.Для удобства практической работы иногда рассматривают указанныевыше операции применительно не к отдельной литере, а к некоторойподстроке. Однако очевидно, что любую операцию над подстрокамиможно свести к последовательности операций над отдельными литерами.В языке паскаль строку можно представить с помощью различных типовзначений.
Преимущества и недостатки того или иного способа представления выявляются в их сравнении, поэтому мы рассмотрим два наиболеетипичных способа: векторное представление (с использованием регулярного типа значений) и представление в виде цепочки (с использованием комбинированного и ссылочного типов),13.3.1. Векторное представление строкЭтот способ представления строк, вообще говоря, очень прост и естественен: здесь последовательные литеры строки принимаются в качестве последовательных компонент литерного вектора (одномерного массива типаchar).
В этом случае последовательный перебор элементов строки при поиске заданной литеры обеспечивается тем, что индекс следующего элемента определяется значением стандартной функции succ от индекса предыдущего элемента.Кроме того, индекс элемента однозначно определяет сам элементи доступ к нему. Это несомненное достоинство векторного представления. Но вместе с тем, любая операция над строкой, приводящая к ееизменению, может быть весьма длительной.
Действительно, чтобы вставитьв такую строку новую литеру, необходимо освободить для нее место,а для этого требуется "раздвинуть" строку, т.е. все литеры, которые должны следовать за вставляемой, нужно принять в качестве следующих эле252ментов вектора. Например, если исходная строка имела вид:П А С А Л Ь1 2 3 4 5 6(литеры)(их координаты в строке)то для того, чтобы вставить литеру 'К' после третьего элемента строки(т.е. после литеры 'С'), необходимо предварительно все последующие литеры сдвинуть на одну позицию вправо, т.е. координата каждой из этихлитер увеличится на единицу:П А С К А Л Ь1 2 3 4 5 6 7(литеры)(их координаты в строке)Это технические сложности, связанные со вставкой и удалением литер.Однако возникает и вопрос о том, как задать сам массив, компонентамикоторого будут являться литеры строки.
Очевидно, что для хранения строки придется определить массив в расчете на максимально допустимую длину строки. А поскольку число литер в строке обычно будет меньше числакомпонент массива и в процессе выполнения программы длина строки может меняться, то строку необходимо снабдить информацией, обеспечивающей доступ только к существующим элементам строки в массиве. Д л я решения этой проблемы наиболее часто используются следующие два способа.Первый состоит в том, чтобы снабдить строку специальным признаком(маркером) конца строки. Для этого выделяют определенную литеру,которая не может быть элементом строки, например, литеру #, и помещают ее в конец строки (пустая строка состоит из одной этой литеры # ) .В этом случае конец строки может быть определен лишь при полном переборе всех ее элементов.
Второй способ состоит в том, чтобы каким-либообразом в явном виде задавать фактическую длину строки. И при первом,и при втором способе определения конца строки выполнение основныхопераций над строками требует значительного числа действий. Приведем,к примеру, процедуры поиска, удаления и вставки заданной литеры из указанной строки, в предположении, что в качестве маркера конца строкииспользуется литера #, и что в программе имеются следующие описания:constN=100;type строка= array C1..N] o-f char;Процедура поиска должна ответить на вопрос — входит ли заданная литера в заданную строку.
Так что эту процедуру естественно описать как логическую процедуру-функцию, вырабатывающую значение true, если заданная литера входит в строку, и значение false — в противном случае. На практике довольно типична ситуация, когда вхождение заданной литеры в строку влечет за собой необходимость изменения этой строки, причем место ееизменения обычно определяется местом вхождения в нее заданной литеры.Поэтому в упомянутой выше процедуре-функции целесообразно предусмотреть побочный эффект — фиксацию в качестве значения одного из еепараметров индекса первого вхождения заданной литеры в строку. С учетом этого замечания дадим следующее описание процедуры-функциипоиска, которой дадим имя поиск 1:•function поиск1(литера: char; var st: строка;var index:integer): boolean;253var к: integer; -flags boolean;beginks=l; f 1 ag: =-f al se;while( s t C k 3 * ' ) a n d ( n o t flag)doif stС к3=литера thenbegin index:=k;flag:=true endelse k:=k+l;поиск1s =f1agendПроцедуру удаления элемента строки, следующего за элементом, заданным его индексом, можно описать следующим образом:procedure удаление(var st: строка; index: integer);var k: integer;begink:=i ndex + 1;while s t C k 3 # 'dobegin st С k 3:=st С k +13; k:=k+l endendПроцедура вставки в строку литеры вслед за литерой, заданной ее индексом, усложняется тем, что для сдвига части строки необходимо предварительно найти маркер ее конца:procedure вставка(уаг st:cTpoKa; лит:сИаг;var i,j:index:inteqpr);integer;begin{поиск маркера конца)i:=index+l;while stCi3*'#' do i:=i+l;{значение i - индекс маркера конца){сдвиг вправо элементов, следующих заэлементом с индексом index}for j:=i downto index+1 dostCs3 + 13:=stCj3;{вставка литеры в заданное место}st С i ndex + 13:=литendИтак, каковы достоинства и недостатки векторного представления строк?Основное достоинство — достаточно простой и быстрый поиск заданногоэлемента, а также возможность непосредственного доступа к элементу позаданному его индексу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
