МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ICM Лабораторна робота №5 з дисципліни “Алгоритми і структури даних” “ Робота з динамічними структурами..” Львів 2007 Мета роботи: набуття практичних навичок опрацювання таких динамічних структур як звязні списки і дерева. Завдання на роботу: Розробити програми які виконують операції вказані в індивідуальному завданні. Програму для роботи з двонапрваленими звязними списками. Кожен елемент списку містить зсилки на наступний і попередній елемент в списку. Програма повинна забезпечувати ввід і побудову списку. Програму для роботи для роботи з деревами. Кожен елемент дерева містить зсилку на батьківський елемент і зсилки на елементи-нащадки (необмежена кількість). Програма повинна забезпечувати ввід і побудову дерева. Кожен елемент списку містить інформаційне поле(атрибут) деякого простого типу: символ, стрічка, число. Всі операції над динамісними стурктурами повинні супроводжуватись відповідним виводом на екран. В контрольних прикладах забезпечити опрацювання стурктур з 10-20 елементами. 2 Вставка нововго елемента в список після вказаного елемнта за значенням інформаційного атрибуту. Визначення кількості нащадків в кожного елемнту дерева.  Хід виконання завдання 1) #include <stdio.h> #include <alloc.h> #include <conio.h> struct element { int info; struct element *next,*prev; }*p1,*po,*el1,*el2,*p,*t; int znach,n,m=1,k=1; void main() { clrscr(); puts("VVEDIT ZNACHENNYA ELEMENTIV"); puts("---------------------------\n"); scanf("%d",&znach); p1=(struct element *)malloc(sizeof(struct element)); p1->info=znach; p1->next=NULL; p1->prev=NULL; el1=(struct element *)malloc(sizeof(struct element)); el1=p1; scanf("%d",&znach); while(znach!=0) {el2=(struct element *)malloc(sizeof(struct element)); el2->info=znach; el2->prev=el1; el2->next=NULL; el1->next=el2; el1=el2; po=el2; scanf("%d",&znach);m++;} el1=p1; puts("\n"); puts("ELEMENTY SPYSKU"); puts("---------------------------\n"); do {printf("%d\n",el1->info); el1=el1->next;} while(el1!=NULL); puts("\n"); puts("vvedit element"); scanf("%d",&znach); puts("na yaku pozyciyu vstavyty"); scanf("%d",&n); puts("\n"); el1=p1; while(n>m) {puts("V spysku nema stilky elementiv, vvedit inshu pozyciyu"); scanf("%d",&n);} if(n==1) {el2=(struct element *)malloc(sizeof(struct element)); el2->info=znach; el2->prev=NULL; el2->next=el1; p1=el2;} else if(n==m) {el2=(struct element *)malloc(sizeof(struct element)); el2->info=znach; el2->prev=po; el2->next=NULL; po->next=el2; } else {while(k!=m) {if(k==n-1) t=el1; if(k==n) p=el1; el1=el1->next; k++;} el2=(struct element *)malloc(sizeof(struct element)); el2->info=znach; el2->prev=t; t->next=el2; el2->next=p; p->prev=el2;} el1=p1; puts("NOVYI SPYSOK"); puts("---------------------------\n"); do {printf("%d\n",el1->info); el1=el1->next;} while(el1!=NULL); } Результати виконання
2) #include <stdio.h> #include <conio.h> #include <stdlib.h> typedef struct tree {int info; struct tree *left,*right; } TreeNode; TreeNode *NewNode(void); void AddNode(TreeNode *pnew,TreeNode ** root_adr); void ShowTree(TreeNode *proot,int lev); void PrintTree(TreeNode *proot); int TreeHeigh(TreeNode *proot); TreeNode *root; int main(void) {TreeNode *node; clrscr(); puts("formuvannya dereva"); while((node=NewNode())!=0) AddNode(node,&root); puts("\n\t Cformovane derevo"); PrintTree(root); return 0; } TreeNode * NewNode (void) {TreeNode *pel; int buf; if(scanf("%d",&buf)==0) return 0; pel=(TreeNode *)malloc(sizeof(TreeNode)); pel->info=buf; pel->left=pel->right=NULL; return pel; } void AddNode(TreeNode *pnew,TreeNode **root_adr) {TreeNode *proot=*root_adr; int cmp; if(proot==NULL) {*root_adr=pnew; return ;} cmp=proot->info>pnew->info; if (cmp>0) AddNode(pnew,&proot->left); else AddNode(pnew,&proot->right); } void PrintTree(TreeNode *proot) {if(proot==NULL) return; PrintTree(proot->left); printf("%d",proot->info); PrintTree(proot->right); } Висновок: на даній лабораторній роботі я набув практичних навичок опрацювання таких динамічних структур як звязні списки і дерева.