Очереди

Другой стандартной структурой данных является очередь [1]. Очередь аналогична очереди людей в магазине: первый клиент в ней обслуживается первым, а другие клиенты ожидают своей очереди. Узлы очереди удаляются только из головы очереди, а помещаются в очередь только в ее хвосте. Это структура данных типа FIFO(first in first out– первым вошел - первым вышел).

У очередей имеется множество применений в вычислительных системах. У большинства компьютеров имеется только один процессор, в один и тот же момент времени может быть обслужен только один процесс. Запросы других процессов помещаются в очередь. Каждый запрос постепенно продвигается по очереди вперед по мере того, как происходит обслуживание пользователей. Запрос в начале очереди является очередным кандидатом на обслуживание.

Информационные пакеты также ожидают своей очереди в компьютерных сетях. Пакет может поступить на узел сети в любой момент времени, а затем он должен быть отправлен к следующему узлу сети по направлению своего конечного пункта назначения. Узел маршрутизации (т.е. узел, хранящий информацию о маршруте) направляет в каждый момент времени один пакет, поэтому пакеты помещаются в очередь до тех пор, пока программа маршрутизации не обработает их.

Задача. Получить от пользователя строку и распечатать каждое слово на отдельной строке

//Файл queue.h*************************

#ifndef _QUEUE_H_

#define _QUEUE_H_

struct Queue

{

char* str;

Queue* next;

};

Queue* Add(char*, Queue*); //добавляем в хвост

void Print(Queue*); //печатаем

Queue* Delete(Queue*); //удаляем из головы

#endif

//************************************

Рис. 10.21. Заголовочный файл очереди

//Файл queue.cpp*************************

#include "queue.h"

#include <iostream>

#include <string.h>

using namespace std;

Queue* Add(char* s, Queue* phead)

{

Queue* pnew= new Queue;

Queue *p = phead;

while(p)

{

if(p->next)

p=p->next;

else

break;

}

pnew->str = new char [strlen(s)+1];

pnew->next = NULL;

strcpy(pnew->str, s);

if(p)

p->next = pnew;

if(phead)

return phead;

return pnew;

}

void Print(Queue* phead)

{

while(phead)

{

cout<<phead->str<<endl;

phead = phead->next;

}

}

Queue* Delete(Queue *phead)

{

Queue *p;

if(phead)

p=phead->next;

delete []phead->str;

delete phead;

return p;

}

//***********************************

Рис. 10.22. Описание функций создаваемой очереди

//Файл test.cpp**********************

#include "queue.h"

#include <string.h>

#include <iostream>

using namespace std;

int main()

{

Queue * head = 0;

char stroka[255];

cout<<"Enter a string:\n";

cin.getline(stroke,255);

while(strlen(stroka))

{

char raz[] = {' ', '\t', '\0'};

char *s=strtok(stroka, raz); //разбиение строки на слова

while(s)

{

head = Add(s, head);

s = strtok(NULL, raz); // продолжение разбиения

}

cout<<"Enter a string:\n";

cin.getline(stroke,255);

}

Print(head);

while(head)

head = Delete(head);

return 0;

}

//*******************************************

Рис. 10.23. Основная функция программы

Деревья

Связные списки, стеки и очереди являются линейными структурами данных [1]. Дерево является нелинейной двумерной структурой данных с особыми свойствами. Узлы дерева могут содержать два и более указателей связи. Бинарные деревья содержат по два указателя. Или один из них, или оба могут быть нулевыми. Корневой узел является первым узлом дерева. Каждый указатель связи в корневом узле ссылается на дочерний узел или узел-потомок. Левый узел-потомок является первым узлом в левом поддереве, а правый узел-потомок является первым узлом в правом поддереве. Узлы-потомки, порожденные одним каким-либо узлом, называются родственными узлами (или узлами-братьями). Узел без узлов-потомков называется листом дерева или концевым узлом. Деревья обычно рисуют сверху вниз, начиная с корневого узла, то есть противоположно тому, как растут деревья в природе.

Задача. Написать программу, реализующую бинарное дерево поиска для целых чисел [5].

//Файл btree.h**********************

#ifndef _BTREE_H_

#define _BTREE_H_

struct Node

{

int num;

Node* Left;

Node* Right;

};

struct List

{

Node* elem;

List* next;

};

Node* add(Node* root, int a);

void print(Node* root, int l);

Node* del(Node* root, int a);

void post(Node *root);

void in(Node* root);

void pre(Node* root);

Node* isonechild(Node* root);

#endif

//*******************************************

Рис. 10.24. Заголовочный файл задачи построения бинарного дерева поиска

//Файл btree.cpp**********************

#include <iostream>

#include "btree.h"

using namespace std;

Node* add(Node* root, int a){

if(!root) {

Node *pnew = new Node;

pnew->num = a;

pnew->Left = NULL;

pnew->Right = NULL;

root = pnew; }

else if(root->num < a)

root->Right = add(root->Right, a);

else

root->Left = add(root->Left, a);

return root;}

Рис. 10.25. Добавление элемента в бинарное дерево поиска

void print(Node* root, int level){

if(root)

print(root->Right, level+1);

for(int i=0; i<level; i++)

cout<<" ";

if(root)

cout<<root->num<<" ("<<level<<")\n";

else

cout<<"#\n";

if(root)

print(root->Left, level+1);

}

void replace(Node** elem, int* a){

if((*elem)->Left)

replace(&((*elem)->Left), a);

else {

*a = (*elem)->num;

Node *p = *elem;

*elem = (*elem)->Right;

p->Right = NULL;

delete p;

}

}

Node* delNode(Node* elem){

if(!elem->Left&&!elem->Right)

{

delete elem;

return NULL;

}

else if((elem->Left&&!elem->Right)||

(!elem->Left&&elem->Right)) {

Node *p = elem;

if(elem->Left) {

elem = elem->Left;

p->Left = NULL;

}

else {

elem = elem->Right;

p->Right = NULL;

}

delete p;

return elem;

}

else {

int a;

replace(&(elem->Right), &a);

elem->num = a; }

}

Рис. 10.26. Функции работы с бинарным деревом поиска - продолжение

Node* del(Node* root, int a){

if(!root) {

cout<<"No such element!"<<endl;

return NULL;

}

else if(root->num == a) {

root = delNode(root);

return root;

}

else if(root->num< a) {

root->Right = del(root->Right, a);

return root;

}

else {

root->Left = del(root->Left, a);

return root;

}

}

void post(Node *root){

if(root) {

post(root->Left);

post(root->Right);

cout<<root->num<<" "; }

}

void in(Node *root){

if(root) {

in(root->Left);

cout<<root->num<<" ";

in(root->Right); }

}

void pre(Node *root){

if(root) {

cout<<root->num<<" ";

pre(root->Left);

pre(root->Right); }

}

Node* isonechild(Node* elem){

if(!elem) return 0;

if(elem->Left && elem->Right) return 0;

if(elem->Left)

return elem->Left;

if(elem->Right)

return elem->Right;}

//*******************************************

Рис. 10.27. Функции работы с бинарным деревом поиска - окончание

//Файл test.cpp**********************

#include <stdlib.h>

#include <time.h>

#include <iostream>

#include "btree.h"

using namespace std;

int main()

{

Node* root = NULL;

srand(time(0));

for(int i = 0; i<10; i++)

{

int a = rand()%101-50;

root = add(root, a);

}

print(root,0);

cout<<"\npost\n\n";

post(root);

cout<<"\nin\n\n";

in(root);

cout<<"\npre\n\n";

pre(root);

return 0;

}

//*******************************************

Рис. 10.28. Работа с бинарным деревом поиска