Динамические структуры данных
Лекция 5.
Замечание. В языке С++ были рассмотрены данные простых и сложных типов. Перед новой темой можно привести некоторую классификацию данных:
=данные статической структуры, которые получают структуру при описании и сохраняют её (не нарушая) до конца программы: данные стандартного типа (например, int), массив сохраняет количество элементов, объявленное в описании, и др.
=данные динамической структуры, в которых не фикситруется количество элементов, они могут быть пустые, могут состоять из одного, двух и более элементов, которые могут добавляться и удаляться из этих данных.
= статически размещаемые данные: int X; float a[100], память которых сохраняется за ними в течении всей программы, пока работает их область действия.
=динамически размещаемые данные: память для них выделяется по операции new, существуют они пока эта память не будет освобождена.
Динамические структуры данных.
Элементы в них однотипные, но количество их не фиксируется в структуре. Динамические структуры – это:
|
последовательность,
стек,
|
очередь,
дек,
|
список,
деревья,
|
графы (на 2 курсе)
|
У каждого из этих типов своя дисциплина работы с элементами, она определяет свой набор допустимых операций над элементами.
- Последовательность – характерен последовательный доступ к элементам, последовательно расположенным, так, что добраться до какого–то элемента можно только просмотрев все предшествующие ему. Поступающие элементы встают в конец последовательности, а читаются из её начала Этот тип данных реализован в языках в типе “последовательный файл” , все операции соответствуют операциям чтения из файла, записи в файл. Последовательность может быть закрыта, либо открыта для чтения из неё элементов, либо открыта для записи в неё элементов..
Операции: пусть S – последовательность элементов типа T.
1.Открыть последовательность S для чтения.
2.Читать элемент x типа T из последовательности S, если есть непрочитанные.
3. Проверить , есть ли непрочитанные элементы в последовательности.
4. Открыть последовательность S для записи.
5. Добавить элемент x типа T в последовательность S.
6. Закрыть последовательность S.
- Стек – структура данных, в которой могут накапливаться однотипные данные, при этом выполняется условие: элементы можно выбирать из стека в порядке, обратном порядку их поступления. Это условие называют принципом LIFO: Last –In- First- Out (последний пришел, первый уйдёшь).
дно стека вершина
Пусть S – стек элементов типа Т.
Операции для работы со стеком:
- Сделать стек S пустым: clrst (S).
- Добавить элемент x типа Т в стек S: push(S, x).
- Удалить элемент из непустого стека S: pop(S).
- Проверить стек S на пустоту:
true , если S пустой
emptyst(S)= .
- Выбрать элемент x типа Т из вершины стека без удаления: x = topst(S).
Типа стек в языках нет. Такие совокупности можно моделировать, например на базе массива, тогда получается ограниченный стек.
- Очередь – структура данных, в которой элементы накапливаются в соответствии с принципом FIFO:
First –In- First- Out (первый пришел, первый уйдешь)
Операции для очереди q с элементами типа Т:
- Сделать очередь q пустой: clrqu(q).
- Добавить элемент a типа Т в очередь q : insqu(q,a).
- Удалить элемент из непустой очереди q: remqu(q).
- Проверить очередь q на пустоту:
true , если q пустая
emptyqu(q)= .
- Выбрать элемент a типа Т из непустой очереди без удаления: a= topqu(q).
4. Дек – очередь с двумя концами (double ended queue)
Самим записать операции для дека
Реализация очереди на основе массива.
0 1 2 3 4 . . . . . . . . . . size . . . . . . . . . . . . . . . . NN-1
beg
Очередь циклическая. Примером такой очереди в нашем ПК является буфер клавиатуры. В данном примере будет описана очередь, реализованная на массиве, и программа, использующая очередь для одного алгоритма. Программа многофайловая, состоит из 3-х файлов:
1-ый файл – заголовочный –описывает тип структуры-очереди, объявляет прототипы функций - операций, это интерфейсный файл.
2-ой файл – файл реализации содержит описание функций- операций, спецификации этого типа данных
3-ий файл – главный файл с алгоритмом, использующим очереди.
Абстрактный тип данных (АТД) – это тип данных (набор значений и совокупность операций для этих значений), доступ к которому осуществляется только через интерфейс. Программа, которая использует АТД, называется клиентской (3-ий файл).
Пример программы из 3-х файлов.
ОЧЕРЕДЬ на основе массива
//queue3f.h -интерфейсный файл
#include <iostream>
#include <fstream>
using namespace std;
const int NN=100;
typedef int tip;
struct queue
{ int beg;
int size;
tip x[NN];
};
void clrqu(queue &q);
void insqu(queue &q, tip a);
void remqu (queue &q);
tip topqu (queue q);
bool emptyqu (queue q);
bool overqu (queue q);
void wrfqu(ofstream &fout,queue q);
//queue3fR.cpp - файл реализации
#include "queue3f.h"
//очистка очереди
void clrqu(queue &q){q.beg=0;q.size=0;}
//добавление элемента в очередь
void insqu(queue &q, tip a)
{q.x[(q.beg+q.size)%NN]=a;
q.size++;
}
//удаление элемента из непустой очереди
void remqu (queue &q)
{q.size--;
if(q.beg==NN-1) q.beg=0;
else q.beg++;
}
//выбрать элемент из очереди без удаления
tip topqu (queue q)
{return q.x[q.beg];}
//проверка очереди на пустоту
bool emptyqu (queue q){return q.size==0;}
//проверка очереди на заполненность
bool over (queue q){return q.size==NN;}
//вывод элементов очереди в файл
void wrfqu(ofstream &fout,queue s)
{while (!empty(s))
{fout<<s.x[s.beg]<<"\n";remqu(s);}}
//queue3fgl.cpp -главная программа (клиентская часть)
#include <iomanip>
#include "queue3f.h"
//использование очереди: записать в файл //первые N чисел,
//в разложение которых на простые
//множители входят заданные в файле числа
const int N=100;
const int nq=10;
int main()
{ifstream fin;
ofstream fout;
int b[nq];
queue w[nq];
fin.open("dan.txt");
if (fin.fail())
{cout<<"error open \n"; return(1);}
fout.open("rez.txt");
if (fout.fail())
{cout<<"error open rez.txt \n"; return(1);}
fout<<"mnojiteli: " ;
int l=0;
while (fin>>b[l])
{ fout<<setw(6)<<b[l];
l++;
}
fout<<endl;
fin.close();
//1)сделать очереди пустыми
for (int i=0; i<l; i++) clrqu(w[i]);
int x=1,k=1;
//2)записать x в файл
fout<<setw(6)<<x;
//3)основной цикл
while (k<N)
{ //3.1)записать элемент x*b[i] в очередь w[i]
for (int i=0; i<l; i++) insqu(w[i], x*b[i]);
//3.2)найти и поместить в x минимальный
// элемент из первых в w[i]
x=topqu(w[0]);
for (int i=1;i<l;i++)
{int t=topqu(w[i]);
if (t<x)x=t;
}
//3.3)добавить x в fout
fout<<setw(6)<<x; k++;
if (k%10==0) fout<<endl;
//3.4 убрать из очередей элементы == x
for (int i=0;i<l;i++)
if (x==topqu(w[i])) remqu(w[i]);
}
fout<<endl;
fout.close();
return 0; }
dan.txt
2 7 13
rez.txt
mnojiteli: 2 7 13
1 2 4 7 8 13 14 16 26 28
32 49 52 56 64 91 98 104 112 128
169 182 196 208 224 256 338 343 364 392
416 448 512 637 676 686 728 784 832 896
1024 1183 1274 1352 1372 1456 1568 1664 1792 2048
2197 2366 2401 2548 2704 2744 2912 3136 3328 3584
4096 4394 4459 4732 4802 5096 5408 5488 5824 6272
6656 7168 8192 8281 8788 8918 9464 9604 10192 10816
10976 11648 12544 13312 14336 15379 16384 16562 16807 17576
17836 18928 19208 20384 21632 21952 23296 25088 26624 28561
PAGE \* MERGEFORMAT1
Динамические структуры данных