Среда программирования Visual C++ 0 Общий вид окна

Скачать 1.11 Mb.

Название	Среда программирования Visual C++ 0 Общий вид окна
страница	8/18
Дата публикации	15.05.2014
Размер	1.11 Mb.
Тип	Документы

literature-edu.ru > Информатика > Документы

1 ... 4 5 6 7 8 9 10 11 ... 18

5. Методические указания

Ввод данных в задачах №1и №2 осуществляется с клавиатуры.
Массивы при решении задач не используются.
При решении задачи №1 целесообразно использовать цикл с параметром, т. к. известно количество элементов последовательности.
При решении задачи №2 целесообразно использовать цикл с условием, т. к. известно, что признаком окончания последовательности является 0.

6. Содержание отчета

1. Постановка задач для конкретного варианта.

2. Алгоритм решения каждой задачи в виде блок-схемы.

3. Программы для решения задач на языке C++.

4. Результаты решения.

Лабораторная работа №4
Работа с одномерными массивами

1. Цель работы:

Получение практических навыков при работе с массивами.
Получение практических навыков при работе с указателями.

2. Краткие теоретические сведения

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

2.1. Определение массива в C/C++

Массивы определяются следующим образом:
int a[100];//массив из 100 элементов целого типа
Операция sizeof(a) даст результат 400, т. е. 100 элементов по 4 байта.

Элементы массива всегда нумеруются с 0.

45	352	63		124	значения элементов массива
0	1	2	…..	99	индексы элементов массива

Чтобы обратиться к элементу массива, надо указать имя массива и номер элемента в массиве (индекс):

a[0] – индекс задается как константа,

a[55] – индекс задается как константа,

a[i] – индекс задается как переменная,

a[2*i] – индекс задается как выражение.
Элементы массива можно задавать при его определении:
int a[10]={1,2,3,4,5,6,7,8,9,10};

int a[]={1,2,3,4,5};

2.2. Понятие указателя

Указатели являются специальными объектами в программах на C/C++. Указатели предназначены для хранения адресов памяти.

Когда компилятор обрабатывает оператор определения переменной, например, int i=10;, то в памяти выделяется участок памяти в соответствии с типом переменной (для int размер участка памяти составит 4 байта) и записывает в этот участок указанное значение. Все обращения к этой переменной компилятор заменит адресом области памяти, в которой хранится эта переменная.

Рис. 3. Значение переменной и ее адрес

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

В простейшем случае объявление указателя имеет вид:

тип* имя;

Знак *, обозначает указатель и относится к типу переменной, поэтому его рекомендуется ставить рядом с типом, а от имени переменной отделять пробелом, за исключением тех случаев, когда описываются несколько указателей. При описании нескольких указателей знак * ставится перед именем переменной-указателя, т. к. иначе будет не понятно, что эта переменная также является указателем.
int* i;

double *f, *ff;//два указателя

char* c;
Размер указателя зависит от модели памяти. Можно определить указатель на указатель: int** a;

Указатель может быть константой или переменной, а также указывать на константу или переменную.
int i; //целая переменная

const int ci=1; //целая константа

int* pi; //указатель на целую переменную

const int* pci; //указатель на целую константу
Указатель можно сразу проинициализировать:
//указатель на целую переменную

int* pi=&i;
С указателями можно выполнять следующие операции:

разыменование (*);
присваивание;
арифметические операции (сложение с константой, вычитание,
инкремент ++, декремент --);
сравнение;
приведение типов.

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

int* pa=new int; //указатель и выделение памяти под //динамическую переменную

*pa=10;//присвоили значение динамической
//переменной, на которую указывает указатель

a=*pa;//присвоили значение переменной а

Арифметические операции применимы только к указателям одного типа.

Инкремент увеличивает значение указателя на величину sizeof(тип).

char* pc;

int* pi;

double* pd;

. . . . .

pc++; //значение увеличится на 1

pi++; //значение увеличится на 4

pd++; //значение увеличится на 8

Декремент уменьшает значение указателя на величину sizeof(тип).
Разность двух указателей – это разность их значений, деленная на размер типа в байтах.

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

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

2.3. Одномерные массивы и указатели

При определении массива ему выделяется память. После этого имя массива воспринимается как константный указатель того типа, к которому относятся элементы массива. Исключением является использование операции sizeof(имя_массива) и операции &имя_массива.
int a[100];
/*определение количества занимаемой массивом памяти, в нашем случае это 4*100=400 байт*/

int k=sizeof(a);
/*вычисление количества элементов массива*/

int n=sizeof(a)/sizeof(a[0]);
Результатом операции & является адрес нулевого элемента массива:
имя_массива==&имя_массива=&имя_массива[0]
Имя массива является указателем-константой, значением которой служит адрес первого элемента массива, следовательно, к нему применимы все правила адресной арифметики, связанной с указателями. Запись имя_массива[индекс] это выражение с двумя операндами: имя массива и индекс. Имя_массива – это указатель-константа, а индекс определяет смещение от начала массива. Используя указатели, обращение по индексу можно записать следующим образом: *(имя_массива+индекс).
for(int i=0;i

cout<<*(a+i)<<" ";

/*к имени (адресу) массива добавляется константа i и полученное значение разыменовывается*/
Так как имя массива является константным указателем, то его невозможно изменить, следовательно, запись *(а++) будет ошибочной, а *(а+1) – нет.

Указатели можно использовать и при определении массивов:
int a[100]={1,2,3,4,5,6,7,8,9,10};
//поставили указатель на уже определенный массив

int* na=a;
/*выделили в динамической памяти место под массив из 100 элементов*/

int b = new int[100];

2.4. Перебор элементов массива

Элементы массива можно обрабатывать по одному элементу, двигаясь от начала массива к его концу (или в обратном направлении):
for(int i=0;i<�обработка a[i]>
Элементы массива можно обрабатывать по два элемента, двигаясь с обеих сторон массива к его середине:
int i=0,j=n-1;
while (i
<�обработка a[I] и a[j]>;
i++;j--;}
Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 1(т. е. обрабатываются пары элементов a[0]и a[1], a[1]и a[2] и т. д.)
for(i=0;i
<�обработка a[i] и a[i+1]>
Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 2(т. е. обрабатываются пары элементов a[0]и a[1], a[2]и a[3] и т. д.)
i=1;
while(i
<�обработка a[i] и a[i+1]>
i=i+2;}

2.5. Классы задач по обработке массивов

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

R=a[I];a[I]=a[J]; a[J]=R;//обмен a[I]и a[J]элементов массива.

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

2.4. Сортировка массивов

Сортировка – это процесс перегруппировки заданного множества объектов в некотором установленном порядке.

2.4.1. Сортировка с помощью включения

Элементы массива делятся на уже готовую последовательность и исходную. При каждом шаге, начиная с I=2, из исходной последовательности извлекается i-ый элемент и вставляется на нужное место готовой последовательности, затем i увеличивается на 1 и т. д.

44	55	12	42	94	18
готовая	исходная

В процессе поиска нужного места осуществляются пересылки элементов больше выбранного на одну позицию вправо, т. е. выбранный элемент сравнивают с очередным элементом отсортированной части, начиная с j:=i-1. Если выбранный элемент больше a[i], то его включают в отсортированную часть, в противном случае a[j] сдвигают на одну позицию, а выбранный элемент сравнивают со следующим элементом отсортированной последовательности. Процесс поиска подходящего места заканчивается при двух различных условиях:

если найден элемент a[j]>a[i];
достигнут левый конец готовой последовательности.

int i,j,x;

for(i=1;i

{

x=a[i];//запомнили элемент, который будем вставлять

j=i-1;

while(x=0)//поиск подходящего места

{

a[j+1]=a[j];//сдвиг вправо

j--;

}

a[j+1]=x;//вставка элемента

}

2.4.2. Сортировка методом простого выбора

Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.

44	55	12	42	94	18
1

int i,min,n_min,j;

for(i=0;i

{

min=a[i];n_min=i;//поиск минимального

for(j=i+1;j

if(a[j]

{

min=a[j];

n_min=j;

}

a[n_min]=a[i];//обмен

a[i]=min;

}

2.4.3. Сортировка методом простого обмена

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

44	55	12	42	94	18

for(int i=1;i

for(int j=n-1;j>=i;j--)

if(a[j]

{

int r=a[j];

a[j]=a[j-1];

a[j-1]=r;}

}

2.5. Поиск в отсортированном массиве

В отсортированном массиве используется дихотомический (бинарный) поиск. При последовательном поиске требуется в среднем n/2 сравнений, где n – количество элементов в массиве. При дихотомическом поиске требуется не более m сравнений, если n- m-ая степень 2, если n не является степенью 2, то n^m.

Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части массива находится нужный элемент Х. Так как массив упорядочен, то, если a[S]

1	3	8	10	11	15	19	21	23	37
0	1	2	3	4	5	6	7	8	9

L S R
int b;

cout<<"\nB=?";cin>>b;

int l=0,r=n-1,s;

do

{

s=(l+r)/2;//средний элемент

if(a[s]

else r=s;//перенести правую границу

}while(l!=r);

if(a[l]==b)return l;

else return -1;

…