Инициализация массивов и классы памяти




Скачать 234.97 Kb.
НазваниеИнициализация массивов и классы памяти
Дата17.10.2012
Размер234.97 Kb.
ТипДокументы
Одномерный массив:

int a[50];

Переменная а - массив из 50 целых чисел.

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

char m[7][50];

Переменная m - массив из семи массивов, каждый из которых состоит из 50 символов.

Массив из семи указателей:

char *r[7];

Массив r состоит из указателей на символы.

Массивы


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

Тип данных x[n1][n2]...[nk]

Где x - идентификатор, определяемый в качестве имени массива, а ni - размерности массиваМассив x называется k-мерным массивом с элементами типа тип данных. Элементы i-го измерения имеют индексы от 0 до ni-1. Тип элемента массива может быть одним из основных типов, типом другого массива, типом указателя (pointer), типом структуры (struct) или типом объединения (union). Хотя элементы массива не могут быть функциями, они могут быть указателями на функции. Ниже приведены некоторые примеры определений массива:

int page[10]; /* одномерный массив из 10

элементов, перенумерованный с 0 до 9 */

char line[81];

float big[10][10], sales[10][5][8]; /*двумерный

массив и трехмерный массив*/

Ссылки на элемент k-мерного массива x делаются с помощью следующего обозначения:

x[i1][i2]...[ik]

где ij - целое выражение, при этом 0<=ij<=nj-1, а nj - максимальное значение j-го индекса массива x. Например:

page[5]

line[i+j-1]

big[i][j]

Указывая только первые p индексов, можно ссылаться на k-p-мерный подмассив k-мерного массива (p<=k), например,

sales[i] /* ссылка на двумерный подмассив массива

sales */

sales[i][j] /* ссылка на одномерный подмассив */

sales[i][j][k] /* ссылка на элемент массива*/

Инициализация массивов и классы памяти


Мы знаем, что скалярные переменные можно инициализировать в описании типа при помощи таких выражений, как например:

int fix = 1;

float flax = PI*2;

при этом предполагается, что PI - ранее введенное макроопределение. Можно ли инициализировать массивы?

Внешние, статические и автоматические массивы можно инициализировать!

Регистровые массивы инициализировать нельзя!

Если ничего не засылать в массив перед началом работы с ним, то внешние, статические и автоматические массивы инициализируются для числовых типов нулем и '\0' (null) для символьных типов, а регистровые массивы содержат какой-то мусор, оставшийся в этой части памяти. Если в статическом, внешнем или автоматическом массиве нам нужны первоначальные значения, отличные от нуля, в этом случае мы можем делать так:

/* дни месяца */

int days[12]={31,28,31,30,31,30,31,31,30,31,30,31};

main( )

{

int index;

extern int days[];/*необязательное описание */

for(index = 0; index<12; index++)

printf("Месяц %d имеет %d дней.\n", index+1,

days[index]);

}

Результат:

Месяц 1 имеет 31 дней.

Месяц 2 имеет 28 дней.

Месяц 3 имеет 31 дней.

Месяц 4 имеет 30 дней.

Месяц 5 имеет 31 дней.

Месяц 6 имеет 30 дней.

Месяц 7 имеет 31 дней.

Месяц 8 имеет 31 дней.

Месяц 9 имеет 30 дней.

Месяц 10 имеет 31 дней.

Месяц 11 имеет 30 дней.

Месяц 12 имеет 31 дней.

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

Предыдущую программу лучше переписать так:

int days[ ] = {31,28,31,30,31,30,31,31,30,31,30,31};

main( )

{

int index;

extern int days[ ];/* необязательное описание */

for(index=0;index
index++)

printf("Месяц %d имеет %d дней.\n",index +1,

days[index]);

}

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

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

Второе: оно касается добавления, сделанного в управляющем операторе for. Не полагаясь на свои вычислительные способности, мы возложили задачу подсчета размера массива на компилятор. Оператор sizeof определяет размер в байтах объекта или типа, следующего за ним. Предположим в нашей вычислительной системе размер каждого элемента типа int равен двум байтам, поэтому для получения количества элементов массива мы делим общее число байтов, занимаемое массивом, на 2. Однако в других системах элемент типа int может иметь иной размер. Поэтому в общем случае выполняется деление на значение переменной sizeof для элемента типа int.

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

