Динамические структуры данных

Дек – очередь с двумя концами double ended queue Самим записать операции для дека Реализация очереди на основе массива. ОЧЕРЕДЬ на основе массива queue3f.h интерфейсный файл include iostrem include fstrem using nmespce std; const int NN=100; typedef int tip; struct queue { int beg; int size; tip x[NN]; }; void clrququeue q; void insququeue q tip ; void remqu queue q; tip topqu queue q; bool emptyqu queue q; bool overqu queue q; void wrfquofstrem foutqueue q; queue3fR.cpp ...

2014-07-07

23.57 KB

0 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


Лекция 5.

Замечание.  В языке С++  были рассмотрены данные  простых  и  сложных  типов.  Перед новой темой  можно привести некоторую  классификацию  данных:

  •  по структуре:  

=данные статической  структуры, которые получают структуру при описании и сохраняют её (не нарушая) до конца программы:  данные  стандартного типа (например, int),  массив сохраняет количество элементов, объявленное в описании, и др.

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

  •  по способу размещения:

= статически  размещаемые данные:  int  X; float  a[100],  память которых  сохраняется за ними в течении  всей программы, пока работает их область действия.

=динамически размещаемые  данные:   память для них выделяется по операции new, существуют  они пока эта память не будет освобождена.

Динамические  структуры данных.

Элементы в них однотипные,  но количество  их не фиксируется  в структуре.  Динамические структуры – это:

последовательность,

стек,

очередь,

дек,

список,

деревья,

графы (на 2 курсе)

У каждого из этих типов  своя дисциплина  работы с элементами, она определяет  свой набор  допустимых операций  над элементами.

  1.  Последовательность – характерен последовательный доступ к элементам, последовательно расположенным, так, что добраться до какого–то элемента можно только просмотрев все предшествующие ему. Поступающие элементы встают в конец последовательности, а  читаются из её начала Этот тип данных реализован  в языках  в типе “последовательный  файл” , все операции соответствуют операциям чтения из файла, записи в файл. Последовательность может быть закрыта, либо открыта для чтения из неё элементов, либо открыта для записи в неё элементов..

Операции:    пусть   S – последовательность элементов типа T.

1.Открыть последовательность S для чтения.

2.Читать элемент x типа T из последовательности S, если есть непрочитанные.

3. Проверить , есть ли непрочитанные элементы в последовательности.

4. Открыть последовательность S для   записи.

5. Добавить элемент x типа T в последовательность S.

6. Закрыть последовательность S.

  1.  Стек – структура данных, в которой могут накапливаться однотипные данные, при этом выполняется условие:  элементы можно выбирать из стека  в порядке, обратном порядку их поступления. Это условие называют  принципом LIFO:  LastIn- First- Out  (последний пришел, первый уйдёшь).

дно стека                               вершина

Пусть  S – стек элементов  типа  Т.

Операции  для работы со стеком:

  1.  Сделать стек  S пустым:  clrst (S).
  2.   Добавить  элемент x  типа Т в стек S:  push(S, x).
  3.   Удалить элемент  из  непустого  стека S:  pop(S).
  4.   Проверить  стек S на пустоту:  

                        true  , если S  пустой

emptyst(S)=    .

  1.  Выбрать элемент  x типа Т из вершины стека без удаления: x = topst(S).

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

  1.   Очередьструктура данных, в которой элементы накапливаются в соответствии с принципом FIFO: 

FirstIn- First- Out  (первый пришел, первый уйдешь)

        

Операции для очереди q с элементами типа Т:

  1.  Сделать очередь q  пустой:  clrqu(q).
  2.   Добавить  элемент a  типа Т в очередь q  :  insqu(q,a).
  3.   Удалить элемент  из  непустой очереди q:  remqu(q).
  4.   Проверить  очередь q  на пустоту:  

                        true , если q  пустая

emptyqu(q)=    .

  1.  Выбрать элемент  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

2

2≠

4≠

8≠

14

7

7≠

14

28

49

13

13

26

52

91

PAGE   \* MERGEFORMAT1



 

