Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ЛАБОРАТОРНАЯ РАБОТА 10
(динамические переменные)
1. Используйте линейные списки для хранения последовательности чисел. Опишите процедуру
или функцию, которая:
а) переносит в начало непустого списка его последний элемент;
б) добавляет в конец списка L1 все элементы списка L2;
в) вставляет в список L за первым вхождением элемента E все элементы списка L1, если E входит в L.
2. Используйте линейные списки для хранения последовательности чисел. Опишите процедуру, которая удаляет:
а) из списка второй элемент, если такой есть;
б) из непустого списка последний элемент;
в) из списка первый отрицательный элемент, если такой есть;
г) из списка все отрицательные элементы.
3. Используйте линейные списки для хранения последовательности строк. Опишите функцию, подсчитывающую количество строк - элементов списка, которые:
а) начинаются и оканчиваются одним и тем же символом;
б) начинаются с того же символа, что и следующая строка;
в) совпадают с последней строкой.
Напишите процедуру, которая удаляет вторую строку из списка.
4. Используйте линейные списки для хранения последовательности чисел. Опишите процедуру или функцию, которая:
а) проверяет на равенство списки L1 и L2;
б) проверяет, есть ли в списке L хотя бы два одинаковых элемента;
в) переносит в конец непустого списка его первый элемент.
5. Используя представление последовательности чисел в виде линейного списка, напишите программу, решающую задачу: "Объедините две упорядоченные последовательности в одну упорядоченную последовательность (сортировка слиянием)".
6. Используя представление последовательности чисел в виде линейного списка, напишите программу, сортировки этой последовательности при помощи алгоритма простого обмена.
7. Используйте линейные списки для хранения последовательности чисел. Опишите процедуру или функцию, которая:
а) для данного списка L создает список L1, содержащий те же элементы, но в обратном порядке;
б) для данного элемента E, входящего в список, оставляет только его первое вхождение;
в) то же, что и б), но оставляется последнее вхождение.
8. Используйте линейные списки для хранения последовательности вещественных чисел. Опишите процедуру или функцию, которая:
а) находит среднее арифметическое элементов непустого списка;
б) заменяет в списке все вхождения элемента E1 на элемент E2;
в) меняет местами первый и последний элементы непустого списка;
г) удаляет последний элемент списка.
9. Используйте линейный список для представления многочлена от переменной x, упорядоченного по степеням x. Напишите программу для сложения двух многочленов от переменной x (удобно воспользоваться сортировкой слиянием).
10. Используйте линейный список для представления многочлена от переменно x, упорядоченного по степеням x. Напишите программу для дифференцирования многочлена.
11. Используйте линейные списки для хранения последовательности чисел. Опишите процедуру, которая вставляет:
а) новый элемент Е после первого элемента непустого списка;
б) новый элемент Е1 за каждым вхождением элемента Е;
в) новый элемент Е1 перед первым вхождением элемента Е, если Е входит в список;
г) новый элемент Е перед последним элементом непустого списка.
12. Используйте представление последовательности строк в виде линейного списка и опишите:
а) процедуру ПЕРЕСТАНОВКА(L , i , j), меняющую местами i-ю и j-ю строки списка L;
б) процедуру ЗАМЕНА(L , i , j), заменяющую i-ю строку списка L на копию j-й строки;
в) процедуру ДОБАВИТЬ(L , i , j), добавляющую после i-ой строки списка L копию j-й строки;
г) процедуру УДАЛИТЬ(L , i), удаляющую i-ю строку из списка L.
13. Используя представление последовательности чисел в виде линейного списка, напишите программу сортировки этой последовательности при помощи алгоритма простыми включениями.
14. Используя представление последовательности чисел в виде линейного списка, напишите программу сортировки этой последовательности при помощи алгоритма простого выбора.
15. Используйте линейный список для хранения очень длинного целого числа.
Дано натуральное n. Напишите программу для вычисления 2 n.
16. Используйте линейный список для представления стека для решения следующей задачи. Пусть дан файл, состоящий из чисел. За один просмотр файла и без использования дополнительных файлов напечатать элементы файла в следующем порядке: сначала все числа, меньшие a, затем все числа >=a, причем числа в каждой группе должны печататься в обратном порядке относительно исходного (а - заданное число).
Пример: элементы файла - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
a = 6
Порядок при печати: 5 4 3 2 1 10 9 8 7 6
17. Используя стек - представленный в виде линейного списка – решить следующую задачу (решение описать в виде процедуры). В текстовом файле записан текст, сбалансированный по круглым скобкам. Требуется для каждой парв соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексте, упорядочив пары номеров в порядке возрастания номеров позиций закрывающих скобок.
Например, для текста a + (45 - f(x) * (b - c)) надо напечатать 8 10; 12 16; 3 17;
18. Используйте линейный двунаправленный список для представления многочлена относительно переменной x. Многочлены Чебышева (относительно x) n-го порядка определяются следующим образом:
T 0 (x) = 1, T 1 (x) = x
T n (x) = 2*x*T n -1 (x) – T n - 2 (x) (n=2,3,...)
Напишите программу для получения n-го многочлена Чебышева.
19. Дан файл целых чисел, содержащий не менее двух элементов. Выбрав для представления данных подходящую списковую структуру, напечатайте в обратном порядке все числа между наибольшим и наименьшим членами этой последовательности.
20. Реализуйте двусвязные списки для представления очереди. Реализуйте следующие операции над очередью:
а) очистить очередь (создать пустую очередь);
б) проверить, является ли очередь пустой;
в) добавить в конец очереди элемент;
г) удалить из строки первый элемент.
21. Напечатать в порядке возрастания все неправильные несократимые дроби со знаменателями, меньшими заданного натурального числа p. Массивов не заводить.
22. Дано натуральное n. Программа: напечатать в порядке возрастания вес рациональные числа
вида a / b, где a , b > 0, b <= n , 1 < a/b <= 2, a и b – взаимно просты. Используйте сортировку с
помощью дерева.
23. Дано натуральное n. Программа: напечатать в порядке убывания все рациональные числа вида
a / b, где a , b > 0, b <= n, 0 < a/b <= 1, a и b - взаимно просты. Используйте сортировку с
помощью дерева.
*************************************************************************************
Примеры решения некоторых задач
*************************************************************************************
1. type telem='a'..'z'.
list=^node;
node= record
info:telem;
next:list
end;
Пусть E1 и E2 - данные типа telem.
Описать функцию или процедуру, которая :
а) заменяет в списке L все вхождения Е1 и Е2;
б) проверяет, упорядочены ли элементы списка L по алфавиту
а)
type telem='a'..'z';
list=^node;
node= record
info : telem;
next : list
end;
var s,l : list;
x,e,e1 : telem;
n,i : integer;
procedure change (l : list; e,e1: telem);
var p:list; {ссылка на очерeдное звено}
begin
p:=L;
while p<>nil do
begin
if p^.info=e then p^.info:=e1;
p:=p^.next {переход к следующему звену}
end;
end;
procedure out_spisok(l : list); {выводит список на экран}
begin
while l<> nil do
begin
s:=l^.next;
write(l^.info,' ');
l:=s;
end;
writeln;
end;
begin
{формируем список}
s:=nil;
writeln('Введите количесто элементов списка');
readln(n);
for i:=1 to n do
begin
new(l);
l^.next:=s;
readln(x);
l^.info:=x;
s:=l;
end;
{выводим список на экран}
writeln('Введенный список');
out_spisok(l);
{заменяем элемент Е на Е1}
writeln('Введите элемент, который Вы хотите заменить');
readln(e);
writeln('Введите элемент, на который Вы хотите заменить');
readln(e1);
change (l,e,e1);
writeln('Полученный список');
out_spisok(l);
{освобождаем динамическую память}
while l<> nil do
begin
s:=l^.next;
dispose(l);
l:=s;
end;
end.
б)
type telem='a'..'z';
list=^node;
node= record
info : telem;
next : list
end;
var s,l : list;
x : telem;
n,i : integer;
function sort(l : list) : boolean;
var p,q : list; {ссылка на пару соседних звеньев}
ok : boolean;
begin
ok:=true;
p:=L; {nil или ссылка на 1-звено}
if p<>nil then
begin q:=p^.next; {nil или ссылка на 2-е звено}
while (q<>nil) and ok do
begin
ok:=p^.info<=q^.info;
p:=q; q:=q^.next {переход к след. паре}
end
end;
sort:=ok
end;
procedure out_spisok(l:list);
begin
while l<> nil do
begin
s:=l^.next;
write(l^.info,' ');
l:=s;
end;
writeln;
end;
begin
{формируем список}
s:=nil;
writeln('Введите количесто элементов списка');
readln(n);
for i:=1 to n do
begin
new(l);
l^.next:=s;
readln(x);
l^.info:=x;
s:=l;
end;
{выводим список на экран}
writeln('Введенный список');
out_spisok(l);
if sort(l) then writeln('Список отсортирован по алфавиту')
else writeln('Список не отсортирован по алфавиту');
{освобождаем динамическую память}
while l<> nil do
begin
s:=l^.next;
dispose(l);
l:=s;
end;
end.
2. type telem=...;
list=^node;
node=record
info : telem;
next : list
end;
Описать процедуру, которая вставляет в список L новый элемент Е1 перед первым вхождением элемента Е, если Е входит в L;
type telem=0..999;
list=^node;
node= record
info : telem;
next : list
end;
var s,l : list;
x,e,e1 : telem;
n,i : integer;
procedure insert( l : list; e,e1 : telem);
var p,q : list; eq : boolean;
begin { поиск звена с Е:}
p:=L; eq:=false;
while (p<>nil) and not eq do
if p^.info=e then eq:=true
else p:=p^.next;
if eq then { вставка Е1 перед Е}
begin {внимание-трюк: запись Е1 в звено p
вместо Е и вставка Е за звеном p:}
p^.info:=e1; new(q); q^.info:=e;
q^.next:=p^.next; p^.next:=q
end;
end;
procedure out_spisok(l : list);
begin
while l<> nil do
begin
s:=l^.next;
write(l^.info,' ');
l:=s;
end;
writeln;
end;
begin
{формируем список}
s:=nil;
writeln('Введите количесто элементов списка');
readln(n);
for i:=1 to n do
begin
new(l);
l^.next:=s;
readln(x);
l^.info:=x;
s:=l;
end;
{выводим список на экран}
writeln('Введенный список');
out_spisok(l);
writeln('Введите элемент, перед которым Вы хотите вставить число');
readln(e);
writeln('Введите элемент, который Вы хотите вставить в список');
readln(e1);
insert(l,e,e1);
writeln('Полученный список');
out_spisok(l);
{освобождаем динамическую память}
while l<> nil do
begin
s:=l^.next;
dispose(l);
l:=s;
end;
end.
3. Описать процедуру, которая удаляет из непустого списка l последний элемент.
type list=^node;
node= record
info : integer;
next : list
end;
var s,l : list;
x : integer;
n,i : integer;
procedure del(var l : list);
var p,q : list;
begin
if l=nil then {удалять нечего}
else if l^.next=nil {в списке один элемент} then
begin dispose(l);l:=nil end
else begin
{поиск предпослед.(p) и послед.(q) звеньев: }
p:=l; q:=p^.next;
while q^.next<>nil do
begin p:=q; q:=q^.next end;
{удаление последнего звена:}
dispose(q); p^.next:=nil
end;
end;
procedure out_spisok(l : list);
begin
while l<> nil do
begin
s:=l^.next;
write(l^.info,' ');
l:=s;
end;
writeln;
end;
begin
{формируем список}
s:=nil;
writeln('Введите количесто элементов списка');
readln(n);
for i:=1 to n do
begin
new(l);
l^.next:=s;
readln(x);
l^.info:=x;
s:=l;
end;
{выводим список на экран}
writeln('Введенный список');
out_spisok(l);
del(l);
writeln('Полученный список');
out_spisok(l);
{освобождаем динамическую память}
while l<> nil do
begin
s:=l^.next;
dispose(l);
l:=s;
end;
end.
4. Описать рекурсивную функцию или процедуру, которая:
а) определяет, входит ли элемент E в список L;
б) удаляет из списка L первое вхождение элемента Е, если такое есть;
а)
type list=^node;
node= record
info : integer;
next : list
end;
var s,l : list;
x,e : integer;
n,i : integer;
function memb(l : list; e : integer) : boolean;
var l1 : list;
begin
if l=nil then memb:=false
else if l1^.info=e then memb:=true
else memb:=memb(l1^.next,e)
end;
procedure out_spisok(l : list);
begin
while l<> nil do
begin
s:=l^.next;
write(l^.info,' ');
l:=s;
end;
writeln;
end;
begin
{формируем список}
s:=nil;
writeln('Введите количесто элементов списка');
readln(n);
for i:=1 to n do
begin
new(l);
l^.next:=s;
readln(x);
l^.info:=x;
s:=l;
end;
{выводим список на экран}
writeln('Введенный список');
out_spisok(l);
writeln('Введите интересующий Вас элемент');
readln(e);
if not(memb(l,e)) then writeln('Элемент ', e, ' входит в список')
else writeln('Элемент ', e, ' не входит в список');
{освобождаем динамическую память}
while l<> nil do
begin
s:=l^.next;
dispose(l);
l:=s;
end;
end.
б)
type list=^node;
node= record
info : integer;
next : list
end;
var s,l : list;
x,e : integer;
n,i : integer;
procedure delete(var l : list; e :integer);
var p : list;
begin
if l<>nil then
begin
if l^.info=e then {удалить первое звено}
begin p:=l; l:=L^.next; dispose(p) end
else {удалить Е из "хвоста" списка
и записать в 1-е звено ссылку на измененный "хвост":}
delete(l^.next,e)
end;
end;
procedure out_spisok(l : list);
begin
while l<> nil do
begin
s:=l^.next;
write(l^.info,' ');
l:=s;
end;
writeln;
end;
begin
{формируем список}
s:=nil;
writeln('Введите количесто элементов списка');
readln(n);
for i:=1 to n do
begin
new(l);
l^.next:=s;
readln(x);
l^.info:=x;
s:=l;
end;
{выводим список на экран}
writeln('Введенный список');
out_spisok(l);
writeln('Введите интересующий Вас элемент');
readln(e);
delete(l,e);
writeln('Полученный список');
out_spisok(l);
{освобождаем динамическую память}
while l<> nil do
begin
s:=l^.next;
dispose(l);
l:=s;
end;
end.