Функции, массивы и указатели


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

/* массив-аргумент */

main( )

{

int ages[50]; /* массив из 50 элементов */

convert(ages);

_

}

convert(years);

int years[ ];/* каков размер массива? */

{

_

}

Очевидно, что массив ages состоит из 50 элементов. А что можно сказать о массиве years? Оказывается в программе нет такого массива. Описатель

int years[ ];

создает не массив, а указатель на него! Посмотрим, почему это так. Вот вызов нашей функции:

convert(ages);

ages - аргумент функции convert. Имя ages является указателем на первый элемент массива, состоящего из 50 элементов. Таким образом, оператор вызова функции передает ей указатель, т. е. адрес функции convert( ). Это значит, что аргумент функции является указателем, и мы можем написать функцию convert( ) следующим образом:

convert(years);

int *years;

{

_

}

Действительно, операторы

int years[ ];

int *years;

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

Как теперь связать его с массивом ages? При использовании указателя в качестве аргумента, функция взаимодействует с соответствующей переменной в вызывающей программе, т.е. операторы, использующие указатель years в функции convert( ), фактически работают с массивом ages, находящимся в теле функции main( ). Короче говоря, когда имя массива применяется в качестве аргумента, функции передается указатель. Затем функция использует этот указатель для выполнения изменений в исходном массиве, принадлежащем программе, вызывающей функцию.

Определение структурных переменных


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

struct имя_структуры {

Описание_элементов

};

Пример:

struct dinner {

char *place;

float cost;

struct dinner *next;

};

Структурная переменная описывается с помощью переменной структурного типа.

Примеры:

struct dinner week_days [7]; /* массив структур */

struct dinner best_one; /* одна структурная переменная */

struct dinner *p; /* указатель на структурную переменную */

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

struct{

список описаний

}

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

тип-данных описатели;

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

struct {

double x,y;

} a,b,c[9];

переменные a и b определяются как структуры, каждая из которых состоит из двух компонентов - x и y. Переменная c определяется как массив из девяти таких структур.

Из определения

struct {

int year;

short int month, day;

} date1,date2;

следует, что каждая из двух переменных date1, date2 состоит из трех компонентов: year, month, day.

С типом структуры может быть ассоциировано имя, которое задается описанием типа в форме

typedef struct {

список описаний

} имя-типа-структуры;

Спецификатор typedef (определяет класс памяти) позволяет нам создать свое собственное имя типа. Это напоминает директиву #define, но со следующими тремя изменениями:

  1. В отличие от #define спецификатор typedef дает символические имена, но ограничивается только типами данных.

  2. Спецификатор typedef выполняется компилятором, а не препроцессором.

  3. В своих пределах спецификатор typedef более гибок, чем #define.

В дальнейшем эти имена могут использоваться для определения структур. Ниже приведен пример описания типа структуры с именем employee:

typedef struct {

char name[30];

int id;

dept d;

family f;

} employee;

где слова dept, family указывают типы, а именно типы структур, предварительно определенные пользователем. Тип структуры employee может быть использован для определения переменных. Например, определение

employee chairperson, president, e1, e2;

описывает переменные chairperson, president, e1, e2 как структуры типа employee.

Существует и другой способ ассоциирования имени с типом структуры. Этот способ основан на применении меток структурыМетки структурыаналогичны меткам перечисляемого типа. Метка структуры описывается следующим образом:

struct метка{

список описаний

}

где метка является идентификатором. В приведенном ниже примере слово student описывается как метка структуры:

struct student {

char name[25];

int id,age;

char sex;

};

Метки структуры используются для определения структур записью вида

struct метка список-идентификаторов;

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

struct node {

int data;

struct node *next;

};

метка структуры node действительно является рекурсивной, так как она используется в своем собственном описании, т.е. в описании указателя next. Из-за наличия знака * переменная next описана как указатель на объекты типа node. Структуры не могут быть прямо рекурсивными. Структура типа Sне может содержать компонент, являющийся структурой типа S. Однако структура типа S может содержать компонент, указывающий на структурутипа S.

Доступ к компонентам структуры


Такой доступ осуществляется с помощью специального обозначения для выделенного компонента, имеющего следующий вид:

s.c

где s является именем структуры или значением структуры с компонентом c. s может быть выражением, дающим в результате значение структуры. Например, s может быть вызовом функции со структурой в качестве ее значения. К компонентам определенной выше структуры date1 можно обратиться, указав их обозначения:

date1.year

date1.month

date1.day

Поля битов в структурах


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

Пример:

struct bfeg {

unsigned int bf_flg1 : 10;

unsigned int bf_flg2 : 6;

};

Данная структура описывает 10-битовое поле, которое для вычислений преобразуется в значение типа unsigned int, и 6-битовое поле, которое обрабатывается как значение типа unsigned int.

Объединения


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

Определение объединенного типа данных аналогично определению структурного типа данных:

union имя_объединения {

Описания_элементов

};

Пример:

union bigword {

long bg_long;

char *bg_char [4];

};

Данные типа union bigword занимают память, необходимую для размещения наибольшего из своих элементов, и выравниваются в памяти к границе, удовлетворяющей ограничениям по адресации как для типа long, так и для типа char *[4].

Описание переменной объединенного типа:

Пример:

union bigword x;

union bigword *p;

union bigword a[100];

Перечисления


Данные перечислимого типа относятся к некоторому ограниченному множеству данных.

Определение перечислимого типа данных:

enum имя_перечислимого_типа {

Список_значений

};

Каждое значение данного перечислимого типа задается идентификатором.

Пример:

enum color {

red, green, yellow

};

Описание переменной перечислимого типа:

enum color chair;

enum color suite [40];

Использование переменной перечислимого типа в выражении.

Пример:

chair = red;

suite[5] != yellow;

Переменные структуры


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

struct {

общие компоненты;

метка активного компонента;

union {

описание компонента 1

описание компонента 2

...

описание компонента n

} идентификатор;

}

Ниже приведен пример определения переменной структуры health_record:

struct {

/* общая информация */

char name[25];

int age;

char sex;

/* метка активного компонента */

marital_status ms;

/* переменная часть */

union {

/* холост */

/* нет компонентов */

/* женат */

struct {

char marriage_date[8];

char spouse_name[25];

int no_children;

}

/* разведен */

char date_divorced[8];

} marital_info;

} health_record;

где тип marital_status, т.е. тип метки активного компонента ms, описан как

typedef enum {SINGL,MARRIED, DIVORCED}

marital_status;

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

health_record.name

health_record.ms

health_record.marital_info.marriage_date

Указатели и структуры


Рассмотрим метку структуры student, описание которой было дано выше как

struct student {

char name[25];

int id, age;

char sex;

}

Указатель new_student определен как

struct student *new_student;

Предположим, что память выделена таким образом, чтобы new_student указывал на объект student. Тогда на компоненты этого объекта можно ссылаться следующим образом:

(*new_student).name

(*new_student).id

(*new_student).age

(*new_student).sex

Поскольку указатели часто используются для указания на структуры, в языке Си специально для ссылок на компоненты таких структур введен оператор выбора стрелка вправо ->. Например, ссылки на вышеприведенные компоненты структуры можно записать с использованием оператора стрелки вправо -> как:

new_student->name

new_student->id

new_student->age

new_student->sex

Массив структур


Процесс описания массива структур совершенно аналогичен описанию любого другого типа массива:

struct book libry[MAXBKS];

Этот оператор объявляет libry массивом, состоящим из MAXBKS-элементов. Каждый элемент массива представляет собой структуру типа book. Таким образом, libry[0] является book-структурой, libry[1] - второй book-структурой и т.д.

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

libry[0].value value - первый элемент массива

libry[4].title title - пятый элемент массива

Метод ветвей и границ

Впервые метод ветвей и границ был предложен Лендом и Дойгом [1] в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела [2], посвященной задаче комивояжера [3]. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.

В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия “разделяй и властвуй”). На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. Проверка осуществляется посредством вычисления оценки снизу для целевой функции на данном подмножестве. Если оценка снизу не меньше рекорда— наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы.

Если удается отбросить все элементы разбиения, то рекорд — оптимальное решение задачи. В противном случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д.

Вычисление нижней границы является важнейшим элементом данной схемы. Для простейшей задачи размещения один из способов ее построения состоит в следующем.

Запишем исходную задачу в терминах целочисленного линейного программирования [4].

Введем следующие переменные:




 

 

С использованием введенных обозначений простейшая задача размещения записывается следующим образом





yi xij i I,  j J,

xij, yi , yi  {0, 1},    iI,  jJ.

