Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Робота з динамічними структурами
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Інформаційні системи та мережі
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми і структури даних
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет "Львівська політехніка"
Кафедра "Інформаційні системи та мережі"
Лабораторна робота № 5
з предмету:
Алгоритми і Структури Даних
на тему:
Робота з динамічними структурами
ЛЬВІВ-2008
Тема:
Робота з динамічними структурами.
Мета роботи:
Набуття практичних навичок опрацювання таких динамічних структур, як звязні списки і дерева.
Постановка завдання:
Розробити програми які виконують операції вказані в індивідуальному завданні.
Програму для роботи з двонапрвленими звязними списками. Кожен елемент списку містить зсилки на наступний і попередній елемент в списку. Програма повинна забезпечувати ввід і побудову списку.
Програму для роботи з деревами. Кожен елемент дерева містить зсилку на батьківський елемент і зсилки на елементи-нащадки (необмежена кількість). Програма повинна забезпечувати ввід і побудову дерева.
Кожен елемент списку містить інформаційне поле (атрибут) деякого простого типу: символ, стрічка, число.
Всі операції над динамісними стурктурами повинні супроводжуватись відповідним виводом на екран.
В контрольних прикладах забезпечити опрацювання стурктур з 10-20 елементами.
Варіант індивідуального завданя:
Двонаправлений зв’язний список: Видалення елемента зі списку за вказаним значенням інформаційного атрибуту.
Дерево: Визначення максимуму і мінімуму арифметичних чисел в дереві, кожен елемент якого містить деяке число як значення інформаційного показника.
Хід виконання роботи:
Я розробив програми даних для роботи з двонаправленим лінійним списком і деревом.
Перша програма видаляє елемент зі вказаним значенням інформаційного атрибуту.
Друга програма визначає максимум і мінімум арифметичних чисел в дереві, кожен елемент якого містить деяке число як значення інформаційного показника.
Текст програми на мові С++:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
class list
{
protected:
int val;
list *prev, *next;
public:
list()
{ val=-1; prev=NULL; next=NULL; }
list &operator()(int index) // List node #index
{
list *temp=next;
if(index==0) return *this;
for(int i=1; i<index; i++)
{
if(!temp)
{ printf("List no node error\n"); exit(-1); }
temp=temp->next;
}
return *temp;
}
int &operator[](int index) // List node #index value
{
list *temp=next;
if(index==0) return val;
for(int i=1; i<index; i++)
{
if(!temp)
{ printf("List no node error\n"); exit(-1); }
temp=temp->next;
}
return temp->val;
}
void add(int nval)
{
list *temp=new list;
temp->prev=this;
temp->next=next;
next->prev=temp;
next=temp;
next->val=nval;
}
void remove()
{
if(!next)
{ printf("List no node error\n"); exit(-1); }
list *temp=next;
next=next->next;
if(next)next->prev=this;
//delete temp;
}
void show()
{
printf("{");
if(next)
{
printf("%d", next->val);
for(list *temp=next; temp->next; temp=temp->next)
printf(",%d", temp->next->val);
}
printf("}\n");
}
~list()
{
list *temp;
while(next!=NULL)
{
temp=next;
next=next->next;
delete temp;
}
}
};
class tree
{
public:
int val;
tree *parent, *son, *brother;
public:
tree(int nval=0)
{ val=nval; parent=son=brother=NULL; }
void addson(int nval)
{
tree *temp=new tree(nval);
temp->parent=this;
temp->brother=son;
son=temp;
}
void form(int number, int level)
{
if(level==0)return;
int lim=random(level)+1;
for(int i=0; i<lim; i++)
{
addson(random(100));
son->form(number/lim, level-1);
}
}
void show(int level=0)
{
if(level==0)printf("{\n");
for(int i=0; i<level; i++) putch(' ');
printf("%d\n", val);
if(son) son->show(level+1);
if(brother) brother->show(level+1);
if(level==0)printf("}\n");
}
int min()
{
int m=val;
if(son) if(son->min()<m) m=son->min();
if(brother) if(brother->min()<m) m=brother->min();
return m;
}
int max()
{
int m=val;
if(son) if(son->max()>m) m=son->max();
if(brother) if(brother->max()>m) m=brother->max();
return m;
}
~tree()
{
if(son) delete son;
if(brother) delete brother;
}
};
int main()
{
int i, v;
list l1;
tree *t1;
randomize();
clrscr();
//-----------------------------------------------------------------------------------
puts("Form list:");
for(i=0; i<10; i++)
l1.add(random(100));
l1.show();
printf("Enter value of node to delete: ");
scanf("%d", &v);
for(i=0; i<10; i++)
if(l1[i]==v)
{ l1(i-1).remove(); break; }
l1.show();
getch();
//-----------------------------------------------------------------------------------
puts("Form tree:");
t1=new tree(random(100));
t1->form(10, 3);
t1->show();
printf("min=%d, max=%d\n", t1->min(), t1->max());
getch();
return 0;
}
Результати компютерної реалізації програми:
Результати компютерної реалізації програми виправдали очікування і підтвардили правильність її складання. Нижче наведено скріншот, який демонструє це:
Висновки
Під час виконання роботи я придбав і закріпив практичні навички опрацювання таких динамічних структур, як звязні списки і дерева.
30.11.2012 00:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора