- •Оглавление
- •1.2. Свойства языков программирования
- •1.3. Основные парадигмы программирования Процедурное программирование
- •Модульное программирование
- •Абстракция данных
- •Объектно-ориентированное программирование
- •Непечатные символы
- •Тема 2 Типы данных
- •2.1. Понятие переменной и объявление переменных
- •Объявление переменных
- •Встроенные типы данных
- •Размер памяти, выделяемой под встроенные типы данных
- •2.2. Константы и перечисления Константные переменные
- •Перечисления
- •2.3. Операции и выражения
- •Мультипликативные операции
- •Операции сравнения
- •Побитовые логические операции
- •Побитовые операции
- •Комментарии
- •Оператор while(пока)
- •Оператор do/while(выполнять/пока)
- •Оператор for(цикл)
- •Оператор множественного выбора switch
- •Операторы breakиcontinue
- •Тема 4 Массивы
- •4.1.Определение, объявление и инициализация массивов
- •Объявления и инициализация массивов в программе
- •4.2. Сортировка массивов Пузырьковая сортировка
- •Сортировка вставками
- •4.3. Поиск в массивах Линейный поиск
- •Двоичный поиск
- •4.4. Многомерные массивы
- •Тема 5 Указатели Объявления и инициализация переменных указателей
- •5.1. Операции над указателями
- •5.2. Выражения и арифметические действия с указателями
- •5.3. Взаимосвязи между указателями и массивами
- •5.4. Массивы указателей
- •5.5. Динамическое выделение памяти под массивы
- •Тема 6 Функции
- •6.2. Определения функций
- •Генерация случайных чисел
- •6.3. Классы памяти и область действия Классы памяти
- •Область действия
- •6.4. Рекурсия
- •6.5. Ссылки и ссылочные параметры
- •Вызов функций по ссылке с аргументами указателями
- •6.6. Использование спецификатораconstс указателями
- •6.7. Перегрузка функций
- •Аргументы по умолчанию
- •6.8. Передача массивов в функции
- •6.9. Указатель на функцию
- •6.10. Командная строка аргументов
- •6.11 Неопределенное количество аргументов
- •Тема 7 Введение в обработку строк
- •7.1. Работа со строками в с
- •Понятие символов и строк в с
- •Функции для работы со строками
- •Определение длины строки
- •Сложение двух строк (конкатенация)
- •Добавление к исходной строке указанного количества символов.
- •Копирование строки в другую строку
- •Сравнение строк
- •Получение строки от пользователя
- •Тема 8 Работа с файлами
- •Открытие файла
- •Чтение из файла символа или строки символов
- •Запись символа или строки символов в файл
- •Смещение внутри файла
- •Значения параметра fromwhereфункцииfseek
- •Закрытие файла
- •Тема 9 Компоновка программ и препроцессор
- •9.1. Компоновка программ
- •Проблема использования общих функций и имен
- •Использование включаемых файлов
- •9.2. Препроцессор
- •Определение макросов
- •Условная компиляция
- •Дополнительные директивы препроцессора
- •Тема 10 Структуры
- •10.1. Определение структур и доступ к элементам
- •Доступ к элементам структур
- •Использование структур
- •10.2. Битовые поля
- •10.3. Объединения
- •10.4. Построение связных списков на основе структур с самоадресацией
- •Создание простого связного списка
- •Очереди
- •Деревья
- •Список рекомендуемой литературы
Очереди
Другой стандартной структурой данных является очередь [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. Работа с бинарным деревом поиска