Методические указания для выполнения лабораторных работ и курсовой работы содержание

Вид материала

Методические указания

Содержание 10Лабораторная работа № 9. Односвязные списки 2.Цель работы 4. Варианты заданий для второго этапа 4.Пояснения к выполнению работы

Подобный материал:

• Методические указания по выполнению курсовых работ для студентов заочной формы обучения, 300.18kb.
• Рабочая программа, методические указания по выполнению курсовой работы, темы курсовых, 1694.43kb.
• Методические указания по выполнению курсовой работы Составитель Виничук, 2013.82kb.
• Методические указания для выполнения курсовой работы по дисциплине «Макроэкономика», 976.03kb.
• Методические указания к выполнению лабораторных работ по дисциплине «Интеллектуальные, 653.36kb.
• Методические указания для выполнения курсовой работы по дисциплине: «Метрология, стандартизация, 170.43kb.
• Методические указания для выполнения курсовой работы по дисциплине «Теория принятия, 547.84kb.
• Методические указания для ее выполнения по дисциплине «финансы» 2008-2009 уч. Год (для, 247.31kb.
• Методические указания по содержанию и организации выполнения курсовой работы по дисциплине, 1445.93kb.
• Петроченко Любовь Викторовна Учебно методические указания, 199.16kb.

10Лабораторная работа № 9. Односвязные списки

1.Общие понятия


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

По числу указателей списки подразделяются на: односвязные, двусвязные и многосвязные.

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

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

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

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


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


Целью работы является изучение и отработка техноогии использования списков в организации алгоритмических структур. Машинная реализация этих структур планируется на языке Турбо Паскаль или С++. Отводимое на эту работу время- 4 часа.

Работа выполняется в два этапа. На первом этапе создается модуль, который описан по соответствующему формату (см. лекции) и содержит полную информацию о связанном списке (т.е. его описание и функции, изменяющие состояние).Далее объединить этот модуль с основной программой и выполнить соответствующий из нижепредставленных простых вариантов.

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


3 Список вариантов для первого зтапа

Используя стек, выполнить следующие варианты:

1. Создать один элемент связанного списка и затем добавить второй элемент;

2. Создать связанный список из двух элементов и затем исключить второй элемент связанного списка;

3. Создать связанный список из двух элементов и затем исключить первый элемент связанного списка;

4. Создать связанный список из двух элементов и поменять их местами;

5. Создать связанный список из трех элементов;

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

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

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

9. Создать связанный список из трех элементов и затем поменять местами второй элемент и первый элемент;

10. Создать связанный список из трех элементов и затем поменять местами второй и третий элементы;

11. Создать связанный список из трех элементов и затем поменять местами первый и третий элементы;

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


4. Варианты заданий для второго этапа

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

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

2. Разработать программу автоматического включения и выключения нового элемента списка по значению приоритета.

3. Разработать программу автоматического включения и выключения нового элемента списка в хронологическом порядке.

4. Разработать программу включения и выключения из списков пачки элементов, обладающих каким либо свойством (например, введенных в список в какой нибудь определенный день).

5.Разработать программу обмена элементов между двумя списками.

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

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

8.Разработать программу объединения двух списков, расположив в полученном списке элементы в хронологическом порядке.

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

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

11.Разработать программу объединения двух списков, расположив в полученном списке элементы по значениям приоритетов.

12.Используя список, вывести из экзаменационной ведомости список студентов, получивших одинаковые оценки.

13. На основе односвязного списка организовать стек.

14. На основе кольцевого односвязного списка организовать стек.

15. На основе кольцевого односвязного списка организовать очередь.

16. На основе односвязного списка организовать очередь.


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

#include

#include

#include

#include

#include


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 ;

}

} //конец процедуры "просмотр"