Другие похожие работы, которые могут вас заинтересовать.
8334. Формулы Шеннона и Хартли. Расчёт количества информации. Кодирование символьных, графических и звуковых данных. Структуры данных Формула Шеннона 140.5 KB
  Для решения обратных задач, когда известна неопределенность (H) или полученное в результате ее снятия количество информации (I) и нужно определить какое количество равновероятных альтернатив соответствует возникновению этой неопределенности, используют обратную формулу Хартли, которая выводится в соответствии с определением логарифма и выглядит еще проще...
1596. СТРУКТУРЫ И МОДЕЛИ ДАННЫХ 43.58 KB
  Временные характеристики фиксируют время исследования объекта и важны для оценки изменений свойств объекта с течением времени. Основное требование к таким данным – актуальность, что означает возможность их использования для обработки, неактуальные данные – это устаревшие данные.
20323. Разработка структуры базы данных информационной системы 971.23 KB
  Требуется разработать приложение и базу данных для компьютерной фирмы занимающейся продажей вычислительной техники комплектующих для неё и периферии. Формы первичных учетных документов определяются и устанавливаются организацией в составе применяемой ею системы учетной документации для регистрации хозяйственных операций. Первые быстродействующие компьютеры использовались предпринимателями в основном для автоматизации процессов которые раньше выполнялись вручную большим числом сотрудников невысокой квалификации; типичный пример - обработка...
18464. Разработка структуры базы данных информационной системы 971.23 KB
  Требуется разработать приложение и базу данных для компьютерной фирмы занимающейся продажей вычислительной техники комплектующих для неё и периферии. Формы первичных учетных документов определяются и устанавливаются организацией в составе применяемой ею системы учетной документации для регистрации хозяйственных операций. Первые быстродействующие компьютеры использовались предпринимателями в основном для автоматизации процессов которые раньше выполнялись вручную большим числом сотрудников невысокой квалификации; типичный пример - обработка...
5915. ТИПОВЫЕ ДИНАМИЧЕСКИЕ ЗВЕНЬЯ САУ 443.42 KB
  Типовыми называются элементарные звенья, описываемые дифференциальными уравнениями не выше второго порядка, которым соответствует широкий класс реальных технических устройств.
8881. Динамические процессы в экосистемах 127.3 KB
  Биоценоз экосистемы изменяется под воздействием факторов экотопа причем эти воздействия обладают различной интенсивностью и скоростью например биотические и геологические круговороты. Вместе с тем мы прекрасно знаем что подвижность экосистемы также относительна: экосистемы таежных лесов или целинных степей существуют длительное время сотни лет и на первый взгляд стабильны устойчивы неподвижны. Таким образом мы сталкиваемся с тем фактом что экосистемы с одной стороны действительно стабильны а с другой подвижны динамичны во...
10075. Динамические процессы в письменной речи возникающие под влиянием устной 98.55 KB
  Вопрос об изменении языка ни у кого не вызывает сомнений, а вопрос развития и совершенствования остается в языкознании дискуссионным. Различный подход к данной проблеме связан с двоякой природой языка как природного и общественного явления. Как природное явление язык выступает в виде определенной функции человеческого организма; и как таковой вплетен в человеческую деятельность, объективно существуя в виде речи и речевой деятельности.
7176. ОРГАНИЗАЦИЯ БАЗ ДАННЫХ И СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ 116.07 KB
  Например в качестве информационной системы можно рассматривать расписание движения поездов или книгу регистрации данных о заказах. Атрибут записанный на каком-либо носителе информации называют элементом данных полем данных или просто полем. При обработке данных часто встречаются однотипные объекты с одинаковыми свойствами.
8335. Аналоговая и дискретная информация. Носители данных. Операции с данными. Кодирование данных. Системы счисления. Энтропия и количество информации 227.54 KB
  Системы счисления. Системы счисления Кодирование данных используется издавна: код Морзе Брайля морской сигнальный алфавит и т. В истории человечества для кодировании чисел наиболее известны две системы счисления: непозиционная и позиционная. Как та так и другая системы счисления характеризуются основанием – количеством различных цифр используемых для записи чисел например от 0 до 9 т.
3944. Составление программ циклической структуры 18.93 KB
  Вычислить на ЭВМ значение интеграла на отрезке. Число разбиений отрезка интегрирования равен 100, метод интегрирования – метод трапеций. Изучил основные операторы для организации циклов. Разработал алгоритм решения задачи. Составил программу решения задачи.
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.