2.1.4. Организация двусвязных списков

Связанное хранение линейного списка называется списком с двумя связями или двусвязным списком, если каждый элемент хранения имеет два компонента указателя(ссылки на предыдущий и последующий элементы линейного списка).

В программе двусвязный список можно реализовать с помощью описаний:

typedef struct ndd

{ float val; /* значение элемента */

struct ndd * n; /* указатель на следующий элемент */

struct ndd * m; /* указатель на предыдующий элемент */

} NDD;

NDD * dl, * p, * r;

Графическая интерпретация метода связанного хранения списка F=как списка с двумя связями приведена на рис.20.

Рис.20. Схема хранения двусвязного списка.

Вставка нового узла со значением new за элементом, определяемым указателем p,осуществляется при помощи операторов:

r=malloc(NDD);

r->val=new;

r->n=p->n;

(p->n)->m=r;

p->=r;

Удаление элемента, следующего за узлом, на который указывает p

p->n=r;

p->n=(p->n)->n;

( (p->n)->n )->m=p;

free(r);

Связанное хранение линейного списка называется циклическим списком, если его последний указывает на первый элемент, а указатель dl - на последний элемент списка.

Схема циклического хранение списка F= приведена на рис.21.

Рис.21. Схема циклического хранения списка.

При решении конкретных задач могут возникать разные виды связанного хранения.

Пусть на входе задана последовательность целых чисел B1,B2,...,Bn из интервала от 1 до 9999, и пусть Fi (1 по возрастанию. Составить процедуру для формирования Fn в связанном хранении и возвращения указателя на его начало.

При решении задачи в каждый момент времени имеем упорядоченный список Fi и при вводе элемента Bi+1 вставляем его в нужное место списка Fi, получая упорядоченный список Fi+1. Здесь возможны три варианта: в списке нет элементов;число вставляется в начало списка; число вставляется в конец списка. Чтобы унифицировать все возможные варианты, начальный список организуем как связанный список из двух элементов .

Рассмотрим программу решения поставленной задачи, в которой указатели dl, r, p, v имеют следующее значение: dl указывает начало списка; p, v - два соседних узла; r фиксирует узел, содержащий очередное введенное значение in.

2.1.6. Сжатое и индексное хранение линейных списков

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

Сжатое хранение. Пусть в списке B= несколько элементов имеют одинаковое значение V, а список B'= получается из B заменой каждого элемента Ki на пару Ki'=(i,Ki). Пусть далее B"= -подсписок B', получающийся вычеркиванием всех пар Ki=(i,V). Сжатым хранением В является метод хранения В", в котором элементы со значением V умалчиваются.Различают последовательное сжатое хранение и связанное сжатое хранение.Например, для списка B=, содержащего несколько узлов со значением Х, последовательное сжатое и связанное сжатое хранения, с умалчиванием элементов со значением Х, представлены на рис.22,23.

1,C	3,Y	6,S	7,H	9,T
Рис.22. Последовательное сжатое хранение списка.

Рис.23. Связное сжатое хранение списка.

Достоинство сжатого хранения списка при большом числе элементов со значениемV заключается в возможности уменьшения объема памяти для его хранения.

В практике часто используется последовательно-связанное индексное хранение.

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

последовательно, обеспечивая прямой доступ к любому элементу списка индексов.

Подсписки B1,B2,...,Bm хранятся связанно, что упрощает вставку и удаление

узлов(элементов). В частности, подобный метод хранения используется в ЕС ЭВМ

для организации, так называемых, индексно-последовательных наборов данных, в

которых доступ к отдельным записям возможен как последовательно, так и при

помощи ключа.

Последовательно-связанное индексное хранение для приведенного примера

изображено на рис.24, где X=.

Рис.24. Последовательно-связанное индексное хранение списка.

18	Способы описания структуры. Способы обращения к элементу структуры. Описание массива структур.

Структура – тип данных, задаваемый пользователем. В общем случае при работе со структурами следует выделить четыре момента:

- объявление и определение типа структуры,

- объявление структурной переменной,

- инициализация структурной переменной,

- использование структурной переменной.

Определение типа структуры представляется в виде

struct ID

{

<тип> <имя 1-го элемента>;

<тип> <имя 2-го элемента>;

…………

<тип> <имя последнего элемента>;

};

Определение типа структуры начинается с ключевого слова struct и содержит список объявлений, заключенных в фигурные скобки. За словом struct следует имя типа, называемое тегом структуры (tag – ярлык, этикетка). Элементы списка объявлений называются членами структуры или полями. Каждый элемент списка имеет уникальное для данного структурного типа имя. Однако следует заметить, что одни и те же имена полей могут быть использованы в различных структурных типах.

Определение типа структуры представляет собой шаблон (template), предназначенный для создания структурных переменных.

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

struct ID var1;

при этом в программе создается переменная с именем var1 типа ID. Все переменные, использующие один шаблон (тип) структуры, имеют одинаковый набор полей, однако различные наборы значений, присвоенные этим полям. При объявлении переменной происходит выделение памяти для размещения переменной. Шаблон структуры позволяет определить размер выделяемой памяти.

В общем случае, под структурную переменную выделяется область памяти не менее суммы длин всех полей структуры, например,

struct list

{

char name[20];

char first_name[40];

int;

}L;

В данном примере объявляется тип структура с именем list, состоящая из трех полей, и переменная с именем L типа struct list,при этом для переменной L выделяется 64 байта памяти.

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

Создание структурной переменной возможно двумя способами: с использованием шаблона (типа) или без него.

Создание структурной переменной pt на основе шаблона выполняется следующим образом:

struct point //Определение типа структуры

{

int x;int y;

};

……

struct point pt; //Создание структурной переменной

Структурная переменная может быть задана уникальным образом:

struct //Определение анонимного типа структуры

{

char name[20];

char f_name[40];

char s_name[20];

} copymy; //Создание структурной переменной

При размещении в памяти структурной переменной можно выполнить ее инициализацию. Неявная инициализация производится для глобальных переменных, переменных класса static. Структурную переменную можно инициализировать явно при объявлении, формируя список инициализации в виде константных выражений.

Формат: struct ID name_1={значение1, … значениеN};

Внутри фигурных скобок указываются значения полей структуры, например,

struct point pt={105,17};при этом первое значение записывается в первое поле, второе значение – во второе поле и т. д., а сами значения должны иметь тип, совместимый с типом поля.

Над структурами возможны следующие операции:

- присваивание значений одной структурной переменной другой структурной переменной, при этом обе переменные должны иметь один и тот же тип;

- получение адреса переменной с помощью операции &;

- осуществление доступа к членам структуры.

Присваивание значения одной переменной другой выполняется путем копирования значений соответствующих полей, например:

struct point pt={105,15},pt1;

pt1=pt;

В результате выполнения этого присваивания в pt1.x будет записано значение 105, а в pt1.y – число 15.

Работа со структурной переменной обычно сводится к работе с отдельными полями структуры. Доступ к полю структуры осуществляется с помощью операции. (точка) посредством конструкции вида:

имя_структуры.имя_поля_структуры;

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

Структуры нельзя сравнивать. Сравнивать можно только значения конкретных полей

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

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

int a[100];

char b[20];

float d[50];

В первой строке объявлен массив а из 100 элементов целого типа: а[0], а[1], ..., а[99] (индексация всегда начинается с нуля). Во второй строке элементы массива b имеют тип char, а в третьей - float.

Двумерный массив представляется как одномерный, элементами которого так же являются массивы. 

19. Логические операции

Операнды логических операций И ( && ), ИЛИ ( || ) НЕ ( ! ) могут иметь логический или числовой тип

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

ния типов не производятся, каждый операнд оценивается с точки зрения его эквивалентности нулю (опе-

ранд, равный нулю, рассматривается как false, не равный нулю – как true).

Результатом логической операции является true или false. Результат операции логическое И имеет

значение true только если оба операнда имеют значение true. Результат операции логическое ИЛИ имеет

значение true, если хотя бы один из операндов имеет значение true. Результат унарной операции логиче-

ского отрицания НЕ имеет значение true, если операнд имеет значение false.

Логические операции выполняются слева направо. Если значения первого операнда достаточно, что-

бы определить результат операции, второй операнд не вычисляется.

Условная операция

Эта операция тернарная, то есть имеет три операнда. Ее формат:

операнд1 ? операнд2 : операнд3

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

точки зрения его эквивалентности нулю (операнд, равный нулю, рассматривается как false, не равный ну-

лю – как true). Если результат вычисления операнда1 равен true, то результатом условной операции бу-

дет значение второго операнда, иначе – третьего операнда. Вычисляется всегда либо второй операнд,

либо третий. Их тип может различаться. Условная операция является сокращенной формой условного

оператора if.

#include <iostream.h>

void main ( )

{

int a = 11 , b = 4 , max ;

max = b > a ? b : a ;

cout << ”max = ” << max <<’\n’ ; // выводит на экран: max = 11

}

20 Одномерные массивы. Объявление массивов. Инициализация. Использование указателей при работе с одномерными массивами.

Массив - это последовательность элементов одного типа, расположенных в памяти последовательно.

Массивы: Одномерные, Многомерные.

Для объявления массива в с++ необходимо указать тип элементов имя переменной и количество элементов в квадратных скобках:

int arr[10];

Таким образом мы получим статический массив целых чисел из 10 элементов.

Общая форма объявления одномерного массива имеет следующий вид:

<класс> тип имя [размер]

где класс – необязательный элемент, определяющий класс памяти (extern, static, register);

тип – базовый тип элемента массива;

имя – идентификатор массива;

размер – количество элементов в массиве.

Для обращения к элементам массива используют индексы - целые числа указывающие на порядок элемента в массиве. Индексация массива начинается с 0.

arr[0] = 1;

arr[9] = 10;

Сейчас я записала на первого элемента - 1, а на место последнего - 10.

Для того чтобы заполнить таким образом весь массив воспользуемся циклом:

for (int i = 0; i < 10; i++) {

arr[i] = i;}

Так же значения массива можно определять при создании:

int arr[10] = {1,2,3,4,5,6,7,8,9,10};

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

В языке C массивы при объявлении можно инициализировать. Общая форма инициализации массива аналогична инициализации переменной:

<класс> тип имя [размер] = {список значений};

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

static float x[5]={7.5,0,–3.2,0,4};

В этом случае будет создан массив на 5 элементов. Если в списке инициализации задать количество элементов меньше, чем задано в объявлении массива, то остальные элементы принимаются равными нулю. Если в списке инициализации задать количество элементов больше, чем задано в объявлении массива, это вызовет ошибку при компиляции программы.

При инициализации допустима и следующая форма объявления:

<класс> тип имя [] = {a0,a1,…,aМ–1};

Компилятор сам создает массив из М элементов, присваивая им значения a0, a1,…, aМ–1.

Поскольку имя массива является указателем-константой, допустимо, например, такое присваивание:

int a[25];

int *ptr;

ptr=a;

В этом примере в переменную-указатель ptr записывается адрес начала массива a, т. е. адрес первого элемента массива.

Также справедливы следующие соотношения: например, имеется массив a[N], тогда истинными будут следующие сравнения:

a==&a[0];

*a==a[0].

Указатели можно увеличивать или уменьшать на целое число:

ptr=a+1;Теперь указатель ptr будет указывать на второй элемент массива a, что эквивалентно &a[1].

21. Двумерные массивы. Объявление. Инициализация массивов. Использование указателей при работе с двумерными массивами.

Двумерные массивы

Статические

В случае статического массива, все принципы работы, такие же как и у одномерного:

//---------------------------------------------------------------------------

 

#pragma hdrstop

#include <iostream>

using namespace std;

 

//---------------------------------------------------------------------------

 

#pragma argsused

int main(int argc, char* argv[])

{

int array_2d[3][3] = { {11, 12, 13}, {21, 22, 23}, {31,32,33}};

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

cout << array_2d[i][j] << " ";

}

cout << endl;

}

cin.get();

return 0;

}

//---------------------------------------------------------------------------

Данный код выведет на экран:

11 12 13

21 22 23

31 32 33

Динамические

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

int n = 3; // Колличество строк

int m = 3; // Колличество столбцов

int** array_2d;

 

// Создаем массив указателей

array_2d = new int*[n];

 

// А теперь создаем массивы значений, для каждой строки

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

array_2d[i] = new int[m];

}

Удаляется такой массив в обратном порядке:

// Удаляем массивы значений

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

delete[] array_2d[i];

}

// Удаляем массив указателей

delete[] array_2d;

В остальном никаких изменений:

//---------------------------------------------------------------------------

 

#pragma hdrstop

#include <iostream>

using namespace std;

 

//---------------------------------------------------------------------------

 

#pragma argsused

int main(int argc, char* argv[])

{

int n = 3; // Колличество строк

int m = 3; // Колличество столбцов

int** array_2d;

 

// Создаем массив указателей

array_2d = new int*[n];

 

// А теперь создаем массивы значений, для каждой строки

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

array_2d[i] = new int[m];

}

 

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

array_2d[i][j] = (i+1)*10+(j+1);

cout << array_2d[i][j] << " ";

}

cout << endl;

}

 

// Удаляем массивы значений

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

delete[] array_2d[i];

}

// Удаляем массив указателей

delete[] array_2d;

 

cin.get();

return 0;

}

//---------------------------------------------------------------------------

 

Вывод этого примера абсолютна аналогичен предыдущему.

Объявление

. В языках программирования объявление (англ. declaration) включает в себя указание идентификатора, типа, а также других аспектов элементов языка, например, переменных и функций. Объявление используется, чтобы уведомить компилятор о существовании элемента; это весьма важно для многих языков (например, таких как Си), требующих объявления переменных перед их использованием.

Объявление, зачастую, используется для того, чтобы получить доступ к функции или переменной, определённым в другом исходном файле или библиотеке.

Объявления переменных

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

Си, C++

Объявления указываются:

вне функции, класса, метода для глобальных переменных;

в начале блока инструкций { } для локальных переменных;

как выражение в последующих частях блока инструкций {} для локальных переменных (не для языка Си).

int global_var;

main()

{

int y;

...

{

int z=1;

getch();

int x=5; /*не работает для языка Си*/

...

}

...

}

Инициализация массивов.

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

Массив может быть инициолизирован сразу во время объявления:

Float floatArray [5] ={0,1,2,3,4};

В этом фрагменте элементу floatArray [0] присваивается значение 0,

floatArray [1] - 1, и т п.

—2 и Т.Д. Размер массива может определяться и количеством инициализирующих констант. Например, перечислив в скобках значения инициализаторов, можно ограничить раз-мер массива floatArray пятью элементами. C++ умеет очень хорошо считать (по крайней мере, его можно спокойно использовать для этого). Так, следующее объявле-ние идентично представленному выше:

Float floatArray [5] = {4,5,6,7,8};

Использование указателей при работе с двумерными массивами.

В языке С++ имеется механизм работы с переменными через их адрес. Для этого необходимо объявить указатель соответствующего типа. Указатель объявляется также как и переменная, но перед его именем ставится символ ‘*’: