Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
М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;
}
Висновок.
Я набув навичок щодо реалізації АТД «Дерево» та дерева Хаффмана.