ИДЗ Нелинейные типы данных (стек, дек, очередь, односвязный список)
.docСтек
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <locale.h>
struct stack
{
int val;
struct stack *next;
};
struct stack* push(struct stack *root,int elem)
{
struct stack *vsp;
vsp=(struct stack *)malloc(sizeof(stack));
vsp->val=elem;
vsp->next=root;
return vsp;
}
struct stack* pop(struct stack *root)
{
struct stack *vsp=root->next;
printf("\nИз стека извлечен элемент со значением %d",root->val);
free(root);
return vsp;
}
void menu()
{
int p=1,elem;
struct stack *root=NULL, *posled=NULL;
while((p==1)||(p==2))
{
printf("\nЧто вы хотите сделать?\n1.Положить элемент в стек\n2.Изъять элемент из стека\n0.Выход\n");
scanf("%d",&p);
switch(p)
{
case 1:
printf("\nВведите элемент, который хотите положить:");
scanf("%d",&elem);
root=push(root, elem);
break;
case 2:
root=pop(root);
break;
default:
exit(1);
}
}
}
void main()
{
setlocale(LC_ALL,"Rus");
menu();
}
Очередь
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <locale.h>
struct och
{
int val;
struct och *next;
};
och *root=NULL,*last=NULL;
struct och* push(struct och *last,int elem)
{
if(last)
{
och *vsp=(struct och *)malloc(sizeof(och));
vsp->val=elem;
vsp->next=NULL;
last->next=vsp;
return last->next;
}
else
{
last=root=(och*)malloc(sizeof(och));
last->val=root->val=elem;
last->next=root->next=NULL;
return last;
}
}
struct och* pop(struct och *last)
{
struct och *vsp=root->next;
printf("\nИз очереди извлечен элемент со значением %d",root->val);
free(root);
return vsp;
}
void menu()
{
int p=1,elem;
while((p==1)||(p==2))
{
printf("\nЧто вы хотите сделать?\n1.Добавить элемент в очередь\n2.Изъять элемент из очереди\n0.Выход\n");
scanf("%d",&p);
switch(p)
{
case 1:
printf("\nВведите элемент, который хотите добавить:");
scanf("%d",&elem);
last=push(last, elem);
break;
case 2:
if(root)
root=pop(root);
else
printf("\nДерево пустое");
break;
default:
exit(1);
}
}
}
void main()
{
setlocale(LC_ALL,"Rus");
menu();
}
Односвязный список
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <locale.h>
#include <string.h>
int num;
struct dann
{
int key;
struct dann *next;
};
struct dann* add_to_begin(struct dann *root,int key)
{
struct dann *vsp;
vsp=(struct dann *)malloc(sizeof(dann));
vsp->key=key;
vsp->next=root;
return vsp;
}
struct dann* add_to_end(struct dann *root,int key)
{
if(root==NULL)
{
root=(struct dann*)malloc(sizeof(struct dann));
root->key=key;
root->next=NULL;
}
else
root->next = add_to_end(root->next,key);
return root;
}
struct dann* add_to_middle(struct dann *root, int key,int number)
{
struct dann *vsp;
if((num==number)||(!root))
{
vsp=(struct dann*)malloc(sizeof(struct dann));
vsp->key=key;
vsp->next=root;
return vsp;
}
else if(root->next)
{
num++;
root->next=add_to_middle(root->next,key,number);
}
else if(!root->next)
{
vsp=(struct dann*)malloc(sizeof(struct dann));
vsp->key=key;
vsp->next=NULL;
root->next=vsp;
return root;
}
return root;
}
struct dann* del_from_begin(struct dann *root)
{
struct dann *vsp;
vsp=root->next;
free(root);
return vsp;
}
struct dann* del_from_end(struct dann *root)
{
if(root->next==NULL)
{
free(root);
return NULL;
}
else
root->next=del_from_end(root->next);
return root;
}
struct dann* del_from_middle(struct dann *root,int number)
{
struct dann *vsp;
if(num==number)
{
vsp=root->next;
free(root);
return vsp;
}
else if(root->next)
{
num++;
root->next=del_from_middle(root->next,number);
}
return root;
}
void vyvod_screen(struct dann *root)
{
if(root!=NULL)
{
printf("\n%d",root->key);
if(root->next!=NULL)
vyvod_screen(root->next);
}
}
struct dann* make_null(struct dann *root)
{
free(root);
return NULL;
}
void menu()
{
struct dann *root=NULL,usel;
int p=0,t,key,q,number;
while(p!=10)
{
printf("\nЧто вы хотите сделать?\n1. Ввести данные\n2. Очистить\n3. Вывести данные\n4.Удалить элемент\n10.Выход\n");
scanf("%d",&p);
switch(p)
{
case 1:
printf("\n1.В начало\n2.В конец\n3.В середину\n");
scanf("%d",&q);
printf("Введите ключ: ");
scanf("%d",&key);
switch(q)
{
case 1:
root=add_to_begin(root,key);
break;
case 2:
root=add_to_end(root,key);
break;
case 3:
printf("Введите номер, на место которого вы хотите вставить элемент: ");
scanf("%d",&number);
num=0;
root=add_to_middle(root,key,number);
break;
}
break;
case 2:
root=make_null(root);
break;
case 3:
vyvod_screen(root);
break;
case 4:
printf("\n1.Из начала\n2.Из конца\n3.Из середины\n");
scanf("%d",&q);
switch(q)
{
case 1:
root=del_from_begin(root);
break;
case 2:
root=del_from_end(root);
break;
case 3:
printf("Введите номер, который хотите удалить: ");
scanf("%d",&number);
num=0;
root=del_from_middle(root,number);
break;
}
break;
default:
break;
}
}
}
void main()
{
setlocale(LC_ALL,"Rus");
menu();
}
Дек
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <locale.h>
#include <windows.h>
struct data
{
int val;
struct data *next,*prev;
};
struct data* add_to_end(struct data *last,int elem)
{
last->next=(data*)malloc(sizeof(data));
last->next->val=elem;
last->next->prev=last;
last->next->next=NULL;
return last->next;
}
struct data* add_to_begin(struct data *root,int elem)
{
struct data *vsp;
vsp=(struct data *)malloc(sizeof(data));
vsp->val=elem;
vsp->next=root;
root->prev=vsp;
return vsp;
}
void prohod(struct data *root)
{
if(root)
printf("\n%d",root->val);
if(root->next)
prohod(root->next);
}
struct data* clear(struct data *root)
{
free(root);
return NULL;
}
struct data* del_from_begin(struct data *root)
{
struct data *vsp;
vsp=root->next;
free(root);
if(vsp)
vsp->prev=NULL;
return vsp;
}
struct data* del_from_end(struct data *last)
{
if(last->prev)
{
data *vsp=last->prev;
free(last);
vsp->next=NULL;
return vsp;
}
else
free(last);
return NULL;
}
void menu()
{
int p=1,elem;
struct data *root=NULL, *last=NULL;
while((p>0)||(p<8))
{
printf("\nЧто вы хотите сделать?\n1.Добавить элемент в конец\n2.Добавить элемент в начало\n3.Удалить элемент из начала");
printf("\n4.Удалить элемент из конца\n5.Очиcтить список\n6.Вывести все элементы\n0.Выход\n");
p=getch();
switch(p)
{
case '1':
printf("\nВведите элемент, который хотите добавить:");
scanf("%d",&elem);
if(last)
last=add_to_end(last, elem);
else
{
last=root=(data*)malloc(sizeof(data));
last->next=last->prev=NULL;
last->val=elem;
root=last;
}
break;
case '2':
printf("\nВведите элемент, который хотите добавить:");
scanf("%d",&elem);
root=add_to_begin(root, elem);
break;
case '3':
if(root && root->next)
root=del_from_begin(root);
else if(root)
last=root=NULL;
else
printf("\nСписок пуст!");
break;
case '4':
if(last && last->prev)
last=del_from_end(last);
else if(last)
last=root=NULL;
else
printf("Список пустой");
break;
case '5':
root=clear(root);
break;
case '6':
if(root!=NULL)
prohod(root);
else
printf("\nСписок пустой!!!");
break;
default:
exit(1);
}
}
}
void main()
{
setlocale(LC_ALL,"Rus");
menu();
}