Лабораторная 2
Задание 1
Организовать заданную структуру данных. Определить структуру элемента и написать подпрограммы добавления, удаления и чтения элемента. Написать тестовую программу.
Варианты заданий
|
|
Очередь |
Стек |
Дек |
Односвязный циклический список |
Двухсвязный циклический список |
Дерево поиска |
|
точка (x, y) плоскости |
1 |
2 |
3 |
4 |
5 |
6 |
|
точка (x, y, z) пространства |
7 |
8 |
9 |
10 |
11 |
12 |
|
Строка символов |
13 |
14 |
15 |
16 |
17 |
18 |
|
Символ s и позиция (x, y) |
19 |
20 |
21 |
22 |
23 |
24 |
|
Длинное целое число |
25 |
26 |
27 |
28 |
29 |
30 |
Элементы списков определяются как
struct NODE{ double x, y; struct NODE *next; }
struct NODE{ double x, y, z; struct NODE *next; }
struct NODE{ char *s; struct NODE *next; }
struct NODE{ char c; int x, y; struct NODE *next; }
struct NODE{ long x; struct NODE *next; }
(Для двухсвязного циклического списка и дерева поиска определено два указателя.)
Пример выполнения задания 1
Задание. Организовать структуру данных дек, элементами которого являются пары, состоящие из строки символов и ее длины. Тестовая программа должна проверять правильность выполнения подпрограмм включения элемента в начало и в конец дека, а также подпрограммы удаления первого и последнего элемента дека. Входные данные вводятся в главной программе.
// дек элементов
// элемент состоит из строки и ее длины
#include <alloc.h>
#include <conio.h>
#include <stdio.h>
#include <string.h>
#define deque struct deq
deque
{
char *s ;
int length;
deque *next ;
};
void insert ( deque **q, char *item )
{
deque *new_item;
new_item = (deque * ) malloc (sizeof(deque) );
new_item -> s = item;
new_item -> length = strlen(item);
new_item -> next = *q ; *q = new_item;
}
void append( deque **q, char *item )
{
deque *current = *q, *prev = 0;
deque *new_node = (deque * ) malloc (sizeof(deque) );
new_node -> s = item;
new_node -> length = strlen(item);
new_node -> next = 0;
while(current)
{
prev = current; current = current->next;
}
if (prev) prev->next = new_node;
else *q = new_node;
}
char *take_out ( deque **q, int *error )
{
deque *old_item = *q;
char* old_info = 0;
if ( *q )
{
old_info = old_item -> s;
*q = ( *q ) -> next;
free (old_item );
*error = 0;
}
else *error = 1;
return ( old_info ) ;
}
char *peek( deque **q, int *error)
{
if ( *q ) { *error = 0 ; return (*q) -> s;}
else { *error = 1 ; return 0;}
}
char *delend(deque **d, int *error)
{
deque *current = *d, *prev = *d;
char* oldinfo=0; *error = 0;
if((*d) == 0) // if empty
{ *error=1; return 0; }
if (current->next==0) // if 1 element
{
*d=0; oldinfo = current->s;
free (current); return oldinfo;
}
else
while (current->next != 0)
{
prev = current; current = current->next;
}
oldinfo = current->s; free( current);
prev->next = 0; return oldinfo;
}
int isempty(deque **q)
{
if(*q) return 0; // nonempty
else return 1;
}
void show_deque( deque *q )
{
printf("\n");
if ( q )
{
printf(" %s ", q->s); printf( " %-7d ", q->length);
show_deque(q->next);
} }
main()
{
char *names[] = {"Category","Morphism", "Functor" ,"Domain"};
deque *d1 = 0;
int i, err;
clrscr();
for (i=0; i<4; i++) append(&d1,names[i]);
insert(&d1,"Algebra");
insert(&d1,"Inclusion");
show_deque(d1);
printf("\n delete %s", delend(&d1,&err));
printf("\n delete %s", take_out(&d1,&err));
show_deque(d1);
getch();
}
Программа выводит
Inclusion 9
Algebra 7
Category 8
Morphism 8
Functor 7
Domain 6
delete Domain
delete Inclusion
Algebra 7
Category 8
Morphism 8
Functor 7
Задание 2
Применить списки для построения и реализации алгоритмов. Написать программу на языке С++.