Размещено на http://www.allbest.ru/

Введение

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

Список, в котором каждый элемент имеет ссылки на последующий и предыдущий (в нашем случае, на n-ый), называется двусвязным. Его основное отличие от односвязного - возможность просмотра его в обоих направлениях. Основное применение двусвязных списков - создание упорядоченных последовательностей элементов при достаточно частых операциях включения и исключения. В данной курсовой работе, в части I, строится списочная структура, состоящая из трехнаправленного и двух однонаправленных списков, связанных между собой. У каждого элемента трехнаправленного списка присутствует три поля. Первое и второе поля - для связи с элементами однонаправленных списков, третье - для связи элементов списка. Первое поле элемента однонаправленного списка - информационное, а второе используется для связи элементов списка.

Двоичное дерево является наиболее удобной структурой для реализации двоичного поиска. Напомню основное свойство такого дерева: если вершина дерева содержит некоторое значение, то в левом поддереве содержатся значения, меньшие данного, а в правом - большие данного. Алгоритмы поиска и включения в такое дерево являются рекурсивными. В данной курсовой работе, в части II, строится дерево двоичного поиска для заданного множества целых чисел и нумеруются его вершины в соответствии с их обходом снизу.

Часть I. Теоретические сведения. Односвязные и двусвязные списки

1.1 Линейные динамические структуры - односвязные и двухсвязные списки

Динамическая структура характеризуется следующими чертами:

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

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

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

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

Поле указателя хранит адрес следующего элемента списка. Пользуясь указателем, можно получить доступ к следующему элементу списка, а из следующего списка - к очередному элементу и т.д., пока не будет достигнут последний элемент. Поле указателя последнего элемента должно содержать специальный признак нулевого или пустого указателя, свидетельствующий о конце списка. Линейность односвязного списка вытекает из линейной логически упорядоченности его элементов: для каждого элемента (кроме первого и последнего) имеются единственный предыдущий и единственный следующий элементы.

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

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

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

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

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

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

1.2 Листинг программы на языке Си

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#include <stdlib.h>

# define sp struct edin

sp

{

int info;

sp *right;

sp *down;

};

void main()

{

sp *s,*d,*t1,*t2,*p1,*p2;

int FL,k,n,a,ST,i,q,w;

char y,ch;

textcolor(2);

clrscr();

gotoxy(20,3);

printf("Kursovaya rabota po SAODu\n");

gotoxy(20,4);

printf("Vypolnil student II kursa FMRM S-610 Vishyakov Sergey\n\n");

gotoxy(25,5);

printf("Variant # 3\n ");

getch();

printf("\n");

printf(" Vvedite posledovatelnost chisel dlya zapolneniya ");

printf("spisochnoi structury\n");

printf(" Priznak okonchaniya oboih spiskov - vvod 0\n");

scanf("%d",&a);

if (a==0)

{

scanf("%d",&a);

if (a!=0)

{

k=1;

FL=0;

s=NULL;

while (a!=0)

{

t2=(sp*)malloc(sizeof(sp));

t2->right=NULL;

t2->info=a;

t2->down=NULL;

if (s==NULL)

{

s=t2;

p2=s;

}

else

{

p2->right=t2;

p2=t2;

}

scanf("%d",&a);

k=k+1;

}

}

else

{

printf(" Spisok ne byl sozdan!");

FL=2;

}

}

else /* teper esli est niznii*/

if (a!=0)

{

n=1;

d=NULL;

while (a!=0)

{

t1=(sp*)malloc(sizeof(sp));

t1->right=NULL;

t1->info=a;

t1->down=NULL;

if (d==NULL)

{

d=t1;

p1=d;

}

else

{

p1->right=t1;

p1=t1;

}

scanf("%d",&a);

n=n+1;

}

scanf("%d",&a);

if (a!=0)

{

k=1;

FL=0;

s=NULL;

t1=d;

while (a!=0)

{

t2=(sp*)malloc(sizeof(sp));

t2->right=NULL;

t2->info=a;

if (k<=n)

t2->down=t1;

else

t2->down=NULL;

if (s==NULL)

{

s=t2;

p2=s;

}

else

{

p2->right=t2;

p2=t2;

}

scanf("%d",&a);

k=k+1;

p1=t1;

t1=p1->right;

}

}

else

{

printf("\n Verhnii spisok pust !");

FL=1;

}

}/* Sozdau stundartnii spisok */

getch();

printf("\n");

textcolor(8);

printf("\nSozdanaya spisochnaya structura:\n");

p2=s;

p1=d;

gotoxy(5,14);

q=wherex();

w=wherey();

if (FL==2)

printf("\n Spisok ne byl sozdan! ");

if (FL==1)

{

printf("%d",p1->info);

for (i=1;i<n-1;i++)

{

p1=p1->right;

printf(" --> ");

printf("%d",p1->info);

}

printf(" --> ");

printf("nil");

}

if (FL==0)

{

if (d==NULL)

{

printf("%d",s->info);

q=wherex();

w=wherey();

gotoxy(q-1,w+2);

printf("|");

gotoxy(q-1,w+3);

printf("Y");

gotoxy(q-1,w+5);

printf("nil");

gotoxy(q,w);

for(i=1;i<k-1;i++)

{

p2=p2->right;

printf(" --> ");

printf("%d",p2->info);

q=wherex();

w=wherey();

gotoxy(q-1,w=2);

printf("|");

gotoxy(q-1,w+3);

printf("Y");

gotoxy(q-1,w+5);

printf("nil");

gotoxy(q,w);

}

printf(" --> ");

printf("nil");

}

else

{

if (k>=n)

{

for (i=0;i<n;i++)

{

printf("%d",p2->info);

printf(" --> ");

q=wherex();

w=wherey();

gotoxy(q-6,w+2);

printf("|");

gotoxy(q-6,w+3);

printf("Y");

gotoxy(q-6,w+5);

printf("%d",p1->info);

printf(" --> ");

gotoxy(q,w);

p2=p2->right;

p1=p1->right;

}

gotoxy(q-6,w+5);

printf("nil ");

gotoxy(q,w);

for (i=n;i<k-1;i++)

{

printf("%d",p2->info);

printf(" --> ");

q=wherex();

w=wherey();

gotoxy(q-6,w+2);

printf("|");

gotoxy(q-6,w+3);

printf("Y");

gotoxy(q-6,w+5);

printf("nil ");

gotoxy(q,w);

p2=p2->right;

}

}

if (n>k)

{

for(i=0;i<k;i++)

{

printf("%d",p2->info);

printf(" --> ");

q=wherex();

w=wherey();

gotoxy(q-6,w+2);

printf("|");

gotoxy(q-6,w+3);

printf("Y");

gotoxy(q-6,w+5);

printf("%d",p1->info);

printf(" --> ");

gotoxy(q,w);

p2=p2->right;

p1=p1->right;

}

printf("nil ");

gotoxy(q-6,w+5);

}

for(i=k+1;i<n-1;i++)

{

printf("%d",p1->info);

printf(" --> ");

p1=p1->right;

}

printf("nil ");

}

}/* zakryvaet fl0*/

printf("\n");

printf("\n");

textcolor(2);

y='y';

while ((y!='n')&& (y!='N'))

{

gotoxy(4,25);

printf(" Vvedite upravlyaushchuu posledovatelnost (vniz(z) ili vpravo(v)):\n");

printf(" Dlya vyhoda nazmite Esc\n");

printf("\n");

p1=d;

p2=s;

ch=getch();

ST=FL;

while (ch!=27)

{

switch(ch)

{

case 'z':

{

if(FL==2)

printf("\n Spiska net \n");

if(FL==1)

printf (" Perehod vniz ne vozmozen \n");

if(FL==0)

{

if (p2->down!=NULL)

{

printf("\n");

printf(" Perehod vniz\n");

p1=p2->down;

printf("%d ",p1->info);

ST=0;

FL=1;

}

else

printf(" Perehod ne vozmozen \n");

}

break;

}

case 'v':

{

if(FL==2)

printf(" Spiska net");

if(FL==0)

{

if(p2->right!=NULL)

{

p2=p2->right;

printf("--> |%d ",p2->info," |");

}

else

printf(" Konec verhnego spiska !");

}

if (FL==1)

{

if (p1->right!=NULL)

{

p1=p1->right;

printf("--> | %d ",p1->info,"|");

}

else

printf("Konec niznego spiska!");

}

break;

}

default:

printf("Vvedite vniz(z) ili vverh(v)!!!");

}/* Zakryvaet switch*/

ch=getch();

}/* While pomenshe */

FL=ST;

printf(" \n Zelaete prodolzit? (y/n)\n");

y=getch();

}/* Samii bolshoi while */

}/* okonchanie programmy*/

1.3 Листинг программы на языке Паскаль

program spisok;

uses crt;

type

sp=^edin;

edin=record

info:integer;

right:sp;

down:sp;

end;

var s,t1,p1,t2,p2,d:sp;

q,w,z,v,FL,k,n,a,ST,i:integer;

y,ch:char;

begin

textcolor(3);

clrscr;

gotoxy(20,3);

writeln('Kursovaya rabota po SAODu');

gotoxy(20,4);

writeln(' Vypolnil student II kursa FMRM S-610 Vishyakov Sergey ');

gotoxy(25,5);

writeln(' Variant # 3');

writeln;

writeln(' vvedite posledovatelnost chisel');

writeln(' okonchanie kazdogo spiska 0:');

read(a);

if a=0 then

begin

read(a);

if a<>0 then

begin

k:=1;

FL:=0;

s:=nil;

while a<>0 do

begin

new(t2);

t2^.right:=nil;

t2^.info:=a;

t2^.down:=nil;

if s=nil then

begin

s:=t2;

p2:=S;

end

else

begin

p2^.right:=t2;

p2:=t2;

end;

read(a);

k:=k+1;

end;

end {esli sush. verhnii spisok}

else

begin

writeln(' spisok ne byl sozdan!');

FL:=2;

end;

end

else

if a<> 0 then

begin

n:=1; {*********** sozdau niznii spisok ************************}

d:=nil;

while a<>0 do

begin

new(t1);

t1^.right:=nil;

t1^.info:=a;

t1^.down:=nil;

if d=nil then

begin

d:=t1;

p1:=d;

end

else

begin

p1^.right:=t1;

p1:=t1;

end;

read(a);

n:=n+1;

end; {*********************************************}

read(a);

if a<>0 then

begin

k:=1;

FL:=0;

s:=nil;

t1:=d;

while a<>0 do

begin

new(t2);

t2^.right:=nil;

t2^.info:=a;

if k<=n then

t2^.down:=t1

else

t2^.down:=nil;

if s=nil then

begin

s:=t2;

p2:=s;

end

else

begin

p2^.right:=t2;

p2:=t2;

end;

read(a);

k:=k+1;

p1:=t1;

t1:=p1^.right;

end;

end {esli sush. verhnii spisok}

else

begin

writeln('Verhnii spisok pust!');

FL:=1;

end;

end;

readln; {**************************Upravlenie**************************}

{_______________________Vyvozu spisok ____________ }

writeln;

textcolor(2);

writeln (' Sozdannaya spisochnaya structura: ');

p2:=s;

p1:=d;

gotoxy(5,14);

q:=wherex;

w:=wherey;

if FL=2 then

writeln('Spisok ne byl sozdan ');

if FL=1 then

begin

write(p1^.info);

for i:=2 to N-1 do

begin

p1:=p1^.right;

write(' --> ',p1^.info);

end;

write(' -->','nil');

end;

if FL=0 then

begin

if d=nil then

begin

write(s^.info);

q:=wherex;

w:=wherey;

gotoxy(q-1,w+2);

write('|');

gotoxy(q-1,w+3);

write('Y');

gotoxy(q-1,w+5);

write('nil');

gotoxy(q,w);

for i:=2 to k-1 do

begin

p2:=p2^.right;

write(' --> ',p2^.info);

q:=wherex;

w:=wherey;

gotoxy(q-1,w+2);

write('|');

gotoxy(q-1,w+3);

write('Y');

gotoxy(q-1,w+5);

write('nil');

gotoxy(q,w);

end;

write(' --> ','nil');

end

else

begin

if K>=n then

begin

for i:=1 to n do

begin

write(p2^.info,' --> ');

q:=wherex;

w:=wherey;

gotoxy(q-6,w+2);

write('|');

gotoxy(q-6,w+3);

write('Y');

gotoxy(q-6,w+5);

write(p1^.info,' --> ');

gotoxy(q,w);

p2:=p2^.right;

p1:=p1^.right;

end;

gotoxy(q-6,w+5);

write('nil');

gotoxy(q,w);

for i:=n+1 to k-1 do

begin

write(p2^.info,' --> ');

q:=wherex;

w:=wherey;

gotoxy(q-6,w+2);

write('|');

gotoxy(q-6,w+3);

write('Y');

gotoxy(q-6,w+5);

write('nil');

gotoxy(q,w);

p2:=p2^.right;

end;

write('nil');

end;

if n>k then

begin

for i:=1 to k-1 do

begin

write(p2^.info,' --> ');

q:=wherex;

w:=wherey;

gotoxy(q-6,w+2);

write('|');

gotoxy(q-6,w+3);

write('Y');

gotoxy(q-6,w+5);

write(p1^.info,' --> ');

gotoxy(q,w);

p2:=p2^.right;

p1:=p1^.right;

end;

write('nil');

q:=wherex;

w:=wherey;

