Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Занятие 3. Упорядочивание списка. Вставление элемента в середину списка.Содержание книги
Поиск на нашем сайте
Сформируем список целых чисел упорядоченный по неубыванию, т.е. каждый следующий элемент списка должен быть больше или равен предыдущему. Для решения этой задачи рассмотрим основные части алгоритма, который мы будем воплощать в программе. После ввода очередного числа с клавиатуры определяем его место в списке. Заметим, что при этом элемент может быть вставлен либо в начало списка, либо в конец его, либо во внутрь. Первый и второй случаи мы уже рассмотрели выше. Остановимся на третьем случае. Для того чтобы вставить в список элемент со значением Digit между двумя элементами, нужно найти эти элементы и запомнить их адреса (первый адрес – в переменной dx, второй – в рх), после чего установить новые связи с переменной, в которой хранится значение Digit. Графически это можно представить так:
Операторы, выполняющие данную задачу будут следующими:
New(x); x^.Data:= Digit; px^.Next:= x; x^.Next:= dx;
Приведем процедуру InsInto, которая ищет место в списке и вставляет элемент, переданный ей как параметр. В результате сразу получается упорядоченный список. Адрес первого элемента списка хранится в глобальной переменной Head.
Procedure InsInto(Digit: integer; Var Head: Ukazatel); Var dx, px, x: Ukazatel; Begin New(x); x^.Data:= Digit; x^.Next:= Nil; if Head = Nil then {Если список пуст, то вставляем первый элемент} Head:= x else {Если список не пуст, то просматриваем его до тех пор, пока не отыщется подходящее место для x^ или не закончится список} Begin dx:= Head; px:= Head; while (px<>Nil) and (px^.Data<=Digit) do Begin dx:= px; px:=px^.Next; End; if px=Nil then {Пройден весь список} dx^.Next:= x {Элемент добавляется в конец списка} else {Пройден не весь список} Begin x^.Next:= px; if px=Head then Head:= x {Вставляем в начало списка} else dx^.Next:= x; {Вставляем внутрь списка} End; End; End;
Задание. Создайте программу, формирующую упорядоченный список, вставив в нее рассмотренную выше процедуру и процедуру просмотра и вывода на экран элементов списка. Отладьте программу, добавьте комментарий, покажите учителю результат для оценки.
Занятие 4-5. Примеры задач, решаемых с помощью списка. Решение задач.
Задание. Просмотрите предложенные решения задач и приготовьтесь объяснить алгоритм их решения учителю. Если необходимо, то наберите программы на компьютере и просмотрите их действие.
Задача 1. Проверить есть ли и сколько раз встречается список М1 в списке М2.
Program BaranovA; Uses Crt; Type EXS = ^ S; S = Record Data: integer; Next: EXS; End; Var u, x, m1, m2: EXS; i, Kol: integer;
Procedure Poisk(Var x1, x2: EXS); Var m3, m4: EXS; Begin Kol:= 0; m3:= m1; m4:= m2; while m4 <> Nil do Begin if m4^.Data = m3^.Data then Begin m3:= m3^.Next; m4:= m4^.Next; if m3 = Nil then Begin Kol:= Kol+1; m3:= m1; End; End; else Begin m3:= m1; m4:= m4^.Next; End; End; End;
Procedure Init (Var u: EXS); Var y: EXS; Digit: integer; Begin Writeln('Введите список. Конец ввода – 0'); u:= Nil; Read(Digit); while Digit <> 0 do Begin New(y); y^.Next:= Nil; y^.Data:= Digit; if u = Nil then u:= y else x^.Next:= y; x:= y; Read(Digit); End; Writeln; End;
Procedure Print(X: EXS); Begin while X <> Nil do Begin Write(X^.Data: 5); X:= X^.Next; End; Readln; Writeln; End;
Begin ClrScr; Init(m1); Init(m2); Writeln('***Список 1***'); Print(m1); Writeln('***Список 2***'); Print(m2); Poisk(m1, m2); Writeln('Список 1 встречается в списке 2 ', Kol, ' раз(а)'); Readln; End.
Задача 2. Из текстового файла, состоящего из строк, сформировать список, запросить слово и удалить это слово из списка.
Program; Uses Crt; Type EXS = ^ Spisok; Spisok = Record Data: string; Next: EXS; End; Var Golova _ Spiska, Golova _ Spiska _ Udalen_: EXS; F: text; S, St: string;
Procedure Smotr(x: EXS); Begin TextColor(LightRed); Write('Ваш список...'); while x <> Nil do Begin Writeln (x^.Data,' '); x:= x^.Next; End; End;
Procedure Reading; Begin Reset (F); Writeln('Ваш файл...'); while no Eof(F) do Begin Readln (F, St); Writeln (St); End; close (F); End;
Procedure CreateFile; Begin Writeln('Создание файла'); Write('Введите имя файла...'); Readln(S); Assign (F, S); rewrite('Вводите текст в файл (окончание ввода - <Enter>'); Repeat Readln(St); Writeln (F, St); until St = ''; Write('Файл создан'); close (F); Reading; End;
Procedure Proverka; Var x, y, u: EXS; i: integer; Begin Reset (F); while not Eof (F) do Begin Readln (F, St[i]); while i < Length (St) do Begin New (x); x^.Next:= Nil; if (St[i] <> '') or (St[i] <> St[Length(St)]) then x^.Data:= x^.Data + St[i]; if u = Nil then u:= x else y^.Next:= x; y:= x; End; End; close (F); Smotr (u); End;
Begin ClrScr; TextColor (White); CreateFile; Proverka; End.
Выберите с учителем задачи для самостоятельного решения.
1. Написать программу, содержащую процедуру, которая меняет местами первый и второй элементы непустого списка. Если элементы не найдены, то выдать на экран соответствующие сообщение.
2. Написать программу, содержащую процедуру, которая меняет местами первый и пятый элементы непустого списка. Если элементы не найдены, то выдать на экран соответствующие сообщение.
3. Написать программу, содержащую процедуру, которая меняет местами первый и последний элементы непустого списка. Если элементы не найдены, то выдать на экран соответствующие сообщение.
4. Написать программу, содержащую процедуру, которая вставляет новый элемент перед каждым вхождением заданного элемента. Если элементы не найдены, то выдать на экран соответствующие сообщение.
5. Написать программу, содержащую процедуру, которая вставляет новый элемент за каждым вхождением заданного элемента. Если элементы не найдены, то выдать на экран соответствующие сообщение.
6. Написать программу, содержащую подпрограмму, которая проверяет на равенство списки М1 и М2.
7. Написать программу, содержащую функцию, которая определяет, входит ли список М1 в список М2. Предполагается, что списки существуют.
8. Написать программу, содержащую подпрограмму, которая копирует в конец непустого списка М его первый элемент. Если элементы не найдены, то выдать на экран соответствующие сообщение.
9. Написать программу, содержащую подпрограмму, которая копирует в начало непустого списка М его последний элемент. Если элементы не найдены, то выдать на экран соответствующие сообщение.
10. Написать программу, содержащую процедуру, которая копирует в список М за каждым вхождением заданного элемента все элемента списка М1.
11. Написать программу, содержащую процедуру, которая объединяет два упорядоченных по неубыванию списка М1 и М2 в один упорядоченный по неубыванию список, построив новый список М.
12. Написать программу, содержащую процедуру, которая объединяет два упорядоченных по неубыванию списка М1 и М2 в один упорядоченный по неубыванию список, сменив соответствующим образом ссылки в М1 и М2.
13. Написать программу, содержащую функцию, которая проверяет, упорядочены ли элементы списка по алфавиту.
14. Напишите программу сортировки существующего списка по алфавиту. В программе используйте подпрограммы.
15. Напишите программу, которая создавала бы файл целых чисел, а затем формировала список целых чисел файла. Создайте в конце списка элемент, содержащий сумму всех чисел файла. В программе используйте подпрограммы.
16. Напишите программу, которая создавала бы файл целых чисел, а затем формировала список целых чисел файла. Создайте список чисел, являющихся суммой соседних элементов. В программе используйте подпрограммы.
17. Напишите программу, которая создавала бы текстовый файл, а затем формировала список строк файла. Создайте список обратных строк. В программе используйте подпрограммы.
18. Напишите программу, которая создавала бы текстовый файл, а затем формировала список строк файла. Создайте отсортированный список строк. В программе используйте подпрограммы.
19. Напишите программу, которая создавала бы файл комбинированного типа, а затем формировала список, используя какое-либо поле записи. Создайте отсортированный список. В программе используйте подпрограммы.
20. Напишите программу, которая создавала бы файл комбинированного типа, а затем формировала список элементов файла. Создайте отсортированный по какому-либо полю список. В программе используйте подпрограммы.
|
||||
Последнее изменение этой страницы: 2016-08-12; просмотров: 189; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.117.8.177 (0.011 с.) |