Создание прямого односвязного списка



В прямом односвязном линейном списке связь устанавливается от i-го элемента к i+1.

Inf  
Link  
Inf  
Link  
Inf  
Link  
       i                             i+1                         i+2

Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  
Inf  
Link  


Type T = ^ Rec;

                   Rec = record

                   Inf : integer;

                   Link : T

                              End;

       VarP , Q : T ;

Пример: Создать односвязный линейный список, содержащий числа.

Сложить положительные элементы списка.

 

 

Inf  
Link  
Inf  
Link  
Inf  
Link  
                                            

 

 

 

 

Program Spisok11;

{создать односвязный линейный список, содержащий числа.

Сложить положительные элементы списка.}

UsesCrt;

Typeaa =^spisok;

spisok = record

zn:integer;

next:aa;

end;

Var

s,p:aa;

i,zna,kol, sum:integer;

// процедура добавление элемента в список

ProcedureAddSp;

var q:aa;

Begin

if s=nil then //создаетсяпервыйэлемент

Begin

New(p);

s:=p

End

Elsebegin

q:=p;

New(p);

q^.next:=p;

end;

p^.next:=nil;

Writeln('Введитезначение',i,' элемента');

readln(zna);

p^.zn:=zna;

end;

// функция определения конца списка

FunctionGoNext:boolean;

Begin

if p^.next <> nil then

Begin

p:=p^.next;

GoNext:=true;

End

elseGoNext:=false

end;

//функция освобождения памяти и вывода элементов списка

Function DisposeAll:boolean;

var q:aa;

Begin

p:=s;

while p<>nil do

Begin

q:=p^.next;

write(p^.zn,' ');

Dispose(p);

p:=q;

end ;

writeln;

writeln('Освобождениепамяти...');

DisposeAll:=true;

end;

 

begin//операторы основной программы

 

s:=nil; // nil- признак конца списка

writeln('Введите количество элементов списка');

readln(kol);

for i:=1 to kol do//созданиесписка

Addsp;

 

p:=s; //установка р на начало списка

Repeat

if p^.zn>0 then

sum:=sum+p^.zn; //суммируем положительные элементы

until not gonext;

 

ifsum=0 then writeln('вспискенетполож. элементов')

else writeln('sum=',sum);

DisposeAll;

End.

Порядок выполнения работы:

  1. Для загрузки интегрированной среды запустите файл  - РascalABC.exe.
  2. Создайте новый файл для ввода текста программы: меню Файлà пункт Новый(Ctrl+N) или кнопка на панели инструментов Новый файл.
  3. В окне для ввода текста программы наберите свою программу. После заголовка программы в комментарии напишите условие задания.
  4. Запустите программу на выполнение: меню Программа àпункт Выполнить или кнопка Выполнить на панели инструментов
  5. Сохраните программу: меню Файлàпункт Сохранить какàукажите место сохранения файла и имя файла.àV:\группа\студент\задача _номер

Содержание отчёта:

15. Шифр работы

16. Название работы

17. Цель работы

18. Условие задачи

19. Блок-схема алгоритма

20. Текст программы

21.

Из окна вывода  
Исходные данные

             Результат решения

 

Контрольные вопросы

1. Что называют динамическими переменными, каковы причины их использования?

2. В чем особенность объявления данных динамической структуры?

3. Что выполняет операция разыменования?

4. С помощью каких процедур происходит распределение памяти под динамические переменные?

5. Какие состояния может принимать указательная переменная?

6. В чем различие между состоянием nil и неопределенным состоянием?

7. В каких случаях указатель может находиться в неопределенном состоянии?

8. Какие действия выполняют процедуры NEW и DISPOSE?

9. В чем сходство и различие между линейными и кольцевыми списками?

10. Как добавить и удалить элемент очереди?

11. Сколько указателей требуется для работы со стеком?

Индивидуальные задания:

Вариант № 1

Создать файл символов. Разместить элементы файла в динамической памяти. Описать функцию, которая добавит в начало списка 1 или несколько элементов.

 

Вариант № 2

Создать файл вещественных чисел. Разместить элементы файла в динамической памяти. Вставить в список L новый элемент F1 перед первым вхождением максимального элемента.

 

Вариант № 3

Создать файл целых чисел. Разместить элементы файла в динамической памяти. Поменять местами первый и последний элементы списка.

 

Вариант № 4

Создать файл вещественных чисел. Разместить элементы файла в динамической памяти.. Написать программу, которая по данному списку L строит два новых списка:

L1 – из положительных элементов.

L2 – из остальных элементов.

 

Вариант № 5

Создать файл символов. Разместить элементы файла в динамической памяти. Написать программу, которая вставляет в список L пару новых элементов F1 и F2 перед последним элементом.

 

Вариант № 6

 Создать файл вещественных чисел. Разместить элементы файла в динамической памяти. Описать функцию, значением которой является первый четныйэлемент связного списка или 0, если такого элемента нет.

 

Вариант № 7

Создать файл целых чисел. Разместить элементы файла в динамической памяти. В связном списке удалить все числа, меньше заданного.

 

Вариант № 8

Создать файл вещественных чисел. Разместить элементы файла в динамической памяти. Добавить элемент в конец связного списка, и замкнуть список циклически.

 

Вариант № 9

 Создать файл вещественных чисел. Разместить элементы файла в динамической памяти. Определить количество ненулевых элементов связного списка и содержимое этих элементов сложить.

 

Вариант № 10

Создать два файла вещественных чисел. Разместить элементы файлов в динамической памяти. Определить, тождественны ли 2 списка L1 и L2 по значению своих элементов.

 

Вариант № 11

Создать файл целых чисел. Разместить элементы файла в динамической памяти. В связном списке, элементы с минимальным значением перенести в начало списка.

 

Вариант № 12

Создать файл символов. Разместить элементы файла в динамической памяти. Создать строку из элементов списка с четными кодам.

 

Вариант № 13

Создать текстовый файл в котором слова разделены пробелами. В связанный список переписать слова, начинающиеся и оканчивающиеся одной и той же буквой. Упорядочить связанный список по возрастанию.

 

Вариант № 14

Создать связанный список, состоящий из слов, находящихся в текстовом файле. Слова могут разделятся (, . ; ! ? и пробелом). Написать программу, подсчитывающую количество слов списка, которые совпадают с последним словом.

 

Вариант № 15

Создать файл целых чисел. Разместить элементы файла в динамической памяти. Из связного списка, содержащего целые числа, удалить все положительные.

 

Вариант № 16

Создать файл целых чисел. Разместить элементы файла в динамической памяти. Написать программу, которая удаляет из списка Lвторой положительный элемент если такой есть.

 

Вариант № 17

Создать файл целых чисел. Разместить элементы файла в динамической памяти. Написать программу, которая вставляет новый элемент Е, после первого отрицательного элемента списка L.

 

Вариант № 18

Создать текстовый файл целых чисел. Разместить элементы файла в динамической памяти. Написать программу, которая удаляет из списка Lпоследний отрицательный элемент кратный 3.

 

Вариант № 19

Создать текстовый файл целых чисел. Разместить элементы файла в динамической памяти. В связный список вставить 0 после последнего элемента с отрицательным значением

 

Вариант № 20

Создать файл символов. Разместить элементы файла в динамической памяти. Рассортировать элементы связанного списка в алфавитном порядке.

 

Вариант № 21

Создать файл целых чисел. Разместить элементы файла в динамической памяти.    В связном списке поменять местами элемент с максимальным значением с последним.

 

Вариант № 22

Создать файл вещественных чисел. Разместить элементы файла в динамической памяти.

Список разделить на два. Первый - содержащий целые положительные числа. Второй- четные отрицательные числа.

 

Вариант № 23

Создать файл целых чисел. Разместить элементы файла в динамической памяти. Описать процедуру, исключающую из списка требуемые элементы. Исключение осуществляется запросом: Удалить? Y/N

Вариант № 24

Создать файл целых чисел. Разместить элементы файла в динамической памяти и замкнуть в цикл. В циклический список добавить элемент, разорвав цикл. Новый элемент должен быть последним в цепочке.

 

Вариант № 25

Создать файл символов. Разместить элементы файла в динамической памяти. Добавить в список L в требуемую позицию Р список из К элементов.

 

Вариант № 26

Создать файл целых чисел. Разместить элементы файла в динамической памяти. Определить адреса максимальных и минимальных элементов списка.

 

Вариант № 27

Создать файл символов. Разместить элементы файла в динамической памяти. Добавить через один элемент в связанный список L элемент F.

 

Вариант № 28

Создать файл целых чисел. Разместить элементы файла в динамической памяти.   Из связного списка исключить повторяющиеся элементы.

 

Вариант № 29

В текстовом файле представленные данные типа byte, integer, real. Считать их в динамическую память: byte - в список L1, integer - в список L2, real - в список L3.

 

Вариант № 30

Создать файл, содержащий следующую информацию:

  • фамилия имя
  • пол

В динамической памяти разместить элементы, которые будут содержать фамилии девушек, заканчивающихся на согласный звук.

 

Вариант № 31

Создать файл целых чисел. Разместить элементы файла в динамической памяти. В связный список вставить 0 перед элементом с максимальным значением

 

Вариант № 32

Создать два файла целых чисел, упорядоченные по возрастанию. Разместить элементы файлов в динамической памяти в двух связанных списках. Объединить списки в один, не нарушая упорядоченности.

 

Вариант № 33

Связанный список состоит из слов текстового файла. Написать программу, которая проверяет упорядочены ли элементы списка по алфавиту.

 

Вариант № 34

Создать файл целых чисел. Разместить элементы файла в динамической памяти. В связанном списке поменять местами первый элемент и элемент с минимальным значением.

 

Вариант № 35

Создать файл символов. Разместить элементы файла в динамической памяти. Написать программу, которая проверяет, есть ли в списке L хотя бы два одинаковых элемента.

Вариант №  36

Связный список состоит из слов текстового файла. Слова в файле разделены пробелом, переносов слов нет. Написать программу, подсчитывающую количество слов списка, которые начинаются с той же буквы, что и следующее слово.

 

Вариант № 37

Создать файл вещественных чисел. Разместить элементы файла в динамической памяти. Найти среднее арифметическое положительных элементов списка.

 

Вариант № 38

Создать файл вещественных чисел. Разместить элементы файла в динамической памяти. Вставить список L, элементы которого упорядочены по убыванию, новый элемент F так чтобы сохранить упорядоченность.

 

Вариант № 39

Создать файл AX.dat содержащий вещественные числа. Для каждой тройки чисел найти площадь треугольника, если считать, что числа являются сторонами этого треугольника. (Считается, что не из каждой тройки чисел можно составить треугольник). В динамической памяти разместить связанный список, который будет содержать длины сторон и площадь треугольника.

 

Вариант № 40

Из текстового файла выбрать те слова, которые отличаются от первого слова и первая буква слова входит в него еще раз и разместить их в динамической памяти. Созданный список отсортировать в алфавитном порядке. Слова в файле разделены пробелом.

Вариант № 41

 

Создать файл, содержащий следующую информацию о каждом студенте:

  • Фамилия;
  • Дата рождения (год);
  • № группы;
  • пол.

В динамической памяти разместить элементы, которые будут содержать фамилии студентов призывного возраста, заданной специальности.


Вариант № 42

Файл VED.dat содержит список учащихся, занимающихся в спортивных секциях.

В списке указаны следующие сведения: фамилия, год рождения, пол, вид спорта.

В динамической памяти разместить элементы, которые будут содержать список девушек заданного возраста по заданному виду спорта.

 

Вариант № 43

Используя подпрограмму функцию найти строку текстового файла, имеющую максимальную длину. Слова этих строк разместить в динамической памяти. Слова в файле разделены пробелом.

 

Вариант № 44

Создать файл целых чисел. Разместить элементы файла в динамической памяти. Заменить цифру на следующую по величине (‘9’ заменить на ‘0’).

 

Вариант № 45

Создать файл вещественных чисел. Разместить элементы файла в динамической памяти

Определить сумму элементов, стоящих между максимальным и минимальным элементами списка, включая оба эти значения. Повторяющихся элементов нет.


Вариант № 46

Создать файл символов. В динамической памяти разместить строчные гласные буквы, стоящие на нечетных местах в файле.

 

Вариант № 47

Создать файл записей:

  • фамилия учащегося;
  • дата рождения xx.xx.xx.

Разместить элементы файла в динамической памяти. Упорядочить элементы списка порядке возрастания месяца рождения.

 

Вариант № 48

В текстовом файле записана последовательность целых чисел, разделенных пробелами. В динамической памяти разместить элементы, которые будут содержать простые числа.

 

Вариант № 49

В файле типа char содержатся цифры и знаки ‘*’ и ‘/’. В динамической памяти разместить элементы файла ,а затем удвоить каждую цифру.

 

Вариант № 50

Создать файл , содержащий следующую информацию о студентах.

  • фамилия имя отчество;
  • семестровые оценкаи;
  • группа.

В динамической памяти разместить элементы, которые будут содержать только сведения о тех студентах, которые успешно сдали все экзамены.

 

Вариант № 51

Создать файл символов. Разместить элементы файла в динамической памяти в два списка: гласные буквы и согласные и упорядочить списки по алфавиту.

 

Вариант № 52

Создать файл , содержащий следующую информацию : фамилия автора, название книги,

год издания. В динамической памяти разместить элементы, которые будут содержать

книги с интересующим названием и заданного года издания.

 

Вариант № 53

Создать файл , содержащий следующую информацию: фамилия, возраст, пол

В динамической памяти разместить связанный список содержащий фамилии самых старших по возрасту с указанием пола.

 

Вариант № 54

Создать файл , содержащий сведения о владельцах автомоблей: фамилии владельца, марка автомобиля и дата покупки. Разместить элементы файла в динамической памяти.

Упорядочить список по датам покупки.

 

Вариант № 55

Создать файл , содержащий следующую информацию : фамилия владельца автомобиля,

регион регистрации. В динамической памяти разместить элементы, которые будут содержать фамилии владельцев автомобилей, зарегистрированных в 78 и 47 регионах.

 

Вариант № 56

Создать символьный файл f. Разместить элементы файла в динамической памяти в обратном порядке.

 

Вариант № 57

Создать текстовый файл содержащий целые числа, разделенные пробелом. Разместить в динамической памяти только элементы, встречающиеся один раз.

 

Вариант № 58

Создать файл , содержащий следующую информацию : название товара и его цена. Разместить элементы файла в динамической памяти и отсортировать список в порядке возрастания стоимости.

 

 


 

Лабораторная работа №8


Дата добавления: 2018-06-26; просмотров: 60; ЗАКАЗАТЬ РАБОТУ