Напишите программу которая переворачивает массив записанный в файл с помощью стека паскаль
Для связи файла в коде программы и действительного файла на внешнем носителе используется процедура ASSIGN :
где myfile — имя переменной (объявленной ранее в области var ), ассоциированной с файлом
c:\text.txt — путь к реальному файлу
Первый аргумент процедуры assign в паскаль — переменная, второй – путь к файлу на диске.
Для считывания из файла достаточно связать поток ввода с файлом:
begin Assign(input,'24.txt'); var s := ReadString; . end.
begin Assign(input,'26.txt'); var N := ReadInteger; var a := ReadArrInteger(N); . end.
Текстовые файлы в паскале: процедуры работы
Текстовый файл в Паскале — это совокупность строк произвольной длины, которые разделены между собой метками конца строки, а весь файл заканчивается меткой конца файла.
Возможные расширения файлов:
*.txt, *.log,
*.htm, *.html
Метод работы с текстовым файлом в Паскале предусматривает лишь последовательный доступ к каждой строке файла. Это означает, что начинать всегда возможно только с первой строки, затем проходя по каждой строке, дойти постепенно до необходимой. Т.е. можно сказать, что чтение (или запись) из файла (в файл) ведутся байт за байтом от начала к концу.
Предусмотрены два режима работы: режим для записи в файл информации и для чтения ее из файла. Одновременная запись и чтение запрещены.
Открытие файла (классический Pascal)
Допустим, мы в программе описали переменную для работы с текстовым файлом:
Рассмотрим дальнейшую последовательность работы с ним, и рассмотрим процедуры, необходимые для работы с текстовым файлом в Паскале:
процедура открытия существующего файла для чтения при последовательном доступе:
процедура открытия создаваемого файла для записи в него информации; если файл с таким именем уже существует, то информация в нем стирается:
процедура добавления в конец:
- При открытии курсор устанавливается в начало файла.
Чтение из файла (классический Pascal)
Read (f, список переменных); ReadLn (f, список переменных);
Отличие ReadLn от Read в том, что при использовании readln после прочтения данных пропускаются все оставшиеся символы в данной строке, включая метку конца строки.
- чтение осуществляется с той позиции, где в данный момент стоит курсор;
- после чтения курсор сдвигается к первому непрочитанному символу.
close ( f ); reset ( f );
Запись в текстовый файл (классический Pascal)
Write (f, список переменных); WriteLn (f, список переменных);
где f — файловая переменная, а второй параметр – выводимые из программы и вводимые в файл данные (в виде значений переменных или просто данные)
Процедуры работы с файлом и закрытие файла
Нахождение конца файла:
Логическая функция, возвращающая True, если достигнут конец файла.
Нахождение конца строки:
Логическая функция, возвращающая True, если достигнут конец строки.
Удалить файл в Паскале
Переименование файла в Паскале
rename(переменная_файла,'новое имя файла');
Закрытие:
Рассмотрим пример работы с файлами в паскале:
Пример 1: В файле text.txt записаны строки. Вывести первую и третью из них на экран.
(предварительно создать text.txt с тремя строками)
var filetext: text; a,b,c:string; begin assign(filetext,'c:\text.txt'); reset(filetext); readln(filetext,a); readln(filetext,b); readln(filetext,c); close(filetext); writeln(a); writeln(c); end.
begin Assign(input, '1.txt'); var a := ReadString; var b := ReadString; var c := ReadString; print(a, c) end.
Пример 2: Дан текстовый файл. Вывести количество содержащихся в нем символов и строк (маркеры концов строк EOLN и конца файла EOF при подсчете количества символов не учитывать).
* Из задачника М. Э. Абрамян (Text4)
var F: Text; N,K:integer; Name:String; C:Char; begin Assign(F,'c:\text.txt'); Reset(F); N:=0; K:=0; While not eof(F) do begin inc(N); While not eoln(f) do begin inc(K); Read(F,C); end; Readln(F); end; Close(F); Writeln(N,' ',K); end.
begin Assign(input, '1.txt'); var n, k: integer; while not eof(input) do begin inc(n); while not eoln(input) do begin inc(k); var a := ReadChar; end; var b := ReadString; end; print($'строк , символов ') end.
Пример 3:
Считать из файла input.txt числа (числа записаны в столбик). Затем записать их произведение в файл output.txt
var p, x: integer; f: text; begin assign(f, 'input.txt'); reset(f); p := 1; while not eof(f) do begin readln(f, x); p := p * x; end; close(f); assign(f, 'output.txt'); rewrite(f); writeln(f, 'Произведение чисел ', p); close(f); end.
begin Assign(input, 'input.txt'); Assign(output, 'output.txt'); var p := 1; while not eof(input) do begin var x := readInteger; p := p * x; end; print($'произведение
'); end.
pascal file text1. В цикле записать в файл числа от 1 до 10 (каждое — в своей строке), а затем их считать и отобразить на экране.
Дополните код:
var filetext: text; a:string; i:integer; begin assign(filetext,'c:\text.txt'); rewrite(filetext); for i:=1 to 10 do . reset(filetext); for i:=1 to 10 do begin . . end; close(filetext); end.
pascal file text2. Даны целые положительные числа N и K. Создать текстовый файл и записать в него N строк, каждая из которых состоит из K символов «*» (звездочка).
* Из задачника М. Э. Абрамян (Text1)
* Из задачника М. Э. Абрамян (Text5)
* Из задачника М. Э. Абрамян (Text7)
var F_in,F_out: Text; Name,S: String; begin Write('S: '); Readln(S); Assign(F_in,'c:\text.txt'); Reset(F_in); Assign(F_out,'c:\text1.txt'); Rewrite(F_out); Writeln(F_out,S); While not eof(F_in) do begin Readln(F_in,S); Writeln(F_out,S); end; Close(F_in); Close(F_out); Erase(F_in); Rename(F_out,'c:\text.txt'); end.
begin var s := readstring('s: '); Assign(input, 'input.txt'); Assign(output, 'output.txt'); println(S); while not eof(input) do begin s := ReadString; println(s); end; close(input); // обязательно! close(output); // обязательно! Erase(input); Rename(output, 'input.txt'); end.
pascal file text4. Дано целое число K и текстовый файл. В данном файле вставить пустую строку перед строкой с номером K . Если строки с таким номером нет, то оставить файл без изменений.
Для решения задачи можно использовать дополнительный временный файл.
* Из задачника М. Э. Абрамян (Text9)
Пример 5: Дано целое число K и текстовый файл. Удалить из файла строку с номером K . Если строки с таким номером нет, то оставить файл без изменений.
Примерный результат:
до:
* Из задачника М. Э. Абрамян (Text15)
var F_in,F_out: Text; Name,line: string; K,i:integer; begin Write('K: '); Readln(K); Assign(F_in,'c:\text.txt'); Assign(F_out,'c:\text1.txt'); Reset(F_in); Rewrite(F_out); i:=0; While not eof(F_in) do begin Readln(F_in,line); inc(i); if i<>K then Writeln(F_out,line); end; Close(F_in); Close(F_out); Erase(F_in); Rename(F_out,'c:\text.txt'); end.
begin var k := readinteger('k: '); Assign(input, 'input.txt'); Assign(output, 'output.txt'); var i:=0; while not eof(input) do begin var s := ReadString; inc(i); if i<>k then println(s); end; close(input); // обязательно! close(output); // обязательно! Erase(input); Rename(output, 'input.txt'); end.
Пример 6: Дан текстовый файл F1 с набором нулей и единиц. Необходимо заменить все вхождения сочетаний 101 на 000 . Скорректированные записи поместить в файл F2 .
var f1,f2: text; pole:string; pz:integer; begin assign(f1,'1.txt'); assign(f2,'2.txt'); reset(f1); rewrite(f2); while not eof(f1) do begin readln(f1, pole); while pos('101',pole)<>0 do begin pz:=pos('101',pole); delete(pole,pz,3); insert('000',pole,pz); end; writeln(f2,pole) end; close(f1); close(f2); end.
begin Assign(input, 'input.txt'); Assign(output, 'output.txt'); var s:=readString; var s1:=''; var ind := s.IndexOf('101'); while ind<>-1 do begin s1+=s[:ind+1]; s1+='000'; delete(s,1,ind+3); // удаляем всё вместе с 101 ind := s.IndexOf('101'); end; s1+=s; Println(s1); end.
Работа с данными из файла как с массивом
Пример 7: В файле input.txt записаны числа (каждое — с новой строки), их количество не превышает 100. Необходимо отсортировать их по возрастанию и записать в файл output.txt.
- для сортировки необходим массив, для того чтобы одновременно работать со всеми числами;
- неизвестно общее количество чисел.
- объявляем массив для 100 элементов;
- открываем файл на чтение, просчитываем количество чисел, заполняя массив, сохраняем количество в N;
- сортируем N элементов массива;
- записываем результат в файл.
pascal file text5. В файле input.txt записаны числа (каждое — с новой строки), их количество не превышает 100. Необходимо найти максимальное и минимальное число и записать их в файл output.txt.
* Из задачника М. Э. Абрамян (Text16)
А теперь вернемся к олимпиадному заданию по Паскалю, частично решенному на одном из предыдущих заданиях:
Пример 8: Шифр Цезаря заключается в том, что каждая буква исходной строки заменяется третьей после нее буквой в алфавите, который считается написанным по кругу (все символы текста латинские и прописные).
Решить ту же задачу, в которой сдвиг будет не на 3 позиции, а на k, причем отрицательное значение является признаком сдвига влево, положительное — вправо.
Формат входных данных (файл p.in): В первой строке записано число k, не превышающее по модулю 20. Во второй строке — текст, который необходимо зашифровать. Все символы текста латинские и прописные.
Формат выходных данных (файл p.out): Выведите зашифрованный текст.
Пример:
p.in | p.out |
---|---|
3 hello earth | khoor hduwk |
* желательно создать файлы и записать данные в исходный файл «вручную»
* программа решена для k=3, выполните программу для любых k (не превышающих 20 по модулю)
var a:char; i,n,k:byte; s,s1:string; f_in,f_out:text; begin Assign(F_in,'z:\p.in'); Assign(F_out,'z:\p.out'); Reset(F_in); Rewrite(F_out); s1:=''; readln(f_in,k); readln(f_in,s); for i:=1 to length(s) do begin n:=ord(s[i]); if n<>32 then n:=n+3; if . then . ; if . then . ; if . then . ; a:=chr(. ); s1:=. ; end; writeln(s1); writeln(f_out,s1); close(f_in); close(f_out) end.
var a:char; i,n,k:byte; s,s1:string; f_in,f_out:text; begin Assign(F_in,'z:\p.in'); Assign(F_out,'z:\p.out'); Reset(F_in); Rewrite(F_out); s1:=''; readln(f_in,k); readln(f_in,s); for i:=1 to length(s) do begin n:=ord(. ); if n<>32 then n:=n+3; if n=123 then n:=97; if n=124 then n:=98; if n=125 then n:=99; a:=chr(n); s1:=s1+a; end; writeln(s1); writeln(f_out,s1); close(f_in); close(f_out) end.
полное решение var s, s1: string; i, j, a, n, k, b: integer; begin n := 97; s1 := ''; readln(s); readln(k); for i := 1 to length(s) do begin if s[i] <> ' ' then begin a := ord(s[i]); if a > 122 - k then for j :=123 - k to 122 do begin b:=122-j; if a = j then begin a := n+k-b-1; inc(n); end; end else a := a + k; s1 := s1 + chr(a) end else s1 := s1 + ' ' end; writeln(s1)end. -->
Для участия в олимпиаде по информатике вы должны уметь работать с текстовыми файлами (считывать и записывать информацию). На олимпиадах, начиная с областных, они используются для ввода и вывода данных. Лучше всего попробовать работать с файлами до того, как Вы пойдете на олимпиаду.
На этом уроке мы рассмотрим, как используются текстовые файлы для ввода и вывода данных в программе на языке Паскаль.
Текстовые файлы – это файлы, содержащие символы, разделенные на строки. Причем в конце каждой строки стоит символ конца строки.
Общая последовательность действий при работе с файлами в языке программирования Паскаль:
- описать переменную файлового типа;
- связать ее с конкретным физическим файлом процедурой Assign;
- открыть файл для чтения процедурой ReSet или для записи процедурой ReWrite;
- выполнить чтение или запись информации;
- по окончании работы с файлом закрыть файл процедурой Close.
Описание переменной файлового типа
С текстовым файлом на диске в программе должна быть связана файловая переменная, которая описывается с указанием стандартного типа Text:
Связь переменной файлового типа с конкретным внешним файлом
Для установления связи между файловой переменной и именем файла, присваиваемого операционной системой, имеется стандартная процедура Assign.
Такое соответствие обозначает, что все операции, выполняемые над переменной F1, будут выполняться над файлом, хранящемся на диске и имеющим имя ‘Int.dat’
Чтение из файла
Под чтением из файла понимается ввод данных из внешнего файла, находящегося на диске, в оперативную память. Данные входного файла становятся доступными программе.
Для чтения файла в программе необходимо выполнить следующие действия:
Открыть файл для чтения:
Прочитать данные файла в программу с помощью процедуры Read или Readln .
Процедура Read последовательно считывает все элементы строки:
Процедура Readln – считывает элемент из текущей строки и переходит на следующую строку (независимо от того, достигнут конец строки или нет):
Если не указывать второй параметр, то произойдет переход в начало следующей строки без ввода данных:
Закрытие файла
После завершения работы с файлом, его нужно закрыть и «освободить» файловую переменную . Это делается с помощью процедуры Сlose.
Общий вид оператора:
Общая форма чтения файла имеет вид:
Многоточием отмечено наличие других операторов в программе.
Признак конца файла
Так как, по определению, число элементов файла не задается заранее, то в языке Паскаль введена логическая функция Eof() для определения признака конца файла.
Общий вид функции:
Она определяет, достигнут ли конец файла или еще нет (принимает значение (true), если достигнут конец файла, и ложь (false) — в противном случае).
Для определения конца файла используется оператор цикла, например, (пока не достигнут конец файла …):
Запись в файл
Под записью файла понимается вывод результатов программы из оперативной памяти на диск, т.е. создание нового файла на внешнем устройстве.
Для записи файла в программе необходимо выполнить следующие действия:
Открыть файл для записи с помощью процедуры Rewrite:
Записать данные в файл спомощью процедур Write или Writeln.
Процедура Write производит запись поэлементно в текущую строку:
Процедура WriteLn записывает элемент и переводит указатель в начало следующей строки:
Если не указывать второй параметр процедуры, то в конце данной строки ставится признак конца файла и текущий указатель перемещается на начало следующей строки:
После завершения работы с файлом его закрытие обязательно.
Общая форма записи файла имеет вид:
Логическая функция Eoln()
Часто для обработки текстовых файлов используется специфичная для них функция Eoln(), позволяющая определить, достигнут ли конец строки. Если достигнут — значение функции равно True, а если нет — False.
Таким образом, для анализа конкретных символов строк файла можно применить вложенный цикл типа:
Пример. Дан текстовый файл, содержащий только целые числа, в каждой строке может быть несколько чисел, которые разделяются пробелами. Вывести на экран все числа с учетом разбиения на строки и подсчитать количество элементов в каждой строке.
Пусть в файле содержится следующая информация:
-32 16 0 8 7
4 5 9 13 11 -5 -8
6 -8 0 12
1 2
-1 -2 -4
-1 -2 4
Этот файл можно создать в среде Паскаль следующим образом:
- Создать новый файл (команда Файл-Новый).
- Записать все числа в строке через пробелы.
- Сохранить его, например, как ‘primer1.dat’.
Для этого в диалоговом окне сохранения файла в списке Тип файла выбрать Все файлы. В поле Имя файла ввести полное имя файла (имя с расширением).
Программа будет иметь следующий вид:
На этом уроке было рассмотрено, как использовать текстовые файлы для ввода и вывода данных в программе на языке Паскаль.
На следующем уроке Вы узнаете, как использовать тип данных Bulean для представления данных логического типа.
Следующий урок: Логический тип данных
Урок понравился? Отзывы и замечания можно оставить в форме для комментариев, расположенной в нижней части страницы.
Перевернуть массив
Дан исходный массив, состоящий из n элементов. Необходимо сначала ввести элементы массива , а затем перевернуть массив и вывести результат на экран.
Разбираемся. Что вообще значит перевернуть массив? Это значит, что первый элемент массива надо поменять местами с последним, второй с предпоследним и т.д. Рассмотрим 2 случая: массив имеет четное количество элементов и массив имеет нечетное количество элементов. В первом случае все просто: имея массив от 1 до n последовательно меняем 1 с n , 2 с n-1, 3 с -3 и т.д. элементы массива. В результате будет выполнено n/2 шагов цикла. Во втором случае все также, но появляется ситуация, когда элемент нечетного массива, находящийся посередине меняется сам с собой (всего происходит n/2+1 шагов цикла). Однако нам нужна ситуация, когда в обоих случаях будет сделано n/2 шагов. Можно сделать это, использовав условный оператор, но можно поступить проще и воспользоватся оператором div.
Обратите внимание на эту строчку (p — шаги цикла ). Если n равен 4, то будет сделано 2 шага цикла, если же n равен 5, то шагов будет опять 2. То, что и требовалось. А теперь весь код программы
const
n = 5;var
m, p: integer;
s: array [1..n] of real;
k: real;begin
writeln(‘Введите последовательно через пробел ‘, n, ‘ элементов массива’);
for m := 1 to n do
read(s[m]);p := n div 2;
writeln(p);
for m := 1 to p do
begin
k := s[m];
s[m] := s[n + 1 — m];
s[n + 1 — m] := k;
end;
writeln(‘Перевернутый массив’);
for m := 1 to n do
write(s[m]);end.
Как вы заметили, код представлен как для целых чисел, так и для дробных. На этом все, теперь вы знаете как можно легко перевернуть массив в паскале.
5 Replies to “Перевернуть массив”
а я бы от так сделал)
uses crt;
const n = 5;
var
m, p: integer;
s,s2: array [1..n] of real;
k: real;
begin
clrscr;
writeln(‘Vvedite posledovatelno cherez probel ‘, n, ‘ elementov massiva’);
for m := 1 to n do
read(s[m]);
writeln(‘Perevernutyi massiv’);
for m := n downto 1 do
begin
s2[abs(m-n-1)]:=s[m];
write(s2[abs(m-n-1)]:2:0);
end;
readkey;
end.
Захар,
Признаюсь вначале я думал сделать так же))
Просто потом в голову пришла мысль проверить другие варианты.
Так то мой код ничем не отличается ,кроме того,что делается меньше шагов цикла )
TempB := b[n];
for k:=n-1 downto 1 do
b[k+1] := b[k];
b[1] := TempB;
а если так. winked
][omak,
Можно и так
Просто, как я уже сказал, мой вариант ориаентирован на меньшее колличество шагов цикла
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Информатика. 11 класс. Углубленный уровень. В 2 ч. Поляков К.Ю., Еремин Е.А.
§ 42. Стек, очередь, дек
Вопросы и задания
1. Что такое стек? Какие операции со стеком разрешены?
2. Как используется системный стек при выполнении программ?
3. Какие ошибки могут возникнуть при использовании стека?
4. В каких случаях можно использовать обычный массив для моделирования стека?
5. Как построить стек на основе динамического массива?
6. Почему при передаче стека в подпрограммы, приведённые в параграфе, соответствующий параметр должен быть изменяемым?
7. Что такое очередь? Какие операции она допускает?
8. Приведите примеры задач, в которых можно использовать очередь.
а) «Моделирование стека и очереди в языке Си»
б) «Моделирование стека и очереди в языке Python»
в) «Моделирование очереди с помощью стеков»
г) «Очередь с приоритетом»
Задача
1. Напишите программу, которая «переворачивает» массив, записанный в файл, с помощью стека. Размер массива неизвестен. Все операции со стеком вынесите в отдельный модуль.
2. Напишите программу, которая вычисляет значение арифметического выражения, записанного в постфиксной форме. Выражение вводится с клавиатуры в виде символьной строки.
3. Напишите программу, которая проверяет правильность скобочного выражения с четырьмя видами скобок: (), [], <> и <>. Все операции со стеком вынесите в отдельный модуль.
*4. Найдите в литературе или в Интернете алгоритм перевода арифметического выражения из инфиксной формы в постфиксную и напишите программу, которая решает эту задачу.
5. Напишите программу, которая выполняет заливку одноцветной области заданным цветом. Матрица, содержащая цвета пикселей, вводится из файла. Затем с клавиатуры вводятся координаты точки заливки и цвет заливки. На экран нужно вывести матрицу, которая получилась после заливки. Все операции с очередью вынесите в отдельный модуль.
*6. Перепишите программу из задачи 5 — используйте статический массив для организации очереди. Считайте, что в очереди может быть не более 100 элементов. Предусмотрите обработку ошибки «очередь переполнена».
*7. Напишите программу решения задачи о заливке области, помечая при этом точки, добавленные в очередь, чтобы не добавлять их повторно. В чём преимущества и недостатки такого алгоритма?
Стек — динамическая структура данных, в которой добавление и удаление элементов доступно только с одного конца (с верхнего (последнего) элемента).
Существуют такие сокращения:
Последовательные этапы засылки в стек чисел 1, 2, 3
Над стеком выполняются следующие операции:
- добавление в стек нового элемента;
- определение пуст ли стек;
- доступ к последнему включенному элементу, вершине стека;
- исключение из стека последнего включенного элемента.
Создание структуры узла:
Добавление элемента в стек:
procedure Push( var Head: PNode; x: char); var NewNode: PNode; begin New(NewNode); < выделение памяти >NewNode^.data := x; < запись символа >NewNode^.next := Head; < сделать первым узлом >Head := NewNode; end;
Забор элемента с вершины:
function Pop ( var Head: PNode ): char; var q: PNode; begin if Head = nil then begin < если стек пустой >Result := char(255); < неиспользуемый символ, т.е. ошибка >Exit; end; Result := Head^.data; < берем верхний символ >q := Head; < запоминаем вершину >Head := Head^.next; < удаляем вершину >Dispose(q); < удаление из памяти >end;
Проверка, пустой ли стек:
function isEmptyStack ( S: Stack ): Boolean; begin Result := (S = nil); end;
Объявления в основной программе:
var S: PNode; . S := nil;
Рассмотрим подробную работу со стеком на примере:
Пример: вводится символьная строка, в которой записаны теги в угловых скобках (<>). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы).
Алгоритм выполнения задания:
- изначально стек пустой;
- в цикле просматриваем каждый символ строки;
- если текущий символ – открывающая угловая скобка, то вставляем ее на вершину стека;
- если текущий символ – закрывающая угловая скобка, то проверяем верхний элемент стека: там должна находиться открывающая угловая скобка (иначе — ошибка);
- в конце стек должен стать пустым, иначе — ошибка.
Создаем структуру стека:
const MAXSIZE = 50; type Stack = record < стек рассчитан на 50 символов >tags: array[1..MAXSIZE] of char; size: integer; < число элементов >end;
Процедура добавления элемента в стек:
procedure Push( var S: Stack; x: char); begin if S.size = MAXSIZE then Exit; // выход, если произошло переполнение стека S.size := S.size + 1; S.tags[S.size] := x; // добавляем элемент end;
Функция взятия элемента с вершины:
function Pop ( var S:Stack ): char; begin if S.size = 0 then begin Result := char(255); // 255 - пустой символ, ошибка - стек пуст Exit; end; Result := S.tags[S.size]; S.size := S.size - 1; end;
Создаем функцию для проверки, пустой ли стек:
function isEmptyStack ( S: Stack ): Boolean; begin Result := (S.size = 0); end;
var expr: string; br1, br2: char; < угловые скобки >i, k: integer; upper: char; < верхний символ, снятый со стека >error: Boolean; < признак ошибки >S: Stack; begin br1 := ''; S.size := 0; error := False; writeln('Введите html-текст'); readln(expr); . < здесь вставляется цикл с обработкой строки >if not error and isEmptyStack(S) then writeln('Текст верный.') else writeln('Текст составлен неверно.') end.
Обработка строки в цикле:
for i:=1 to length(expr) < проходимся по всем символам строки expr >do begin if expr[i] = br1 then begin < открывающая скобка < >Push(S, expr[i]); < втолкнуть в стек >break; end; if expr[i] = br2 then begin < закрывающая скобка < >upper := Pop(S); < снять символ со стека >error := upper <> br1; < ошибка: стек пуст или не та скобка >break; end; if error then break; // была ошибка, значит, прерываем цикл end;
Очереди
Очередь — динамическая структура данных, у которой в каждый момент времени доступны только два элемента: первый и последний. Добавление элементов возможно только с одного конца (конца очереди), а удаление элементов – только с другого конца (начала очереди).
Существует сокращение для очереди: FIFO = First In – First Out, с английского — «Кто первым вошел, тот первым вышел».
Для очереди доступны следующие операции:
- добавить элемент в конец очереди (PushTail);
- удалить элемент с начала очереди (Pop).
Работа с очередью обычным массивом:
Это достаточно простой способ, который подразумевает два неблагоприятных момента: заблаговременное выделение массива, сдвиг элементов при удалении из очереди.
Работа с очередью с помощью кольцевого массива:
Если в очереди 1 элемент:
Если очередь пуста:
Если очередь заполнена:
Определение размера массива (при пустой и заполненной очереди):
Очередь в Паскале (использование кольцевого массива)
Создание структуры:
type Queue = record data: array[1..MAXSIZE] of integer; head, tail: integer; end;
Как добавить в очередь:
procedure PushTail( var Q: Queue; x: integer); begin if Q.head = (Q.tail+1) mod MAXSIZE + 1 then Exit; < очередь уже полна >Q.tail := Q.tail mod MAXSIZE + 1; Q.data[Q.tail] := x; end;
Как выбрать из очереди:
function Pop ( var S: Queue ): integer; begin if Q.head = Q.tail mod MAXSIZE + 1 then begin Result := MaxInt; Exit; end; Result := Q.data[Q.head]; Q.head := Q.head mod MAXSIZE + 1; end;
Создание очереди посредством списка
Объявление узла:
type PNode = ^Node; Node = record data: integer; next: PNode; end; type Queue = record head, tail: PNode; end;
Добавляем новый элемент:
procedure PushTail( var Q: Queue; x: integer ); var NewNode: PNode; begin New(NewNode); NewNode^.data := x; NewNode^.next := nil; if Q.tail <> nil then Q.tail^.next := NewNode; Q.tail := NewNode; if Q.head = nil then Q.head := Q.tail; end;
Выбираем элемент из списка:
function Pop ( var S: Queue ): integer; var top: PNode; begin if Q.head = nil then begin Result := MaxInt; Exit; end; top := Q.head; Result := top^.data; Q.head := top^.next; if Q.head = nil then Q.tail := nil; Dispose(top); end;
Дек — англ. double ended queue, т.е. очередь с двумя концами – это динамическая структура данных, добавлять и удалять элементы в которой можно с обоих концов.
Деревья
Дерево – это структура данных, которая состоит из узлов и соединяющих их направленных ребер или дуг; в каждый узел за исключением корневого ведет только одна дуга.
- Корнем называется главный или начальный узел дерева.
- Листом называется узел, из которого не выходят дуги.
1 — предок для всех других узлов в дереве
6 — потомок для узлов 5, 3 и 1
3 — родитель узлов 4 и 5
5 — сын узла 3
5 — брат узла 4
Двоичные деревья
В двоичном (бинарном) дереве каждый узел имеет не более двух дочерних узлов (сыновей).
Объявление:
type PNode = ^Node; < указатель на узел >Node = record data: integer; < данные >left, right: PNode; end;
Поиск по дереву:
При поиске в дереве используется понятие ключ. Ключ — это характеристика узла, по которой осуществляется поиск.
В левую сторону отходят узлы с меньшими ключами, а в правую — с большими.
- если дерево пустое, значит, ключ не найден;
- если ключ узла равен k, то остановка;
- если ключ узла меньше k, то искать k в левом поддереве;
- если ключ узла больше k, то искать k в правом поддереве.
Сравним поиск в массиве c n элементами с поиском в бинарном дереве:
Поиск в массиве: каждое сравнение — отбрасываем 1 элемент.
Число сравнений – N.
При каждом сравнении отбрасывается половина оставшихся элементов.
Число сравнений ~ log2N
Поиск в бинарном дереве на Паскале:
Создадим функцию для поиска. На вход функции из главной программы подаются два параметра: tree — адрес корня дерева и x — искомое число. Функция возвращает адрес узла с искомым значением или nil, если ничего не найдено.
function SearchInTree(Tree: PNode; x: integer): PNode; begin if Tree = nil then begin Result := nil; Exit; end; if x = Tree^.data then Result := Tree else if x < Tree^.data then Result := SearchInTree(Tree^.left, x) else Result := SearchInTree(Tree^.right, x); end;
Создание дерева поиска:
Для создания дерева воспользуемся процедурой с двумя параметрами: tree — адрес корня дерева, x — добавляемый элемент.
procedure AddToTree( var Tree: PNode; x: integer ); begin if Tree = nil then begin New(Tree); Tree^.data := x; Tree^.left := nil; Tree^.right := nil; Exit; end; if x < Tree^.data then AddToTree(Tree^.left, x) else AddToTree(Tree^.right, x); end;
Обход дерева:
Данное действие необходимо для перечисления всех узлов в определенном порядке.
Рассмотрим варианты обхода:
Создадим процедуру для обхода ЛКП дерева. Процедура имеет один параметр — tree — адрес корня.
procedure LKPObhod(Tree: PNode); begin if Tree = nil then Exit; LKPObhod(Tree^.left); write(' ', Tree^.data); LKPObhod(Tree^.right); end;
Читайте также: