Рекурсивный алгоритм. Определение рекурсивной функцию int Lat, возвращающую количество латинских букв в текстовом файле, страница 7

Элементы списков определяются как

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

Применить списки для построения и реализации алгоритмов. Написать программу на языке С++.

Варианты заданий

1.  Задан текстовый файл. Вычислить частоты повторения слов, с помощью двоичного дерева, информационная часть которого состоит из слова и частоты.

2.  Организовать двоичное дерево поиска, состоящее из целых чисел. Вывести содержимое его узлов, обходя это дерево в ширину.

3.  Применить стек для обхода вершин графа, заданного с помощью матрицы смежности, в ширину.

4.  Применить очередь для преобразования рекурсивной подпрограммы обхода дерева поиска в прямом порядке.

5.  Написать программу вычисления значения логического выражения, состоящего из натуральных чисел, скобок и поразрядных операций ‘–’ (“не”), ‘&’ (“и”), ‘|’ (“или”). Приоритет у ‘–’ самый высокий, далее идет ‘&’. Самый низкий приоритет у операции ‘|’. Применить стеки для вычисления этого значения.