Двойственная задача линейного программирования имеет вид:




vj  gij + wij,  iI, jJ,

wij  0, iI,  jJ.

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

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

  

Если для оптимального решения двойственной задачи выражение в скобках положительно для некоторого iI , то “скорее всего” в исходной целочисленной задаче yi = 0, и размерность можно уменьшить. Понятно, что данный эвристический прием не всегда приводит к правильному решению. Поэтому в качестве порога лучше брать не 0, а некоторую величину d 0, выбор которой зависит от исходных данных. Эту величину называют порогом отбраковки. Очевидно, что при d  max ci, размерность задачи не сокращается.

Другой способ уменьшения трудоемкости алгоритма состоит в искусственном завышении нижней оценки. Предположим, что нас интересует не только оптимальное решение, но и приближенные решения с относительной погрешностью не более e . Тогда завышение нижней оценки в (1 + e ) раз приводит к желаемому результату.

Литература

  1. Land A.H., and Doig A.G. An autmatic method of solving discrete programming problems. Econometrica. v28 (1960), pp 497-520.

  1. Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the traveling salesman problem. Operations Research. v11 (1963), pp 972-989.

  1. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.

  1. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск. Наука, 1978.



Метод ветвей и границ


[править]

Материал из Википедии — свободной энциклопедии


Метод ветвей и границ — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является комбинаторным (алгоритм перебора) с отсевом подмножеств множества допустимых решений, не содержащих оптимальных решений. Метод был впервые предложен Ленд и Дойг в 1960 г. для решения задач целочисленного линейного программирования.

Содержание


 [убрать]

  • 1 Общее описание

  • 2 Применение

  • 3 Примечания

  • 4 См. также

[править]Общее описание


Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

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

В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.

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

[править]Применение


Метод используется для решения некоторых NP-трудных задач, такие как:

Похожие:

Инициализация массивов и классы памяти icon14 Типы параметров-массивов
Разрешены три типа массивов: array, char и table. Тип array используется для задания чисел в удобной табличной форме. Примеры таких...
Инициализация массивов и классы памяти icon1. Общие представления о памяти. Круг явлений памяти. Патологии памяти
Ассоциативная теория памяти. Виды ассоциации и законы их образования, критика ассоцианизма
Инициализация массивов и классы памяти iconЛекционный курс в 6-7 семестрах для специальности 510200 Лекция 2
Мультипроцессорная обработка. Расслоение памяти. Регистр перемещения. Прерывания и опрос состояний. Буферизация. Защита памяти. Периферийные...
Инициализация массивов и классы памяти iconЛабораторная работа. "Обработка одномерных массивов (векторов)"
Цель работы: Знакомство с структурированными типами данных, получение практических навыков в организации одномерных массивов данных....
Инициализация массивов и классы памяти iconБилеты: 1
Единицей измерения объема памяти является бит – наименьшая структурная единица памяти. Для определения емкости обычно используют...
Инициализация массивов и классы памяти iconПримерные программы учебных предметов в 7-9-х классах Русский язык
В школьном курсе русского языка можно выделить несколько этапов: начальный период обучения (1-4 классы), переходный период (5-6 классы),...
Инициализация массивов и классы памяти iconПамять, виды памяти, методы тренировки памяти
При этом память всегда связывалась с процессом обучения (т е накопления информации), а попытки объяснения памяти всегда совпадали...
Инициализация массивов и классы памяти iconПсковской области приказ от 03. 04. 2012 №354 г. Псков об утверждении итогов областного
«Юный знаток истории» (6, 7 и 8 классы), «Юный знаток русского языка» (6, 7 и 8 классы), «Юный знаток литературы» (6, 7 и 8 классы),...
Инициализация массивов и классы памяти iconХотя мы и совершили переход от простой памяти емкостью 1 бит к 8-разрядной памяти (см рис. 27, б), чтобы построить память большого объема, требуется другой
Каждая операция считывает или записывает целое 3-разрядное слово. Хотя общий объем памяти A2 бит не намного больше, чем у 8-разрядного...
Инициализация массивов и классы памяти iconКнига Памяти в новых социальных условиях «В начале было слово…» или Государственная задача
В январе 1989 года было принято решение о создании территориальных Книг Памяти Советского Союза. По Постановлению ЦК кпсс «о всесоюзной...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница