ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.06.2021
Просмотров: 1684
Скачиваний: 3
36
При асинхронной обработке массивов индекс каждого массива меняется по
своей схеме.
Пример 2. В массиве целых чисел все отрицательные элементы перенести в
начало массива.
int b[10];//вспомогательный массив
int i,j=0;
for(i=0;i<n;i++)
if(a[i]<0){b[j]=a[i];j++;}//переписываем из а в b все отрицательные
элементы
for(i=0;i<n;i++)
if(a[i]>=0){b[j]=a[i];j++;}// переписываем из а в b все
положительные элементы
for(i=0;i<n;i++) cout<<b[I]<<” “;
Пример3.
Удалить из массива все четные числа
int b[10];
int i,j=0;
for(i=0;i<n;i++)
if(a[i]%2!=0){b[j]=a[i];j++;}
for(i=0;i<j;i++) cout<<b[i]<<" ";
cout<<"\n";
6.3.4. Задачи 4-ого класса
В поисковых задачах требуется найти элемент, удовлетворяющий заданному
условию. Для этого требуется организовать перебор массива и проверку условия. Но
при этом существует две возможности выхода из цикла:
-
нужный элемент найден ;
-
элемент не найден, но просмотр массива закончен.
Пример1. Найти первое вхождение элемента К в массив целых чисел.
int k;
cout<<"\nK=?";cin>>k;
int ok=0;//признак найден элемент или нет
int i,nom;
for(i=0;i<n;i++)
if(a[i]==k){ok=1;nom=i;break;}
if(ok==1)
cout<<"\nnom="<<nom;
else
cout<<"\nthere is no such element!";
6.4. Сортировка массивов
Сортировка – это процесс перегруппировки заданного множества объектов в
некотором установленном порядке.
Сортировки массивов подразделяются по быстродействию. Существуют
простые методы сортировок, которые требуют n*n сравнений, где n – количество
элементов массива и быстрые сортировки, которые требуют n*ln(n) сравнений.
Простые методы удобны для объяснения принципов сортировок, т. к. имеют простые и
37
короткие алгоритмы. Усложненные методы требуют меньшего числа операций, но сами
операции более сложные, поэтому для небольших массивов простые методы более
эффективны.
Простые методы подразделяются на три основные категории:
-
сортировка методом простого включения;
-
сортировка методом простого выделения;
-
сортировка методом простого обмена;
6.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<n;i++)
{
x=a[i];//запомнили элемент, который будем вставлять
j=i-1;
while(x<a[j]&&j>=0)//поиск подходящего места
{
a[j+1]=a[j];//сдвиг вправо
j--;
}
a[j+1]=x;//вставка элемента
}
6.4.2. Сортировка методом простого выбора
Выбирается минимальный элемент массива и меняется местами с первым
элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.
4
4
5
5
1
2
4
2
9
4
1
8
1
м
ин
int i,min,n_min,j;
38
for(i=0;i<n-1;i++)
{
min=a[i];n_min=i;//поиск минимального
for(j=i+1;j<n;j++)
if(a[j]<min){min=a[j];n_min=j;}
a[n_min]=a[i];//обмен
a[i]=min;
}
6.4.3. Сортировка методом простого обмена
Сравниваются и меняются местами пары элементов, начиная с последнего. В
результате самый маленький элемент массива оказывается самым левым элементом
массива. Процесс повторяется с оставшимися элементами массива.
4
4
5
5
1
2
4
2
9
4
1
8
for(int i=1;i<n;i++)
for(int j=n-1;j>=i;j--)
if(a[j]<a[j-1])
{int r=a[j];a[j]=a[j-1];a[j-1]=r;}
}
6.5. Поиск в отсортированном массиве
В отсортированном массиве используется дихотомический (бинарный) поиск.
При последовательном поиске требуется в среднем n/2 сравнений, где n – количество
элементов в массиве. При дихотомическом поиске требуется не более m сравнений,
если n- m-ая степень 2, если n не является степенью 2, то n<k=2
m
.
Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части
массива находится нужный элемент Х. Т .к. массив упорядочен, то если a[S]<X, то
искомый элемент находится в правой части массива, иначе - находится в левой части.
Выбранную часть массива снова надо разделить пополам и т. д., до тех пор, пока
границы отрезка L и R не станут равны.
1 3 8 1
0
1
1
1
5
1
9
2
1
2
3
3
7
0 1 2 3
4
5
6
7
8
9
L S R
S=(L+R)/2=4
int b;
cout<<"\nB=?";cin>>b;
int l=0,r=n-1,s;
do
{
s=(l+r)/2;//средний элемент
if(a[s]<b)l=s+1;//перенести леую границу
else r=s;//перенести правую границу
}while(l!=r);
if(a[l]==b)return l;
else return -1;
39
7. Указатели
7.1. Понятие указателя
Указатели являются специальными объектами в программах на Си++.
Указатели предназначены для хранения адресов памяти.
Пример: Когда компилятор обрабатывает оператор определения переменной,
например, int i=10;, то в памяти выделяется участок памяти в соответствии с типом
переменной (int=> 4байта) и записывает в этот участок указанное значение. Все
обращения к этой переменной компилятор заменит на адрес области памяти, в которой
хранится эта переменная.
а
Программист может определить собственные переменные для хранения адресов
областей памяти. Такие переменные называются указателями. Указатель не является
самостоятельным типом, он всегда связан с каким-то другим типом.
Указатели делятся на две категории: указатели на объекты и указатели на
функции. Рассмотрим указатели на объекты, которые хранят адрес области памяти,
содержащей данные определенного типа .
В простейшем случае объявление указателя имеет вид:
тип *имя;
Тип может быть любым, кроме ссылки.
Примеры:
int *i;
double *f, *ff;
char *c;
Размер указателя зависит от модели памяти. Можно определить указатель на
указатель: int**a;
Указатель может быть константой или переменной, а также указывать на
константу или переменную.
Примеры:
1. int i;
//целая переменная
const int ci=1; //целая константа
int *pi;
//указатель на целую переменную
const int *pci;//указатель на целую константу
Указатель можно сразу проинициализировать:
int *pi=&i;
//указатель на целую переменную
const int *pci=&ci;;//указатель на целую константу
2.
int*const cpi=&i;//указатель-константа на целую переменную
const int* const cpc=&ci;//указатель-константа на целую константу
Если модификатор const относится к указателю (т. е. находится между именем
указателя и * ), то он запрещает изменение указателя, а если он находится слева от типа
(т. е. слева от * ), то он запрещает изменение значения, на которое указывает указатель.
Для инициализации указателя существуют следующие способы:
1)
Присваивание адреса существующего объекта:
1) с помощью операции получения адреса
int a=5;
int *p=&a; или int p(&a);
2) с помощью проинициализированного указателя
int *r=p;
10
&a
a
*p
*r &a
5
40
3) адрес присваивается в явном виде
char*cp=(char*)0х В800 0000;
где 0х В800 0000 – шестнадцатеричная константа, (char*) – операция приведения
типа.
4) присваивание пустого значения:
int*N=NULL;
int *R=0;
7.2. Динамические переменные
Все переменные, объявленные в программе размещаются в одной непрерывной
области памяти, которую называют сегментом данных (64К). Такие переменные не
меняют своего размера в ходе выполнения программы и называются статическими.
Размера сегмента данных может быть недостаточно для размещения больших массивов
информации. Выходом из этой ситуации является использование динамической памяти.
Динамическая память – это память, выделяемая программе для ее работы за вычетом
сегмента данных, стека, в котором размещаются локальные переменные подпрограмм и
собственно тела программы.
Для работы с динамической памятью используют указатели. С их помощью
осуществляется доступ к участкам динамической памяти, которые называются
динамическими переменными. Динамические переменные создаются с помощью
специальных функций и операций. Они существуют либо до конца работы программ,
либо до тех пор, пока не будут уничтожены с помощью специальных функций или
операций.
Для создания динамических переменных используют операцию new,
определенную в СИ++:
указатель = new имя_типа[инициализатор];
где инициализатор – выражение в круглых скобках.
Операция new позволяет выделить и сделать доступным участок динамической
памяти, который соответствует заданному типу данных. Если задан инициализатор, то
в этот участок будет занесено значение, указанное в инициализаторе.
int*x=new int(5);
Для удаления динамических переменных используется операция delete,
определенная в СИ++:
delete указатель;
где указатель содержит адрес участка памяти, ранее выделенный с помощью
операции new.
delete x;
В языке Си определены библиотечные функции для работы с динамической
памятью, они находятся в библиотеке <stdlib.h>:
1)
void*malloc(unsigned s) – возвращает указатель на начало области динамической
памяти длиной s байт, при неудачном завершении возвращает NULL;
2)
void*calloc(unsigned n, unsigned m) – возвращает указатель на начало области
динамической для размещения n элементов длиной m байт каждый, при неудачном
завершении возвращает NULL;
3)
void*realloc(void *p,unsigned s) –изменяет размер блока ранее выделенной
динамической до размера s байт, р – адрес начала изменяемого блока, при неудачном
завершении возвращает NULL;
4)
void *free(void *p) – освобождает ранее выделенный участок динамической памяти, р-
адрес начала участка.
Пример: