LAB / _2017-ЛАБОРАТОРНЫЕ РАБОТЫ 2 КУРС / _4_LISP
.docxЛАБОРАТОРНАЯ РАБОТА 4
Односвязные списки
1.Общие понятия
Списком называется такая линейная структура, элементами которой служат за-
писи с одним и тем же форматом, связанные друг с другом с помощью указателей,
хранащихся в самих элементах.
По числу указателей списки подразделяются на: односвязные, двусвязные и
многосвязные.
Односвязные списки, на основе которых построена данная лабораторная рабо-
та, имеют как минимум два поля: содержательное поле и поле с адресом
следующего элемента.
Двусвязные и двунаправленные списки дополнительно содержат поле с адресом
предыдущего элемента. В этом случае они также как и односвязные списки явля-
ются линейными динамическими структурами. В элементе двусвязного, но недву-
направленного списка могут содержатся ссылки на два других произвольных
элемента. В этом случае списки образуют уже нелинейную структуру.
На основе таких списков можно построить и бинарное дерево-типичную нелинейную
динамическую структуру. Ссылки в этой структуре будут указывать на два
элемента, находящиеся на более низком иерархическом уровне.
Многосвязные списки содержат адреса многих злементов. Частным случаем
многосвязного списка является граф. Многосвязные списки также как и деревья
являются основой нелинейных динамических структур.
2.Цель работы
Целью работы является изучение и отработка приемов и навыков использования
списков в организации алгоритмических структур. Машинная реализация этих
структур планируется на языке Турбо Паскаль или С++. Отводимое на эту работу
время- 4 часа.
3.Список заданий на выполнение работы
При выполнении заданий следует задействовать все стандартные операции
работы со списком, каждая из которых должна быть оформлена в виде отдельной
функции или процедуры, а также все доплнительные процедуры,необходимые
для выполнения кокретного задания, указанного ниже.
1. Разработать программу автоматического включения и выключения нового
элемента списка в алфавитном порядке.
2. Разработать программу автоматического включения и выключения нового
элемента списка по значению приоритета.
3. Разработать программу автоматического включения и выключения нового
элемента списка в хронологическом порядке.
4. Разработать программу включения и выключения из списков пачки элемен-
тов, обладающих каким либо свойством(например,введенных в сисок в какой нибудь
определенный день).
5.Разработать программу обмена элементов между двумя списками.
6.Разработать программу вычитания двух списков, расположив в полученном
списке элементы в алфавитном порядке.
7.Разработать программу объединения двух списков, расположив в полученном
списке элементы в алфавитном порядке.
8.Разработать программу объединения двух списков, расположив в полученном
списке элементы в хронологическом порядке.
9.Разработать программу вычитания двух списков, расположив в полученном
списке элементы в хронологическом порядке.
10.Разработать программу вычитания двух списков, расположив в полученном
списке элементы по значениям приоритетов.
11.Разработать программу объединения двух списков, расположив в полученном
списке элементы по значениям приоритетов.
12.Используя список, вывести из экзаменационной ведомости список сту-
дентов, получивших одинаковые оценки.
13. На основе односвязного списка организовать стек.
14. На основе кольцевого односвязного списка организовать стек.
15. На основе кольцевого односвязного списка организовать очередь.
16. На основе односвязного списка организовать очередь.
17. На основе односвязного списка разработать процедуру сложения больших
чисел.
18. На основе двухсвязанного списка разработать процедуру вычитания больших
чисел.
19. На основе связанного списка разработать процедуру вычисления синуса
большого угла.
20. На основе связанного списка разработать процедуру вычисления экспоненты
при большом параметре.
4.Пояснения к выполнению работы
Односвязный список также как и предыдущие структуры (см. вторую и третью
лабораторные работы) реализуется на основе рассмотренных ниже стандартных
операций со списками. Однако в отличии от них односвязный список наиболее
эффективно реализуется в динамической памяти. Поэтому работа со списками
в большой степени потребует приемов и навыков, отработанных в первой
лабораторной работе.
Вторым отличием от указанных структур является то обстоятельство, что
список практически невозможно построить, если не использовать составной
элемент (например, запись-в Паскале , а в С++ - структуру), так как
наряду с информационной частью, элемент списка должен содержать указатель
на соседний элемент.
К стандартным операциям, из которых любая задача, решаемая на основе
односвязных списков, строится как из кирпичиков можно отнести следующие:
-инизиализация списка;
- проверка "пуст ли список?" ;
- вообще говоря, проверка "полон ли список ?" ( эта проверка сов-
падает с проверкой "израсходована ли динамическая память ?");
- поиск требуемого элемента;
- включение нового элемента после заданного в список ( в
отличии от стека и очереди в списке новый элемент можно включить в любое место);
- выключение элемента из списка после заданного ( в отличии от
стека и очереди в списке элемент можно выключить из любого места).
ПРИЛОЖЕНИЕ 1
Пример программы с использованием списка
Пусть имеется список свяэанных элементов. Требуется просмотреть все элеме-
нты и сравнить их с первым. В случае совпадения соответствующий элемент иск-
лючается из списка. Если совпадение отсутствует, то первый элемент перемес-
тить в конец списка.
Для решения этой задачи представим стек в виде символьного массива. При
этом максимальное число элементов этого массива будет соответствовать верхней
границе стека. Эту задачу решает программа, текст которой приведен ниже.
program spicok;
uses crt;
type
zam=^per;
per =record {ЛИЧНОСТЬ}
key: byte;
fam : string[10];
nam : string[10];
next: zam;
end;
var
ch:char;
i:byte;
kod:byte;
h,d,c,first,newy:zam;
flag:boolean;
procedure del(flag:boolean;var first,r:zam );
forward;
{*****************************************************************
ввод данных
******************************************************************}
procedure inp(var d:zam);
var
ch :char;
first:zam;
begin
with d^ do
begin
writeln('Введите значение ключа');
readln(key);
writeln('Введите фамилию ');
readln(fam);
writeln('Введите имя ');
readln(nam);
end;
writeln;
end;
{****************************************************************
отображение данных
****************************************************************}
PROCEDURE oto(d:zam);
begin
with
d^ do
begin
write(key,' ',fam,' ',nam,' ');
end;
writeln;
end;
{**********************************************************
Добавление в список
**********************************************************}
procedure add(var first,r,ny:zam);
var c,b,newr :zam;
begin
new(newr);
inp(newr);
if r=nil then
begin
r^.next:=newr;
r:=newr;
r^.next:=nil;
end
else
begin
ny^.next:=r^.next;
r^.next:=ny;
end
end;{proc add}
{**********************************************************
Удаление из списка элемента, следующего
после элемента "r"
**********************************************************}
procedure del(flag:boolean;var first,r,:zam );
var c,b:zam;
f:string[15];
begin
if r<>nil then
begin
clrscr;
if flag then
begin
first:=first^.next;
end
else
begin
b:=r^.next;
r^.next:=b^.next;
end;
dispose(r);
end
else
writeln('удаление не возможно');
end;{proc del}
{**********************************************************
Просмотр списка c элемента, определяемого указателем "r"
**********************************************************}
procedure see(r:zam);
var b:zam;
{ z,y:integer;
h:boolean;
ch:char;}
begin
repeat
begin
oto(r);
r:=r^.next ;
end;
until r=nil;
end;{proc see}
{**** программа ******}
BEGIN
clrscr;
{Заполнение списка}
new(d);
first:=d;
repeat
inp(d);
write('Ввод закончен(y/n) ');
ch:=readkey;
if( ch in['y','Y']) then
begin
d^.next:=nil;
end
else
begin
new(c);
d^.next:=c;
d:=d^.next;
end;
until ch in['y','Y']; {СПИСОК ЗАПОЛНЕН}
d:=first;
see(d);
d:=first;
while d^.next<> nil do {удаление совпадающего элемента}
begin
h:=d^.next;
if (first^.key =h^.key) then
del(false,first,d)
else d:=h;
end; {окончание операции удаления совпадающего элемента}
{Вставка первого элемента после эемента с меньшим значением ключа}
d:=first;
repeat
h:=d^.next;
if (first^.key >h^.key)and(h<>nil) then
begin
new(newy);
newy^.key:=first^.key;
newy^.fam:=first^.fam;
newy^.nam:=first^.nam;
del(true,first,first);
add(first,h,newy);
end;
d:=h;
until h=nil; {конец вставки}
see(first);
repeat until keypressed;
END.
ПРИЛОЖЕНИЕ 2
Пример программы с использованием списка на С++
Ниже приведена программа на С++ для задачи, указанной в приложении 1.
/* !!=======================!!
!! односвязный список !!
!!=======================!! */
#include <dos.h>
#include <alloc.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <mem.h>
typedef
struct lis{
int key;
char fam[10];
char nam[10];
struct lis *next;
} ;
void input(struct lis *d);
void inputf(struct lis *d,struct lis *f);
void oto(struct lis *d);
void add(struct lis *r,struct lis *f);
void del(struct lis *first,struct lis *r,struct lis *ny);
void see(struct lis *r);
/* {**** программа ******} */
main()
{
char ch;
int i,kod;
struct lis rr;
struct lis *h,*d,*c,*first;
kod=1;
/*Заполнение списка */
d=(struct lis *) malloc(sizeof(struct lis));
first=d;
input(d);
ch='0';
while((ch!='y')&&(ch!='Y'))
{
printf("Ввод закончен(y/n)\n ");
scanf("%c",&ch);
scanf("%c",&ch);
if((ch=='y')||(ch=='Y'))
{
d->next=NULL;
}
else
{
c=(struct lis *) malloc(sizeof(struct lis));
input(c);
d->next=c;
d=c;
}
} /* СПИСОК ЗАПОЛНЕН */
d=first;
printf("Исходный вариант\n") ;
see(d);
d=first;
while (d->next!= NULL) /* удаление совпадающего элемента */
{
h=d->next;
if(first->key==h->key)
{del(first,h,d);
kod=2;
}
else d=h;
} /* окончание операции удаления совпадающего элемента */
/* Перемещение первого элемента в конец списка */
if(kod==1)
{ d=first;
while(d->next!=NULL)
d=d->next;
h=first;
first=first->next;
d->next=h;
h->next=NULL;
}
/* конец вставки */
printf(" Окончательный вариант\n");
see(first);
}
/* {*****************************************************************
ввод данных
***************************************************************** */
void input(struct lis *d)
{
printf("Введите значение ключа\n");
scanf("%d",&d->key);
printf("Введите фамилию ");
scanf("%s",d->fam);
printf("Введите имя ");
scanf("%s",d->nam);
printf("\n");
}
/* {*****************************************************************
ввод данных, соответствующих первому элементу
***************************************************************** */
void inputf(struct lis *newy,struct lis *f)
{
int i;
newy->key=f->key;
for(i=0;i<11;i++)
{ newy->fam[i]=f->fam[i];
newy->nam[i]=f->nam[i];
}
}
/* {****************************************************************
отображение данных
*************************************************************** */
void oto(struct lis *d)
{
printf(" %i %s %s %x",d->key,d->fam,d->nam,d->next);
printf("\n");
}
/* {**********************************************************
Добавление в список первого после найденного элемента
**********************************************************} */
void add(struct lis *r,struct lis *f)
{
struct lis *newr;
newr=(struct lis *) malloc(sizeof(struct lis));
inputf(&*newr,&*f);
newr->next=r->next;
r->next=newr;
} /*конец операции "добавления элемента" */
/* **********************************************************
Удаление из списка элемента с указателем "r":
элемент с указателем "ny" предшествует удаляемому
элементу
********************************************************** */
void del(struct lis *first,struct lis *r,struct lis *ny)
{ if (r==first)
first=first->next;
else
ny->next=r->next;
free(r);
} /* окончание операции del */
/* {**********************************************************
Просмотр списка c элемента, определяемого указателем "r"
**********************************************************} */
void see(struct lis *r)
{
for(;r!=NULL;)
{
oto(r);
r=r->next ;
}
} /*конец процедуры "просмотр" */