Мiнiстерство освіти і науки України

Мiнiстерство освіти і науки України

Тернопільський національний технічний університет імені Івана Пулюя

Факультет комп'ютерно-інформаційних систем і програмної інженерії

Кафедра програмної інженерії

ЗВІТ

до лабораторної роботи №5

з навчальної дисципліни «Алгоритми та структури даних»

Тема: Абстрактний тип даних ”Дерево”

Підготував:

студент групи СП-11

Cрогий Юрій Павлович

Тернопіль 2013

Мета роботи: засвоїти теоретичний матеріал та набути практичних навичок по роботі з абстрактним типом даних “Дерево”

Короткі теоретичні відомості:

Дерево (tree) – це сукупність елементів, які називаються вузлами та відношень між цими елементами, що утворюють ієрархічну структуру дерева.

Початковий вузол дерева називається його коренем (root).

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

1.Побудувати графічно дерево для виразу

(c+b)*(a+c)+(b+c^2)

2. Реалізувати (з використанням функцій АТД Tree), функції для обходу дерев та привести список обходу вузлів дерева побудованого в п.1

1 – у прямому порядку

2 – у зворотньому порядку

3 – у симетричному порядку

3. Реалізувати (з використанням мови програмування) основні функції для АТД Tree (PARENT, LEFTMOST_CHILD, RIGTH_SIBLING, LABEL, ROOT).

#include <iostream>

#include <locale.h>

using namespace std;

const int maxn=13;

struct node

{

char label;

int lmc;

int rc;

int idx;

};

void in(node []);

int parent(int, node[]);

int root();

int left(int, node[]);

int right(int, node[]);

char label(int, node[]);

void preorder(int, node[]);

void postorder(int, node[]);

void inorder(int, node[]);

void main()

{

setlocale(LC_ALL, "Ukrainian");

node tree[maxn];

in(tree);

cout<<"Прямий обхід:"<<endl;

preorder(0,tree);

cout<<endl<<"Зворотній обхід:"<<endl;

postorder(0,tree);

cout<<endl<<"Симетричний обхід:"<<endl;

inorder(0,tree);

}

void in(node tree[maxn])

{

tree[0].label='+';

tree[1].label='*';

tree[2].label='+';

tree[3].label='+';

tree[4].label='+';

tree[5].label='b';

tree[6].label='^';

tree[7].label='c';

tree[8].label='b';

tree[9].label='a';

tree[10].label='c';

tree[11].label='c';

tree[12].label='2';

for (int i=0; i<maxn; i++)

{

tree[i].lmc=NULL;

tree[i].rc=NULL;

}

tree[0].lmc=1;

tree[0].rc=2;

tree[1].lmc=3;

tree[1].rc=4;

tree[2].lmc=5;

tree[2].rc=6;

tree[3].lmc=7;

tree[3].rc=8;

tree[4].lmc=9;

tree[4].rc=10;

tree[6].lmc=11;

tree[6].rc=12;

for (int i=0; i<maxn; i++)

{

tree[i].idx=i;

}

}

int root()

{

return 0;

}

int left(int c, node t[maxn])

{

return t[c].lmc;

}

int right(int c, node t[maxn])

{

return t[c].rc;

}

char label(int c, node t[maxn])

{

return t[c].label;

}

int parent(int c, node t[maxn])

{

if (c==0){ cout<<"Це корінь"; return 0;}

else

for (int i=0; i<maxn; i++)

if (t[left(i,t)].idx==t[c].idx || t[right(i,t)].idx==t[c].idx) return i;

}

void preorder(int i, node t[maxn])

{

cout<<t[i].label;

if (t[i].lmc!=NULL && t[i].rc!=NULL)

{

preorder(t[i].lmc,t);

preorder(t[i].rc,t);

}

}

void postorder(int i, node t[maxn])

{

if (t[i].lmc!=NULL && t[i].rc!=NULL)

{

postorder(t[i].lmc,t);

postorder(t[i].rc,t);

}

cout<<t[i].label;

}

void inorder (int i, node t[maxn])

{

if (t[i].lmc==NULL && t[i].rc==NULL) cout<<t[i].label;

else

{

inorder(t[i].lmc,t);

cout<<t[i].label;

inorder(t[i].rc, t);

}

}

4. Знайти код Хаффмана для повідомлення, що складається з символів [abcde] з наступними ймовірностями:

a:1111
b:1110
c:10
d:0

e:110

5. Написати програму по кодування та декодуванню повідомлення відповідно до отриманих кодів з п.4

#include <iostream>

#include <locale.h>

using namespace std;

const int k=9;

struct elem

{

char c;

int lc;

int rc;

int parent;

int idx;

bool code;

};

void code(char, elem[]);

void decode(char [], elem[]);

void main()

{

setlocale(LC_ALL, "Ukrainian");

elem t[k];

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

{

t[i].idx=i;

t[i].c='^';

t[i].lc=-1;

t[i].rc=-1;

t[i].code=-1;

}

t[2].c='d';

t[4].c='c';

t[6].c='e';

t[7].c='a';

t[8].c='b';

t[0].lc=1;

t[0].rc=2;

t[1].lc=3;

t[1].rc=4;

t[3].lc=5;

t[3].rc=6;

t[5].lc=7;

t[5].rc=8;

t[0].parent=-1;

t[1].parent=0;

t[2].parent=0;

t[3].parent=1;

t[4].parent=1;

t[5].parent=3;

t[6].parent=3;

t[7].parent=5;

t[8].parent=5;

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

{

if (t[i].lc!=-1)

t[t[i].lc].code=1;

if (t[i].rc!=-1)

t[t[i].rc].code=0;

}

cout<<"Введіть стрічку для кодування"<<endl;

char s[10];

gets(s);

int b=0;

while(s[b]!='\0')

{

code(s[b],t);

b++;

}

cout<<endl;

cout<<"Введіть код для декодування"<<endl;

char d[40];

gets(d);

decode(d,t);

cout<<endl;

system("pause");

}

void code(char c, elem t[k])

{

int i=0;

while (c!=t[i].c)

{

i++;

}

bool r[5];

r[0]=t[i].code;

int k=i;

int j=1;

while (t[k].parent!=-1)

{

r[j]=t[t[k].parent].code;

k=t[t[k].parent].idx;

j++;

}

for (int h=j-2; h>=0; h--)

{

cout<<r[h];

}

}

void decode(char c[40], elem t[k])

{

int p=0;

elem g=t[0];

int i=0;

while (c[i]!='\0')

{

if (g.lc!=-1)

{

if (c[i]=='1')

{

g=t[g.lc];

}

else

{

g=t[g.rc];

}

i++;

}

else

{

cout<<g.c; g=t[0];

}

}

cout<<g.c;

}

Висновок.

Я набув навичок щодо реалізації АТД «Дерево» та дерева Хаффмана.

---

Дата добавления: 2015-11-04