10.Использование динамич. Переменных для представл. И работы со стеком.

Struct tstack { int inf; tstack*next}; //описание стека

tstack *init_stack() {return NULL; } //инициализация стека

void push(tstack *&sp, init item) {tstack *r=new tstack; r->inf=item; r->next=sp; sp=r; } //добавление эл-та

int pop(tstack*&sp){ tstack*r=sp; int i=r->inf; sp=r->next; delete r; return i;} //удаление эл-та

int peek(tstack *sp){return sp->inf;} //просмотр эл-та, расположенного на вершине стека

int empty_stack(tstack*s) { return(s)&0:1;}; // определение стека на пустоту: 0, если пуст

Объединив все функции в файл stackint.h и сохранив его в папке INCLUDE, можно подключить его к любой программе с помощью #include<stackint.h>

Пример: Переписать из h в g в обратной последовательности.

# include <stdio.h> # include “stackint.h” #include <iostream> using namespace std;

FILE*h=fopen(“input_stack.txt”, “r”); FILE*g=fopen(“output.txt”, “w”);

int i; tstack*sp=init_stack(); sp=NULL while (!feof(h)) { fscanf (h, “%d”, &i);

push (sp, i); printf(“%d\t”, i); }; cout<<”\n”; while (!empty_stack(sp)) { i=pop (sp);

printf (“%d\t”, i); fprintf (g, “%d\t”, i); } ;

11.Очередь,реализация очереди массивом.

Очередь — линейный список, где все включения производится с одной стороны, а исключения и всякий доступ с другой; абстрактная структура данных, работающая по принципу FIFO. Доступ возможен с двух концов, существуют 2 переменные: head и tail.

Можно описать с помощью массива:

Const int n=100; float Queue[n], x; int head, tail;

Основные операции:

1)Инициализация очереди. Пусть head=0, tail=0. Head указывает на 1-ый элемент в очереди,tail – на последний или на 1-ю свободную ячейку. Сначала tail head чтобы не переполнить массив, присвоить tail значение 1 и заполнять очередь с начала массива, т.о. закольцованная структура. Чтобы отличить пустую ячейку от непустой, оставляем 1 ячейку свободной. Если пуста, то head=tail,если полна, то head = tail+1.

2) Взятие элементов. If (head == tail) cout<<”Очередь пуста”; else {x=Queue[head];

head=head+1; if (head == n) head = 0;}

3) Добавление элемента. r=tail +1; if (r==n) r=0; if (r==head) cout<<”Очередь полна”;

else {Queue[tail] = x; tail = r;}

12.Очередь, представление и реализация основных операций с помощью динамических переменных.

Графическое представление очереди: имеет две точки доступа. Head – для удаления элементов,tail – для добавления элементов. Описание: struct tqueue{int inf;tqueue*next};

1)Инициализация очереди: head=NULL, tail=NULL;

2)Добавление элемента в очередь: r=new tqueue; r->inf=x;r->next=NULL; if(head==NULL) {head=r; tail=r;}; else{tail->next=r; tail=r};

3)Взятие элемента из очереди: if(head!=NULL) {r=head;x=head->inf;head=head->next; delete r;}/*удаление первого элемента. r - указатель на 1-ый элемент. (r=NULL).*/

4)Освобождение динамической памяти, занятой очередью:

void clear_queue(tqueue*&head) {tqueue *r; while(head!=NULL) {r=head;head=head->next; delete r;};}