Структура и организация данных ЭВМ

 

 

ОГЛАВЛЕНИЕ

 

 

 

1 Множества. Множества в Pascal …………..…………………………………………….…… 2

2.Граф.Машинное представление графов……………..……………………………………….5

   Матрица смежности. Нахождение кратчайшего пути в графе……………………………..6

3. Практическая часть ………………………………………………...………..……………….5

4.Список используемой литературы…...………………………………………………...…..…7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теоретическая часть

 

1. Множества. Множества в Pascal.

 

Множество — это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества.

 

Все элементы множества должны принадлежать одному из порядковых типов, содержащему не более 256 значений. Этот тип называется базовым типом множества. Базовый тип задается диапазоном или перечислением.

 

Область значений типа множество — набор всевозможных подмножеств, составленных из элементов базового типа. В выражениях на языке Паскаль значения элементов множества указываются в квадратных скобках: [1,2,3,4], ['а',‘b','с'], ['a'..'z'].

 

Если множество не имеет элементов, оно называется пустым и обозначается как []. Количество элементов множества называется его мощностью.

 

Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char, boolean и производные от них типы.

 

Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Максимальное число элементов множества 256, а данные типа множество могут занимать не более 32 байт.

 

Число байтов, выделяемых для данных типа множество, вычисляется по формуле:

ByteSize = (max div 8) - (min div 8) + 1,

 где max и min — верхняя и нижняя границы базового типа данного множества.

 

Номер байта для конкретного элемента Е вычисляется по формуле:

ByteNumber = (E div 8) - (min div 8),

 номер бита внутри этого байта по формуле:

BitNumber = E mod 8

 

Не имеет значения порядок записи элементов множества внутри конструктора. Например, [1, 2, 3] и [3, 2, 1] — это эквивалентные множества.

 

Каждый элемент в множестве учитывается только один раз. Поэтому множество [1, 2, 3, 4, 2, 3, 4, 5] эквивалентно [1..5].

 

Переменные множественного типа описываются так:

Var <идентификатор> : set of <базовый тип>;

 

Например:

           Var A, D : Set Of Byte;

               B : Set Of 'a'..'z';

               C : Set Of Boolean;

 

Нельзя вводить значения во множественную переменную процедурой ввода и выводить процедурой вывода.

 

Множественная переменная может получить конкретное значение только в результате выполнения оператора присваивания:

<множественная  переменная> := <множественное выражение>;

 

Например:

A : = [50, 100, 150, 200];

B : = ['m', 'n', 'k']; C : = [True, False];

D : = A;

 

Кроме того, выражения могут включать в себя операции над множествами.

 

Операции над множествами

 

Объединением двух множеств A и B называется множество, состоящее из элементов, входящих хотя бы в одно из множеств A или B. Знак операции объединения в Паскале «+».

 

 

 

 

 

 

 

 

Примеры:

1) [1, 2, 3, 4] + [3, 4, 5, 6] => [1, 2, 3, 4, 5, 6]

2) []+[‘a’..’z’]+[‘A’..’E’, ‘k’]  => [‘A’..’E’, ‘a’..’z’]

3) [5<4, true and false] + [true]  => [false, true]

 

Пересечением двух множеств A и B называется множество, состоящее из элементов, одновременно входящих во множество A и во множество B.

 

Знак операции пересечения в Паскале «*»

 

Примеры:

1) [1, 2, 3, 4] * [3, 4, 5, 6] => [3, 4]

2) [‘a’..’z’]*[‘A’..’E’, ‘k’]  => [‘k’]

3) [5<4, true and false] * [true]  => []

 

 

Разностью двух множеств A и B называется множество, состоящее из элементов множества A, не входящих во множество B.

 

 

Примеры:

1a) [1, 2, 3, 4] - [3, 4, 5, 6] => [1, 2]

1b)  [3, 4, 5, 6] - [1, 2, 3, 4]  => [5, 6]

2a) [‘a’..’z’]-[‘A’..’E’, ‘k’]  => [‘a’..’j’, ‘i’..’z’]

2b) [‘A’..’E’, ‘k’] - [‘a’..’z’]  => [‘A’..’E’]

3a) [5<4, true and false] - [true] => [false]

3b) [true] - [5<4, true and false] => [true].

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Граф. Машинное представление графов. Матрица смежности. Нахождение кратчайшего пути в графе.

Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.

Многосвязная структура обладает следующими свойствами:

• 1) на каждый элемент (узел, вершину) может быть произвольное количество ссылок;
• 2) каждый элемент может иметь связь с любым количеством других элементов;
• 3) каждая связка (ребро, дуга) может иметь направление и вес.

В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра графа могут иметь направленность, показываемую стрелками, тогда они называются ориентированными, ребра без стрелок - неориентированные.

Граф, все связи которого ориентированные, называется ориентированным графом или орграфом; граф со всеми неориентированными связями - неориентированным графом; граф со связями обоих типов - смешанным графом. Обозначение связей: неориентированных - (A,B), ориентированных - <A,B>. Примеры изображений графов даны на рис.1. Скобочное представление графов рис.5.1:

 а).((A,B),(B,A)) и б).(< A,B >,< B,A >).

 

Рис.5.1. Граф неориентированный (а) и ориентированный (б).

Для ориентированного графа число ребер, входящих в узел, называется полустепенью захода узла, выходящих из узела -полустепенью исхода. Количество входящих и выходящих ребер может быть любым, в том числе и нулевым. Граф без ребер является нуль-графом.

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

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

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

Логически структура-граф может быть представлена матрицей смежности или матрицей инцидентности.

Матрицей смежности для n узлов называется квадратная матрица adj порядка n. Элемент матрицы a(i,j) равен 1, если узел j смежен с узлом i (есть путь < i,j >), и 0 -в противном случае (рис.5.2).

 

Рис.5.2. Графа и его матрица смежности

Если граф неориентирован, то a(i,j)=a(j,i), т.е. матрица симметрична относительно главной диагонали.

Матрицы смежности используются при построении матриц путей, дающих представление о графе по длине пути: путь длиной в 1 - смежный участок - , путь длиной 2 - (< A,B >,< B,C >), ... в n смежных участков: где n - максимальная длина, равная числу узлов графа. На рис.5.3 даны путевые матирцы пути adj2, adj3, adj4 для графа рис.5.2.

Рис.5.3. Матрицы путей

Матрицы инцидентности используются только для орграфов. В каждой строке содержится упорядоченная последовательность имен узлов, с которыми данный узел связан ориетрированными (исходящими) ребрами. На рис.5.4 показана матрица инцидентности для графа рис. 5.2.

 

Рис.5.4. Матрицы инцидентности

Существуют два основных метода представления графов в памяти ЭВМ: матричный, т.е. массивами, и связными нелинейными списками. Выбор метода представления зависит от природы данных и операций, выполняемых над ними. Если задача требует большого числа включений и исключений узлов, то целесообразно представлять граф связными списками; в противном случае можно применить и матричное представление.

Матричное представление орграфов.

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

Например, для простого ориентированного графа, изображенного на рис.5.2 массив определяется как:

 array[4][4]={{0,1,0,0},{0,0,1,1},{0,0,0,1},{1,0,1,0}}

Матрицы смежности применяются, когда в графе много связей и матрица хорошо заполнена.

Общее правило для нахождения кратчайшего пути в графе состоит в том, чтобы каждой вершине xi приписать индекс li, равный длине кратчайшего пути из данной вершины в конечную. Приписывание индексов вершинам в случае графа с ребрами единичной длины производится в следующем порядке:

 

1) конечной  вершине х0 приписывается индекс 0;

 

2) всем вершинам, из которых идет ребро в  конечную вершину, приписывается  индекс 1;

 

3) всем вершинам, еще не имеющим индексов, из  которых идет ребро в вершину  с индексом li, приписывается индекс li+1. Этот процесс продолжается до тех пор, пока не будет помечена начальная вершина. По окончании разметки индекс у начальной вершины будет равен длине кратчайшего пути. Сам кратчайший путь найдем, если будем двигаться из начальной вершины в направлении убывания индексов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Практическая часть.

Написать программы на языке программирования С++ или Pascal.

1) Просматривая поочередно элементы диагоналей двумерного массива выбрать все положительные числа в одномерный массив и произвести его сортировку методом прямого включения в порядке убывания.

 

Код программы:

#include <iostream>

 

using namespace std;

 

//*

const int SIZE = 4; // размер матрицы

 

const int MATRIX[SIZE][SIZE] = {

{1, 2, 3, 4},

{6, 7, 8, 9},

{11, 12, 13, 14},

{16, 17, 18, 19},

};

//*/

 

 

void print_array(const char* message, int n, const int* array)

{

cout << message << ":";

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

cout << " " << array[i];

cout << endl;

}

 

void extract_diagonals(int n, const int matrix[SIZE][SIZE], int result[])

{

int result_size = 0; // число добавленных элементов

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

{

// главная диагональ

result[result_size++] = matrix[i][i];

}

 

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

{

// побочная диагональ

int j = n - 1 - i;

if (j != i) // условие не будет выполнено только для центр. элемента матрицы нечетного размера - он уже добавлен на главной дигонали

{

result[result_size++] = matrix[i][j];

}

 

}

}

 

void sort_inclusion(int n, int* array)

{

for (int i = 1; i < n; ++i)

{

int item = array[i];

int j = i - 1;

for (; j >= 0 && array[j] < item; --j)

{

array[j + 1] = array[j];

}

array[j + 1] = item;

}

}

 

 

int main()

{

int result_size = SIZE * 2 - (SIZE % 2); // для матрицы нечетного размера центральный элемент нужен только один раз

 

int *result = new int[result_size];

 

extract_diagonals(SIZE, MATRIX, result);

 

cout << "Massiv: " << endl;

cout << " 1, 2, 3, 4" << endl;

cout << " 6, 7, 8, 9" << endl;

cout << "11,12,13,14" << endl;

cout << "16,17,18,19" << endl << endl;

print_array("Diagonals", result_size, result);

 

sort_inclusion(result_size, result);

 

print_array("Sorted", result_size, result);

 

delete[] result;

system("pause");

return 0;

}

 

 

Результат работы: (Рис. 5)

Рис. 5

 

2) Разработать программу формирования стека, куда помещаются целые числа вводимые с клавиатуры. Процесс ввода прекращается после ввода отрицательного числа. Затем программа выводит сообщение о том, что введено отрицательное число и отображает содержимое стека на экран в порядке ввода.

 

Код программы:

#include <iostream>

using namespace std;

 

struct stack_item {

struct stack_item* next;

int data;

};

 

void stack_add(struct stack_item* &head, int data)

{

// добавляем элемент к стеку

struct stack_item *neu = new struct stack_item;

neu->next = head;

neu->data = data;

head = neu;

}

 

void stack_rollout(struct stack_item* const head)

{

// выводим элементы  стека задом наперед

if (head)

{

stack_rollout(head->next);

cout << head->data << " ";

}

}

 

int main()

{

struct stack_item* head = 0; // новый стек

 

cout << "Vvedite elementi steka. Otricatelniy element budet poslednim:" << endl;

do

{

// цикл ввода

int item;

cin >> item;

 

if (item < 0)

{

cout << "Otricatelniy\n\n";

break;

}

 

stack_add(head, item);

} while (1);

 

cout << "Vivod steka: ";

stack_rollout(head);

cout << endl;

system("pause");

return 0;

}

 

Результат работы: (рис. 6)

Рис. 6

 

 

 

 

 

3) Разработать алгоритм генерирования перестановок n-элементного множества за минимальное число транспозиций соседних элементов.