gotoxy(q-3,w+5);

for i:=k to n-1 do

begin

write(p1^.info,' --> ');

p1:=p1^.right;

end;

write('nil');

end;

end;

end;

writeln;

{_______________________________________________}

writeln;

textcolor(3);

writeln;

y:='y';

while (y<>'n')and(y<>'N') do

begin

gotoxy(5,22);

write(' Vvedite upravlyaushchuu posledovatelnost (vniz ili vpravo):');

gotoxy(10,24);

write(' Dlya vyhoda nazmite Esc'); writeln;

p1:=d;

p2:=s;

ch:=readkey;

ST:=FL;

while (ch<>#27) do

begin

case ch of

#80:

begin

if FL=2 then writeln(' Spiska net');

if Fl=1 then writeln(' Perehod vniz nevozmozen');

if FL=0 then

begin

if p2^.down<>nil then

begin

writeln;

writeln(' Perexod vniz');

p1:=p2^.down;

writeln(' ',p1^.info);

ST:=0;

Fl:=1;

end

else

writeln(' Perexod nevozmozen');

end;

end; {-->}

#77:

begin

if FL=2 then writeln(' Spiska net');

if Fl=0 then

begin

if (p2^.right)<> nil then

begin

p2:=p2^.right;

write('--> |',p2^.info,'|');

end

else

writeln(' Konec verhnego spiska');

end;

if Fl=1 then

begin

if p1^.right<>nil then

begin

p1:=p1^.right;

write(' --> |',p1^.info,'|');

end

else

writeln(' Konec niznego spiska');

end;

end;

end;

ch:= readkey;

end;

FL:=ST;

writeln(' Zelaete prodolzit? (y/n)');

readln(y);

end;

end.

1.4 Пример расчетов

Kursovaya rabota po SAODu

Vypolnil student II kursa FMRM S-610 Vishyakov Sergey

Variant # 3

Vvedite posledovatelnost chisel dlya zapolneniya spisochnoi structury

Priznak okonchaniya oboih spiskov - vvod 0

1 34 56 3 0 21 7 2 5 8 92 14 0

Sozdanaya spisochnaya structura:

21--> 7--> 2--> 5--> 8--> 92--> 14--> nil

| | | | | | |

Y Y Y Y Y Y Y

1--> 34--> 56--> 3--> nil--> nil--> nil

Vvedite upravlyaushchuu posledovatelnost (vniz(z) ili vpravo(v)):

Dlya vyhoda nazmite Esc

--> | 7 |--> | 2 |

Perehod vniz

56 --> | 3 | Konec niznego spiska !

Perehod vniz ne vozmozen

Zelaete prodolzit? (y/n)

1.5 Блок схема



1.6 Дескриптор списка

Часть II. Теоретические сведения: Нелинейные связные структуры

2.1 Деревья как частный случай многосвязных списков

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

Наиболее общий вид многосвязной структуры - многосвязная структура, которая характеризуется следующими свойствами:

1. Каждый элемент структуры содержит произвольное число направленных связок с другими элементами (или ссылок на другие элементы).

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

3. Каждая связка в структуре имеет не только направление, но и вес.

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

Сетевые структуры широко применяются при организации банков данных, систем управления базами данных, в системах программ имитационного моделирования сложных комплексов и т.д.

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

Деревом называется сетевая структура, которая характеризуется следующими свойствами:

1. Существует единственный элемент, или узел, на который не ссылается никакой другой элемент и который называется корнем.

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

3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

Определенная таким образом структура называется также корневым деревом. Название “дерево” проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется ветвью. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются листьями. Узел, ни являющийся листом или корнем, считается промежуточным, или узлом ветвления. Если в дереве узел X ссылается на узел Y, то X называется ”родителем”, а Y - его “сыном ”. Все узлы с общим родителем являются “братьями”. Число сыновей у родителя X - степень исхода узла X. При графическом представлении дерева упорядоченность сыновей любого родителя обычно задается изображением узлов - сыновей в порядке убывания их старшинства слева направо.

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

Частный случай дерева - бинарное дерево. Бинарным деревом называется дерево с m = 2. любое m-арное дерево может быть преобразовано в эквивалентное ему бинарное дерево, которое проще исходного с точки зрения изучения, представления в памяти и обработке. Для этого сначала в каждом узле исходного дерева вычеркиваем все ветви, кроме самой левой, которая соответствует ссылке на старшего сына, после этого соединяем горизонтальными ветвями те узлы одного уровня, которые братьями в исходном дереве.

Важнейшие операции над бинарными деревьями: добавление и исключение некоторого поддерева, обход узлов. Обход осуществляется: обходом сверху (шаги выполняются в порядке 1, 2, 3), обход слева направо (2, 1, 3) и обход снизу (2, 3, 1). Можно существенно ускорить операцию обхода, используя прошивки. Это позволит обойтись без стека, требуемого при обходе непрошитого дерева. Вместо пустых указателей можно поместить вспомогательные связки, которые называются прошивками.

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

Если прошивка находится в поле левого указателя, то она адресует предыдущий узел дерева, а прошивка в поле правого указателя адресует следующий узел в выбранной схеме обхода.

При исключении элемента проблема возврата элементов многосвязной списковой структуры в свободный список может решаться разными методами. Наиболее известны: метод счетчика (после каждый операции исключения элемента делается проверка, остался ли этот элемент хотя бы в каком-нибудь одном функциональном списке, и в случае отрицательного ответа элемент присоединяется к свободному списку), метод сборки мусора (освободившийся элемент как бы “повисает ”до тех пор, пока не будет исчерпан свободный список. После этого запускается процедура сборки мусора, которая отыскивает все освободившиеся к этому времени элементы и включает их в свободный список).

2.2 Листинг программы на языке Си.

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#include <stdlib.h>

#define TREE struct tree

TREE

{

int key;

TREE *left,*right;

};

TREE *t1,*kuku;

int a,da;

char y;

TREE *element()

{

TREE *r;

scanf ("%d",&a);

while (a!=0)

{

r=(TREE*)malloc(sizeof(TREE));

r->key=a;

r->left=element();

r->right=element();

return(r);

}

return(0);

}

int opr1(TREE*kk, TREE*ss,int da)

{

if (kk)

{

if (kk->key!=0)

{

if((kk->key==ss->key)&&(kk!=ss))

{

da=999;

return(da);

}

}

if (da!=999)

{

if (opr1(kk->left,ss,da)==999)

da=999;

if (opr1(kk->right,ss,da)==999)

da=999;

}

}

return(da);

}

int opr(TREE*s, TREE*ku, int da)

{

int br;

if (s)

{

if (s->key!=0)

{

br=opr1(ku,s,da);

if (br==999)

da=999;

}

if (br!=999)

{

if (opr(s->left,ku,br)==999)

br=999;

if (opr(s->right,ku,br)==999)

br=999;

}

}

return(br);

}

void display (TREE*s)

{

if (s)

{

printf("%d ",s->key);

display(s->left);

display(s->right);

}

}

void main()

{

int ik;

clrscr();

textcolor(7);

gotoxy(5,3);

printf("Kursovaya rabota po SAODu");

gotoxy(5,5);

printf("Vypolnil student II kursa FMRM S-610 Vishyakov Sergey ");

gotoxy(3,8);

printf("Postroit derevo i opredelit ");

printf(" est li v nem hotya by 2 odinakovyh elementa.");

getch();

y='y';

while (y=='y')

{

printf("\n\nVvedi derevo: ");

t1=element();

printf("\n\nDEREVO: ");

display(t1);

printf("\n");

da=1;

kuku=t1;

ik=opr(t1,kuku,da);

printf("\n");

if (ik==999)

printf(" V dereve imeutsia odinakovie elementi");

else

printf(" V dereve net odinakovih elementov");

getch();

printf("\n\nHotite prodolzit? (y/n)");

y=getch();

}

}

2.3 Пример расчетов

Kursovaya rabota po SAODu

Vypolnil student II kursa FMRM S-610 Vishyakov Sergey

Postroit derevo i opredelit est li b nem hotya by 2 odinakovyh elementa.

Vvedi derevo: 3 4 8 0 0 9 0 0 11 0 8 0 0

DEREVO: 3 4 8 9 11 8

V dereve imeutsia odinakovie elementi

Hotite prodolzit? (y/n)

Vvedi derevo: 1 2 0 0 3 0 0

DEREVO: 1 2 3

V dereve net odinakovih elementov

2.4 Блок схемы

2.4.1 Функция element создает дерево

2.4.2 Функция вывода дерева display.

2.4.3 Функция Opr

2.4.4 Функция opr1

2.4.5 Главная программа

2.5 Дескриптор дерева

Вывод по курсовой работе

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

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

дерево многосвязный список двоичный

Список использованной литературы

1. Сергеев А. Структура программ на языке Си.- М., 1993г.

2. Си, Паскаль, Ада. Сравнение и оценка. - М., 1991г.

3. Си для начинающих. - Спб.: Изд-во "Макет", 1998г.

Размещено на Allbest.ru