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

Лекция 5.

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

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

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

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

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

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

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

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

У каждого из этих типов своя дисциплина работы с элементами, она определяет свой набор допустимых операцийнад элементами. 1) Последовательность –характерен последовательный доступ к… Операции:пусть S – последовательность элементов типа T.

Реализация очереди на основе массива.

beg Очередь циклическая. Примером такой очереди в нашем ПК является буфер… 1-ый файл – заголовочный –описывает тип структуры-очереди, объявляет прототипы функций - операций, это интерфейсный…

Пример программы из 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);

  //queue3fR.cpp - файл реализации #include "queue3f.h"

Tip topqu (queue q)

//проверка очереди на пустоту bool emptyqu (queue q){return q.size==0;} //проверка очереди на заполненность

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();

for (int i=0; i<l; i++) clrqu(w[i]); int x=1, k=1; //2)записать x в файл

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

1 2 4 7 8 13 14

Замечание. Об использовании АТД.

Вместо topqu(w[0]) использовать w[0].x [w[0].beg]

Лекция 6.

в начале текущий в конце

Связанный список.

Можно описать массив указателей и для каждого создать динамическую переменную:     . . . . . .   … Xn-1 X2 X1   …

Организация связанного списка.

1.Определить тип элемента связанного списка.

Обозначим tip – тип информационной части элемента списка. Например,

Typedef int tip;

Структура элемента связанного списка:

Struct tel

tel *next; //указатель на следующий элемент }; 2. Описать указатель на связанный список (иногда удобно описать два указателя: на начало и на конец), рабочие…

Q= new tel;

(*q). next=beg; beg = q; 6. Включить элемент x : tip в связанный список

Delete q;

7. Передвинуть указатель p на следующий элемент связанного списка:

p = p-> next;

8.Обработать все элементы связанного списка по очереди с помощью функции void W(tip t).

P=beg;

while (p) // while (p!=null)

{W (p->inf);

p=p->next; }

10.Освободить память, занятую под связанный список.

While (beg)

{ q= beg;

beg= beg ->next;

Delete q;

11.Пример функции, которая вставляет в связанный список beg элемент x : tip на свое место, и создаёт упорядоченный список за несколько обращений к… void ВСТАВКА (tel * & beg, tip x) {tel *p, *q, *t;